Erdős Problem #575
Status Solved · erdosproblems.comLLM status Solved from source status
Erdős problemsTop Open Problems openaigpt 6 astra ultragpt pro 5.2 60% cataloguedSolvedSolvedStatement
Let $\mathcal{F}$ be a finite family of finite simple graphs. Define $\mathrm{ex}(n;\mathcal{F})$ to be the maximum number of edges in an $n$-vertex graph containing no subgraph isomorphic to any $F\in\mathcal{F}$.
Assume $\mathcal{F}$ contains at least one bipartite graph. The question is whether there always exists a bipartite graph $G\in\mathcal{F}$ and a constant $C_{\mathcal{F}}>0$ such that for all $n$, \[ \mathrm{ex}(n;G) \le C_{\mathcal{F}}\, \mathrm{ex}(n;\mathcal{F}). \] (Using Vinogradov notation: $\mathrm{ex}(n;G)\ll_{\mathcal{F}} \mathrm{ex}(n;\mathcal{F})$.)
Restatement from Math-858-A2 r1, with the source manuscript’s qualifications.
Original problem on erdosproblems.com
Statement licence: CC-BY-4.0 · Source file
Contributions 2
GPT 6 Astra Ultra attempt on Math-858
Erdős Problem 575
Statement and scope.
Let $\mathcal F$ be a finite family of graphs containing a bipartite graph. Must some bipartite $F\in\mathcal F$ satisfy \[ \operatorname{ex}(n,F)\ll\operatorname{ex}(n,\mathcal F)? \] As literally written, the answer has an elementary negative example using forests. We prove it exactly. The more substantial version in which all forbidden graphs contain cycles remains unresolved in this attempt; its known negative solution is not reconstructed here.A two-member forest family.
Take $\mathcal F=\{P_3,2K_2\}$, where $P_3$ is a two-edge path and $2K_2$ consists of two disjoint edges. Both are bipartite. Any two distinct edges either meet at a vertex, giving a $P_3$, or are disjoint, giving a $2K_2$. Hence for $n\geq2$, \[ \operatorname{ex}(n,\mathcal F)=1. \tag{1} \] On the other hand, avoidance of $P_3$ means maximum degree at most one, so \[ \operatorname{ex}(n,P_3)=\lfloor n/2\rfloor. \tag{2} \] We next establish the other individual extremal number without an asymptotic assumption.Pairwise intersecting edges.
In a $2K_2$-free graph every two edges intersect. If there are two edges $ab,ac$, then either every edge contains $a$, giving a star, or there is an edge avoiding $a$. That edge must meet both $ab$ and $ac$, so it is $bc$. Any further edge must intersect all three edges of this triangle, forcing it to be one of the same three edges. Thus every such graph with at least two edges is either a star or a triangle, together with isolated vertices. Consequently \[ \operatorname{ex}(n,2K_2)=n-1\quad(n\geq4), \tag{3} \] attained by the spanning star. Equations $1$--$3$ show that neither family member has extremal number bounded by a constant multiple of the family extremal number.Why this does not reconstruct the cyclic counterexample.
The example exploits the different ways two edges can intersect. Its simultaneous forbidden family has bounded extremal number, whereas each forest individually permits linearly many edges. Requiring every forbidden graph to contain a cycle removes both members of this example. For that strengthened question one needs a different construction and estimates separating two superlinear orders; $1$--$3$ supply neither.The current problem page reports a counterexample even with connected bipartite cyclic members. The primary treatment also explicitly distinguishes the elementary forest issue from this stronger result: Chapter 10 of Ten Advances in Mathematics and Theoretical Computer Science, https://cdn.openai.com/pdf/ten-proofs-oai.pdf. That construction and its estimates are not assumed as proved steps in this attempt.
Assessment.
The literal printed statement is completely disproved above. The intended stronger cyclic version remains unresolved here, and the completion estimate reflects that missing part. The forest observation is already recorded in the primary discussion; no novelty or Lean verification is claimed. Statement checked 24 September 2026: https://www.erdosproblems.com/575.Completion rate estimate: 60%.
gpt pro 5.2 attempt on Math-858
1) FORMAL RESTATEMENT
Let $\mathcal{F}$ be a finite family of finite simple graphs. Define $\mathrm{ex}(n;\mathcal{F})$ to be the maximum number of edges in an $n$-vertex graph containing no subgraph isomorphic to any $F\in\mathcal{F}$.
Assume $\mathcal{F}$ contains at least one bipartite graph. The question is whether there always exists a bipartite graph $G\in\mathcal{F}$ and a constant $C_{\mathcal{F}}>0$ such that for all $n$, \[ \mathrm{ex}(n;G) \le C_{\mathcal{F}}\, \mathrm{ex}(n;\mathcal{F}). \] (Using Vinogradov notation: $\mathrm{ex}(n;G)\ll_{\mathcal{F}} \mathrm{ex}(n;\mathcal{F})$.)
2) QUICK LITERATURE/CONTEXT CHECK
The source file lists this as a problem of Erdős and Simonovits and points to related problem [180] and the graphs collection. The Erdős Problems website currently lists #575 as open (as of the access date shown there).
3) ATTACK PLAN
Proof-track ideas: - Identify natural sufficient conditions on $\mathcal{F}$ under which $\mathrm{ex}(n;\mathcal{F})$ is within a constant factor of $\min\{\mathrm{ex}(n;H):H\in\mathcal{F}\text{ bipartite}\}$. - Use subgraph containment relations inside $\mathcal{F}$: if one bipartite member is contained in all others, the problem becomes trivial.
Disproof-track ideas: - Search for a family $\mathcal{F}$ with multiple bipartite members such that avoiding all of them simultaneously forces a much smaller edge count than avoiding any one of them. - Attempt small $n$ brute force over families of small graphs to see whether a counterexample pattern emerges.
I provide two unconditional "sanity" lemmas (covering some degenerate and some structured cases) but do not resolve the general question.
4) WORK
FAST REALITY CHECK (sanity on degenerate cases). - If $K_2\in\mathcal{F}$ then $\mathrm{ex}(n;\mathcal{F})=0$ for all $n$, and choosing $G=K_2$ makes the desired inequality trivial. - If $\mathcal{F}$ contains a bipartite graph $G$ that is a subgraph of every $F\in\mathcal{F}$, then forbidding $\mathcal{F}$ is the same as forbidding $G$.
These are formalized below.
Lemma 575.1 (trivial case when $K_2\in\mathcal{F}$). If $K_2\in\mathcal{F}$ then $\mathrm{ex}(n;\mathcal{F})=0$ and taking $G=K_2$ satisfies $\mathrm{ex}(n;G)\ll_{\mathcal{F}}\mathrm{ex}(n;\mathcal{F})$. Proof. A graph contains no $K_2$ subgraph if and only if it has no edges. So forbidding $K_2$ forces $e(G)=0$, hence $\mathrm{ex}(n;\mathcal{F})=0$. Also $\mathrm{ex}(n;K_2)=0$. Thus $\mathrm{ex}(n;K_2)=0\le C\cdot 0$ for any constant $C$. $\square$
Lemma 575.2 (subgraph-dominating bipartite member). Suppose there exists a bipartite graph $G\in\mathcal{F}$ such that $G$ is a subgraph of every $F\in\mathcal{F}$. Then for every $n$, \[ \mathrm{ex}(n;\mathcal{F})=\mathrm{ex}(n;G). \] In particular, the conjectured inequality holds with this $G$ and constant $C_{\mathcal{F}}=1$. Proof. Let $H$ be any $n$-vertex graph. If $H$ contains some $F\in\mathcal{F}$, then (since $G\subseteq F$) the same copy of $F$ contains a copy of $G$; hence $H$ contains $G$. Therefore, if $H$ is $G$-free then $H$ is $F$-free for every $F\in\mathcal{F}$, i.e. $H$ is $\mathcal{F}$-free. This shows that the class of $G$-free graphs is a subset of the class of $\mathcal{F}$-free graphs, so $\mathrm{ex}(n;G)\le \mathrm{ex}(n;\mathcal{F})$.
Conversely, because $G\in\mathcal{F}$, any $\mathcal{F}$-free graph is in particular $G$-free. So the class of $\mathcal{F}$-free graphs is a subset of the class of $G$-free graphs, giving $\mathrm{ex}(n;\mathcal{F})\le \mathrm{ex}(n;G)$.
Combining the two inequalities yields equality. $\square$
Why the general case is hard. Outside Lemma 575.2, forbidding multiple graphs can interact nontrivially: graphs that are extremal for one forbidden subgraph can be structurally very different from extremal graphs for another. The question asks whether this interaction can ever reduce $\mathrm{ex}(n;\mathcal{F})$ by more than a constant factor compared to every bipartite member of $\mathcal{F}$.
5) VERIFICATION
- Lemma 575.1 and Lemma 575.2 follow directly from the definition of subgraph containment and the monotonicity $\mathrm{ex}(n;\mathcal{F})\le \mathrm{ex}(n;F)$ for each $F\in\mathcal{F}$. - In Lemma 575.2, both inclusions of forbidden classes were checked carefully: (i) $G$-free implies $\mathcal{F}$-free by $G\subseteq F$ for all $F$, and (ii) $\mathcal{F}$-free implies $G$-free because $G\in\mathcal{F}$.
6) FINAL
UNRESOLVED
(i) Strongest fully proved partial result: The conjecture holds in the degenerate case $K_2\in\mathcal{F}$ (Lemma 575.1) and in the structured case where some bipartite $G\in\mathcal{F}$ is a subgraph of every member of $\mathcal{F}$ (Lemma 575.2).
(ii) First gap (crisp): Either prove that for every finite family $\mathcal{F}$ containing a bipartite graph there exists a bipartite $G\in\mathcal{F}$ with $\mathrm{ex}(n;G)=O_{\mathcal{F}}(\mathrm{ex}(n;\mathcal{F}))$, or exhibit a concrete family $\mathcal{F}$ for which \[\frac{\mathrm{ex}(n;G)}{\mathrm{ex}(n;\mathcal{F})}\to\infty\quad\text{for every bipartite }G\in\mathcal{F}. \]
(iii) Top 3 next moves (concrete): 1. Systematically search for a counterexample among small families $\mathcal{F}$ built from standard bipartite obstructions (even cycles, complete bipartite graphs, trees) by comparing growth exponents. 2. Prove a "winner-takes-all" principle for families whose bipartite members have distinct known extremal exponents: show $\mathrm{ex}(n;\mathcal{F})$ is within a constant of the smallest exponent member. 3. Try to construct $\mathcal{F}=\{G_1,G_2\}$ with incomparable bipartite graphs where known extremal constructions for $G_1$ necessarily contain $G_2$ and vice versa, potentially forcing a new (smaller) extremal order.
(iv) Minimal counterexample structure: A counterexample would require a family $\mathcal{F}$ with at least two bipartite members such that avoiding all of them forces a substantially sparser graph than avoiding any one of them (ratio diverging with $n$). This would likely involve two bipartite graphs with extremal constructions of very different "geometry" so that the intersection of the two avoidance properties severely restricts edge density.