The Interval-Graph Collapse

The theorem is elementary and load-bearing. It says that one-dimensional threshold graphs have no hidden global width invariant. Any width question for spectra on a line factors through local occupancy.

Suppose you have a finite set of points on the real line. Choose a distance threshold delta. Now draw a graph: each point becomes a vertex, and two vertices are adjacent when the corresponding points are at most delta apart.

At first glance, this looks like a graph decomposition problem. How large are the separators? How large is the treewidth? Does a repulsive spectrum have a global graph backbone?

The collapse theorem says the answer is much simpler. Assign each point x the interval [x, x + delta]. Two such intervals intersect exactly when the original points are within delta. So the threshold graph is a unit interval graph. Its largest clique is the largest number of points in any width-delta window, and its sweep decomposition has bags of exactly that size.

The Formal Spine

• Input: a finite point set X on the real line and a threshold delta > 0.
• Graph: connect two points when their distance is at most delta.
• Occupancy: let M(X, delta) be the largest number of points in any window of width delta.
• Conclusion: tw(G_delta(X)) = pw(G_delta(X)) = M(X, delta) - 1.

Why It Matters

This is a no-go theorem for overlarge one-dimensional separator claims. If the data live on a line and the graph only connects nearby points, then treewidth cannot see more than local crowding. It cannot carry a separate global rigidity invariant.

That does not make the graph useless. It makes the right question sharper. Separator growth becomes an extreme-value statistic: how quickly does the fullest local window fill as the point process grows?

Poisson Versus Repulsion

For unit-intensity Poisson points, the fullest window grows like log n / log log n. That is the independent null: random clumps appear, and the worst clump grows slowly.

For the sine-kernel determinantal process, a model of repulsive random matrix spectra, the paper proves an almost-sure upper bound of the form delta + C(delta) sqrt(log n). The proof uses the Bernoulli decomposition of determinantal counts and eigenvalue decay for the restricted sine-kernel operator.

The result separates universality classes. Independent points crowd more; repulsive points crowd less. Treewidth survives as a useful measurement only after it is understood as occupancy.

What Is Still Open

The sharp lower/extreme law for sine-kernel overcrowding remains conjectural. The paper proves the upper envelope and the Poisson comparison; the exact asymptotic constant and a full two-sided maximum law are left as open problems.