Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Ramsey Theory

ageron_2021_new_lower_bounds_schur_weak_schur/: Gives improved lower bounds for Schur and weak Schur numbers by generalizing Rowley's template constructions.

ajtai_1980_note_ramsey_numbers/: Ajtai, Komlós and Szemerédi's 1980 note proving that a triangle-free graph on n vertices with average degree t has an independent set of at least 0.01 (n/t) ln t vertices, hence R(3,x) < 100 x^2/ln x, and by induction R(k,x) ≤ 5000^k x^(k-1)/(ln x)^(k-2) for every fixed k and large x; with the extension to graphs with few triangles and Erdős's question for K_4-free graphs.

alon_1994_subdivided_graphs_have_linear_ramsey_numbers/: Proves the absolute bound r(G) at most 12 times the vertex count when no two vertices of degree at least three are adjacent.

alon_1999_norm_graphs_variations_applications/: Varies the norm-graphs to get dense K_{3,3}-free graphs, the asymptotic k-color Ramsey number of K_{3,3}, and the order k^t of the k-color Ramsey number of K_{t,s} whenever s is at least (t-1)! + 1.

alon_2005_sharp_bounds_some_multicolor_ramsey_numbers/: Determines several multicolor Ramsey numbers up to polylogarithmic factors, proving r(K3,K3,Km) is m^3 polylog m and settling an Erdos-Sos conjecture.

alweiss_2023_monochromatic_sums_products_over/: Proves that for every n the subset sums and subset products of n rationals can be forced monochromatic in any finite coloring of the rationals.

aragao_2025_exponential_upper_bound_induced_ramsey_numbers/: Proves the induced Ramsey number of any k-vertex graph is at most 2^{Ck}, settling a 1975 conjecture of Erdos.

axenovich_2024_rainbow_subgraphs_edge_colored_complete_graphs/: Answers two Erdos-Tuza questions negatively by building completely balanced colorings of complete graphs with no rainbow clique.

axenovich_2025_improved_upper_bound_multicolour_ramsey_number/: Proves that the k-color Ramsey number of the cycle of length 2l+1 is at most (4l-2)^k times k^(k/l) plus one, confirming a conjecture of Fox.

bai_2026_new_tower_type_lower_bounds_hypergraph/: Improves the tower-type lower bound for the hypergraph Ramsey number of k+1 versus k+1 and characterizes the three-color shift number.

balister_2024_upper_bounds_multicolour_ramsey_numbers/: Gives an exponential improvement on the Erdos-Szekeres bound for r-color Ramsey numbers for every fixed number of colors at least two, the first for three or more colors.

balogh_2017_improved_lower_bound_folkman_theorem/: Improves the lower bound for the two-color Folkman number to a doubly exponential bound, replacing the earlier Erdos-Spencer bound.

baumgartner_1974_improvement_partition_theorem_erdos_rado/: Baumgartner's 1974 note proving the Erdős–Rado conjecture that the least k with ω_α · k → (m, ω_α · n)^2 does not depend on the initial ordinal ω_α: ω_α · l_0(m,n) → (m, ω_α · n)^2 for every α, so l_α(m,n) = l_0(m,n), the finite threshold of Problem 112, for every infinite initial ordinal.

baumgartner_1974_short_proof_hindman_theorem/: A three-page note proving Hindman's theorem through its finite-unions form; the theorem says that in any finite partition of the nonnegative integers, one cell contains an infinite sequence all of whose finite sums of distinct terms lie in that cell.

beck_1980_remark_concerning_arithmetic_progressions/: Proves that for every epsilon greater than zero one has F(d) at most (1 + epsilon) log base 2 of d for all sufficiently large d.

beck_1990_size_ramsey_number_paths_trees_circuits_ii/: Beck's 1990 sequel on size Ramsey numbers: the tree parameter Δ(T) that determines the size Ramsey number of a tree up to a polylogarithmic factor, an induced size Ramsey bound for trees, the lower bound 9/4 for paths, and the bounded-degree linear question later refuted by Rödl and Szemerédi.

benevides_2009_3_colored_ramsey_number_even_cycles/: Proves that for all sufficiently large even n the three-color Ramsey number of the cycle on n vertices is exactly 2n.

bermond_1974_some_ramsey_numbers_directed_graphs/: Bermond's 1974 paper on Ramsey numbers of directed graphs, colorings of the arcs of the complete symmetric digraph: existence iff at most one of the graphs contains a circuit, the upper bound R(TT_{n_1}, ..., TT_{n_{k-1}}, K_p^) ≤ r(ν(r(n_1, ..., n_{k-1})), p), the exact values R(TT_n, K_2^) = ν(n), R(TT_3, K_3^) = 9 and R(TT_3, TT_3, K_2^) = 14, and the directed-path Ramsey numbers R(P_{n_1}, ..., P_{n_{k-1}}, G) = n_1 ... n_{k-1}(p-1) + 1 for a directed hamiltonian G on p vertices.

bikov_2020_independence_number_ramsey_graphs_folkman_number/: On the independence number of $(3,3)$ -Ramsey graphs and the Folkman number $F_e(3,3;4)$ .

bohman_2010_early_evolution_free_process/: Analyses the H-free random graph process to give new lower bounds for Turan numbers of bipartite graphs and for Ramsey numbers R(s,t) with s fixed.

bohman_2021_dynamic_concentration_triangle_free_process/: Determines the asymptotic size of the graph produced by the triangle-free process and deduces the lower bound R(3,t) > (1/4-o(1))t^2/log t.

bondy_1973_ramsey_numbers_cycles_graphs/: Determines Ramsey numbers pairing a long cycle with cycles and complete graphs, including R(C_n, C_n) = 2n - 1 for odd n.

bowen_2022_monochromatic_products_sums_2_colorings_naturals/: Proves that every two-coloring of the natural numbers contains monochromatic sets x, y, xy, x+y and, for every n, arbitrarily large distinct x_1, ..., x_n whose elements, initial products and total sum share one color.

bowen_2022_monochromatic_products_sums_rationals/: Proves every finite coloring of the rationals yields a monochromatic set of the form x, y, xy, x+y with x and y nonzero.

boza_2024_exact_values_bounds_ramsey_numbers_c4/: Determines eight previously unknown values of the Ramsey number R(C_4, K_{1,n}) for n at most 38 and proves new general inequalities for that function.

bradac_2022_ramsey_size_linear_graphs_related_questions/: Proves size-linearity for subdivisions of K_4 on at least six vertices, a bipartite-target result for K_4*, and a cubic clique bound for connected H with e(H) - v(H) at most four.

bradac_2025_lower_bounds_ramsey_numbers_bounded_degree/: Constructs bounded-degree k-uniform hypergraphs whose 4-color Ramsey numbers are at least a tower function of the degree times the number of vertices.

bradac_2026_off_diagonal_ramsey_numbers/: Proves an off-diagonal Ramsey lower bound matching the Erdos-Szekeres upper bound up to polylogarithmic factors for every fixed clique size.

brandt_1996_expanding_graphs_ramsey_numbers/: Shows that for every nonbipartite graph G the Ramsey number of G against almost every d-regular graph H exceeds a multiple of the order of H that grows without bound in d, refuting several goodness conjectures of Burr and of Burr and Erdős. Bounds the largest edge count below which every connected graph on n vertices is triangle-good by 84 n.

brown_1999_monochromatic_arithmetic_progressions_large_differences/: Studies van der Waerden numbers where the common difference must be at least a function of the first term, bounding the three-term two-color case.

bucic_2026_maximal_anti_ramsey_conjecture_burr_erdos/: Proves the Burr-Erdős-Graham-Sós maximal anti-Ramsey conjecture for odd cycles of length at least nine and finds the asymptotics for all edge counts.

bukh_2007_induced_subgraphs_ramsey_graphs_many_distinct/: Proves every n-vertex graph G with hom(G) at most C log n has a linear-size induced subgraph with order square-root-n distinct degrees.

burr_1975_magnitude_generalized_ramsey_numbers_graphs/: The 1975 Burr–Erdős paper that conjectures linear Ramsey numbers for graphs of bounded arboricity, edge density or degeneracy, and poses the cubes as a test case with a prize offer; the origin of Erdős problems 163 and 181.

burr_1975_ramsey_theorems_multiple_copies_graphs/: Gives sharp linear upper and lower bounds for the Ramsey number of m and n disjoint copies of two fixed graphs, shows r(nK3) equals 5n, and solves Moon's decomposition problem for fixed clique size and large n.

burr_1976_extremal_ramsey_theory_graphs/: Introduces the extremal Ramsey functions exr and Exr over classes of graphs and evaluates several of them exactly for connected graphs and chromatic classes.

burr_1978_ramsey_minimal_graphs_multiple_copies/: Determines the size Ramsey number of multiple copies of stars together with all extremal graphs, and bounds the copies of G that arrow-graphs must contain.

burr_1980_extremal_problem_generalized_ramsey_theory/: Studies how many edges force a connected graph to be m-good, computing the extremal functions for small orders and giving asymptotic bounds.

burr_1985_ramsey_type_property_additive_number_theory/: Bounds how fast a sequence of integers can grow and still be Ramsey-complete: one exists with fewer than 2 lg^2 x terms in each window (x/2, x], for some ε > 0 none has fewer than ε lg x, and a substantial gap remains.

burr_1989_complete_bipartite_graph_tree_ramsey_numbers/: Reduces the Ramsey number of a four-cycle against any tree to the star case, and bounds the K(3,3) versus tree Ramsey number above, best possible except for the constant.

burr_1989_difference_between_consecutive_ramsey_numbers/: Proves that consecutive classical Ramsey numbers differ by at least 2m-3, together with a superadditive-type inequality and applications.

burr_1989_maximal_anti_ramsey_graphs_strong_chromatic/: Introduces and estimates the anti-Ramsey function counting colors needed so every copy of a fixed graph is totally multicolored.

cambie_2026_general_bound_r_c_k_h/: Proves R(C_k, H) at most (k-1)m+1 for every k at least three and every m-edge no-isolate graph H, determining the universal linear coefficient.

cambie_2026_ramsey_number_cycle_versus_graph_given/: Proves that the Ramsey number of a cycle against any graph with m edges and no isolated vertices is at most 2m plus a constant depending only on the cycle length, once m is large.

campos_2023_exponential_improvement_diagonal_ramsey/: Proves the diagonal Ramsey number is at most four minus a constant, raised to the kth power, the first exponential gain since 1935.

campos_2025_new_lower_bound_ramsey_numbers/: Improves the lower bound for the off-diagonal Ramsey numbers R(3,k) from a quarter to a third of k squared over log k.

caro_2000_asymptotic_bounds_some_bipartite_graph_complete_graph_ramsey_numbers/: Caro, Li, Rousseau and Zhang's 2000 upper bounds for bipartite-versus-complete Ramsey numbers: r(K_{2,m}, K_n) at most (m - 1 + o(1))(n / log n)^2 and r(C_{2m}, K_n) at most c (n / log n)^{m/(m-1)} for fixed m, from a Turán number to independence number transfer; the case m = 2 prints a proof of the bound r(C_4, K_n) at most c (n / log n)^2, which the paper says Szemerédi noted around 1980 and whose proof was never published. Also r(K_{2,n}, K_n) of order n^3 / log^2 n and r(C_5, K_n) at most 2 (3n)^{3/2} / (log n)^{1/2}.

chen_2026_monochromatic_path_covers_conjecture_erdos_gyarfas/: An unrefereed 2026 arXiv preprint claiming the Erdős–Gyárfás monochromatic path cover conjecture for every n, by a minimal counterexample argument ruling out the small cases left by Pokrovskiy, Versteegen and Williams; submitted to the site as a proof claim, not adopted, not checked here.

chung_graham_1975_multicolor_ramsey_numbers_complete_bipartite/: Chung and Graham's 1975 bounds on the k-color Ramsey number of the complete bipartite graph K_{s,t} with s ≤ t: the upper bounds (t-1)(k+k^{1/s})^s (Theorem 1), (t-1)k^2+k+2 for K_{2,t} (Theorem 2) and k^2+k+1 for the four-cycle (Corollary 1); the lower bounds k^2-k+1 for the four-cycle when k-1 is a prime power (Theorem 3) and the counting bound of Theorem 4; the bound ck^3/log^3 k for K_{3,3} from Turán numbers; and the conjecture r(K_{s,t};k) ~ (t-1)k^s.

clemen_2023_balanced_edge_colorings_avoiding_rainbow_cliques_size_four/: Constructs, for every k, a balanced edge-coloring with six colors of the complete graph on 13 to the k vertices that has no rainbow K_4, answering the Erdős-Tuza question negatively for K_4.

cohen_2015_two_source_dispersers_polylogarithmic_entropy/: Gives an explicit construction of bipartite Ramsey graphs on n vertices with no complete or empty k by k bipartite subgraph for k = 2^{(log log n)^{O(1)}}, via two-source dispersers for polylogarithmic entropy.

conlon_2008_hypergraph_ramsey_numbers/: New upper and lower bounds for off-diagonal and multicolor hypergraph Ramsey numbers, with a section on discrepancy that restates Erdős's density threshold F^{(k)}(N, alpha) and its logarithmic two-sided bound for graphs.

conlon_2012_two_problems_graph_ramsey_theory/: Proves r(H) at most 2^(c d log d) n for n-vertex graphs of maximum degree d, and the induced Ramsey bound 2^(c n log n) for n-vertex graphs.

conlon_2013_two_extensions_ramsey_s_theorem/: Shows every 2-coloring on {2,...,n} has a monochromatic clique of weight at least c log log log n, and bounds Ramsey numbers for prescribed order types.

conlon_2022_size_ramsey_number_cubic_graphs/: Shows the size-Ramsey number of every cubic graph on n vertices is O(n^{8/5}), improving the previous n^{5/3+o(1)} bound.

conlon_2022_upper_logarithmic_density_monochromatic_subset_sums/: Determines the optimal constant for two-colorings: some color class has subset sums of upper logarithmic density at least (2+sqrt 3)/4.

conlon_2023_three_early_problems_size_ramsey_numbers/: Determines the size Ramsey numbers of book graphs and starburst graphs up to constant factors and improves the lower bound for complete bipartite graphs.

davies_2017_multicolour_ramsey_numbers_paths_even_cycles/: Proves new upper bounds on multicolor Ramsey numbers of paths and even cycles, improving the linear coefficient by an absolute constant.

davoodi_2025_conjecture_erdos_size_ramsey_number_star/: Confirms the Burr-Erdos-Faudree-Rousseau-Schelp formula for the size Ramsey number of star forests in several new cases.

davoodi_2026_asymptotic_version_erdos_sos_conjecture_beyond/: Proves an asymptotic form of a tree-embedding conjecture of Klimosova, Piguet and Rozhon for dense host graphs.

day_2017_multicolour_ramsey_numbers_odd_cycles/: Constructs colorings of complete graphs whose shortest monochromatic odd cycle is arbitrarily long, disproving the Bondy-Erdos conjecture.

draganic_2022_size_ramsey_numbers_graphs_maximum_degree/: Improves the upper bound on the size-Ramsey number of cubic graphs on n vertices to n to the power three halves plus little o of one.

dubo_2024_ramsey_number_double_star/: Gives a short elementary upper bound for the two-color Ramsey number of the double star, covering the range left open by earlier work.

eliahou_2020_adaptive_upper_bound_ramsey_numbers_r_3_3/: Makes explicit how any improvement of the bound R_4(3) at most 62 lifts to an upper bound n!(e - q) + 1 on the multicolor Ramsey numbers R_n(3), reproving in English the 2002 bound n!(e - 1/6) + 1 and, through S(n) at most R_n(3) - 2, the factorial upper bound on Schur numbers.

erdos_1964_representation_directed_graphs_as_unions_orderings/: Shows the number of voters needed to realize every preference pattern on n candidates by majority is of order n over log n.

erdos_1965_partition_relations_cardinal_numbers/: Settles the infinite Ramsey partition relations for cardinals almost completely under the generalized continuum hypothesis.

erdos_1967_partition_relations_transitivity_domains_binary_relations/: Proves ordinal partition relations for products of omega-alpha and derives transitivity domains of binary relations on infinite cardinals.

erdos_1975_anti_ramsey_theorems/: Founds anti-Ramsey theory, tying the maximum rainbow-free edge coloring count of the complete graph to Turan extremal numbers.

erdos_1975_partition_theorems_finite_graphs/: Bounds the k-color Ramsey numbers of trees, forests and cycles as the number of colors grows: polynomial in k for even cycles, between exponential and factorial for odd cycles, and asks whether a fixed odd cycle is negligible against the triangle.

erdos_1975_problems_results_finite_infinite_graphs/: Erdős's short 1975 survey of striking, not widely known problems on finite and infinite graphs, including the conjecture that graphs with no large clique still force monochromatic cliques.

erdos_1975_strong_embeddings_graphs_into_colored_graphs/: Establishes induced Ramsey theorems: finite graphs can be strongly embedded in a host graph, while the infinite bipartite analog fails.

erdos_1976_problems_results_combinatorial_number_theory_ii/: Problem survey from Erdős's 1974 Bombay lecture stating Cohen's question on monochromatic progressions of difference d and length F(d) under a two-class split of the integers, with Erdős's bound F(d) < cd and the announced Petruska–Szemerédi improvement, and the question whether a two-class split always has an infinite sequence with all multilinear expressions in one class, beside progression-free sets, covering systems, Sidon and primitive sequences.

erdos_1978_cycle_complete_graph_ramsey_numbers/: Improves the upper bound for the cycle-complete Ramsey number r(C_m, K_n) and evaluates the short-cycle version exactly when m exceeds n.

erdos_1978_size_ramsey_number/: Introduces the size Ramsey number, minimizing edges rather than vertices, and determines it for complete graphs and stars.

erdos_1979_some_old_new_problems_various_branches_combinatorics/: Erdős's 1979 Boca Raton problem paper: a progress report on his favorite problems in hypergraph coloring, random graphs, extremal graph theory, intersecting families and Ramsey theory, with new problems on block designs, dense induced subgraphs and least common multiples; the origin of Problem 801.

erdos_1980_noen_mindre_kjente_problemer_i_kombinatorisk/: A survey of some lesser known problems in combinatorial number theory, mostly stated with partial bounds and cash prizes, with a few short proofs.

erdos_1981_new_problems_results_graph_theory_other/: Survey collecting Erdős problems and results on Ramsey numbers, generalized and size Ramsey numbers, sequences, divisors and geometric graphs.

erdos_1982_ramsey_numbers_brooms/: Determines the Ramsey number of a broom exactly when the handle is long, and shows brooms attain the smallest possible tree Ramsey number.

erdos_1983_more_results_ramsey_turan_type_problems/: Determines the Ramsey-Turan density for even cliques and proves an Erdos-Stone type theorem bounding it by graph arboricity.

erdos_1984_some_problems_graph_theory_combinatorial_analysis/: Erdős's Cambridge 1983 problem paper in three parts, graph theory, set systems and combinatorial number theory; its item 13 of recent problems asks on p. 10 whether every graph with e edges has Ramsey number below 2^{c e^{1/2}} and adds on p. 11 that the Ramsey number is probably largest when the graph is as complete as possible.

erdos_1985_multipartite_graph_sparse_graph_ramsey_numbers/: Determines the Ramsey number of a complete multipartite graph against a large connected graph of bounded degree and few extra edges as (m-1)(n-1)+s, proves the asymptotic r(F,T)/n -> chi(F)-1 for every fixed F and large trees T, and gives r(K(2,2),T) <= n + ceil(sqrt n); the site's source for Problem 550.

erdos_1989_conjecture_roth_related_problems/: Shows any finite coloring of the positive integers leaves few even integers up to M without a monochromatic sum of two distinct integers, and settles related coloring questions.

erdos_1989_monochromatic_sumsets/: Proves the Folkman function satisfies F(k) greater than two to the power c k squared over log k, a lower bound via random two-colorings.

erdos_1989_multipartite_graph_tree_ramsey_numbers/: Bounds the Ramsey number of a complete multipartite graph with a singleton class against a large tree, k(r(K(1,m_1),T_n)-1)+1 from above and within k of it from below, and asks on p. 153 whether r(K(m_1,...,m_k),T_n) <= (k-1)(r(K(m_1,m_2),T_n)-1)+m_1 for large n, the question that is Problem 550.

erdos_1990_problems_results_graphs_hypergraphs_similarities_differences/: Erdős's 1990 survey of extremal and Ramsey-type problems on graphs against hypergraphs: the site's source for the two-color density threshold F(n, alpha), which it recalls from an earlier paper of Erdős, and a printed source of his prize offers on diagonal and off-diagonal Ramsey numbers.

erdos_1993_ramsey_size_linear_graphs/: Introduces Ramsey size-linearity, records tree-and-clique and odd-cycle coefficient questions, and proves the sharp eventual bound for every even cycle against graphs of prescribed size without isolated vertices.

erdos_1993_turan_ramsey_theorems_simple_asymptotically_extremal/: Determines the asymptotically extremal structures for Turan-Ramsey problems with small independence number, using generalized Bollobas-Erdos graphs.

erdos_1995_vertex_covering_monochromatic_paths/: Shows that in any two-coloring of the complete graph on n vertices, l paths of one color cover at least n(l+1)/(l+2) vertices, so 2 root n paths of one color cover everything, and asks whether root n paths suffice.

erdos_1996_some_my_favourite_problems_cycles_colourings/: Erdős's three-page 1996 list of six problems on cycles and colorings: the bipartite-plus-bounded-set question, the almost-bipartite large-chromatic conjecture with a prize offer, cycle lengths in graphs of infinite chromatic number, the count of cycle spectra, the minimum degree forcing a four-cycle, and the Erdős–Tuza rainbow questions.

erdos_1997_some_my_favorite_problems_results/: Erdős's 1997 survey of his favorite problems in number theory, polynomials, combinatorics and geometry, with their prizes: the Ramsey limit and its constructive lower bound, the orders of r(3,n) and r(4,n), hypergraph Ramsey bounds, the monochromatic unit-fraction question with its reciprocal-sum thresholds, the degenerate Turán conjecture, prime gaps, limit points of d_n/log n, an asymptotic formula for r_k(n), the dilation question, Sidon completion and the convex polygon distance sum.

erdos_1997_some_recent_problems_results_graph_theory/: Erdős's five-page 1997 list of sixteen problems and results in graph theory: the Erdős–Faber–Lovász conjecture with Kahn's n(1+o(1)) bound, the sunflower conjecture, the Ramsey limit with its prizes, the induced subgraph conjectures with Sós, Faudree and McKay, the infinite-cardinal triangle question, the Erdős–Rousseau–Schelp bound on edges in no monochromatic triangle, the pentagon-edges conjecture, and the Erdős–Faudree–Ordman edge-disjoint monochromatic triangles question.

erdos_galvin_1991_some_ramsey_type_theorems/: Erdős and Galvin's 1991 paper on versions of Ramsey's theorem in which the homogeneous set is allowed at most 2^(r-1) colors so that its growth can be bounded: Theorem 2.1, the main result; Theorem 4.1, Galvin's two-class partition under which no sequence with monochromatic consecutive sums grows slowly; Problem 4.2, the (k+1)-class finite-sums question that is Problem 948; Theorem 4.3, consecutive sums in two of k classes with c log log n points below n infinitely often.

erdos_rousseau_1993_size_ramsey_number_complete_bipartite/: Erdős and Rousseau's 1993 note proving that the diagonal size Ramsey number of K_{n,n} exceeds n^2 2^n / 60 for every n at least 1, by a uniformly random two-coloring and their Lemma 1, that a graph with q edges contains at most (2eq/n)(2e^2 q/n^2)^n copies of K_{n,n}; it also records the upper bound (3/2) n^3 2^n for n at least 6, credited to the 1978 size Ramsey paper and derived from a pigeonhole criterion.

erdos_tuza_1993_rainbow_subgraphs_edge_colorings_complete_graphs/: Erdős and Tuza's 1993 note posing the rainbow-subgraph problem for edge-colorings of complete graphs with a minimum degree in every color, the origin of Problem 811: whether d(n,F) is finite for every graph F with e edges and every large n ≡ 1 (mod e); the exact value d(n,K_3) = 2⌊(n−2)/8⌋ + 1; the bounds ⌊n/6⌋ ≤ d(n,C_4) ≤ (1/4 − c)n; d(n,F) ≤ e − 1 for trees; and infinite classes of graphs with d(n,F) = ∞ for infinitely many n ≡ 0 (mod e).

exoo_1994_lower_bound_schur_numbers_multicolor_ramsey/: Gives a sum-free partition of 1 to 160 into five parts, proving the Schur number bound S(5) at least 160 and the five-color triangle Ramsey bound R5(3) at least 162.

faudree_1993_conjecture_erdos_ramsey_number_r_w6/: Disproves Erdős's conjecture that complete graphs minimize diagonal Ramsey numbers among k-chromatic graphs, by computing r(W6) = 17 < 18 = r(K4).

fettes_kramer_radziszowski_2004_upper_bound_62/: Records the published four-color bound of 62 and a reviewed analytic attaching reduction; the final computational proof remains unchecked.

fizpontiveros_2020_triangle_free_process_ramsey_number/: Follows the triangle-free process to its asymptotic end and deduces that R(3,k) is at least (1/4-o(1))k^2/log k.

fox_2008_induced_ramsey_type_theorems/: Gives regularity-free proofs, with much better bounds, of Ramsey-type theorems for graphs with a forbidden induced subgraph, and shows that pseudo-random graphs are induced Ramsey hosts, giving explicit constructions for upper bounds on induced Ramsey numbers.

fox_2012_problem_erdos_rothschild_edges_triangles/: Disproves Erdős's conjecture that some edge must lie in a polynomially large number of triangles in triangle-covered graphs of every fixed density below one quarter, by an explicit construction.

fredricksen_2000_symmetric_sum_free_partitions_lower_bounds/: Gives new lower bounds S(6) >= 536 and S(7) >= 1680 for Schur numbers, hence R_6(3) >= 538 and R_7(3) >= 1682.

fu_2026_size_ramsey_minimal_graphs_uniform_star_forests/: Characterizes the size Ramsey minimal graphs for uniform star forests in any number of colors; its first arXiv version claimed the full Burr-Erdős-Faudree-Rousseau-Schelp star-forest conjecture and was withdrawn the next day.

gerencser_1967_ramsey_type_problems/: Gerencsér and Gyárfás's 1967 note determining the path Ramsey number g(k,l) = k + floor((l+1)/2) for k >= l and stating the largest monochromatic connected subgraph forced by three colors as ceil(n/2), which fails as printed for n = 2, with the footnote observing that two monochromatic paths of possibly different colors cover the vertex set of any two-colored complete graph; read in four pages extracted from the journal's volume scan.

girao_2024_monochromatic_odd_cycles_edge_coloured_complete/: Proves an upper bound of order 2^q/q^(1-o(1)) on the shortest monochromatic odd cycle forced in a q-coloring of the complete graph on two-to-the-q plus one vertices.

goddard_1994_upper_bound_ramsey_numbers_triangle_graph/: Proves the sharp bound r(K_3,G) at most twice the edge count plus one for every graph G without isolated vertices.

graham_et_al_1972_ramseys_theorem_class_categories/: Graham, Leeb and Rothschild's 1972 Ramsey theorem for a class of categories, with Ramsey's theorem, the vector space and affine analogs and the Ramsey theorem for n-parameter sets as corollaries.

graham_rothschild_1971_ramseys_theorem_n_parameter_sets/: Graham and Rothschild's 1971 partition theorem for n-parameter sets, with its corollaries: the affine and vector-space Ramsey theorems for k = 0 and k = 1, the disjoint unions theorem, the theorem of Folkman, Rado and Sanders, van der Waerden's and Ramsey's theorems, and the concluding question that Hindman's theorem answers.

green_2019_monochromatic_solutions_x_plus_y_z_squared/: Shows every 2-coloring of the positive integers has infinitely many monochromatic solutions of x + y = z² while some 3-coloring has only the trivial one; its introduction records that Khalfalah and Szemerédi's theorem colors x and y alike but not necessarily z.

green_2022_new_lower_bounds_van_der_waerden/: Gives a coloring showing the van der Waerden number w(3,k) exceeds k^{c(log k/log log k)^{1/3}}, refuting the guess that it is polynomial.

grossman_1979_generalized_ramsey_theory_graphs_x_double_stars/: Grossman, Harary and Klawe's 1979 Ramsey numbers of the double stars S(n,m): the lower bound max(2n+1, n+2m+2) for n odd and m ≤ 2 and max(2n+2, n+2m+2) otherwise, for every double star, with equality for n ≤ √2·m or n ≥ 3m; the general bound r(S(n,m)) ≤ 2n+m+2; the conjecture of equality in the remaining cases; and the remark that the construction behind the bound 2n+2 for n odd (Lemma 2.4) disproves Burr's conjecture for trees.

gruslys_2020_monochromatic_triangle_packings_red_blue_graphs/: Proves Erdős's conjecture that every two-coloring of a complete graph has about n squared over twelve edge-disjoint monochromatic triangles, with a stability companion; read in the arXiv preprint, no journal version found.

gupta_2024_optimizing_cgms_upper_bound_ramsey_numbers/: Simplifies and optimizes the Campos-Griffiths-Morris-Sahasrabudhe argument to give the bound 3.8 to the k for diagonal Ramsey numbers.

gyori_schelp_2002_two_edge_colorings_graphs_bounded_degree_both_colors/: Győri and Schelp's 2002 determination of m(k, l), the largest number m such that every graph of maximum degree k + l with at most m vertices of that degree can be red-blue edge colored with red degrees at most k and blue degrees at most l, exact except when k and l have different parity, and its application, Theorem 2: the 1978 Burr–Erdős–Faudree–Rousseau–Schelp formula for the size Ramsey number of two star forests holds whenever C(l_j, 2) > Σ_{i≥j} l_i for every j.

hassan_2026_small_folkman_graphs_arrowing_k2_k3/: Gives new bounds on vertex and edge Folkman numbers arrowing K2 or K3 while avoiding graphs on four to six vertices, shows that F_e(3,3;W_5) exists, and reports the known interval 21 <= F_e(3,3;4) <= 786 as prior work.

haxell_1995_induced_size_ramsey_number_cycles/: Shows the induced r-size-Ramsey number of the cycle of length l is at most c_r times l, so it grows only linearly in the cycle length.

heath_2026_generalized_ramsey_numbers_hypercube/: Gives new upper bounds on the number of colors needed to color hypercube edges so that every k-cycle receives at least q colors.

hefty_2025_improving_just_two_bites/: Proves R(3,k) is at least (1/2+o(1))k^2/log k, matching the conjectured constant, via a simple two-step random construction.

heinrich_1977_proper_colourings_k_15/: Heinrich's 1977 classification of the proper 3-colorings of the complete graph on 15 vertices, the edge-colorings with no monochromatic triangle: Theorem 2, there are exactly two up to isomorphism and each is embedded in one of the two proper 3-colorings of K_16 of Kalbfleisch and Stanton, via Theorem 1, every such coloring has 35 edges in each color.

heule_2017_schur_number_five/: Determines the fifth Schur number S(5) = 160 by massively parallel SAT solving with a machine-verified proof of over two petabytes.

hindman_1974_finite_sums_sequences_within_cells_partition_n/: Hindman's 1974 proof of the Graham–Rothschild conjecture, now Hindman's theorem: for every finite partition of the positive integers, some cell contains a sequence all of whose finite sums of distinct terms lie in that cell (Theorem 3.1), with the finite-unions form (Corollary 3.3), an ultrafilter corollary under the continuum hypothesis, and the remark that no bound on the terms holds uniformly over the partitions.

hindman_1979_partitions_sums_integers_repetition/: Hindman's 1979 paper on Owings's question for r cells, whether a finite partition of the positive integers has a cell containing all pairwise sums, doubles included, of an infinite set: a three-cell partition with no such cell and a cell of density zero (Theorem 2.4), the two-cell case proved if a cell contains arbitrarily long even arithmetic progressions of a fixed difference (Theorem 2.9, Corollary 2.10), the conjecture dropping that restriction, and results on finite sums with repetition.

hindman_1980_partitions_sums_products_two_counterexamples/: Hindman's 1980 negative answer to Erdős's question on multilinear expressions: a two-cell partition of the positive integers under which no infinite set inside one cell has all its finite products and pairwise sums in that cell (Theorem 2.14), a seven-cell partition under which no infinite set inside one cell has all its pairwise sums and pairwise products in that cell (Theorem 2.15), and the finite question of Problem 172 stated as open (Question 3.3).

hindman_2017_pairwise_sums_colourings_reals/: Constructs finite colorings of the reals with no large set whose pairwise or k-wise sums are monochromatic, with positive results for nice colorings.

hindman_strauss_2009_simple_characterization_sets_satisfying_central_sets_theorem/: A theorem-indexed source review of Hindman and Strauss's characterization of the sets satisfying the Central Sets Theorem.

hng_2026_ramsey_size_linear_generalization/: Gives an asymptotic upper bound for a fixed odd cycle against a graph with prescribed vertices and edges, retained as qualified context for the odd-cycle constant problem, and polynomial bounds in the edge count for a clique, and for a multicolor triangle, against a graph without isolated vertices.

huang_2026_affirmative_answer_owings_sumset_question/: An unrefereed 2026 preprint claiming that every two-coloring of the natural numbers has an infinite set B with B+B monochromatic, answering Owings's question, together with a weighted form; the claim is not adopted by the site and is not checked here.

huang_2026_new_upper_bound_ramsey_number_odd_cycles/: Improves the multicolor Ramsey upper bound for a fixed odd cycle when the number of colors is sufficiently large.

hunter_2022_improved_lower_bounds_van_der_waerden/: Improves the lower bound for the van der Waerden number w(3,k) to k^{c log k / log log k}, sharpening Green's exponent.

ihringer_2017_new_bounds_ramsey_number_r_i/: Determines r(I_4, L_3) = 15 and r(I_5, L_3) = 23 and shows r(I_m, L_3) has order m squared over log m.

janzer_2025_short_monochromatic_odd_cycles/: Proves every k-coloring of the complete graph on two to the k plus one vertices has a monochromatic odd cycle of length O(k^1.5 times 2^(k/2)).

javadi_2019_size_ramsey_number_cycles/: Gives explicit linear upper bounds for size-Ramsey numbers of cycles, avoiding the regularity lemma, including a concrete two-color constant.

jenssen_2020_distinct_degrees_induced_subgraphs/: Shows every C-Ramsey graph on N vertices has an induced subgraph with at least a C-dependent constant times N^(2/3) distinct degrees, tight up to the constant.

jenssen_2021_exact_ramsey_numbers_odd_cycles_via/: Proves the Bondy-Erdos formula R_k(C_n) = 2^(k-1)(n-1)+1 for every fixed number of colors and all large odd n.

kalbfleisch_stanton_1968_maximal_triangle_free_edge_chromatic_graphs_three_colors/: Kalbfleisch and Stanton's 1968 classification of the triangle-free 3-colorings of the edges of the complete graph on 16 vertices, the extremal colorings for R(3,3,3) = 17: exactly two up to renaming vertices and permuting colors, both constructed from a lemma on common neighbors and a lemma fixing the graph of each color, with their incidence matrices printed in Tables 2(a) and 2(b).

karagiannis_2013_combinatorial_proof_infinite_version_hales_jewett_theorem/: Gives a combinatorial proof, from the classical Hales–Jewett theorem, of the infinite Hales–Jewett theorem of Carlson and of Furstenberg and Katznelson, and of its extension to an increasing sequence of finite alphabets.

keevash_2004_number_edges_not_covered_monochromatic_copies/: Shows the maximum number of edges of a 2-colored complete graph avoiding monochromatic copies of H equals the Turan number when H is edge-color-critical of chromatic number at least 3 and n is large, and when H is C4 and n >= 7, and determines the triangle case exactly for every n.

keevash_2021_cycle_complete_ramsey_numbers/: Shows r(C_l, K_n) = (l-1)(n-1)+1 once l is at least C log n / log log n, and that this threshold is tight up to the constant.

kim_1995_ramsey_number_has_order_magnitude/: Proves a matching lower bound showing the Ramsey number R(3,t) grows like t squared over log t, via the semirandom nibble method.

kohayakawa_1998_induced_ramsey_numbers/: Kohayakawa, Prömel and Rödl's 1998 bound on induced Ramsey numbers: for graphs G on k vertices and H on t at least k vertices of chromatic number q at least 2, r_ind(G, H) is at most t^{Ck log q} (Theorem 3), so r_ind(H) is at most e^{Ct (log t)^2} in the diagonal case, one factor of (log t)(log q) short of the exponential bound Erdős asked for; hosts are random graphs built on projective planes, with polynomial bounds when G is a simple graph or a tree.

kohayakawa_2005_3_colored_ramsey_number_odd_cycles/: Proves the Bondy-Erdős conjecture that the three-color Ramsey number of an odd cycle on n vertices equals 4n-3 for all large odd n.

kwan_2017_proof_conjecture_induced_subgraphs_ramsey_graphs/: Proves the Erdos--Faudree--Sos lower bound on distinct vertex-edge count pairs of induced subgraphs of every fixed-C Ramsey graph.

kwan_2022_anticoncentration_ramsey_graphs_proof_erdos_mckay/: Proves the Erdos-McKay conjecture: every Ramsey graph has induced subgraphs with every edge count up to nearly its total.

lange_2014_use_max_cut_ramsey_arrowing_triangles/: Lowers the upper bound on the smallest K4-free graph forcing a monochromatic triangle in any two-coloring from 941 to 786 vertices.

larson_mitchell_1997_problem_erdos_rado/: Larson and Mitchell's 1997 estimates for the digraph Ramsey numbers r(K_n^, L_m), the least order forcing an independent set of n vertices or a transitive tournament of order m: r(K_n^, L_3) ≤ n^2 (Lemma 4.2), r(K_4^, L_3) > 13 by an explicit 13-vertex digraph (Proposition 3.1), the cubic bound r(K_n^, L_4) ≤ 2n^3/3 + n^2 + 4n/3 − 4 (Lemma 4.4), and a polynomial bound of degree m − 1 in n with leading coefficient 2^(m−2)/(m−1)! (Lemma 4.13) that improves Erdős and Rado's 1967 bound in its dependence on m.

laywine_mayberry_1988_simple_construction_two_non_isomorphic_triangle_free_3_colored_k_16/: Laywine and Mayberry's 1988 construction of the two triangle-free 3-colorings of the edges of the complete graph on 16 vertices from four tricolored tetrahedra properly joined into a super-TCT: the Lemma that every such K_16 is triangle-free, the Theorem that the super-TCTs fall into exactly two isomorphism classes by the parity of the signs of the joinings, and the identification of the even class with the finite-field coloring and the odd class with the computer-found one.

leader_2024_monochromatic_sumsets_countable_colourings_abelian_groups/: Shows every abelian group with no element of order 4 has a countable coloring with no monochromatic sumset X+X even for X of size two.

lee_2017_ramsey_numbers_degenerate_graphs/: Proves the 1973 Burr-Erdos conjecture that every d-degenerate graph on n vertices has Ramsey number linear in n.

li_2023_two_source_extractors_asymptotically_optimal_entropy/: Builds explicit two-source extractors for asymptotically optimal logarithmic min-entropy, giving explicit graphs whose clique and independence numbers are polylogarithmic in the vertex count.

li_2026_resolution_erdos_problem_550_tree_versus/: Claims a resolution of the Erdos-Faudree-Rousseau-Schelp question bounding tree versus complete multipartite Ramsey numbers for all large trees.

li_lih_2009_multi_color_ramsey_numbers_even_cycles/: Li and Lih's 2009 determination of the order of magnitude of the k-color Ramsey number of the even cycles C_4, C_6 and C_10: Theorem 1, r_k(C_2m) has order k^{m/(m-1)} as k grows for m = 2, 3, 5, from an algebraic k-coloring of the complete bipartite graph on two copies of F(q)^m with no monochromatic C_2m and a halving argument that transfers bipartite lower bounds to the complete graph.

li_rousseau_zang_2001_asymptotic_upper_bounds_ramsey_functions/: Li, Rousseau and Zang's 2001 bound r(K_k + K̄_l, K_n) ≤ (l + o(1)) n^k/(log n)^(k-1) for fixed k and l, hence r(k,n) ≤ (1 + o(1)) n^(k-1)/(log n)^(k-2) for every fixed k, from an independence bound α(G) ≥ N f_{a+1}(d) for graphs whose vertex neighborhoods have average degree at most a, generalizing Shearer's triangle-free bound; the constant 1 + o(1) on the Ajtai–Komlós–Szemerédi upper bound of Problems 166 and 986.

lu_2007_explicit_construction_small_folkman_graphs/: Constructs a K4-free graph on 9697 vertices every 2-coloring of whose edges yields a monochromatic triangle, claiming an Erdos prize.

mattheus_2023_asymptotics_r_4_t/: Proves that the off-diagonal Ramsey number r(4,t) is at least of order t cubed divided by the fourth power of log t, settling a conjecture of Erdos.

mccarthy_2025_mathon_type_construction_digraphs_improved_lower_bounds/: Adapts Mathon's construction to digraphs through k-th power Paley digraphs and improves the lower bounds for directed Ramsey numbers, including R(8) at least 57 for the least order forcing a transitive subtournament on eight vertices.

montellano_ballesteros_neumann_lara_2005_anti_ramsey_theorem_cycles/: Montellano-Ballesteros and Neumann-Lara's 2005 determination of h(n,p), the least number of colors that forces a heterochromatic p-cycle in an edge-coloring of the complete graph on n vertices, for all n at least p at least 3: Theorem 5, h(n,p) = E(n,p), the lower bound of Erdős, Simonovits and Sós, with the 1975 cycle conjecture as Corollary 1.

montgomery_2025_ramsey_numbers_trees/: Proves Burr's bound R(T) = max{2t_1, t_1 + 2t_2} - 1 is exact for every tree with maximum degree at most a small linear function of its order.

moon_1966_disjoint_triangles_chromatic_graphs/: Moon's 1966 note on the largest number μ(G_n) of vertex-disjoint monochromatic triangles in a two-coloring G_n of the edges of K_n: the Theorem [n/3] − 1 ≤ μ(G_n) ≤ [n/3] for every n, with μ(G_n) = [n/3] when n ≡ 2 (mod 3) and n ≥ 8, the k = 3 case behind the decomposition problem of Problem 1015.

moreira_2017_monochromatic_sums_products/: Shows every finite coloring of the natural numbers has a monochromatic triple x, x+y, xy, plus a wide new class of nonlinear Ramsey patterns.

morris_2026_recent_results_ramsey_theory/: Survey outlining recent breakthroughs on diagonal, off-diagonal and induced Ramsey numbers, including the exponential improvement over the Erdos-Szekeres bound.

neiman_2022_tighter_bounds_directed_ramsey_number_r_7/: Proves by computer-assisted search that the directed Ramsey number R(7), the least order forcing a transitive subtournament on seven vertices, lies between 34 and 47, after classifying the tournaments on 23, 24 and 25 vertices with no transitive subtournament on six vertices.

nesetril_rodl_1978_structure_critical_ramsey_graphs/: Nešetřil and Rödl's 1978 paper on critical Ramsey graphs, the Ramsey graphs for G minimal under subgraph inclusion: a graph of chromatic number at least 3 (Theorem 1) or a 2.5-connected graph (Theorem 2) has infinitely many critical Ramsey graphs, toward the conjecture that every graph with at least two edges has infinitely many vertex-critical Ramsey graphs; with a forest theorem and a second conjecture. It prints no bound on the number of edges of a Ramsey graph.

nikiforov_2005_cycle_complete_graph_ramsey_numbers/: Proves the cycle-complete Ramsey formula r(C_p, K_r) = (p−1)(r−1)+1 for every cycle length p at least 4r+2, extending the Bondy–Erdős range p at least r²−2, and conjectures a polynomially lower threshold.

norin_2016_asymptotics_ramsey_numbers_double_stars/: Disproves the Grossman-Harary-Klawe conjecture on double-star Ramsey numbers and answers negatively a 1982 question of Erdős, Faudree, Rousseau and Schelp.

openai_2026_cycle_clique_ramsey_numbers/: Claims R(C_m,K_n) = (m-1)(n-1)+1 for all m ≥ n ≥ 3 except (3,3), the whole Erdős–Faudree–Rousseau–Schelp conjecture of Problem 551, by expansion in a minimal counterexample, a large-clique theorem, optimal path systems and a computer check of 3,099 patterns; unverified here.

openai_2026_hypercube_ramsey_number_has_linear_order/: A 172-page manuscript of the OpenAI mathematics release claiming that the two-color Ramsey number of the n-dimensional hypercube is at most C 2^n for an absolute constant C, by a contradiction argument along a counterexample sequence that forces density discrepancy and then embeds the cube through patch tilings and Hall matchings; the claimed resolution of Problem 181.

openai_2026_monochromatic_finite_sums_products_positive_integers/: Claims Hindman's finite sums-and-products conjecture, Problem 172: every finite coloring of the positive integers contains, for each m, an m-element set whose nonempty subset sums and subset products share one color; argued by a weighted count with nilsequence models and nilpotent recurrence.

openai_2026_ratio_consecutive_ramsey_numbers/: A three-page manuscript hosted by OpenAI proving that for every fixed k the ratio of consecutive off-diagonal Ramsey numbers R(k,l+1)/R(k,l) tends to one, with a polynomial rate; the proof is attributed to an internal model at OpenAI and the site accepts it as the resolution of Problem 1014.

openai_2026_sharp_logarithmic_exponent_r_5_t/: A 41-page manuscript of the OpenAI mathematics release claiming r(5,t) = t^4/(log t)^{3+o(1)}: an upper bound C t^4/(log t)^3 by the uniform-independent-set method, and a lower bound t^4/(log t)^{3+eps} from an ordered projective-flag graph over PG(4,q) analyzed by an entropy compression argument; bears on the s = 5 case of Problem 986.

openai_2026_sharp_logarithmic_exponents_fixed_off_diagonal_ramsey_numbers/: A 53-page manuscript of the OpenAI mathematics release claiming, for every fixed s at least 6, r(s,t) = t^(s-1)/(log t)^(s-2+o(1)): a lower bound from Bradač's ordered incident-flag graph over PG(s-1,q) by an entropy-compression argument, and the Ajtai--Komlós--Szemerédi upper bound reproved; Problem 986.

openai_2026_ten_advances_mathematics_theoretical_computer_science/: Records OpenAI's 2026 report, with Chapter 9's complete construction of a superexponential lower bound for multicolor triangle Ramsey numbers.

owings_1974_e2494_sumset_within_set_or_complement/: Owings's 1974 Monthly proposal E 2494, the origin of Problem 1199: prove or disprove that for every subset B of the natural numbers there is an infinite set A whose sumset A + A, doubles included, lies inside B or inside the complement of B; the two-class sumset question, posed as a problem with no conjectured answer.

parsons_1975_ramsey_graphs_block_designs_i/: Bounds the Ramsey number of a four-cycle against a star with n edges by n plus the square root of n minus one plus two, and determines it exactly at n = q squared and q squared plus one for every prime power q through polarity graphs of projective planes.

pikhurko_2001_size_ramsey_numbers_stars_versus_3_chromatic_graphs/: Bounds the size Ramsey number of a star with n edges versus a triangle by n squared plus a term of order n to the three halves, and so disproves for every n at least 5 Erdős's conjecture that any graph with a prescribed number of edges splits into a bipartite graph and a graph of maximum degree below n. Also proves a lower bound of the same form, n squared plus a constant times n to the three halves, against odd cycles.

pokrovskiy_2024_proof_conjecture_erdos_gyarfas_monochromatic_path/: Proves that every 2-edge-colored complete graph on n vertices, for n larger than 20 to the 40th, has root n same-colored monochromatic paths covering all vertices; the Erdős–Gyárfás conjecture for large n, published in JCTB.

potechin_2014_note_problem_erdos_rothschild/: Gives lower bounds on the largest book forced in a graph on n vertices with n squared over 4 minus n f(n) edges in which every edge lies in a triangle, the regime just below the density threshold one quarter; an arXiv note with no journal version found.

promel_voigt_1983_canonical_partition_theorems_parameter_sets/: Proves a canonical Graham-Rothschild theorem for k-parameter words, with the Erdős-Rado canonization theorem, a three-type canonical finite union theorem and a canonical Schur theorem as corollaries.

pyber_1986_clique_covering_graphs/: Pyber's 1986 proof of Erdős's conjecture on clique coverings of complementary graphs: for n larger than a threshold, the largest value of cc(G) + cc(complement of G) over graphs G on n vertices is [n²/4] + 2, that is, at most [n²/4] + 2 monochromatic cliques cover the edges of any 2-edge-colored complete graph on n vertices, with the extremal colorings described; Theorem 1, with the proof's threshold 2^1500.

radziszowski_2007_most_wanted_folkman_graph/: Raises the lower bound for the edge Folkman number Fe(3,3;4) to 19 and gives evidence that the true value is at most 127.

ramsey_1930_problem_formal_logic/: Reconstructs Ramsey's finite and infinite subset theorems and his decision procedure for the relational existential-before-universal prefix class.

reid_parker_1970_disproof_conjecture_erdos_moser_tournaments/: Reid and Parker's 1970 disproof of the Erdős–Moser conjecture f(n) = [log_2 n] + 1, f(n) being the largest k such that every tournament on n vertices contains a transitive subtournament on k vertices: every tournament on 14 vertices contains a transitive subtournament on 5 vertices, f(n) ≥ [log_2(16n/7)] for n ≥ 14, the values of f(n) for n ≤ 27, and the unique 13-vertex tournament with no transitive subtournament on 5 vertices.

rodl_szemeredi_2000_size_ramsey_numbers_graphs_bounded_degree/: Rödl and Szemerédi's 2000 answer to Beck's question whether graphs of bounded maximum degree have linear size Ramsey numbers: Theorem 1, a graph on n vertices with maximum degree three and size Ramsey number at least cn (log_2 n)^α, proved for large n with c = 1/10 and α = 1/60, and the concluding conjecture n^(1+ε) ≤ r̂(n,Δ) ≤ n^(2-ε) for every Δ ≥ 3.

sanders_2020_monochromatic_solutions_x_minus_y_z_squared/: Bounds the largest N admitting a k-coloring of {1, ..., N} with no monochromatic solution of x − y = z² by a triple exponential in O(k); its introduction restates the Khalfalah–Szemerédi theorem with two distinct elements x and y of the same color and x + y = z².

sarkozy_2006_anti_ramsey_problem_burr_erdos_graham_sos/: Proves that for every connected bipartite graph L that is not complete bipartite, a graph with a positive fraction of all possible edges needs more than any constant multiple of n colors before every copy of L can be rainbow. The case of the four-cycle asked by Burr, Erdős, Graham and Sós is left open.

saturnino_2026_counterexample_hereditary_triangle_ramsey_compactness_problem/: Claims hereditary classes of finite graphs holding n-color triangle-Ramsey graphs for every finite n, while no graph whose age (induced age, for the induced class) lies in the class is triangle-Ramsey for an infinite number of colors.

schoen_2021_subexponential_upper_bound_van_der_waerden/: Proves the first subexponential upper bound W(3,k) at most exp(C k^{1-c}) for the off-diagonal van der Waerden numbers, and remarks that the 2020 Bloom–Sisask bound in Roth's theorem gives the same shape directly.

schur_1916_uber_die_kongruenz/: Proves that any partition of 1 to N into m classes with N > m!e has a class containing two numbers whose difference lies in the same class, and derives Dickson's theorem on the congruence x^m + y^m = z^m (mod p) with the bound M = m!e + 1; p. 117 gives the lower bound (3^m - 1)/2 for the largest interval admitting a difference-free partition into m classes.

shearer_1983_note_independence_number_triangle_free_graphs/: Shearer's 1983 note proving that a triangle-free graph on n vertices with average degree d has an independent set of at least n(d ln d - d + 1)/(d - 1)^2 vertices, a one-page induction that sharpens the Ajtai–Komlós–Szemerédi constant and gives R(3,k) ≤ (1 + o(1)) k^2/log k; with bounds for graphs containing few triangles and the question of K_4-free graphs.

simonovits_1984_restricted_colourings_k_n/: Determines the anti-Ramsey numbers for paths in edge-colorings of the complete graph and frames a general spectrum problem for colorings.

soukup_2015_sums_anti_ramsey_colourings_reals/: An unpublished five-page manuscript proving in ZFC that the reals have a two-coloring under which, for every uncountable set and every N at least two, the sums of N distinct elements take both colors; the manuscript records that Komjáth proved the same result independently.

spencer_1975_ramsey_theorem_new_lower_bound/: Improves Erdős's probabilistic lower bound for the diagonal Ramsey number by a factor of two, to the square root of two over e times k times two to the k over two, using the Lovász local lemma, and gives lower bounds for the off-diagonal numbers with k fixed.

spencer_1975_restricted_ramsey_configurations/: Spencer's 1975 paper on Ramsey configurations with forbidden substructures: for every k and c a finite set of integers with no arithmetic progression of length k plus one in which every c-coloring has a monochromatic k-term progression, an induced van der Waerden theorem, and sparse Ramsey and van der Waerden families; the published proof behind Problem 966.

spencer_1977_asymptotic_lower_bounds_ramsey_functions/: Spencer's 1977 paper deriving lower bounds for Ramsey functions from the Lovász local lemma, stated with its proof and in weighted and symmetric forms: R(3,t) ≥ (1/27 − o(1))(t/ln t)^2, R(k,t) ≥ c(t/ln t)^β with β = [C(k,2) − 1]/(k − 2) = (k + 1)/2, r(C_4,K_t) ≥ c(t/ln t)^{3/2}, r(≤C_k,K_t) ≥ c(t/ln t)^{(k−1)/(k−2)}, and graphs of girth above k with chromatic number cn^{1/(k−1)}/ln n.

sudakov_2003_few_remarks_ramsey_turan_type_problems/: Determines which forbidden graphs force Ramsey-Turan numbers to be subquadratic once the independence number is only slightly below linear.

sudakov_2007_ramsey_numbers_size_graphs/: Sudakov's lower bound R(K_s,G) at least c (m/log m)^{(s+1)/(s+3)} for every graph G with m edges and every fixed s at least 3, recorded from the abstract; with s = 3 it gives f(n) = O(n^{3/2} log n) for Problem 1182.

sudakov_2011_conjecture_erdos_graph_ramsey_numbers/: Proves Erdos's conjecture that every graph with m edges and no isolated vertices has Ramsey number at most 2 to the power c times root m.

taranchuk_2024_new_lower_bound_multicolor_ramsey_number/: Builds new K2,t+1-free graphs that decompose complete graphs, giving the lower bound tk squared plus one for the multicolor Ramsey number.

taylor_1981_bounds_disjoint_unions_theorem/: Taylor's 1981 six-page proof of Graham and Rothschild's disjoint unions theorem and of Rado, Folkman and Sanders's non-repeating sums theorem, with iterated exponential upper bounds: Theorem 3.1, U(r,k) at most a stack of k's and 3's of height 2k(r-1), and Corollary 3.4, U(r,2) at most a tower of threes of height 4r-4 and S(r,2), the Folkman function F(r) of Problem 531, at most a tower of threes of height 4r-3.

tikhomirov_2022_bounded_degree_graphs_large_size_ramsey/: Constructs graphs on n vertices of maximum degree at most three whose size-Ramsey number is at least cn exp(c sqrt(log n)).

tikhomirov_2024_remark_ramsey_number_hypercube/: Improves the Ramsey number of the hypercube to r(Q_n) = O(2^{2n-cn}) for a universal positive constant c.

voigt_1985_canonizing_partition_theorems_diversification_products_iterated_versions/: A focused E0774 digest of Voigt's 1985 canonizing partition theorems.

wan_1997_upper_bounds_ramsey_numbers_r_3_3_3_schur_numbers/: Wan's 1997 parity refinement of the Greenwood–Gleason recursion: for n at least 4 the n-color Ramsey number R(3,...,3) is less than n!(e - 1/e + 3)/2 + 1, from Folkman's bound of 65 for four colors, and for even n at least 6 the least N such that every n-coloring of {1,...,N} has a monochromatic solution of x + y = z is less than n!(e - 1/e + 3)/2 - n + 2; the intermediate upper bound between Whitehead's e - 1/24 and Xu, Xie and Chen's e - 1/6.

wigderson_2024_infinitely_many_minimally_non_ramsey_size/: Proves infinitely many graphs are not Ramsey size-linear although every proper subgraph is, answering Erdős Problem 79.

wu_2015_ramsey_numbers_c_4_versus_wheels_stars/: Bounds the number of edges of a C_4-free graph of order q^2+q+2 and determines exact Ramsey numbers of C_4 against stars and wheels.

yuan_2021_anti_ramsey_numbers_paths/: Determines the exact anti-Ramsey number of the path on k vertices for all n at least k, confirming a 1970s conjecture.

zhang_2017_polarity_graphs_ramsey_numbers_c_4_versus_stars/: Zhang, Chen and Cheng's 2017 extension of Parsons's exact values R(C_4, K_{1,q^2-t}) = q^2 + q - (t-1) for odd prime powers q to every t with 1 <= t <= 2 ceil(q/4) except t = 2 ceil(q/4) - 1, adding the odd t, from subgraphs of the polarity graph of the projective plane over GF(q) with one edge added when t is odd (Theorem 4); with a table of the known values of R(C_4, K_{1,n}) for 6 <= n <= 50 and the question whether R(C_4, K_{1,n}) is always n + floor(sqrt(n-1)) + 1 or + 2.

zhang_2017_some_values_ramsey_numbers_c_4_versus_stars/: Zhang, Chen and Cheng's 2017 exact values of R(C_4, K_{1,n}) for two new forms of n, motivated by n not near the square of a prime power, from a C_4-free graph on q^2 - 1 vertices built over the Galois field F_q: Theorem 6, R(C_4, K_{1,(q-1)^2+t}) = (q-1)^2 + q + t for even prime powers q at least 4 and t = 1, 0, -2; Theorem 7, R(C_4, K_{1,q(q-1)-t}) = q^2 - t for odd prime powers q at least 5 and even t up to 2 ceil(q/4); and the question whether R(C_4, K_{1,n}) is always n + floor(sqrt(n-1)) + 1 or + 2.

This folder holds sources whose primary subject is Ramsey Theory.

Sources with other primary subjects

Explicit links to this subject's problems support these cross-references.

Linked from (206)

Graph