REVIEW 1 cited by
Tur\'an's Theorem for random graphs
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Tur\'an's Theorem for random graphs
abstract
For a graph $G$, denote by $t_r(G)$ (resp. $b_r(G)$) the maximum size of a $K_r$-free (resp. $(r-1)$-partite) subgraph of $G$. Of course $t_r(G) \geq b_r(G)$ for any $G$, and Tur\'an's Theorem says that equality holds for complete graphs. With $G_{n,p}$ the usual ("binomial" or "Erd\H{o}s-R\'enyi") random graph, we show: For each fixed r there is a C such that if \[ p=p(n) > Cn^{-\tfrac{2}{r+1}}\log^{\tfrac{2}{(r+1)(r-2)}}n, \] then $\Pr(t_r(G_{n,p})=b_r(G_{n,p}))\rightarrow 1$ as $n\rightarrow\infty$. This is best possible (apart from the value of $C$) and settles a question first considered by Babai, Simonovits and Spencer about 25 years ago.
Forward citations
Cited by 1 Pith paper
-
Random Tur\'an Theorem for the Fano Plane
The largest Fano-free subhypergraph of G_{n,p}^{(3)} is bipartite whp precisely above the sharp threshold p̂ = Θ_F n^{-2/3}(log n)^{1/6}.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.