CS Paper Radar

New lower bounds for six small hypergraph Ramsey numbers

Christian Lysenstøen

cs.DM math.CO ·submitted 2026-11-18 20:23 UTC · v1

Abstract

Let $R(k,l;t)$ denote the least $n$ such that every colouring of the $t$-subsets of an $n$-set with two colours has $k$ points all of whose $t$-subsets have the first colour, or $l$ points all of whose $t$-subsets have the second. We give explicit colourings proving $R(4,5;3)\ge 38$, $R(4,6;3)\ge 71$, $R(5,5;3)\ge 99$, $R(5,6;4)\ge 201$, $R(6,6;4)\ge 601$ and $R(6,6;5)\ge 84$. The first three improve the bounds 35, 63 and 88 listed in Radziszowski's dynamic survey. The last three improve the listed bounds 67, 133 and 72, and for the two 4-uniform numbers also the values 159 and 317 of a recent data deposit. The colourings of 3-subsets are invariant under groups of affine maps $x\mapsto ax+b$ of $\mathbb{Z}_n$, for $n=37$, 69 and 97, in the last two cases with one further fixed point. Those of 4-subsets live on the projective line over $\mathbb{F}_q$, for $q=199$ and $q=599$, and are invariant under $\mathrm{PSL}(2,q)$ or $\mathrm{PGL}(2,q)$, so each is given by a table of $q$ entries. For 5-subsets we show that, for every prime $q\ge 5$, invariance under $\mathrm{PGL}(2,q)$ forces six points all of whose 5-subsets have the same colour; our colouring is invariant under all affine maps of $\mathbb{Z}_{83}$. By known constructions the bounds give $R(5,5,5;3)\ge 9605$ and $R_k(5;3)\ge 98^{2^{k-2}}+1$, and $R(6,7;4)\ge 2001$, $R(7,7;4)\ge 12001$ and $R(8,8;4)\ge 588001$. The colourings, and programs that verify them, accompany the paper as ancillary files.

Comment
13 pages, 3 tables. The colourings and the programs that verify them are included as ancillary files

Closest papers

Nearest neighbours by meaning across the whole index.

Lower bounds for Ramsey numbers: $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$

cs.DM math.CO ·2026-10-08 ·Fritz Cremer
theory similarity 0.79
Abstract · 8 pages, 2 figures

We prove the lower bounds $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$, improving the bounds 134 and 343 listed in the April 2026 revision of Radziszowski's dynamic survey. We give explicit red/blue colorings of $K_{134}$ with no red $K_6$ or blue $K_8$, and of $K_{344}$ with no red $K_8$ or blue $K_{10}$, and verify them with two independently written exhaustive clique checkers. Starting from published colorings, we find these witnesses by adding vertices and repairing the resulting monochromatic cliques through local search. The search uses exact conflict counts, preparation moves aimed at making remaining cliques cheaper to break, and mutations followed by repair. A loss based on the largest monochromatic clique containing each edge yielded a useful intermediate state for the $\mathrm{R}(6,8)$ construction. Guided by the author, an AI coding agent wrote and ran the search code; we describe the methods and document the ancestry of the resulting colorings.

0.11

Counterexamples to a conjecture and improved bounds for bipanchromatic colorings

cs.DM math.CO ·2026-10-19 ·Stefan Novaković, Duško Jojić
theory similarity 0.68
Abstract · 10 pages, 2 figures

We study the bipanchromatic number $χ_B$, introduced by Lalou et al. (Discrete Appl. Math. 391 (2026), 511-522) as the maximum number of colors in a panchromatic hypergraph coloring where every color appears at least twice. They show that merging uniquely occurring colors in a maximum panchromatic coloring gives the lower bound $β=χ_P-\lceilα/2\rceil \leq χ_B$, where $χ_P$ is the panchromatic number and $α$ is the minimum number of such colors among maximum panchromatic colorings. They conjectured that $χ_B=β$ and subsequently disproved it (arXiv:2610.08042). We identify the smallest counterexample, with six vertices and three hyperedges, both minimum possible. We show that the ratio bound $χ_B/β<2$ is asymptotically sharp and prove minimality results for the order and hyperedge count. For $3\leα<χ_P$ we show that every integer from $β$ to $χ_P-1$ occurs as $χ_B$ while $χ_P$ and $α$ are held fixed. Furthermore, we discover that the values $|V|,χ_P,α$ directly decide whether the conjectured equality holds except when $α=4$, where a matching reduction resolves the ambiguity. We derive the optimal universal lower bound $L$ depending only on $|V|,χ_P,α$ in the nontrivial regime $0<2α<|V|$. Finally, we prove $χ_B/L\le5/4$ and $χ_B/L\le6/5+1/(5L)$, with $5/4$ sharp and $6/5$ asymptotically sharp as $L\to\infty$.

0.11

An Integer Programming Approach to Compute Lower Bounds for Ramsey Numbers Using Circulant Graphs

cs.DM math.OC ·2026-08-19 ·Stefano Coniglio, Fabio Furini, Ivana Ljubić, Pablo San Segundo, Johannes Thüerauf +1 more
theory similarity 0.66
Abstract

The Ramsey number $R(m,n)$ is the smallest order at which every red-blue edge coloring of a complete graph must contain a blue clique (a complete subgraph) of size $m$ or a red clique of size $n$. Determining these numbers exactly is extremely hard, and even certifying a lower bound requires exhibiting an explicit coloring that avoids both cliques. We develop an integer programming framework for certifying such lower bounds, restricting the search to circulant graphs, whose rotational symmetry lets us reformulate the problem in a projected distance space, reducing the number of binary variables from quadratic to linear in the graph order. We strengthen this projected model through coefficient reduction and solve it with a branch-and-cut algorithm whose separation routine exploits the common neighborhood structure of circulant graphs, combining heuristic and exact maximum-clique algorithms. In an extensive computational campaign on circulant graphs with up to 410 vertices, we improve the best lower bounds previously obtained by other methods by up to 11 points for 25 values of $R(3,n)$ with $24\le n\le49$ and $n\neq27$, each backed by an explicit graph certificate that can be independently verified with a stand-alone exact clique solver. To the best of our knowledge, our method also provides the first reproducible optimization-based procedure for certifying circulant Ramsey numbers $R_C(m,n)$, which we use to establish eight new values of $R_C(3,n)$ with $13\le n\le20$. Our framework, graph certificates, and stand-alone checker are provided as supplementary material to support independent verification and reuse.

0.18

Erdős-Gyárfás Balanced Five-Colorings

cs.DM math.CO ·2026-10-17 ·Hai Xia, Stefan Szeider
theory similarity 0.66
Abstract

A coloring of the edges of a complete graph with $r$ colors is balanced if the edges among any $r+1$ vertices use all $r$ colors. Erdős and Gyárfás (1999) conjectured that for all $r\ge3$ the complete graph $K_{r^2+1}$ has no balanced $r$-coloring. They proved the conjecture for $r=3$ and $r=4$. We prove the conjecture for $r=5$, the first new case settled in over two decades. There is no balanced $5$-coloring of $K_{26}$, and since $K_{25}$ has one, $K_{25}$ is the largest complete graph admitting a balanced $5$-coloring. We design a reduce--dispatch--enumerate workflow, where every machine step produces an artifact that can be independently checked. First, we use a machine-checked (Lean 4) proof to reduce the conjecture to a single extremal statement about the color class with the fewest edges: no graph on $26$ vertices has between $55$ and $65$ edges while every $6$ of its vertices span between $1$ and $11$ edges. We then search on the sparse class instead of its dense complement, which makes enumeration up to isomorphism feasible. With classical stability theorems for $K_6$-free graphs, we dispatch the five near-extremal edge counts analytically. For the exhaustive enumeration on the remaining six edge counts, we design efficient encodings with SAT modulo symmetries and parallel cube-and-conquer. We also certify all eleven edge counts: each of the $12{,}296$ subproblems carries a clausal refutation checked by the independent verifier drat-trim, and all $273{,}503{,}938$ symmetry-breaking clauses are also validated against the vertex permutations that justify them.

0.21

A proof of Wang's planar $D$-coloring conjecture

cs.DM math.CO ·2026-10-23 ·Harshit Verma
theory similarity 0.66
Abstract · 22 pages, 3 figures. Ancillary files contain the certificates and verification scripts for the computer-assisted case of maximum degree 6

We prove Wang's planar $D$-coloring conjecture. A $D$-coloring of a graph is a proper edge coloring in which every subgraph isomorphic to $K_4$ minus an edge is rainbow. Wang conjectured that every planar graph of maximum degree $Δ$ has a $D$-coloring with $9$ colors if $Δ=4$, $10$ colors if $Δ=5$, and $2Δ-1$ colors if $Δ\ge6$. Hu, Kong and Wang proved the cases $Δ\le5$ and $Δ\ge33$. We prove the sharp bound $2Δ-1$ for every $Δ\ge6$, settling the remaining cases. The proof uses discharging; the case $Δ=6$ is computer-assisted.

0.10

Improved bounds for the smallest 4-chromatic graph of girth six

cs.DM math.CO ·2026-08-24 ·Glauco Rampone
theorycode/data similarity 0.65
Abstract · 12 pages, 1 figure. Ancillary files: independent verification scripts, SAT certificates, and a self-contained Lean 4 formal proof. Code and …

For integers $k,g \ge 3$ let $n_g(k)$ denote the minimum order of a graph with chromatic number $k$ and girth at least $g$. Exoo and Goedgebeur (DMTCS 2019) proved $26 \le n_6(4) \le 66$; their 66-vertex witness has remained the smallest known 4-chromatic graph of girth 6. We improve both bounds to $29 \le n_6(4) \le 64$. The upper bound is witnessed by an explicit 4-chromatic graph of girth 6 on 64 vertices with 152 edges; it is vertex- and edge-critical, and its automorphism group is cyclic of order 8 and acts semiregularly. The lower bound is an exhaustive isomorph-free computation in the SAT modulo symmetries framework with co-certificate learning, driven by the Liu-Postle edge-density bound for 4-critical graphs of girth five; it re-derives $n_6(4) \ge 26$ by a disjoint method and is validated on the known values $n_4(4)=11$ and $n_5(4)=21$. We complement the bounds with structural obstructions: no smaller witness arises from either known witness by local modifications; no 4-chromatic Cayley graph of girth 6 exists on 54-63 vertices (for orders 59 and 61 no vertex-transitive witness exists at all); and no witness on at most 63 vertices admits a semiregular automorphism group with two or three vertex orbits, for any finite group. Since every known witness of an $n_g(4)$ record with $g \ge 6$ is a lift of a small base graph along a semiregular action, these results close the most symmetric part of that regime below 64 vertices. All properties of the new graph are verified by independent programs and formally certified in the Lean 4 proof assistant: the non-3-colourability is established inside Lean by a formally verified checker that re-validates a 219,532-node refutation certificate, with a machine-checked soundness theorem.

0.39

Large diameter for $(Δ+2)$-colouring reconfiguration

cs.DM math.CO ·2026-11-12 ·Wouter Cames van Batenburg
similarity 0.63
Abstract · 15 pages, 2 figures

Given a graph $G$ and an integer $k$, the reconfiguration graph $\mathcal{R}_{k}(G)$ has the proper $k$-colourings of $G$ for vertices, two of which are adjacent if and only if they differ on precisely one vertex of $G$. In $2022$, Cambie, Cranston and the author proved that the diameter of $\mathcal{R}_{Δ+2}(G)$ is at most $n+2μ$, and put forth a collection of conjectures that in its strongest and most beautiful form would imply that the diameter of $\mathcal{R}_{Δ+2}(G)$ is precisely equal to $n + μ$, for every graph $G$ with $n$ vertices, matching number $μ$ and maximum degree $Δ$. Here we disprove most of those conjectures. Our constructions have reconfiguration diameter at least $n+\frac{3}{2}μ-2$. We also provide counterexamples that are $Δ$-regular, we show that every graph has reconfiguration diameter at least $n+\frac{1}{2} μ$, and we advertise an extension to hypergraphs. It is now much more mysterious how the diameter behaves, so we propose a number of open problems.

0.25

Almost Empty Monochromatic Triangles With Many Colors

cs.CG math.CO ·2026-09-11 ·Bhaswar B. Bhattacharya, Sandip Das, Sk Samim Islam, Aashirwad Mohapatra, Saumya Sen
theory similarity 0.63
Abstract · 13 pages, 1 figure

Given integers $c\geq 2$ and $s\geq 0$, let $\mathsf{M}_3(c,s)$ denote the least integer such that every set of at least $\mathsf{M}_3(c,s)$ points in the plane, no three on a line, colored with $c$ colors, contains a monochromatic triangle with at most $s$ interior points. Further, let $λ_3(c)$ be the least integer such that $\mathsf{M}_3(c,λ_3(c))<\infty$. \citet{colorempty} proved that, for every $c\geq 2$, $$\left\lfloor\frac{c-1}{2}\right\rfloor \leq λ_3(c)\leq c-2.$$ Later, \citet{cravioto2019almost} improved the upper bound to $c-3$, for $c\geq 4$. In this paper, we refine their argument to obtain the following asymptotic improvement: $$λ_3(c) \leq c-\sqrt{c\log c}+o (\sqrt{c\log c} ),$$ for all sufficiently large $c$. We also show that every $c$-coloring of a sufficiently large Horton set contains a monochromatic triangle with at most $\lfloor \frac{c-1}{2} \rfloor$ interior points. This shows that the aforementioned lower bound on $λ_3(c)$ is sharp within the class of Horton sets. We conclude with a conjecture on the large-color asymptotics of $λ_3(c)$.

0.44