Counting cliques in graphs with small independence number
We prove that for all fixed $k\geq 4$, any $N$ vertex graph with no independent set of size $n$ and $N\geq Ω(n^{k-1}/\log^{k-2}n)$ contains at least $$ Ω\bigg(\binom Nk \Big(\frac{\log n}{n}\Big)^{\binom k2}/\log n\bigg) $$ cliques of order $k$, and for $k\geq 5$ this is best possible conditional on the known upper bounds for $r(k,n)$. This is also true and tight for $k=2$ by Turán's Theorem and for $k=3$ by a result of Bohman and Mubayi. We show the bound is also tight for $k=4$. We obtain other supersaturation results using the same methods.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.02279
curl -X POST /api/v1/records/arxiv/2608.02279/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.02279/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'