Regenerated from the community database (Apache-2.0), dated, and linked back to it from every problem. erdosproblems.com no longer shows statuses (Bloom's reasons); this is the database's record, not our verdict.
908 of 1221 statements are formalized in Lean (Formal Conjectures) · 107 carry an Erdős prize · 3 are independent of ZFC and 9 more can't be proved, or can't be disproved, from ZFC alone · “open” counts the computable and Lean-checked ones too.
If \(G\) is bipartite then \(\mathrm{ex}(n;G)\ll n^{3/2}\) if and only \(G\) is \(2\)-degenerate, that is, \(G\) contains no induced subgraph with minimal degree at least 3. Conjectured by Erdős and Simonovits [ErSi84]. Erdős first offered…
If \(H\) is bipartite and is \(r\)-degenerate, that is, every induced subgraph of \(H\) has minimum degree \(\leq r\), then \[\mathrm{ex}(n;H) \ll n^{2-1/r}.\] The answer is no. OpenAI [OpenAI26] give a connected bipartite 2-degenerate H…
If \(H\) is bipartite with minimum degree \(r\) then there exists \(\epsilon=\epsilon(H)>0\) such that \[\mathrm{ex}(n;H) \gg n^{2-\frac{1}{r-1}+\epsilon}.\] Conjectured by Erdős and Simonovits [ErSi84]. A probabilistic argument shows that…
If \(\mathcal{F}\) is a finite set of finite graphs then \(\mathrm{ex}(n;\mathcal{F})\) is the maximum number of edges a graph on \(n\) vertices can have without containing any subgraphs from \(\mathcal{F}\). Note that it is trivial that…
What is \(\mathrm{ex}_3(n,K_4^3)\)? That is, the largest number of \(3\)-edges which can placed on \(n\) vertices so that there exists no \(K_4^3\), a set of 4 vertices which is covered by all 4 possible \(3\)-edges. See also…
Show that for any rational \(\alpha \in [1,2)\) there exists a bipartite graph \(G\) such that \[\mathrm{ex}(n;G)\asymp n^{\alpha}.\] The proof constructs balanced rooted models for all rational parameters. Its upper-bound closure replaces…
Show that for \(k\geq 3\) \[\mathrm{ex}(n;C_{2k})\gg n^{1+\frac{1}{k}}.\] This problem is #46 in Extremal Graph Theory in the graphs problem collection.
Is it true that \[\mathrm{ex}(n;\{C_3,C_4\})\sim (n/2)^{3/2}?\] A problem of Erdős and Simonovits. This problem is asking whether the threshold is the same as for forbidding \(C_4\) and all odd cycles (see erdos_573.variants.kst) if one…
Let \(\delta > 0\). If \(n\) is sufficiently large and \(G\) is a graph on \(n\) vertices with no \(K_{2,2,2}\) (the octahedron) and at least \(\delta n^2\) edges, must \(G\) contain an independent set of size \(\gg_\delta n\)? This is a…
Determine, for any \(k>r>2\), the limiting value as \(n\to\infty\) of \[\frac{\mathrm{ex}_r(n,K_k^r)}{\binom{n}{r}},\] where \(\mathrm{ex}_r(n,K_k^r)\) is the largest number of \(r\)-edges which can placed on \(n\) vertices so that there…
Is it true that, for every bipartite graph \(G\), there exists some \(\alpha\in [1,2)\) and \(c>0\) such that \[\mathrm{ex}(n;G)\sim cn^\alpha?\] The condition that \(G\) have at least two edges excludes degenerate forbidden graphs whose…
Is it true that \[\mathrm{ex}(n; K_{r,r}) \gg n^{2-1/r}?\]
Give an asymptotic formula for \(\mathrm{ex}(n; C_4)\). Erdős and Klein [Er38] proved \(\mathrm{ex}(n; C_4) \asymp n^{3/2}\), and Reiman [Re58] proved \[\frac{1}{2\sqrt 2} \le \lim \frac{\mathrm{ex}(n; C_4)}{n^{3/2}} \le \frac12.\] Erdős…
Let \(f(n;k,l)=\min \mathrm{ex}(n;G)\), where \(G\) ranges over all graphs with \(k\) vertices and \(l\) edges. Give good estimates for \(f(n;k,l)\) in the range \(k<l\leq k^2/4\). In [Er64c, p. 33] this question is asked for…
Let \(g_k(n)\) be the maximal number of edges possible on a graph with \(n\) vertices which does not contain a cycle with \(k\) chords incident to a vertex on the cycle. Is it true that \[g_k(n)=(k+1)n-(k+1)^2\] for \(n\) sufficiently…
Is it true that every \(3\)-uniform hypergraph on \(3n\) vertices with at least \(n^3+1\) edges must contain either a subgraph on \(4\) vertices with \(3\) edges or a subgraph on \(5\) vertices with \(7\) edges? Harris has provided the…
Let \(r\geq 4\). If \(G\) is a graph on \(n\) vertices with at least \(\mathrm{ex}(n;K_r)\) edges then must \(G\) contain a vertex with degree \(d\gg_r n\) whose neighbourhood contains at least \(\mathrm{ex}(d;K_{r-1})\) edges? As Erdős…
Let \(s,k,r\geq 2\). Let \(\mathcal{F}\) be the family of all \(r\)-uniform hypergraphs with \(k\) vertices and \(s\) edges. Determine \[\mathrm{ex}_r(n,\mathcal{F}).\]
Let \(K_{t}(r)\) be the complete \(t\)-partite \(t\)-uniform hypergraph with \(r\) vertices in each class. Is it true that \[\mathrm{ex}_t(n,K_t(r)) \geq n^{t-r^{1-t}-o(1)}\] for all \(t,r\geq 2\)? The restriction \(r\geq 2\) excludes…