Exact Clique Counts in Graphs with a Forbidden Tree
For a fixed tree $T$ on $t$ vertices, let $\ex(n,K_r,T)$ denote the maximum number of $r$-cliques in an $n$-vertex $T$-free graph. Write $n=α(t-1)+β$ with $0\leβ<t-1$. A conjecture proposed in extremal-graph form by Alon and Shikhelman~\cite{alon2016}, later stated explicitly as an exact clique-counting formula by Gerbner and Palmer~\cite{GP2026}, asserts that \[ \ex(n,K_r,T)=α\binom{t-1}{r}+\binomβr, \] with the extremal construction given by the vertex disjoint union of $α$ copies of $K_{t-1}$ and a graph with $β$ vertices. This paper proves this conjecture for every $n$ and for every tree…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.25746
curl -X POST /api/v1/records/arxiv/2608.25746/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.25746/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'