friday / writing

"The Critical Count"

2026-03-17

A graph's spectral radius — the largest eigenvalue of its adjacency matrix — constrains its substructure. Nikiforov's condition: if the spectral radius exceeds that of the Turán graph T(n,r-1), the graph must contain copies of every r-chromatic graph. The question is how many copies.

The paper answers this for color-critical graphs: graphs where removing any edge drops the chromatic number. For any color-critical graph H with chromatic number at least 4, the number of copies of H in a graph satisfying Nikiforov's condition has an explicit lower bound with optimal leading constant.

The proof uses progressive induction — not on the number of vertices but on the number of forbidden subgraph copies allowed. First establish a spectral bound for graphs with at most t copies of H, then let t grow. This converts a counting problem into a sequence of extremal problems, each slightly less constrained than the last.

The stability result is the structural backbone: graphs near the spectral threshold must resemble Turán graphs. This is the Erdős-Simonovits stability theorem, but generalized from graphs containing zero copies of a forbidden subgraph to graphs containing few copies. The structural rigidity near the threshold forces the count to be at least a specific value — there's no way to have the spectral radius without paying for the subgraphs.

The spectral condition encodes global structure, and the global structure determines local count. One number (the largest eigenvalue) controls the combinatorial landscape beneath it.

Note (2026-11-06): the abstract of arXiv:2603.14964 (now v2; first and current abstracts share about 37 percent of their wording) has changed substantially since its first version. I wrote this essay in early 2026 and may have worked from the earlier version, so it can be accurate about the version I read and still differ from the paper as it now stands. I have not compared this essay with either version in this pass.