Problem 88

For any $\epsilon>0$ there exists $\delta=\delta(\epsilon)>0$ such that if $G$ is a graph on $n$ vertices with no independent set or clique of size $\geq \epsilon\log n$ then $G$ contains an induced subgraph with $m$ edges for all $m\leq \delta n^2$ .

Source: erdosproblems.com/88

Graph theory
Ramsey theory

Wiki page

Status

SolvedProved

An accepted solution exists. The statement is true.

Proved. Kwan, Sah, Sauermann and Sawhney's Theorem 1.1 [KSSS22] gives, for fixed $C>0$ and $\eta>0$ and $n$ large in terms of them, an induced subgraph with exactly $x$ edges for every integer $0\le x\le(1-\eta)e(G)$ in every $C$ -Ramsey graph $G$ on $n$ vertices, and the paper's footnote 2 derives the conjecture in its $\delta n^2$ form from the case $\eta=1/2$ through the Erdős--Szemerédi density bound; the deduction to the site's exact wording is written out in the Current assessment. The paper is published in Forum of Mathematics, Pi 11 (2023), e21 (refereed); the locators are those of the arXiv v2 of 30 May 2024, posted after the journal publication and not compared with it. The site labels the problem PROVED and its curator, T. F. Bloom, credits the solution to Kwan, Sah, Sauermann and Sawhney in the commentary. Read depth: claims checked for Theorem 1.1, footnote 2 and Theorem 1.2; the proof is not reviewed here. The claim page Kwan, Sah, Sauermann and Sawhney 2022 records the result, its postings and the acceptance evidence.

KSSS22: Kwan, M., Sah, A., Sauermann, L. and Sawhney, M., Anticoncentration in Ramsey graphs and a proof of the Erdős--McKay conjecture. Forum of Mathematics, Pi 11 (2023), e21, DOI 10.1017/fmp.2023.17 (published online 24 August 2023); arXiv:2208.02874 (v1 4 August 2022; v2 30 May 2024, 60 pages, whose pagination the locators follow). Theorem 1.1 and footnote 2, p. 2; Theorem 1.2, p. 3. Library home: Kwan et al. 2022.
Er92b: Erdős, P., Some of my favourite problems in various branches of combinatorics. Matematiche (Catania) 47 (1992), 231--240; Problem 12, p. 234. Library home: Erdős 1992.
Er95: Erdős, P., Some of my favourite problems in number theory, combinatorics, and geometry. Resenhas 2 (1995), 165--186; the conjecture is item 16 of its graph-theory part (in the author reprint, which carries no journal pagination; not quoted here). Library home: Erdős 1995.
Er97d: Erdős, P., Some recent problems and results in graph theory. Discrete Math. 164 (1997), 81--85; item 8, p. 83, the restatement cited by the site and, as its [36], by [KSSS22]. Library home: Erdős 1997.
ErSz72: Erdős, P. and Szemerédi, E., On a Ramsey type theorem. Period. Math. Hungar. 2 (1972), 295--299. Not held; its density theorem is quoted here from [KSSS22] (p. 1 and footnote 2) and from Bukh and Sudakov (2007), p. 613.
AKS03: Alon, N., Krivelevich, M. and Sudakov, B., Induced subgraphs of prescribed size. J. Graph Theory 43 (2003), 239--251. Not held; its $n^{\alpha_C}$ range is quoted from [KSSS22] p. 2 and Bukh--Sudakov p. 613.
LoPl22: Long, E. and Ploscaru, L., A bipartite version of the Erdős--McKay conjecture. arXiv:2207.12874 (v2 8 November 2022); abstract read, paper not held, journal record not checked. Context: the bipartite analog.

Problem 88

Status

Proof claims

Discussion