Skip to content

Erdős Problems

1,217 source-owned questions · 604 with a formal statement · searchable by statement, number, topic and source status.

Add a contributionCollection details
Full distribution

Collection coverage

Source status, exact formal material, and reviewed Results are separate signals.

  • Open per source608
  • Resolved per source556
  • Other source status53
Exact formal statement available604 / 1,217
With Repository-reviewed evidence2 / 1,217
More filters

Coverage is source-observation coverage, not Problem completeness. Inspect coverage

Problems

275 Problems

1/6

SelectNumberQuestionOpen
#19No statement retained — open to read what the source holdsSource says decidableNo formal declaration
#22Let ϵ>0\epsilon > 0 and let nn be sufficiently large depending on ϵ\epsilon. Is there a graph on nn vertices with at least n2/8n^2/8 many edges which contains no K4K_4, such that the largest independent set has size at most ϵn\epsilon n?Source says provedFormalized
#23The blow-up of C5C_5 shows that the bound n2n^2 in Erdős Problem 23 is tight: any bipartite subgraph must omit at least n2n^2 edges.Source says falsifiableFormalized
#24Does every triangle-free graph on 5n5n vertices contain at most n5n^5 copies of C5C_5?Source says proved (Lean)Formalized
#57No statement retained — open to read what the source holdsSource says provedNo formal declaration
#58No statement retained — open to read what the source holdsSource says provedNo formal declaration
#59No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#60Does every graph on nn vertices with >ex(n;C4)>\mathrm{ex}(n;C_4) edges contain ≫n1/2\gg n^{1/2} many copies of C4C_4?Source says openFormalized
#61The Erdős–Hajnal Conjecture states that there is a constant c(H)>0c(H) > 0 for each HH such that we can take f(n)=nc(H)f(n) = n^{c(H)} in the above formulation.Source says openFormalized
#62No statement retained — open to read what the source holdsSource says openNo formal declaration
#63No statement retained — open to read what the source holdsSource says provedNo formal declaration
#64Does every finite graph with minimum degree at least 33 contain a cycle of length 2k2^k for some k≥2k \geq 2?Source says falsifiableFormalized
#65No statement retained — open to read what the source holdsSource says openNo formal declaration
#70Erdős Problem 70: Let c\mathfrak{c} be the cardinality of the continuum, let β\beta be a countable ordinal, and let 2≤n<ω2 \le n < \omega. Is it true that c→(β,n)23\mathfrak{c} \to (\beta, n)^3_2?Source says openFormalized
#71Is it true that for every infinite arithmetic progression PP which contains even numbers there is some constant c=c(P)c=c(P) such that every graph with average degree at least cc contains a cycle whose length is in PP?Source says proved (Lean)Formalized
#72No statement retained — open to read what the source holdsSource says provedNo formal declaration
#73No statement retained — open to read what the source holdsSource says provedNo formal declaration
#74Let f(n)→∞f(n)\to \infty possibly very slowly. Is there a graph of infinite chromatic number such that every finite subgraph on nn vertices can be made bipartite by deleting at most f(n)f(n) edges?Source says openFormalized
#75Is there a graph of chromatic number ℵ_ 1 with ℵ_ 1 vertices such that for all ε > 0, if n is sufficiently large and H is a subgraph on n vertices, then H contains an independent set of size > n ^ (1 - ε)?Source says openFormalized
#76No statement retained — open to read what the source holdsSource says provedNo formal declaration
#77No statement retained — open to read what the source holdsSource says openNo formal declaration
#78No statement retained — open to read what the source holdsSource says openNo formal declaration
#79No statement retained — open to read what the source holdsSource says provedNo formal declaration
#80No statement retained — open to read what the source holdsSource says openNo formal declaration
#81No statement retained — open to read what the source holdsSource says openNo formal declaration
#82F(n)/log⁡n→∞asn→∞F(n) / \log n \to \infty as n \to \inftySource says openFormalized
#84No statement retained — open to read what the source holdsSource says openNo formal declaration
#85Is it true that, for all large nn, f(n+1)≥f(n)f(n + 1) \ge f(n)?Source says openFormalized
#86No statement retained — open to read what the source holdsSource says openNo formal declaration
#87No statement retained — open to read what the source holdsSource says openNo formal declaration
#88No statement retained — open to read what the source holdsSource says provedNo formal declaration
#108For every r ≥ 4 and k ≥ 2 is there some finite f(k,r) such that every graph of chromatic number ≥ f(k,r) contains a subgraph of girth ≥ r and chromatic number ≥ k?Source says openFormalized
#110No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#111No statement retained — open to read what the source holdsSource says openNo formal declaration
#112No statement retained — open to read what the source holdsSource says openNo formal declaration
#113No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#127No statement retained — open to read what the source holdsSource says provedNo formal declaration
#128Let G be a graph with n vertices such that every induced subgraph on ≥ n/2n/2 vertices has more than n2/50n^2/50 edges. Must G contain a triangle?Source says falsifiableFormalized
#129No statement retained — open to read what the source holdsSource says openNo formal declaration
#130Let A⊂R2A\subset\mathbb{R}^2 be an infinite set which contains no three points on a line and no four points on a circle. Consider the graph with vertices the points in AA, where two vertices are joined by an edge if and only if they are an integer distance apart. How large can the chromatic number and clique number of this graph be? In particular, can the chromatic number be infinite?Source says openFormalized
#133No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#134Let ϵ,δ>0\epsilon,\delta>0 and nn be sufficiently large in terms of ϵ\epsilon and δ\delta. Let GG be a triangle-free graph on nn vertices with maximum degree <n1/2−ϵ<n^{1/2-\epsilon}. Can GG be made into a triangle-free graph with diameter 22 by adding at most δn2\delta n^2 edges?Source says proved (Lean)Formalized
#136No statement retained — open to read what the source holdsSource says solvedNo formal declaration
#146If HH is bipartite and is rr-degenerate, that is, every induced subgraph of HH has minimum degree ≤r\leq r, then ex(n;H)≪n2−1/r.\mathrm{ex}(n;H) \ll n^{2-1/r}.Source says open (Lean)Formalized
#147No statement retained — open to read what the source holdsSource says disprovedNo formal declaration
#149No statement retained — open to read what the source holdsSource says openNo formal declaration
#150A minimal cut of a graph is a minimal set of vertices whose removal disconnects the graph. Let c(n)c(n) be the maximum number of minimal cuts a graph on nn vertices can have.Source says proved (Lean)Formalized
#151No statement retained — open to read what the source holdsSource says openNo formal declaration