Three improved lower bounds for hypergraph Ramsey numbers
Explicit group-invariant colourings improving three entries of §7.1(a) of the dynamic survey Small Ramsey Numbers. Each bound is carried by an object small enough to print, not by a search log.
Under the survey's convention that R is the least
n forcing a monochromatic clique, a good colouring on
n points proves R ≥ n+1.
| cell | survey rev. #18 | this work | witness |
|---|---|---|---|
R(4,4,4;3) | ≥ 79 | ≥ 84 | 83 points, 3 colours |
R(4,6;3) | ≥ 63 | ≥ 64 | 63 points, 2 colours |
R(5,5;4) | ≥ 35 | ≥ 36 | 35 points, 2 colours |
The objects, not the search
Each result is a group-invariant colouring given as a small table over group
orbits rather than as solver output. For R(4,4,4;3): let
p = 83, let a = 9 generate the order-41 subgroup of
Z83*, and let G = {x → aix + b},
of order 3403. G acts on the 91,881 triples of
Z83 with exactly 27 orbits, each free of size
3403; 27 numbers give the colours, nine per colour, so the three
colour classes are equal at 30,627 each.
That equality is not forced. Regularity forces each class to be a multiple of 3403, and enumerating every invariant good colouring of this class gives 36 of them — twelve splitting 9/9/9 and twenty-four splitting 8/9/10. The other two witnesses use 120 and 107 orbits, under actions that are not free. Every construction regenerates its whole colouring from its table alone, with no solver.
Verification
All twelve deposited witnesses are checked by complete enumeration, each
under its own hash-bound run. For the three headline objects that is
1,837,620 four-subsets at n = 83,
324,632 five-subsets at n = 35, and all four- and
six-subsets of a 63-set. The R(4,6;3) check runs both ways
round: the intended reading gives zero monochromatic cliques and the
inverse reading gives 102,627, which is what makes the first number
meaningful.
Negative results carry certificates too: an independent RUP/RAT proof
checker re-certifies five UNSAT symmetry classes of the n = 63
tower, and its discriminating control weakens a real instance until it becomes
satisfiable and requires the checker to refuse the original proof.
An obstruction theorem
If an affine group satisfies |G| = C(p,2) and
its multiplier subgroup omits -1 (equivalently
p ≡ 3 mod 4), it acts regularly on unordered pairs. Adjoining
a fixed point then forces every triple through that point into a single orbit,
and hence one colour; no base triple may take that colour, so for the diagonal
problem the base must be coloured with m-1 colours while avoiding a
monochromatic K4(3) — impossible only
once the base reaches or exceeds the (m-1)-colour Ramsey number.
The threshold is a hypothesis, not a detail: at
m = 3 it is R(4,4;3) = 13 and both towers clear it; at
m = 4 it is R(4,4,4;3) itself, and p = 79
does not. Both group conditions are necessary too: for
p ≡ 1 (mod 4) the conclusion genuinely fails, and the
corresponding classes are satisfiable at p = 13 and
p = 37.
What is not claimed
- Novelty is provisional. Both incumbent constructions are personal communications (2018 and 2021) that the bibliographic sources searched could not supply. Nothing stronger was found, but a newer unpublished communication is not excluded.
- No upper bounds. The survey prints none for any of these cells, so these improvements do not narrow a stated gap.
- The incumbent constructions were not re-verified here. Their sizes and hashes were read from the public addendum.
- Every negative result is a statement about a symmetry class, never about a Ramsey number — a class can be empty while the cell is wide open.
Reproducing
git clone https://github.com/SeverinVisionary/hypergraph-ramsey-bounds cd hypergraph-ramsey-bounds pip install -r requirements.txt bash reproduce.sh --full
The harness re-derives every claim above and refuses to report success for a step that produced no evidence.