Triangle Families with Large Edge Up-Laplacian Spectral Gap

Mutasim Mim

arxiv: 2605.27307 · v2 · pith:DR4EQGFZnew · submitted 2026-05-26 · 🧮 math.CO

Triangle Families with Large Edge Up-Laplacian Spectral Gap

Mutasim Mim This is my paper

Pith reviewed 2026-06-29 16:38 UTC · model grok-4.3

classification 🧮 math.CO

keywords triangle familiesspectral gapincidence matrixclique thresholdminimum degreetriple systemsspectral extremizersup-Laplacian

0 comments

The pith

Triangle families achieve spectral gap above n-1 only when they contain exactly binom(n,3) triangles that form all triangles of an n-clique.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the spectral gap λ(T) of the edge-triangle incidence operator forces each edge in the support graph to belong to at least ceil(λ(T))-2 triangles from T, which in turn implies that the minimum degree is at least ceil(λ(T))-1. It proves that binom(n,3) is the exact size threshold at which λ(T) can exceed n-1, and that any family attaining this must be precisely the complete set of triangles on n vertices. The maximum gap function φ(t) at fixed size t therefore has isolated peaks at these complete triple systems, separated by intervals of length Θ(n^2) where the gap stays at most n-1, even though φ(t) overall grows like the cube root of t. This shows that complete triple systems are the unique minimal-size families achieving each gap level n.

Core claim

If |T| is less than binom(n,3), then λ(T) is at most n-1. When |T| equals binom(n,3) and λ(T) exceeds n-1, T must be exactly the set of all triangles on some n-vertex clique. In addition, every support edge lies in at least ceil(λ(T))-2 triangles of T, so the support graph has minimum degree at least ceil(λ(T))-1. The function φ(t) = max λ over families of size t is not monotone and satisfies φ(t) = Θ(t^{1/3}), while the cumulative maximum Λ(t) equals the largest n such that binom(n,3) ≤ t.

What carries the argument

The signed edge-triangle incidence matrix δ_{1,T} (defined via a total order on V) whose Gram matrix δ_{1,T}^T δ_{1,T} has smallest positive eigenvalue λ(T), the spectral gap.

If this is right

Every support edge lies in at least ceil(λ(T))-2 triangles from T.
The support graph has minimum degree at least ceil(λ(T))-1.
If |T| < binom(n,3) then λ(T) ≤ n-1.
Immediately after each binom(n,3) there is a forbidden interval of length Θ(n^2) where φ(t) ≤ n-1.
φ(t) = Θ(t^{1/3}) and Λ(t) equals the largest integer n with binom(n,3) ≤ t.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The isolation of peaks implies that adding a linear number of triangles after a complete system does not restore a gap above n-1.
Spectral gap functions here as a quantitative measure of edge-triangle overlap density.
The cubic-root scaling limits how large a gap any family of size t can achieve regardless of structure.

Load-bearing premise

The signed incidence matrix is defined using a total order on the vertices so that its Gram matrix spectral gap measures the overlap structure of the triangle family.

What would settle it

A set T with |T| less than binom(n,3) yet λ(T) greater than n-1, or a non-clique T of size exactly binom(n,3) with λ(T) greater than n-1.

read the original abstract

Let $\mathcal{T}$ be a finite nonempty set of $3$-element subsets of a totally ordered set $V$. We view $\mathcal{T}$ as the set of triangles in the support graph. Let $\delta_{1,\mathcal{T}}$ be the signed edge-triangle incidence matrix, and $\lambda(\mathcal{T})$ the spectral gap of $\delta_{1,\mathcal{T}}^T\delta_{1,\mathcal{T}}.$ Our main results show that large $\lambda(\mathcal{T})$ forces strong overlap and a large minimum degree in the support graph. In particular, every support edge lies in at least $\lceil \lambda(\mathcal{T})\rceil-2$ triangles in $\mathcal{T}$ and hence the graph has minimum degree at least $\lceil \lambda(\mathcal{T})\rceil-1$. We further prove that $\binom{n}{3}$ is the exact threshold for attaining level $n:$ if $|\mathcal{T}|< \binom{n}{3}$, then $\lambda(\mathcal{T}) \leq n-1,$ while if $|\mathcal{T}|=\binom{n}{3}$ and $\lambda(\mathcal{T}) > n-1,$ then $\mathcal{T}$ is exactly the full set of triangles on an $n$-vertex clique. Moreover, this clique peak is isolated in a strong interval-scale sense: letting $\phi(t)=\max_{|\mathcal{T}|=t} \lambda(\mathcal{T})$, immediately above $\binom{n}{3}$ there is a forbidden interval on which $\phi(t) \leq n-1$, and the first passage above the level $n-1$ is delayed by $\Theta(n^2)$ additional triangles. Since $\binom{n+1}{3} - \binom{n}{3}=\Theta(n^2),$ this implies that after the peak at $\binom{n}{3}$ one must traverse a nonzero proportion of the full gap until the next clique threshold before substantial recovery can occur. In particular, $\phi$ is not monotone. However, $\phi(t)=\Theta(t^{\frac{1}{3}}).$ Finally, if $\Lambda(t):=\max_{1 \leq s \leq t}\phi(s),$ then $\Lambda(t)=\max\{n \in \mathbb{N}:\binom{n}{3} \leq t\}.$ Thus complete triple systems are the unique minimal spectral extremizers, but their peaks are isolated on the natural scale between consecutive clique thresholds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives sharp combinatorial consequences of a large spectral gap for signed edge-triangle incidences, including an exact threshold at complete cliques and isolation of those peaks, but the order dependence in the signing needs explicit handling.

read the letter

The core new results are the lower bound tying lambda(T) to triangle multiplicity per edge (at least ceil(lambda)-2) and the exact characterization that binom(n,3) is the threshold for reaching level n, with the additional claim that any T of that size exceeding n-1 must be the full K_n. The isolation result—that phi(t) stays at most n-1 for a Theta(n^2) interval right after binom(n,3), making phi non-monotone yet still Theta(t^{1/3}) overall, and that Lambda(t) is exactly the largest n with binom(n,3) <= t—looks like the main advance over prior spectral work on hypergraphs.

These statements are internally consistent and translate the linear-algebra gap into concrete overlap and degree conditions without obvious circularity. The non-monotonicity and the precise gap size after each clique threshold are the parts that feel fresh.

The soft spot is the total order used to sign delta_1,T. The matrix entries (and thus the spectrum of delta^T delta) change with the ordering, so lambda(T) is not purely combinatorial. The paper needs to clarify whether the max in phi(t) is taken over orders as well as over T, or whether the threshold and isolation claims are proved to hold for every ordering (or for some canonical one). If the proofs only work for a fixed order chosen after T, the extremal statements could shift. That is the only place where the modeling choice might affect the claimed bounds.

The rest of the argument appears to rest on standard incidence-matrix identities and eigenvalue interlacing, which is fine for this area. This is worth sending to referees who work in spectral combinatorics; the claims are precise enough that a careful check of the proofs would be useful.

Referee Report

2 major / 1 minor

Summary. The paper defines λ(T) as the spectral gap of δ_{1,T}^T δ_{1,T} for a triangle family T on a totally ordered vertex set V, where δ_{1,T} is the signed edge-triangle incidence matrix. It proves that large λ(T) implies every support edge lies in at least ⌈λ(T)⌉−2 triangles (hence min-degree at least ⌈λ(T)⌉−1), that binom(n,3) is the exact threshold for λ(T) > n−1 (with equality only for the complete n-clique when |T|=binom(n,3)), that φ(t)=max_{|T|=t} λ(T) is non-monotone with a forbidden interval of length Θ(n^2) immediately above binom(n,3), and that φ(t)=Θ(t^{1/3}) while Λ(t)=max{ n : binom(n,3) ≤ t }.

Significance. If the central claims hold, the work gives precise combinatorial consequences of large up-Laplacian gaps for triangle families and isolates the clique peaks on the scale between consecutive binom(n,3) thresholds. The exact threshold statement and the isolation result are the strongest contributions; the asymptotic φ(t)=Θ(t^{1/3}) is a secondary but clean global bound.

major comments (2)

[Abstract / §1 (definition)] Abstract, first paragraph, and definition of λ(T): the signed matrix δ_{1,T} depends on the total order chosen on V, which determines the ±1 signs on shared edges. Different orders produce different off-diagonal sign patterns in M=δ^T δ and therefore different spectra. The statements relating λ(T) to minimum overlap and the exact threshold binom(n,3) are therefore order-dependent unless the paper shows either invariance or that the maximum in φ(t) is also taken over orders. This is load-bearing for all main theorems.
[Abstract (threshold and isolation statements)] The claim that |T|< binom(n,3) forces λ(T) ≤ n−1, and the isolation interval after binom(n,3), must be verified to hold uniformly or for the maximizing order; the current abstract statement does not specify the quantification over orders.

minor comments (1)

[Abstract] Notation: the symbol λ(T) is used both for a fixed T and implicitly for the maximized quantity; a clearer distinction between λ(T) and φ(t) would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to clarify the role of the vertex ordering. We respond point by point to the major comments.

read point-by-point responses

Referee: [Abstract / §1 (definition)] Abstract, first paragraph, and definition of λ(T): the signed matrix δ_{1,T} depends on the total order chosen on V, which determines the ±1 signs on shared edges. Different orders produce different off-diagonal sign patterns in M=δ^T δ and therefore different spectra. The statements relating λ(T) to minimum overlap and the exact threshold binom(n,3) are therefore order-dependent unless the paper shows either invariance or that the maximum in φ(t) is also taken over orders. This is load-bearing for all main theorems.

Authors: The definition of λ(T) is with respect to a fixed total order on V. The proofs of the overlap lower bound and the threshold statements at binom(n,3) rely on combinatorial counting that bounds the Rayleigh quotient independently of the concrete sign pattern induced by any particular ordering; the same argument therefore applies uniformly to every ordering. For the definition of φ(t) we agree that the quantification should be stated explicitly. We will revise the abstract and §1 to record that φ(t) is the maximum of λ(T) taken over all triangle families of cardinality t on all possible totally ordered vertex sets. revision: yes
Referee: [Abstract (threshold and isolation statements)] The claim that |T|< binom(n,3) forces λ(T) ≤ n−1, and the isolation interval after binom(n,3), must be verified to hold uniformly or for the maximizing order; the current abstract statement does not specify the quantification over orders.

Authors: Because the threshold and isolation arguments hold for an arbitrary fixed ordering, they hold in particular for any ordering that realizes the maximum value of λ(T). The revision described above will make the quantification over orders explicit in the abstract, thereby confirming that the stated claims apply to the maximizing case. revision: yes

Circularity Check

0 steps flagged

No circularity: definition and claims are independent

full rationale

The paper defines λ(T) explicitly as the smallest positive eigenvalue of δ_{1,T}^T δ_{1,T} where the signed incidence matrix is constructed from a fixed total order on V; all subsequent bounds (edge-triangle overlap, degree lower bounds, exact threshold at binom(n,3), isolation of the clique peak, and the growth ϕ(t)=Θ(t^{1/3})) are derived as theorems from this linear-algebraic object. No parameter is fitted to data and then relabeled a prediction, no self-citation supplies a load-bearing uniqueness theorem, and the combinatorial statements follow from the matrix definition without reducing back to it by construction. The derivation chain is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard facts from linear algebra (eigenvalues of symmetric matrices) and the combinatorial setup of signed incidence matrices; no free parameters or new entities are introduced.

axioms (2)

standard math Eigenvalues of real symmetric matrices are real and the spectral gap is the smallest positive one.
Invoked when defining lambda(T) as the spectral gap of delta_1,T^T delta_1,T.
domain assumption A total order on V allows a consistent signing of the incidence matrix entries.
Stated explicitly in the definition of delta_1,T in the abstract.

pith-pipeline@v0.9.1-grok · 5985 in / 1448 out tokens · 40242 ms · 2026-06-29T16:38:24.610775+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

[1]

The theta number of simpli- cial complexes

[BGP19] Christine Bachoc, Anna Gundert, and Alberto Passuello. “The theta number of simpli- cial complexes”. In:Israel J. Math.232.1 (2019), pp. 443–481.issn: 0021-2172,1565-8511. doi:10.1007/s11856-019-1880-8. [BH12] Andries E. Brouwer and Willem H. Haemers.Spectra of Graphs. Universitext. New York: Springer, 2012.doi:10.1007/978-1-4614-1939-6. [CGJM26] ...

work page doi:10.1007/s11856-019-1880-8 2019
[2]

Spectra of combinatorial Laplace operators on simpli- cial complexes

isbn: 052179160X. [HJ13] Danijela Horak and J¨ urgen Jost. “Spectra of combinatorial Laplace operators on simpli- cial complexes”. In:Advances in Mathematics244 (2013), pp. 303–336.issn: 0001-8708. doi:https://doi.org/10.1016/j.aim.2013.05.007. 19 [JZ24] J¨ urgen Jost and Dong Zhang. “Cheeger inequalities on simplicial complexes”. In:AN- NALI SCUOLA NORMA...

work page doi:10.1016/j.aim.2013.05.007 2013
[3]

Set systems with restricted cross-intersections and the minimum rank of inclusion matrices

issn: 0391-173X.doi:10.2422/2036-2145.202307_009.url:http://dx.doi.org/ 10.2422/2036-2145.202307_009. [KS05] Peter Keevash and Benny Sudakov. “Set systems with restricted cross-intersections and the minimum rank of inclusion matrices”. In:SIAM J. Discrete Math.18.4 (2005), pp. 713–727.issn: 0895-4801,1095-7146.doi:10.1137/S0895480103434634.url:https: //do...

work page doi:10.2422/2036-2145.202307_009.url:http://dx.doi.org/ 2036

[1] [1]

The theta number of simpli- cial complexes

[BGP19] Christine Bachoc, Anna Gundert, and Alberto Passuello. “The theta number of simpli- cial complexes”. In:Israel J. Math.232.1 (2019), pp. 443–481.issn: 0021-2172,1565-8511. doi:10.1007/s11856-019-1880-8. [BH12] Andries E. Brouwer and Willem H. Haemers.Spectra of Graphs. Universitext. New York: Springer, 2012.doi:10.1007/978-1-4614-1939-6. [CGJM26] ...

work page doi:10.1007/s11856-019-1880-8 2019

[2] [2]

Spectra of combinatorial Laplace operators on simpli- cial complexes

isbn: 052179160X. [HJ13] Danijela Horak and J¨ urgen Jost. “Spectra of combinatorial Laplace operators on simpli- cial complexes”. In:Advances in Mathematics244 (2013), pp. 303–336.issn: 0001-8708. doi:https://doi.org/10.1016/j.aim.2013.05.007. 19 [JZ24] J¨ urgen Jost and Dong Zhang. “Cheeger inequalities on simplicial complexes”. In:AN- NALI SCUOLA NORMA...

work page doi:10.1016/j.aim.2013.05.007 2013

[3] [3]

Set systems with restricted cross-intersections and the minimum rank of inclusion matrices

issn: 0391-173X.doi:10.2422/2036-2145.202307_009.url:http://dx.doi.org/ 10.2422/2036-2145.202307_009. [KS05] Peter Keevash and Benny Sudakov. “Set systems with restricted cross-intersections and the minimum rank of inclusion matrices”. In:SIAM J. Discrete Math.18.4 (2005), pp. 713–727.issn: 0895-4801,1095-7146.doi:10.1137/S0895480103434634.url:https: //do...

work page doi:10.2422/2036-2145.202307_009.url:http://dx.doi.org/ 2036