Where the Extremal Graph Switches: Spectral and Clique-Count Transitions for Graphs Without k Disjoint Paths

Extremal graph theory asks which graph is "most" of something while avoiding a forbidden pattern. "Most" can mean most edges, most copies of a small subgraph, or the largest spectral radius, which is the top eigenvalue of the adjacency matrix and roughly measures how fast walks multiply. Many of the strongest theorems here end with the phrase "for sufficiently large n," and they leave the finite range unresolved. That range is not a technicality. For some objectives it can be exponentially long, and the extremal graph inside it can look different. This proposal studies one forbidden family closely: graphs with no $k$ vertex-disjoint copies of $P_3$, the three-vertex path. It asks a question no single existing paper poses: for which $n$ does the extremal graph switch from a dense clique to a small hub joined to a matching, and does the switch point depend on whether we maximize edges, $s$-cliques, or spectral radius?

The opportunity comes from two recent results that study the same structure without connecting to each other. The maximum number of cliques in graphs that avoid vertex-disjoint copies of path of length two shows that the extremal graphs for clique counts are either a clique $K_{3k-1}$ plus leftovers, or the join $K_{k-1}+M_{n-k+1}$, meaning a $(k-1)$-clique connected to every vertex of a matching. It leaves the small-$n$ range open when $3\le s\le k+1$. Subdivision-free graphs with the maximum spectral radius proves that spectral maximizers contain a "generalized book" spine for large $n$, but gives no explicit threshold. Our central claim is that the threshold $n^\ast$ at which the hub structure takes over is a computable function of the objective. The spectral radius sits between edges and triangles on this scale. Clique counts for $s=k+1$ have an unavoidably exponential threshold. The spectral problem, unlike the clique problem, may contain genuine small-$n$ exceptions that lie strictly between the two textbook constructions.

Core Claim

The two classical candidates already pin down where a transition must sit, assuming no other graph intervenes. For $s$-clique counts with $s=k+1$, the join $K_{k-1}+M_{n-k+1}$ contains only about $(n-k+1)/2$ copies of $K_{k+1}$, one per matching edge, while $K_{3k-1}$ contains $\binom{3k-1}{k+1}$. The join can therefore win only once $n$ exceeds roughly $2\binom{3k-1}{k+1}$. This means any "sufficiently large $n$" in the Gao et al. theorem must be exponential in $k$ for $s=k+1$. For triangles the same comparison puts the crossover near $n\approx 9k$, and for edges near $4k$.

For spectral radius the comparison can be done exactly. The join has a two-class equitable partition: hub vertices and matching vertices, where every vertex in a class has the same number of neighbours in each class. Writing $m=n-k+1$ for the number of matched vertices, its spectral radius $\lambda$ is the largest root of

$$ (\lambda-k+2)(\lambda-1)=m(k-1), $$

where the left side comes from the hub vertices (each adjacent to $k-2$ hub neighbours) and the matched vertices (each adjacent to one partner). The disjoint union containing $K_{3k-1}$ has spectral radius exactly $3k-2$, because the spectral radius of a disjoint union is the maximum over its components. Setting $\lambda=3k-2$ gives $m=6k$, so the two-family crossover is at $n=7k-1$. This is linear in $k$ and lies between the edge and triangle crossovers. Seen this way, the spectral radius behaves like a clique count with an effective clique size between 2 and 3.

The finite-$n$ content of the proposal is whether these crossovers are the true thresholds. A natural one-parameter family interpolates between the two constructions: $K_{k-1-j}+(K_{3j+2}\cup M)$, a hub of size $k-1-j$ joined to a page containing a $(3j+2)$-clique and a matching. Every member is $kP_3$-free. A $P_3$ either uses a hub vertex, which allows at most $k-1-j$ of them, or lies inside the page clique, which allows at most $j$.

For clique counts, the count within this family is a sum of terms convex in $j$, so we expect the endpoints to win. That would be consistent with Gao et al.'s two-construction picture. For spectral radius, convexity is not available, and an interior $j$ may beat both endpoints near $n\approx 7k$. If that happens, we have identified a small-scale spectral extremal graph that no large-$n$ theorem predicts. If it does not, we can prove the explicit threshold $n_0=7k-1$ for this case of Sun et al.'s theorem.

This case does fall under Sun et al.'s theorem. A graph contains a subdivision of $kP_3$ exactly when it contains $kP_3$. Their spine size $\gamma=|H|-\alpha(H)-1$ evaluates to $3k-2k-1=k-1$, which matches the hub of the join. Their unresolved "saturated page" must here be $P_3$-free, so it is a near-perfect matching. That settles the page question for this family and leaves the threshold as the real open problem.

Research Program

The work has three parts, each feeding the next.

The first part maps the landscape computationally. For $k\le 3$ and $n$ up to about 11, we enumerate all graphs exhaustively, test $kP_3$-freeness by computing a maximum $P_3$-packing (trivial at this size), and record the exact maximizers for six objectives: edges, $K_3$ through $K_{k+1}$ counts, sum of squared degrees, and spectral radius. Beyond exhaustive range, we run two searches. One is a structured search over hub-plus-page graphs, where the page is any $P_3$-packing-bounded graph on few non-matching vertices. The other is an unstructured local search: simulated annealing over edge flips, rejecting moves that create $k$ disjoint $P_3$s, for $k$ up to 8 and $n$ up to about $12k$. The output is a transition map: for each objective and each $(k,n)$, which structure is extremal and whether anything outside the interpolating family ever wins.

The second part turns the map into proofs. For the spectral problem we use the Perron-vector edge-shifting argument of Sun et al. Moving an edge from low-weight to high-weight endpoints in the principal eigenvector strictly increases $\lambda$. We make every "large $n$" step explicit. The specific target is to show that, for every $n$, a spectral maximizer is a member of the interpolating family, so the remaining problem is a one-variable comparison of quotient-matrix eigenvalues. For clique counts in the range $3\le s\le k+1$, we redo Gao et al.'s double induction on $k$ and $s$ with explicit constants. We then ask whether the resulting $g(k,s)$ can be pushed down to the two-family crossover, which is the best possible threshold if no exotic graph intervenes.

The third part, a stretch goal with a stated stopping rule, attempts finite-$n$ certificates in the gap between exhaustive enumeration and proof. Symmetric sums of squares over k-subset hypercubes shows that symmetric sum-of-squares certificates have size independent of $n$ and can keep lower-order terms, as in their exact certificate for $R(3,3)=6$. The $kP_3$-free constraint is permutation-invariant, so their hook-partition reduction applies. However, the constraint has polynomial degree about $2k$ in the edge variables, and that paper reports certificate size growing rapidly with degree. We attempt $k=2,3$ only, and we stop if certificates for $n\le 15$ do not solve within a fixed solver budget.

Baselines

The naive reference point is the best-of-two-constructions predictor. For each $(n,k,s)$ and for spectral radius, it outputs the larger value of $K_{3k-1}\cup(\text{matching})$ and $K_{k-1}+M_{n-k+1}$. This is the lower bound from Gao et al.'s Theorem 1.1, and for spectral radius it is the quotient computation above. "Doing nothing" means believing this predictor everywhere. We beat it in one of two ways: by finding a $kP_3$-free graph with a strictly larger objective at some $n$, or by proving it exact on a range where it was not previously proven. Both outcomes count.

The strongest existing method for clique counts is Gao et al.'s exact theorem. It covers $k\in\{2,3\}$, all $s\ge k+2$, and $3\le s\le k+1$ for $n\ge g(k,s)$. The file reports no numerical value of $g(k,s)$ (no reported result found on Lacuna for an explicit $g(k,s)$), so the comparison is between our explicit threshold and the first explicit version of theirs that we extract. For spectral radius, the strongest existing results are Sun et al.'s book theorem and the explicit large-$n$ eigenvalue formulas of The spectral radius of minor-free graphs. That paper solves spectral maximization for minor-free graphs, a different forbidden family, using the same quotient-matrix technique we reuse. Neither paper states an explicit $n_0$ (no reported result found on Lacuna for an explicit threshold). We beat them by giving an exact $n_0$ that matches computation.

Two ablations isolate the proposal's key ingredients. The first replaces spectral radius with the sum of squared degrees, which tests whether the spectral transition is just a degree effect. The second runs the unstructured local search without the hub-plus-page restriction under an equal compute budget, which tests whether the structural reduction is hiding maximizers. All objectives share the same graphs, the same $kP_3$-freeness oracle, and the same search budget per $(k,n)$ cell.

Why not just…?

Why not just enumerate all graphs by computer? Exhaustive enumeration is the ground truth where it runs, and we use it. However, the transitions it must resolve sit at $n\approx 7k$ for spectral radius and $n\approx 2\binom{3k-1}{k+1}$ for $K_{k+1}$ counts. The latter is 925 already at $k=4$, far beyond any enumeration. At $k=2$ the spectral crossover is $n=13$, already beyond exhaustive range. Computation can only find counterexamples. The proof in the second part is what turns the map into theorems, and the search ablation tells us whether that proof's structural reduction is safe.

Why not just make Gao et al.'s induction constants explicit and stop? This is a real competitor for the clique part, and we do it as a baseline. Our concern is that induction thresholds of this kind are typically polynomially or exponentially larger than the true crossover. The decisive check is whether their explicit $g(k,s)$ lands near the two-family crossover. If it does for $s=3$, the clique half of the proposal shrinks to bookkeeping, and the spectral half remains, because their method does not touch eigenvalues.

Why not use the sum of squared degrees as a stand-in for spectral radius? Phase Transition of Degenerate Turán Problems in ({p})-Norms shows that degree-power objectives already show a sharp shift from spread-out to star-like extremal graphs. Since $\lambda^2\ge \frac1n\sum_v d(v)^2$, the proxy is tempting. However, The Minimum Spectral Radius of $tP_3$- or $K_5$-Saturated Graphs via the Number of $2$-Walks needed quotient-matrix eigenvalues, not degree sums, to pin down exact extremal graphs. Our first ablation measures directly whether the two objectives' crossovers differ. If they coincide for all tested $k$, the spectral story reduces to a degree story, and we will report it that way.

Why not use flag algebras or regularity? Both methods discard lower-order terms by design. Additive Approximation of Generalized Turán Questions gives regularity-based approximations only up to additive error $n^{\nu(T)-\epsilon}$. A matching on $n$ vertices, which is exactly what separates the competing constructions, lies far below that resolution.

Proposed Experiments

The file's datasets (MUTAG, ENZYMES, IMDB, and neural counting benchmarks) target approximate subgraph counting and do not bear on exact extremal values, so we do not use them. Our benchmarks are the extremal constructions catalogued in the file: generalized books, $K_{k-1}+M_{n-k+1}$, and $K_{3k-1}\cup G_{\mathrm{ex}}$. The metric for each $(k,n,\text{objective})$ cell is the exact extremal value, the isomorphism class of the maximizer, and the gap to the best-of-two predictor.

The first decisive check is the sanity case. For $k\in\{2,3\}$, our clique-count maximizers must reproduce Gao et al.'s solved cases exactly at every $n$ we can enumerate, and any disagreement indicates a bug.

The second decisive check is the spectral exception. Near $n=7k-1$ for $k=2,\dots,8$, we compare the interpolating family $K_{k-1-j}+(K_{3j+2}\cup M)$ against both endpoints. A strictly larger eigenvalue at an interior $j$ would establish a small-scale spectral extremal graph outside Sun et al.'s large-$n$ picture. If no interior winner appears and local search finds nothing better, we expect to prove $n_0=7k-1$ for this family.

The third decisive check is the ordering of thresholds. If edges switch at about $4k$, spectral radius at about $7k$, and triangles at about $9k$, ordered the same way for every tested $k$, that supports the "effective clique size" reading of spectral radius. If spectral radius and squared degrees switch at the same $n$ throughout, that undercuts it.