Erdős Problem #579 — Independent sets in dense -free graphs
For every real number , does there exist a constant and an integer such that, for every integer and every finite simple graph with vertices,
and with no subgraph isomorphic to , one has
Here is the number of edges, is the maximum size of an independent vertex set, and 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 in the original statement means a lower bound by a positive constant depending only on times . 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 , 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 and having independence number must have only edges. In the usual notation, the parameter is the largest size of a vertex set inducing a -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
UnsolvedMath, Erdős Problems set, ULAM AI, licensed CC BY 4.0.
Progress summary
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.