Problem 804

Let $f(m,n)$ be maximal such that any graph on $n$ vertices in which every induced subgraph on $m$ vertices has an independent set of size at least $\log n$ must contain an independent set of size at least $f(n)$ .

Estimate $f(n)$ . In particular, is it true that $f((\log n)^2,n) \geq n^{1/2-o(1)}$ ? Is it true that $f((\log n)^3,n)\gg (\log n)^3$ ?

Source: erdosproblems.com/804

Graph theory

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site labels the problem DISPROVED, and its commentary credits Alon and Sudakov with the two bounds that refute the displayed proposals; the frontmatter standing is derived from the accepted claim page Alon and Sudakov's bounds, whose acceptance evidence is the refereed journal and the site's own commentary, and it targets the two-variable reading stated in the Formulation.

Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988), Wiley, New York (1991), 397--406; the site's source key, where the site calls the problem a question of Erdős and Hajnal; [AlSu07] cites it as its reference [3] for both displayed questions and for Erdős's remark that they expected the bound $n^{1/2-\epsilon}$ .
AlSu07: Alon, Noga and Sudakov, Benny, On graphs with subgraphs having large independence numbers. J. Graph Theory 56 (2007), no. 2, 149--157, doi:10.1002/jgt.20264 (published online 9 August 2007; the site's reference text gives "J. Graph Theory (2007), 149-157" with no volume); arXiv:0706.4099 (v1, 27 June 2007).

Problem 804

Status

Proof claims

Discussion