Exponential tails for factors and the chromatic number of random graphs
The celebrated result of Johansson, Kahn and Vu determined the threshold order for clique factors in random graphs, and subsequent work identified the sharp threshold and the corresponding hitting-time phenomenon. In this paper we study the probability that there is no $K_r$-factor above the threshold and, more generally, the probability that the largest $K_r$-matching covers less than $n-s$ vertices of $G(n,p)$. For every fixed $r\ge3$, throughout the range $$n^{-2/r}(\log n)^{1/\binom r2}\ll p\ll n^{-2/(r+1)},\qquad n-s\in r\mathbb Z,\qquad s=o(n),$$ we prove $$\mathbb…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.12700
curl -X POST /api/v1/records/arxiv/2609.12700/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.12700/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'