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
Collection coverage

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

5/6

NumberQuestionOpen
#808No statement retained — open to read what the source holdsdisprovedNo formal declaration
#809No statement retained — open to read what the source holdsopenNo formal declaration
#810No statement retained — open to read what the source holdsopenNo formal declaration
#811No statement retained — open to read what the source holdsopenNo formal declaration
#812Is it true that R(n+1)R(n)≥1+c\frac{R(n+1)}{R(n)}\geq 1+c for some constant c>0c>0, for all large nn?openFormalized
#813No statement retained — open to read what the source holdsopenNo formal declaration
#814No statement retained — open to read what the source holdsprovedNo formal declaration
#815No statement retained — open to read what the source holdsdisprovedNo formal declaration
#816No statement retained — open to read what the source holdsprovedNo formal declaration
#832No statement retained — open to read what the source holdsdisprovedNo formal declaration
#833No statement retained — open to read what the source holdsprovedNo formal declaration
#834No statement retained — open to read what the source holdssolvedNo formal declaration
#835It is known that for 3≤k≤83 \leq k \leq 8, the chromatic number of J(2k,k)J(2k, k) is greater than k+1k+1, see [Johnson graphs](https://aeb.win.tue.nl/graphs/Johnson.html).verifiableFormalized
#836No statement retained — open to read what the source holdsopenNo formal declaration
#837No statement retained — open to read what the source holdsopenNo formal declaration
#842No statement retained — open to read what the source holdsprovedNo formal declaration
#883No statement retained — open to read what the source holdsopenNo formal declaration
#895No statement retained — open to read what the source holdsprovedNo formal declaration
#900No statement retained — open to read what the source holdsprovedNo formal declaration
#902No statement retained — open to read what the source holdsopenNo formal declaration
#904Let r≥2r\geq 2 and let tr(n)t_r(n) be the Turán number (the maximal number of edges in a graph on nn vertices with no Kr+1K_{r+1}).proved (Lean)Formalized
#905Every graph with nn vertices and >n2/4>n^2/4 edges contains an edge which is in at least n/6n/6 triangles.proved (Lean)Formalized
#911No statement retained — open to read what the source holdsopenNo formal declaration
#914Let r≥2r\geq 2 and m≥1m\geq 1. Every graph with rmrm vertices and minimum degree at least m(r−1)m(r-1) contains mm vertex disjoint copies of KrK_r.proved (Lean)Formalized
#915No statement retained — open to read what the source holdssolvedNo formal declaration
#916No statement retained — open to read what the source holdsprovedNo formal declaration
#917No statement retained — open to read what the source holdsopenNo formal declaration
#918Is there a graph with ℵ2\aleph_2 vertices and chromatic number ℵ2\aleph_2 such that every subgraph on ℵ1\aleph_1 vertices has chromatic number ≤ℵ0\leq\aleph_0?openFormalized
#919No statement retained — open to read what the source holdsopenNo formal declaration
#920Is it true that, for k≥4k\geq 4, fk(n)≫n1−1k−1(log⁡n)ckf_k(n) \gg \frac{n^{1-\frac{1}{k-1}}}{(\log n)^{c_k}} for some constant ck>0c_k>0?solvedFormalized
#921No statement retained — open to read what the source holdsprovedNo formal declaration
#922No statement retained — open to read what the source holdsprovedNo formal declaration
#923Is it true that, for every kk, there is some f(k)f(k) such that if GG has chromatic number ≥f(k)\geq f(k) then GG contains a triangle-free subgraph with chromatic number ≥k\geq k?proved (Lean)Formalized
#924No statement retained — open to read what the source holdsprovedNo formal declaration
#925No statement retained — open to read what the source holdsdisprovedNo formal declaration
#926No statement retained — open to read what the source holdsprovedNo formal declaration
#927No statement retained — open to read what the source holdsdisproved (Lean)No formal declaration
#934No statement retained — open to read what the source holdsopenNo formal declaration
#944Let k≥4k \ge 4 and r≥1r\ge 1. Must there exist a graph GG with chromatic number kk such that every vertex is critical, yet every critical set of edges has size >r>r?openFormalized
#986No statement retained — open to read what the source holdsprovedNo formal declaration
#993No statement retained — open to read what the source holdsfalsifiableNo formal declaration
#1006No statement retained — open to read what the source holdsdisprovedNo formal declaration
#1007The dimension of a graph GG is the minimal nn such that GG can be embedded in Rn\mathbb{R}^n such that every edge of GG is a unit line segment.solved (Lean)Formalized
#1008Does every graph with mm edges contain a subgraph with ≫m2/3\gg m^{2/3} edges which contains no C4C_4?proved (Lean)Formalized
#1009No statement retained — open to read what the source holdsprovedNo formal declaration
#1010No statement retained — open to read what the source holdsprovedNo formal declaration
#1011No statement retained — open to read what the source holdsopenNo formal declaration
#1012No statement retained — open to read what the source holdssolvedNo formal declaration

Search problems.science

Find a Problem, Result, source, or page