A new mathematical preprint says the maximum possible number of large complete subgraphs in a graph that avoids a given tree can be calculated exactly across a broad range of cases. For every sufficiently large tree, the result applies when the size of the clique being counted is at least a constant times the natural logarithm of the tree’s size, and no more than one less than that size. The same exact count applies for every number of graph vertices covered by the theorem.
This is a result about finite, simple, undirected graphs, not a study based on measured observations. The object being counted is an r-clique, a set of r vertices with every possible link between them, in an n-vertex graph containing no copy of a forbidden tree T on t vertices. The paper asks whether a proposed construction always gives the greatest possible count of such cliques; its new theorem settles that question in the stated range.
The shape of the winner
The maximizing shape is strikingly regular. The theorem describes it as a disjoint union of some number of complete components, each with t−1 vertices, together with a remainder graph. If that remainder has at least r vertices, it must also be complete to attain equality. If it has fewer than r vertices, the theorem allows it to be any graph.
That characterization matters because the theorem does more than give an upper bound. It identifies every graph that reaches the maximum, so the result says both how many r-cliques are possible and what all maximizing graphs must look like. The statement covers every n in its range, while the constants setting the lower tree-size threshold and the logarithmic cutoff are existential rather than numerically specified in the supplied text.
A lower threshold, with a clear boundary
The authors describe the result as a change in the general range where the formula can be proved. The earlier threshold they cite required the clique order r to be at least the ceiling of (2t−1)/3, a condition that grows linearly with the number of vertices in the forbidden tree. The new theorem instead starts at C log t. The comparison is the authors’ account of the cited earlier results; those earlier results were not independently assessed in the supplied analysis.
The underlying conjecture is broader. It asks for the same construction to be exact for every tree on t vertices across the range from cliques of size 3 up to t−2. The new general theorem reaches t−1 at its upper end, but its lower end is restricted to logarithmic clique size and to sufficiently large t.
How the proof works
The main argument is a strong induction on the number of vertices. When the graph contains a vertex of sufficiently high degree, the proof removes a carefully chosen sequence of vertices and tracks how many r-cliques touch the deleted set. If no such high-degree structure is available, a bounded-maximum-degree lemma controls the clique count instead. The induction is designed so that when no complete subgraph of the relevant size is present, the bound is strict below the proposed extremal count.
A separate tree-embedding result supplies the proof’s key degree test. It says that sufficiently high minimum and maximum degree are enough to embed every tree of a given edge count, and the proof applies it with a tree having t−1 edges. This gives the argument a way to connect degree information with the structure of the tree the graph is required to avoid.
The counting side has its own equality test. A bounded-degree lemma gives an upper bound for the number of r-cliques and says equality requires the nontrivial components to be complete components of prescribed sizes. In the leaf-focused proof, the deleted vertices are chosen in sequence; the number of cliques meeting them is bounded by the number of deletions times a binomial coefficient. A second lemma shows that the resulting deletion-cost gap is never negative, with equality only in one specified parameter case.
What remains unresolved
A second theorem extends the exact formula to trees that meet a stated common-neighbor condition on their leaves. It applies to trees with at least four vertices, clique orders from 3 through t−1, and every n in the theorem’s range. The extracted text does not render the threshold notation for the leaf parameter reliably, so the boundary of that condition cannot be stated more precisely here without risking an error.
For those trees, the equality cases have the same rigid form as in the general theorem: disjoint copies of a complete graph on t−1 vertices, plus a remainder that is complete when it is large enough to contain an r-clique and otherwise is unrestricted.
The paper identifies the conjecture for arbitrary trees at small clique orders, especially triangles, as the main remaining question. The supplied results therefore do not establish the formula in full generality.
The supplied document identifies itself as arXiv:2608.25746v2 in the math.CO category, dated 13 October 2026. It reports partial support from the National Natural Science Foundation of China and the Natural Science Foundation of Hunan Province. The authors also disclose using ChatGPT5.6 Sol to improve an earlier result and the paper’s language, while taking responsibility for the paper.
Paper data and sources
Original title: Large Cliques and Clique Spectral Radius in the Erdős--Sós Problem
Authors: XiaoJun Zhao, YueJian Peng
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text