Problem 805

For which functions $g(n)$ with $n>g(n)\geq (\log n)^2$ is there a graph on $n$ vertices in which every induced subgraph on $g(n)$ vertices contains a clique of size $\geq \log n$ and an independent set of size $\geq \log n$ ?

In particular, is there such a graph for $g(n)=(\log n)^3$ ?

Source: erdosproblems.com/805

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Open; the site labels the problem OPEN. Two refereed partial results have claim pages. Alon and Sudakov show that no such graph exists for $g(n)\le c(\log n)^3/\log\log n$ , and Alon, Bucić and Sudakov build one for $g(n)=2^{2^{(\log\log n)^{1/2+o(1)}}}$ . The case $g(n)=(\log n)^3$ is open.

ABS21: Alon, Noga and Bucić, Matija and Sudakov, Benny, Large cliques and independent sets all over the place. Proc. Amer. Math. Soc. (2021), 3145-3157.
AlSu07: Alon, Noga and Sudakov, Benny, On graphs with subgraphs having large independence numbers. J. Graph Theory (2007), 149-157.
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 (1991), 397--406. The site's source for the problem; [AlSu07] (its [3]) and [ABS21] (its [13]) cite it for the question.

Problem 805

Status

Proof claims

Discussion