The Ramsey number R(4,6)
Narrow the gap 36 ≤ R(4,6) ≤ 40. A 2-colouring of K_36 with no red K_4 and no blue K_6 would raise the lower bound; lowering the upper bound needs reproducible exhaustive computation.
0claims
0verified
Open problems
Each problem states how progress is verified and what counts as a contribution. Besides the problems curated here, the catalogue includes open conjectures from Formal Conjectures (with Lean statements), optimization constants and the AlphaEvolve problems. Know one that belongs here? Propose a problem.
60 shown· page 1 of 2
The Ramsey number R(5,5)
Narrow the gap between the known lower and upper bounds for R(5,5), currently 43 ≤ R(5,5) ≤ 46.
0claims
0verified
Bondy's conjecture on longest cycles in highly connected graphs
Conjecture 1 (Bondy, 1980). Let k ≥ 1 and let G be a k-connected graph on n vertices. If δ(G) ≥ n + k(k-1)/k+1, then for every longest cycle C of G, every path in G - V(C) has at most k-1 vertices.
0claims
0verified
Conway's 99-graph problem
Does there exist an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors?
0claims
0verified
Dean's conjecture on cycles of length divisible by k
Conjecture 1.1 (Dean, 1988). For every integer k ≥ 3, every finite simple graph with minimum degree at least k contains a cycle whose length is divisible by k. A cycle has length at least 3, so the divisor is never 0 and the statement is not satisfied for a trivial reason.
0claims
0verified
Erdős Problem #1029
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then R(k)/k2^k/2→ ∞.
0claims
0verified
Erdős Problem #1030
Let R(k,l) be the usual Ramsey number: the smallest n such that if the edges of K_n are coloured red and blue then there exists either a red K_k or a blue K_l. Prove the existence of some c>0 such that lim_k→ inftyR(k+1,k)/R(k,k)> 1+c. A problem of Erdős and Sós.
0claims
0verified
Erdős Problem #1035
Is there a constant c > 0 such that every graph on 2^n vertices with minimum degree > (1-c) · 2^n contains the n-dimensional hypercube Q_n? This is Erdős's question [Er93, p. 345]. See also [576] for the extremal number of edges that guarantee a Q_n.
0claims
0verified
Erdős Problem #1068
Does every graph with chromatic number aleph_1 contain a countable subgraph which is infinitely connected?
0claims
0verified
Erdős Problem #108
For 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?
0claims
0verified
Erdős Problem #1175
Let κ be an uncountable cardinal. Must there exist a cardinal λ such that every graph with chromatic number λ contains a triangle-free subgraph with chromatic number κ? Shelah proved that a negative answer is consistent when κ = λ = aleph_1 (see erdos_1175.variants.aleph_one).
0claims
0verified
Erdős Problem #128
Let G be a graph with n vertices such that every induced subgraph on ≥ n/2 vertices has more than n^2/50 edges. Must G contain a triangle?
0claims
0verified
Erdős Problem #159
There exists some constant c>0 such that R(C_4,K_n) ≪ n^2-c. The prize of 100 is offered in [Er78] for a proof or disproof. This problem is #17 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #184
Any graph on n vertices can be decomposed into O(n) many edge-disjoint cycles and edges.
0claims
0verified
Erdős Problem #19
If G is an edge-disjoint union of n copies of K_n, then is χ(G) = n?
0claims
0verified
Erdős Problem #23
Can every triangle-free graph on 5n vertices be made bipartite by deleting at most n^2 edges?
0claims
0verified
Erdős Problem #544
Show that R(3,k+1)-R(3,k)→∞ as k→ ∞. A problem of Erdős and Sós. This problem is #8 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #545
Let m be sufficiently large and let G be a graph with m edges and no isolated vertices. Is the Ramsey number R(G) maximised when G is 'as complete as possible'?
0claims
0verified
Erdős Problem #551
Prove that R(C_k,K_n)=(k-1)(n-1)+1 for k≥ n≥ 3 (except when n=k=3). Asked by Erdős, Faudree, Rousseau, and Schelp. This problem is #18 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #552
Determine the Ramsey number R(C_4, S_n), where S_n=K_1,n is the star on n+1 vertices. A problem of Burr, Erdős, Faudree, Rousseau, and Schelp [BEFRS89]. This problem is #19 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #566
Let G be such that any subgraph on k vertices has at most 2k-3 edges. Is it true that, if H has m edges and no isolated vertices, then R(G,H) ≪ m? In other words: if G is sparse (every induced subgraph on k vertices has ≤ 2k-3 edges), is G Ramsey size linear?
0claims
0verified
Erdős Problem #568
Let G be a graph such that R(G,T_n)≪ n for any tree T_n on n vertices and R(G,K_n)≪ n^2. Is it true that, for any H with m edges and no isolated vertices, R(G,H)≪ m? In other words, is G Ramsey size linear? This problem is #33 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #569
Let k≥ 1. What is the best possible c_k such that R(C_2k+1,H)≤ c_k m for any graph H on m edges without isolated vertices? This problem is #34 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #572
Show that for k≥ 3 ex(n;C_2k)≫ n^1+1/k. This problem is #46 in Extremal Graph Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #579
Let δ > 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 δ n^2 edges, must G contain an independent set of size ≫_δ n? This is a problem of Erdős, Hajnal, Sós, and Szemerédi [EHSS83].
0claims
0verified
Erdős Problem #583
Every connected graph on n vertices can be partitioned into at most ⌈ n/2⌉ edge-disjoint paths. A problem of Erdős and Gallai.
0claims
0verified
Erdős Problem #595
Erdős Problem 595 (\250): Is there an infinite graph G which contains no K_4 and is not the union of countably many triangle-free graphs? A problem of Erdős and Hajnal [Er87].
0claims
0verified
Erdős Problem #596
Erdős Problem 596 (Erdős–Hajnal, [Er87]). For which graph pairs (G_1, G_2) is it true that (1) for every n ≥ 1 there is a graph H without a G_1 such that any n-colouring of H's edges contains a monochromatic G_2, and yet (2) for every graph H without a G_1 there is an aleph_0-colouring of H's edges…
0claims
0verified
Erdős Problem #60
Does every graph on n vertices with >ex(n;C_4) edges contain ≫ n^1/2 many copies of C_4?
0claims
0verified
Erdős Problem #61
The Erdős–Hajnal Conjecture states that there is a constant c(H) > 0 for each H such that we can take f(n) = n^c(H) in the above formulation.
0claims
0verified
Erdős Problem #628
Let G be a graph with chromatic number k containing no K_k. If a,b≥ 2 and a+b=k+1 then must there exist two disjoint subgraphs of G with chromatic numbers ≥ a and ≥ b respectively?
0claims
0verified
Erdős Problem #64
Does every finite graph with minimum degree at least 3 contain a cycle of length 2^k for some k ≥ 2?
0claims
0verified
Erdős Problem #65
Is the sum Σ1/a_i minimised when G is a complete bipartite graph? This problem is #65 in Extremal Graph Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #713
Is it true that, for every bipartite graph G, there exists some α∈ [1,2) and c>0 such that ex(n;G)∼ cn^α? The condition that G have at least two edges excludes degenerate forbidden graphs whose extremal number is eventually zero, for which the displayed asymptotic with c>0 is impossible.
0claims
0verified
Erdős Problem #714
Is it true that ex(n; K_r,r) ≫ n^2-1/r?
0claims
0verified
Erdős Problem #740
Let m be an infinite cardinal and G be a graph with chromatic number m. Let r≥ 1. Must G contain a subgraph of chromatic number m which does not contain any odd cycle of length ≤ r?
0claims
0verified
Erdős Problem #742
Murty-Simon Conjecture Let G be a graph on n vertices with diameter 2 such that deleting any edge increases the diameter. Is it true that G has at most ⌊ n^2 / 4 ⌋ edges? Equality is conjectured to hold for the complete balanced bipartite graph K_⌈ n/2 ⌉, ⌊ n/2 ⌋.
0claims
0verified
Erdős Problem #75
Is 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 - ε)?
0claims
0verified
Erdős Problem #77
If R(k) is the Ramsey number for K_k, the minimal n such that every 2-colouring of the edges of K_n contains a monochromatic copy of K_k, then find the value of lim_k→ inftyR(k)^1/k. This problem is #3 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #78
Let R(k) be the Ramsey number for K_k. Give a constructive proof that R(k) > C^k for some constant C > 1. Equivalently, give an explicit construction of graphs on n vertices which contain no clique and no independent set of size ≥ c log n, for some constant c > 0.
0claims
0verified
Erdős Problem #86
Let Q_n be the n-dimensional hypercube graph (so that Q_n has 2^n vertices and n2^n-1 edges). Is it true that every subgraph of Q_n with ≥ (1/2+o(1))n2^n-1 many edges contains a C_4?
0claims
0verified
Erdős Problem #87
Let 0 < ε < 1. Is it true that, if k is sufficiently large, then R(G) > (1-ε)^k R(k) for every graph G with chromatic number χ(G)=k? The restriction ε < 1 excludes negative bases in (1-ε)^k. This problem is #12 in Ramsey Theory in the graphs problem collection.
0claims
0verified
Erdős Problem #883
For A⊆ 1,…,n let G(A) be the graph with vertex set A, where two integers are joined by an edge if they are coprime. Is it true that if |A| > ⌊ n/2 ⌋ + ⌊ n/3 ⌋ - ⌊ n/6 ⌋ then G(A) contains all odd cycles of length ≤ n/3 + 1? A problem of Erdős and Sárközy [ErSa97].
0claims
0verified
Erdős Problem #918
Erdős Problem #918
0claims
0verified
Kotzig's Conjecture
For any tree T with n edges, the complete graph K_2n+1 decomposes into 2n+1 edge-disjoint copies of T via cyclic shifts of a single embedding.
0claims
0verified
Latin Tableau Conjecture
The Latin Tableau Conjecture: If G is the simple graph of a Young diagram, then G is CDS-colorable.
0claims
0verified
Pebbling number conjecture
The pebbling number conjecture: the pebbling number of a Cartesian product of connected graphs is at most equal to the product of the pebbling numbers of the factors. See Asplund, Hurlbert, and Kenter.
0claims
0verified
Reed's omega, delta, and chi conjecture
For a graph G, we define Δ(G) to be the maximum degree, ω(G) to be the size of the largest clique subgraph, and χ(G) to be the chromatic number. Reed's omega, delta, and chi conjecture states that χ(G) ≤ ⌈ 1/2(ω(G) + Δ(G) + 1) ⌉.
0claims
0verified
Ringel's Conjecture
For any tree T with n edges, the complete graph K_2n+1 decomposes into 2n+1 edge-disjoint copies of T. A "copy" of T is the image T.map(f_i) of T under a vertex embedding f_i : V hookrightarrow Fin(2n+1); the copies are pairwise edge-disjoint and together cover every edge of K_2n+1.
0claims
0verified
Sidorenko's conjecture (1993)
Sidorenko's conjecture (1993). For every finite bipartite simple graph H and every finite simple graph G: t(H, G) ≥ t(K_2, G)^e(H), where K_2 denotes the single-edge graph on 2 vertices (i.e. completeGraph (Fin 2)).
0claims
0verified
Browse by field
CombinatoricsNumber theoryGraph theoryAlgebraGeometryAnalysisProbabilityLogic & formalisationAlgorithmsComplexityComputabilityOptimisationCryptography theoryMachine learningPhysicsTheoretical physicsAstrophysics & cosmologyQuantum informationChemistryMaterialsBiologyNeuroscienceEcologyClimateEarth scienceEconomics