Triangle selection as an optimization problem
Problem-driven note. This is where “your question” is framed in a way that invites theorems.
The data
Fix a base graph $G=(V,E)$ with oriented edges. Let $\mathcal T(G)$ be the set of (undirected) triangles in $G$. Choose $T\subseteq \mathcal T(G)$ and orient each triangle (any consistent choice works for spectra).
The operator
The total 1-Laplacian on edge-cochains is $$L_1(T)=L_1^{\downarrow}+L_1^{\uparrow}(T)=\delta_0\delta_0^{\mathsf T}+\delta_1(T)^{\mathsf T}\delta_1(T).$$ We care about the smallest positive eigenvalue $\lambda_{\min}^+(L_1(T))$.
Optimization objectives
- Max-gap: maximize $\lambda_{\min}^+(L_1(T))$ over $T$.
- Sparse max-gap: maximize $\lambda_{\min}^+(L_1(T))$ subject to $|T|\le m$.
- Thresholding: find smallest $|T|$ such that $\lambda_{\min}^+(L_1(T))\ge \tau$.
Greedy structure from rank-one updates
Adding a triangle $\tau$ changes only the upper term: $$L_1^{\uparrow}(T\cup\{\tau\}) = L_1^{\uparrow}(T)+b_\tau b_\tau^{\mathsf T}.$$ This suggests greedy rules like “choose $\tau$ that maximizes improvement of a proxy Rayleigh quotient.”
Often $L_1^{\downarrow}$ is fixed and $L_1^{\uparrow}(T)$ is the tunable piece. Once $L_1^{\uparrow}(T)$ is “strong enough” on the relevant subspace, the total gap is governed by the fixed graph term, so further triangles have diminishing returns for $\lambda_{\min}^+(L_1(T))$.
What can be proved
- Interlacing-based bounds on how much one triangle can improve (or fail to improve) the bottom of the spectrum.
- Certificates for “no improvement” using orthogonality to all available $b_\tau$.
- Extremal characterizations for highly symmetric families (SRGs, designs).