Ramsey Theory

../

E0054/: Asks to improve the Burr–Erdős bounds on how sparse a Ramsey 2-complete sequence can be; Conlon, Fox and Pham determined the order as the square of the logarithm, closing the gap to a constant factor.

E0055/: Bounds the growth of the sparsest sets of integers for which every large integer is a monochromatic sum under any coloring with more than two colors.

E0076/: Asks whether every two-coloring of the edges of the complete graph on n vertices yields about n squared over twelve edge-disjoint monochromatic triangles; yes, by a 2020 theorem of Gruslys and Letzter the site accepted.

E0077/: Asks for the limit of the k-th root of the Ramsey number of the complete graph on k vertices as k grows, a limit not known to exist.

E0078/: Asks for a constructive proof that the Ramsey number of the complete graph on k vertices grows at least exponentially in k, equivalently for an explicit graph with logarithmic clique and independence numbers.

E0079/: Asks whether there are infinitely many graphs that are not Ramsey size linear even though all of their proper subgraphs are; proved by Wigderson in 2024 non-constructively, with no explicit example beyond K_4 known.

E0080/: Estimates the largest book, an edge lying in many triangles, forced in a graph on n vertices with quadratically many edges each in a triangle; open, the polynomial question answered no and the logarithmic one open.

E0085/: Asks whether the least minimum degree forcing a four-cycle on n vertices is nondecreasing for all large n; open, with the equivalent star Ramsey numbers R(C_4, K_{1,n}) known exactly only for small n and near prime-power squares.

E0087/: Asks whether every graph with chromatic number k has Ramsey number at least a constant fraction, or at least an exponentially small fraction, of the Ramsey number of the complete graph on k vertices; Erdős's original conjecture, at least that Ramsey number itself, fails at k = 4.

E0088/: Asks whether a graph on n vertices with no clique or independent set of logarithmic size has induced subgraphs of every edge count up to order n squared.

E0112/: Determines the fewest vertices forcing every directed graph to contain an independent set of size n or a transitive tournament of size m; open, known exactly when n = 1, m <= 2, n = 2 and m <= 6, or m = 3 and n <= 5.

E0129/: Asks for a bound of the form C^(sqrt n) on the least N forcing, in any r-coloring of K_N, n vertices missing some color's triangle; a random coloring refutes the site's wording, and no source gives another intended form.

E0159/: Asks whether the Ramsey number for a four-cycle versus a complete graph on n vertices is at most order n to the power two minus a fixed positive constant.

E0163/: Asks whether graphs in which every subgraph has a vertex of degree at most a fixed bound have Ramsey number linear in the number of vertices; proved by Lee (2015 preprint, Ann. of Math. 2017), with the constant still open.

E0165/: Asks for an asymptotic formula for the Ramsey number of a triangle versus a complete graph on k vertices; the order k^2/log k is known and the constant lies between 1/2 and 1.

E0166/: Asks whether the Ramsey number of a complete graph on four vertices versus one on k vertices is at least k cubed divided by a power of the logarithm of k; proved by Mattheus and Verstraete with the fourth power.

E0172/: Asks whether every finite coloring of the positive integers admits arbitrarily large finite sets whose sums and products of distinct members share one color.

E0181/: Asks whether the Ramsey number of the n-dimensional hypercube graph is at most a constant times its number of vertices; open on the site, with the linear bound claimed in full by a 2026 OpenAI release preprint.

E0183/: Determines the limit of the k-th root of the least order forcing a monochromatic triangle in every k-coloring of a complete graph.

E0187/: The best length, in the common difference d, of a monochromatic progression of difference d forced for infinitely many d in every two-coloring of the integers; at most (1 + o(1)) log_2 d by Beck 1980, with no usable lower bound known.

E0191/: Asks whether every two-coloring of the pairs from 2 up to n yields a monochromatic complete set whose reciprocal-logarithm sum is arbitrarily large; proved by Rödl, with the order determined by Conlon, Fox and Sudakov.

E0439/: Asks whether every finite coloring of the integers has two distinct integers of one color summing to a square, or to a k-th power; proved by Khalfalah and Szemerédi for every non-constant polynomial with an even value.

E0483/: Estimates the least N forcing a monochromatic solution of a plus b equals c in every k-coloring of one through N, and asks whether it is exponential in k; open between c times 3.28 to the k and (e minus 1/6) times k factorial.

E0484/: Asks whether every k-coloring of the first N integers leaves a positive proportion of them expressible as a sum of two distinct integers of one color.

E0518/: Asks whether every two-coloring of the complete graph on n vertices admits root n monochromatic paths of one color covering all vertices; proved for n above 20 to the 40th, the remaining n claimed in an unrefereed 2026 preprint.

E0531/: Estimates the least N such that every two-coloring of the integers up to N contains a set of k numbers all of whose non-empty subset sums have the same color.

E0532/: Asks whether every two-coloring of the natural numbers admits an infinite set all of whose finite non-empty subset sums share one color; yes, by Hindman's theorem, held in his 1974 paper and Baumgartner's 1974 note.

E0544/: Asks whether the gap between consecutive Ramsey numbers of a triangle against a complete graph tends to infinity, and whether it is smaller than order k; open, with the gap known only to lie between 3 and k+1.

E0545/: Asks whether, for all large m, the graph with m edges that is as complete as possible has the largest Ramsey number among graphs with m edges and no isolated vertices; open, while the site's wording, for every m, fails at two edges.

E0546/: Asks whether the Ramsey number of any graph with m edges and no isolated vertices is at most exponential in the square root of m.

E0547/: Asks whether every tree on n at least 2 vertices has Ramsey number at most 2n minus 2; proved, since 2026 on a third party's Lean proof built here, while the site's wording fails for the one-vertex tree.

E0549/: Asks whether a tree that is bipartite with k vertices in one class and two k in the other has Ramsey number exactly four k minus one.

E0550/: Asks for a proof bounding the Ramsey number of a large tree against a complete multipartite graph by a formula in its chromatic number and smallest class size.

E0551/: Asks for a proof that the Ramsey number of a k-cycle against a complete graph on n vertices is k minus one times n minus one plus one, when k is at least n.

E0552/: Determines the Ramsey number of a four-cycle against the star with n edges.

E0553/: Asks for a proof that the three-color Ramsey number for two triangles and a complete graph on n vertices grows much faster than the two-color version.

E0554/: Asks for a proof that the k-color Ramsey number of an odd cycle on two n plus one vertices is negligible against that of the triangle, for n at least two.

E0555/: Determines the k-color Ramsey number of the even cycle on two n vertices.

E0556/: Asks whether every 3-coloring of the edges of the complete graph on 4n - 3 vertices has a monochromatic cycle of length n, for every n > 3; the site's wording also includes the triangle, where it fails, and the bound is known for all large n.

E0557/: Asks whether the k-color Ramsey number of any tree on n vertices is at most k times n plus a bounded amount.

E0558/: Determines the k-color Ramsey number of the complete bipartite graph with s vertices in one class and t in the other.

E0559/: Asks whether every graph on n vertices with bounded maximum degree has size Ramsey number linear in n; false already for maximum degree three.

E0560/: Asks for the size Ramsey number of the balanced complete bipartite graph with n vertices on each side; known between orders n squared times two to the n and n cubed times two to the n.

E0561/: Asks to prove the 1978 formula for the size Ramsey number of two star forests as a sum over diagonals of the largest star-size sums minus one; proved in special cases only.

E0562/: Estimates the Ramsey number for r-uniform hypergraphs, the fewest vertices forcing a monochromatic complete r-uniform subhypergraph on n vertices.

E0563/: Determines the least size m such that some two-coloring of the complete graph on n vertices leaves every vertex set of size at least m rich in both colors.

E0564/: Estimates the Ramsey number for three-uniform hypergraphs, the fewest vertices forcing a monochromatic complete three-uniform subhypergraph on n vertices.

E0565/: Bounds the induced Ramsey number, the fewest vertices of a host graph in which every two-coloring of the edges gives an induced monochromatic copy of a graph.

E0566/: Asks whether a graph whose subgraphs on k at least 2 vertices have at most 2k-3 edges is Ramsey size linear; corrected from the site's wording, which no graph meets since one vertex exceeds the bound; open.

E0567/: Asks whether the three-cube, the complete bipartite graph with three vertices per side, or the complete graph on four vertices with one edge subdivided is Ramsey size linear; open, with partial results.

E0568/: Asks whether a graph with linear Ramsey numbers against trees and quadratic against complete graphs has Ramsey number linear in the edge count of every graph without isolated vertices.

E0569/: Asks for the least constant c such that the Ramsey number of an odd cycle of length two k plus one against any m-edge graph without isolated vertices is at most c times m.

E0570/: Asks whether, for each k at least three and sufficiently large m, the Ramsey number of a k-cycle against any m-edge graph without isolated vertices is at most two m plus the floor of half of (k minus one).

E0582/: Asks whether there is a graph with no complete subgraph on four vertices in which every two-coloring of the edges produces a monochromatic triangle.

E0609/: Estimates the least m such that n-coloring a complete graph on two to the n plus one vertices forces a monochromatic odd cycle of length at most m.

E0613/: Asks whether every graph with one edge fewer than a conjectured size Ramsey number splits into a bipartite graph and a graph of maximum degree below n; disproved for every n at least five by Pikhurko's constructions.

E0615/: Asks whether a fixed saving below an eighth of n squared edges forces a graph on n vertices to contain a four-vertex clique or an independent set of n over log n vertices; disproved by Fox, Loh and Zhao.

E0636/: Asks whether a graph on n vertices with no large clique or independent set has many induced subgraphs that pairwise differ in vertex count or edge count.

E0637/: Asks whether a graph on n vertices with no large clique or independent set has an induced subgraph on many vertices realizing many distinct degrees.

E0638/: Asks whether a hereditary family of finite graphs forcing monochromatic triangles under every finite number of colors holds the finite subgraphs of a graph forcing them under any infinite cardinal; a disproof is claimed.

E0639/: Asks whether any two-coloring of the edges of K_n leaves at most n²/4 edges on no monochromatic triangle for large n, as Erdős stated it; proved by Keevash and Sudakov's exact theorem, while the site's wording fails for n from 3 to 6.

E0645/: Asks whether every two-coloring of the positive integers has a monochromatic three-term progression whose difference exceeds its first term; proved by Brown and Landman in 1999, with an elementary argument recorded by the site.

E0667/: Asks whether the exponent governing the largest clique forced when every p vertices span at least q edges is strictly increasing in q; open, with the 1997 source's endpoint bounds and a disputed upper bound at the top.

E0720/: Asks whether the size Ramsey number of the path grows faster than linearly but slower than quadratically, and whether that of the cycle is subquadratic; both are linear, so the first answer is no and the others yes.

E0721/: Bounds the least n such that every red-blue coloring of 1 up to n has a red three-term progression or a blue k-term one; Green, Hunter and Schoen meet the two explicit challenges while the order of magnitude stays open.

E0800/: Asks whether every graph on n vertices with no two adjacent vertices both of degree at least three has Ramsey number at most a constant times n.

E0801/: Asks whether a graph on n vertices with no independent set larger than the square root of n has a set of that many vertices spanning many more edges.

E0809/: Asks whether the fewest colors making every odd cycle of length 2k+1 rainbow on some n-vertex graph one edge past the Turán number is asymptotically n squared over eight for all k at least 3; proved by two Lean developments built and audited here, Asad Shahab's, filed first, and the project's claim L17.

E0810/: Asks whether some graph on n vertices with a positive fraction of all possible edges can be edge-colored with n colors so that every four-cycle gets four distinct colors.

E0811/: Asks which graphs are forced as rainbow copies in every balanced coloring of a large complete graph with as many colors as the graph has edges, where each vertex sees equally many edges of every color.

E0812/: Asks whether consecutive diagonal Ramsey numbers grow by at least a constant factor, and whether their difference is at least a constant times n squared.

E0894/: Asks whether the integers can be finitely colored with no two of one color differing by a term of a given lacunary sequence; proved, with Peres and Schlag's bound of order (1/epsilon) log(1/epsilon) colors as the best known.

E0911/: Asks whether the size Ramsey number of every graph with n vertices and at least Cn edges exceeds the edge count by a factor growing faster than linearly in C; open, with no result found beyond Erdős's 1982 statement.

E0924/: Asks whether, for k at least 2 and l at least 3, some graph with no clique on l plus 1 vertices forces a monochromatic l-clique in every k-edge-coloring; true, by Folkman for two colors and by Nešetřil and Rödl for every k.

E0925/: Asks whether every n-vertex graph whose edges can be 2-colored with no monochromatic triangle has an independent set above the cube root of n by a power; disproved through the Alon–Rödl bound on R(3,3,m).

E0948/: Asks whether some bound and some number of colors force, in every coloring of the integers, a slowly growing sequence whose subset sums miss a color; no, by a 2026 AI-generated coloring accepted by the site after review.

E0949/: Asks whether the complement of any sum-free set of reals contains a set of size continuum whose pairwise sums also avoid it; open; AlphaProof's Lean proof of the Sidon case is a pending claim and a thread comment argues the Baire case.

E0965/: Asks whether every two-coloring of the reals admits a set of size aleph one whose sums of two distinct elements share one color; false in ZFC by Komjáth and by Soukup and Weiss, after a CH proof by Hindman, Leader and Strauss.

E0966/: Asks whether, for k and r at least two, some set with no arithmetic progression of length k plus one has a monochromatic k-term one in every r-coloring; true, by Spencer's 1975 restricted van der Waerden theorem.

E0986/: Asks whether, for fixed s at least three, the Ramsey number of s against k is at least k to the s minus one over a power of log k.

E1014/: Asks whether, for each fixed k, the ratio of consecutive off-diagonal Ramsey numbers R(k,l+1)/R(k,l) tends to one; answered yes by a 2026 manuscript hosted by OpenAI, attributed to an internal model and accepted by the site.

E1015/: The most vertices a two-colored complete graph can force to be left over when it is covered by disjoint monochromatic copies of K_t; Burr, Erdős and Spencer determine it for fixed t and large n in terms of R(t,t−1), so it grows exponentially.

E1029/: Asks whether the Ramsey number for a complete graph on k vertices, divided by k times two to the k over two, tends to infinity.

E1030/: Asks whether the off-diagonal Ramsey number R(k+1,k) exceeds the diagonal number R(k,k) by a constant factor in the limit.

E1105/: Asks for the anti-Ramsey numbers of cycles and paths, the most colors on the edges of the complete graph on n vertices without a rainbow copy: an asymptotic formula for cycles and an exact formula for paths.

E1182/: Estimates the largest edge counts for connected graphs on n vertices whose Ramsey number against a triangle equals two n minus one; a 1996 preprint claims a linear threshold for all such graphs, a no to the closing question.

E1183/: Estimates how large a monochromatic family closed under unions and intersections must exist in every two-coloring of the subsets of the first n integers; open, with nothing beyond the trivial chain bound proved.

E1198/: Asks whether every two-coloring of the natural numbers admits an infinite set all of whose sums of products of distinct members share one color; no, by a 1995 theorem of Smith, as the site's thread deduced in 2026.

E1199/: Asks whether every two-coloring of the natural numbers admits an infinite set whose pairwise sums, doubles included, share one color (Owings's question); open on the site, false for three colors, claimed for two.

E1211/: Asks how large the larger upper logarithmic density of the two subset-sum sets must be when the natural numbers are split into two classes; Conlon, Fox and Pham determined the minimum as (2 + sqrt 3)/4.

E1216/: Estimates the largest transitive subtournament every tournament on n vertices must contain; floor(log_2 n) + 1 first fails at n = 14 and fails for infinitely many n; f is known exactly for n <= 33 and 47 <= n <= 56.

---

Ramsey numbers for graphs and hypergraphs, off-diagonal and induced variants, and monochromatic structures forced by colorings of the integers of Schur and Rado type; Euclidean Ramsey problems and colorings of the plane are filed with discrete geometry.

Site tags routed here: additive combinatorics, arithmetic progressions, combinatorics, graph theory, hypergraphs, number theory, ramsey, ramsey theory.