A mathematical preprint examines a fundamental extremal-graph question: how many copies of a clique can an n-vertex graph contain while avoiding a fixed t-vertex tree, and how large can the associated r-clique spectral radius become? Here, an r-clique is a fully connected set of r vertices, while T_t-free means the graph contains no copy of the specified t-vertex tree. The work ranges over finite, simple, undirected graphs rather than sampled units or an empirical dataset.
The main finding is a set of exact answers in two important regimes. In both, the extremal graphs are built by packing in as many disjoint K_{t−1} blocks as possible, then treating the leftover vertices according to a precise remainder rule. The same block also provides the sharp spectral benchmark in the corresponding results.
The sharpest counting result
At clique order t−1, the formula is especially clean. The largest possible number of (t−1)-cliques is ⌊n/(t−1)⌋, the whole-number part of n divided by t−1. Every graph attaining that maximum has exactly that many disjoint K_{t−1} components, together with an arbitrary graph on the remaining vertices.
There is a matching statement for the (t−1)-clique spectral radius, a spectral score attached to the graph’s clique structure. For every T_t-free graph, it is at most 1. If the graph has at least t−1 vertices, it equals 1 exactly when K_{t−1} is a component.
Two wider regimes
One broader counting theorem applies when the forbidden tree has a sufficiently large leaf bunch: at least t−r leaves share a common parent. For 3≤r≤t−1, write n=α(t−1)+β, with α≥0 and 0≤β≤t−2. The exact number of r-cliques is α·binom(t−1,r)+binom(β,r). The extremal graph consists of α disjoint K_{t−1} blocks and a remainder H; H must be K_β when β≥r, but may be any graph on β vertices when β<r.
A separate theorem targets relatively large cliques. For d≥2 and t≥d²−d+3, it sets r=t−d and gives the exact count α·binom(t−1,t−d)+binom(β,t−d), using the theorem’s decomposition of n. The extremal graphs again contain α disjoint K_{t−1} blocks. The β-vertex remainder may be arbitrary when β<t−d and must be K_β when β≥t−d.
How the structure is found
The two settings use different structural arguments. In the leaf-rich case, a leaf-bunch criterion reduces clique counting to a sharp theorem for graphs with bounded maximum degree. In the complementary case, the authors delete edges that lie in no counted (t−d)-clique, group intersecting cliques into equivalence classes, and show that each nontrivial clique-supported component has at most t−1 vertices.
For the spectral analysis, the authors use a clique-tensor variational formulation and the arithmetic–geometric mean inequality. In practical terms, this bounds the global spectral quantity by the largest number of r-cliques containing a single vertex, connecting the final estimate to a local feature of the graph.
The spectral picture
Under the same common-parent leaf condition, every n-vertex T_t-free graph satisfies ρ_r(G)≤binom(t−2,r−1) for 3≤r≤t−1. When n≥t−1, equality holds if and only if K_{t−1} is a component.
In the large-clique regime, the corresponding bound is ρ_{t−d}(G)≤ρ_{t−d}(K_{t−1})=binom(t−2,d−1). If the graph has at least t−1 vertices, equality holds exactly for graphs of the form K_{t−1}∪H, where H is T_t-free.
A conditional advance
The boundaries of the results matter. The counting theorems cover trees with the stated common-parent leaf condition or the range r=t−d with d≥2 and t≥d²−d+3. They therefore do not settle the full question for every t-vertex tree and every clique order; the supplied analysis limits the claims to these named regimes.
This is a mathematical classification of graph classes, not empirical validation or an applied-world study. There are no sampled units, statistical estimates or participant outcomes in the analysis.
Publication and disclosure
The manuscript is an arXiv version 1 preprint dated 26 August 2026. Its acknowledgments say the research was supported in part by the National Natural Science Foundation of China through grants 12571363 and 12371327 and by the Natural Science Foundation of Hunan Province through grant 2025JJ30003. The authors also disclose using GPT 5.5 for English-language editing and say they retain responsibility for the mathematical content.
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