← All problems

Erdős Problem #579 — Independent sets in dense K2,2,2K_{2,2,2}-free graphs

31 years old · documented by

For every real number δ>0\delta>0, does there exist a constant cδ>0c_\delta>0 and an integer n0(δ)n_0(\delta) such that, for every integer n≥n0(δ)n\ge n_0(\delta) and every finite simple graph GG with nn vertices,

e(G)≥δn2e(G)\ge \delta n^2

and with no subgraph isomorphic to K2,2,2K_{2,2,2}, one has

α(G)≥cδn?\alpha(G)\ge c_\delta n?

Here e(G)e(G) is the number of edges, α(G)\alpha(G) is the maximum size of an independent vertex set, and K2,2,2K_{2,2,2} is the complete tripartite graph whose three parts each have size two. The forbidden copy is a subgraph, not necessarily an induced subgraph. The notation ≫δn\gg_\delta n in the original statement means a lower bound by a positive constant depending only on δ\delta times nn. Erdős Problem #579

Background

The question lies in Ramsey–Turán theory, which studies how forbidding a fixed subgraph constrains the maximum edge count when large independent sets are also excluded. Erdős, Hajnal, Sós, and Szemerédi developed this direction following earlier work by Sós; their 1993 paper describes the broader framework as combining Turán-type and Ramsey-type extremal questions. The graph K2,2,2K_{2,2,2}, also called the octahedron graph, is a particularly difficult forbidden graph in this setting. Erdős et al. (1993) Geometric constructions for Ramsey-Turán theory (arXiv:2103.10423)

A closely related Ramsey–Turán formulation asks whether graphs avoiding K2,2,2K_{2,2,2} and having independence number o(n)o(n) must have only o(n2)o(n^2) edges. In the usual notation, the parameter α2(G)\alpha_2(G) is the largest size of a vertex set inducing a K2K_2-free graph, so here it is exactly the independence number. This places the question among problems about whether a dense forbidden-subgraph-free graph must retain a linearly large independent set. Geometric constructions for Ramsey-Turán theory (arXiv:2103.10423)

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.