Skip to content

Erdős problem 180

For every finite family F\mathcal{F} of graphs, is there a single GFG \in \mathcal{F} with ex(n;G)Fex(n;F)\mathrm{ex}(n;G) \ll_{\mathcal{F}} \mathrm{ex}(n;\mathcal{F})? A counterexample refutes the Erdős-Simonovits compactness conjecture.

Sources

Browse retained paths and inspect the exact material available for this Problem.

3 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

180.lean

Retained formal statement1 of 2

If F\mathcal{F} is a finite set of finite graphs then ex(n;F)\mathrm{ex}(n;\mathcal{F}) is the maximum number of edges a graph on nn vertices can have without containing any subgraphs from F\mathcal{F}. Note that it is trivial that ex(n;F)ex(n;G)\mathrm{ex}(n;\mathcal{F})\leq \mathrm{ex}(n;G) for every GFG\in\mathcal{F}. Is it true that, for every F\mathcal{F}, there exists GFG\in\mathcal{F} such that ex(n;G)Fex(n;F)?\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})?

This is the Erdős–Simonovits compactness conjecture. The answer is no: OpenAI [OpenAI26] give a family of connected bipartite graphs, none of them acyclic, for which no single member controls the family extremal number. See erdos_180.variants.counterexample.

FormalConjectures/ErdosProblems/180.leanErdos180.erdos_1803 linesExact file
False  ∀ (family : Finset Erdos180.FiniteGraph),    family.NonemptyErdos180.IsCyclicFamily familyErdos180.IsCompactFamily family
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page