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

3/6

NumberQuestionOpen
#578No statement retained — open to read what the source holdsprovedNo formal declaration
#579Let δ>0\delta > 0. If nn is sufficiently large and GG is a graph on nn vertices with no K2,2,2K_{2,2,2} (the octahedron) and at least δn2\delta n^2 edges, must GG contain an independent set of size ≫δn\gg_\delta n?openFormalized
#580No statement retained — open to read what the source holdsdecidableNo formal declaration
#581No statement retained — open to read what the source holdssolvedNo formal declaration
#582Does there exist a graph GG which contains no K4K_4, and yet any 22-colouring of the edges produces a monochromatic K3K_3?proved (Lean)Formalized
#583No statement retained — open to read what the source holdsfalsifiableNo formal declaration
#584No statement retained — open to read what the source holdsopenNo formal declaration
#585No statement retained — open to read what the source holdsopenNo formal declaration
#593Erdős Problem 593 (500): Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number >ℵ0> \aleph_0.openFormalized
#594Erdős Problem 594 (Erdős–Hajnal [ErHa66], [Er69b]):provedFormalized
#595Erdős Problem 595 (250): Is there an infinite graph G which contains no K4K_4 and is not the union of countably many triangle-free graphs?openFormalized
#596Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G1,G2)(G_1, G_2) is it true thatopenFormalized
#597No statement retained — open to read what the source holdsopenNo formal declaration
#599Erdős Problem 599 (the Erdős–Menger conjecture).provedFormalized
#600Let r≥2r \geq 2. Is it true that e(n,r+1)−e(n,r)→∞e(n,r+1) - e(n,r) \to \infty as n→∞n \to \infty?openFormalized
#601No statement retained — open to read what the source holdsopenNo formal declaration
#608No statement retained — open to read what the source holdsdisproved (Lean)No formal declaration
#609No statement retained — open to read what the source holdsopenNo formal declaration
#610No statement retained — open to read what the source holdsproved (Lean)No formal declaration
#611No statement retained — open to read what the source holdsopenNo formal declaration
#612No statement retained — open to read what the source holdsopenNo formal declaration
#613Erdős Problem 613: Let n≥3n \geq 3 and GG be a graph with (2n+12)−(n2)−1\binom{2n+1}{2} - \binom{n}{2} - 1 edges. Must GG be the union of a bipartite graph and a graph with maximum degree less than nn?disproved (Lean)Formalized
#614No statement retained — open to read what the source holdsopenNo formal declaration
#615Does there exist some constant c>0c > 0 such that for all sufficiently large nn, if GG is a graph with nn vertices and at least (1/8−c)n2(1/8 - c)n^2 edges then GG must contain either a K4K_4 or an independent set on at least n/log⁡nn/\log n vertices?disprovedFormalized
#616No statement retained — open to read what the source holdsopenNo formal declaration
#617Let r≥3r\geq 3. If the edges of Kr2+1K_{r^2+1} are rr-coloured then there exist r+1r+1 vertices with at least one colour missing on the edges of the induced Kr+1K_{r+1}.falsifiableFormalized
#618For a triangle-free graph GG let h2(G)h_2(G) be the smallest number of edges that need to be added to GG so that it has diameter 22 and is still triangle-free. Is it true that if GG has maximum degree o(n1/2)o(n^{1/2}) then h(G)=o(n2)h(G)=o(n^2)?proved (Lean)Formalized
#619Erdős Problem 619 [EGR98, Er99]: For a triangle-free graph GG let hr(G)h_r(G) be the smallest number of edges that need to be added to GG so that it has diameter rr (while preserving the property of being triangle-free). Is it true that there exists a constant c>0c>0 such that if GG is a connected graph on nn vertices then h4(G)<(1−c)nh_4(G)<(1-c)n?solved (Lean)Formalized
#620No statement retained — open to read what the source holdsopenNo formal declaration
#621Let GG be a graph on nn vertices, α1(G)\alpha_1(G) be the maximum number of edges that contain at most one edge from every triangle, and τ1(G)\tau_1(G) be the minimum number of edges that contain at least one edge from every triangle.proved (Lean)Formalized
#622No statement retained — open to read what the source holdsprovedNo formal declaration
#625No statement retained — open to read what the source holdsopenNo formal declaration
#626No statement retained — open to read what the source holdsopenNo formal declaration
#627No statement retained — open to read what the source holdsopenNo formal declaration
#628Let GG be a graph with chromatic number kk containing no KkK_k. If a,b≥2a,b\geq 2 and a+b=k+1a+b=k+1 then must there exist two disjoint subgraphs of GG with chromatic numbers ≥a\geq a and ≥b\geq b respectively?falsifiableFormalized
#629No statement retained — open to read what the source holdsopenNo formal declaration
#630No statement retained — open to read what the source holdsprovedNo formal declaration
#631No statement retained — open to read what the source holdsprovedNo formal declaration
#632No statement retained — open to read what the source holdsdisprovedNo formal declaration
#636No statement retained — open to read what the source holdsprovedNo formal declaration
#637No statement retained — open to read what the source holdsprovedNo formal declaration
#638No statement retained — open to read what the source holdsopenNo formal declaration
#639Is it true that if the edges of KnK_n are 2-coloured then there are at most n2/4n^2/4 many edges which do not occur in a monochromatic triangle?proved (Lean)Formalized
#640No statement retained — open to read what the source holdsopenNo formal declaration
#641No statement retained — open to read what the source holdsdisprovedNo formal declaration
#642No statement retained — open to read what the source holdsopenNo formal declaration
#643No statement retained — open to read what the source holdsopenNo formal declaration
#666Let QnQ_n be the nn-dimensional hypercube graph (so that QnQ_n has 2n2^n vertices and n2n−1n2^{n-1} edges). Is it true that, for every ϵ>0\epsilon>0, if nn is sufficiently large, every subgraph of QnQ_n with ≥ϵn2n−1\geq \epsilon n2^{n-1} many edges contains a C6C_6?disproved (Lean)Formalized

Search problems.science

Find a Problem, Result, source, or page