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

4/6

NumberQuestionOpen
#667No statement retained — open to read what the source holdsopenNo formal declaration
#704No statement retained — open to read what the source holdsopenNo formal declaration
#705Let GG be a finite unit distance graph in \mamthbbR2\mamthbb{R}^2. Is there some kk such that if GG has girth ≥k≥ k, then χ(G)≤3\chi(G) ≤ 3?disprovedFormalized
#706No statement retained — open to read what the source holdsopenNo formal declaration
#712No statement retained — open to read what the source holdsopenNo formal declaration
#713No statement retained — open to read what the source holdsopenNo formal declaration
#714No statement retained — open to read what the source holdsopenNo formal declaration
#715No statement retained — open to read what the source holdsprovedNo formal declaration
#716No statement retained — open to read what the source holdsproved (Lean)No formal declaration
#717No statement retained — open to read what the source holdsprovedNo formal declaration
#718No statement retained — open to read what the source holdsprovedNo formal declaration
#719No statement retained — open to read what the source holdsopenNo formal declaration
#720No statement retained — open to read what the source holdsprovedNo formal declaration
#736No statement retained — open to read what the source holdsnot provableNo formal declaration
#737No statement retained — open to read what the source holdsprovedNo formal declaration
#738No statement retained — open to read what the source holdsopenNo formal declaration
#739No statement retained — open to read what the source holdsnot provableNo formal declaration
#740Let m\mathfrak{m} be an infinite cardinal and GG be a graph with chromatic number m\mathfrak{m}. Let r≥1r\geq 1. Must GG contain a subgraph of chromatic number m\mathfrak{m} which does not contain any odd cycle of length ≤r\leq r?openFormalized
#742The complete bipartite graph Ka,bK_{a, b} has exactly a⋅ba \cdot b edges. The bound ⌊n2/4⌋\lfloor n^2 / 4 \rfloor in the Murty-Simon conjecture is attained by the balanced case K⌈n/2⌉,⌊n/2⌋K_{\lceil n/2 \rceil, \lfloor n/2 \rfloor}.decidableFormalized
#743No statement retained — open to read what the source holdsfalsifiableNo formal declaration
#744No statement retained — open to read what the source holdsdisprovedNo formal declaration
#745No statement retained — open to read what the source holdsprovedNo formal declaration
#746No statement retained — open to read what the source holdsprovedNo formal declaration
#750Let f(m)f(m) be some function such that f(m)→∞f(m)\to \infty as m→∞m\to \infty. Does there exist a graph GG of infinite chromatic number such that every subgraph on mm vertices contains an independent set of size at least m2−f(m)\frac{m}{2}-f(m)?proved (Lean)Formalized
#751Let GG be a graph with chromatic number χ(G)=4\chi(G)=4. If m1<m2<⋯m_1<m_2<\cdots are the lengths of the cycles in GG then can min⁡(mi+1−mi)\min(m_{i+1}-m_i) be arbitrarily large?disproved (Lean)Formalized
#752No statement retained — open to read what the source holdsprovedNo formal declaration
#753The list chromatic number χL(G)\chi_L(G) is defined to be the minimal kk such that for any assignment of a list of kk colours to each vertex of GG (perhaps different lists for different vertices) a colouring of each vertex by a colour on its list can be chosen such that adjacent vertices receive distinct colours.disproved (Lean)Formalized
#758No statement retained — open to read what the source holdssolvedNo formal declaration
#759No statement retained — open to read what the source holdssolvedNo formal declaration
#760The cochromatic number of GG, denoted by ζ(G)\zeta(G), is the minimum number of colours needed to colour the vertices of GG such that each colour class induces either a complete graph or independent set.proved (Lean)Formalized
#761No statement retained — open to read what the source holdsopenNo formal declaration
#762The cochromatic number of GG, denoted by ζ(G)\zeta(G), is the minimum number of colours needed to colour the vertices of GG such that each colour class induces either a complete graph or empty graph.disproved (Lean)Formalized
#765No statement retained — open to read what the source holdssolved (Lean)No formal declaration
#766No statement retained — open to read what the source holdsopenNo formal declaration
#767No statement retained — open to read what the source holdsprovedNo formal declaration
#775Is there a 33-uniform hypergraph on nn vertices which contains at least n−O(1)n-O(1) different sizes of cliques (maximal complete subgraphs)?disproved (Lean)Formalized
#777No statement retained — open to read what the source holdssolvedNo formal declaration
#778No statement retained — open to read what the source holdsopenNo formal declaration
#794Is it true that every 33-uniform hypergraph on 3n3n vertices with at least n3+1n^3+1 edges must contain either a subgraph on 44 vertices with 33 edges or a subgraph on 55 vertices with 77 edges?disproved (Lean)Formalized
#797No statement retained — open to read what the source holdsprovedNo formal declaration
#799No statement retained — open to read what the source holdsprovedNo formal declaration
#800No statement retained — open to read what the source holdsprovedNo formal declaration
#801No statement retained — open to read what the source holdsprovedNo formal declaration
#802No statement retained — open to read what the source holdsopenNo formal declaration
#803No statement retained — open to read what the source holdsdisprovedNo formal declaration
#804No statement retained — open to read what the source holdsdisprovedNo formal declaration
#805No statement retained — open to read what the source holdsopenNo formal declaration
#807No statement retained — open to read what the source holdsdisprovedNo formal declaration

Search problems.science

Find a Problem, Result, source, or page