betaFeedback

WorksMathematics

New lower bounds for six small hypergraph Ramsey numbers

Abstract

Let R(k,l;t)R(k,l;t) denote the least nn such that every colouring of the tt-subsets of an nn-set with two colours has kk points all of whose tt-subsets have the first colour, or ll points all of whose tt-subsets have the second. We give explicit colourings proving R(4,5;3)≥38R(4,5;3)\ge 38, R(4,6;3)≥71R(4,6;3)\ge 71, R(5,5;3)≥99R(5,5;3)\ge 99, R(5,6;4)≥201R(5,6;4)\ge 201, R(6,6;4)≥601R(6,6;4)\ge 601 and R(6,6;5)≥84R(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↦ax+bx\mapsto ax+b of Zn\mathbb{Z}_n, for n=37n=37, 69 and 97, in the last two cases with one further fixed point. Those of 4-subsets live on the projective line over Fq\mathbb{F}_q, for q=199q=199 and q=599q=599, and are invariant under PSL(2,q)\mathrm{PSL}(2,q) or PGL(2,q)\mathrm{PGL}(2,q), so each is given by a table of qq entries. For 5-subsets we show that, for every prime q≥5q\ge 5, invariance under PGL(2,q)\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 Z83\mathbb{Z}_{83}. By known constructions the bounds give R(5,5,5;3)≥9605R(5,5,5;3)\ge 9605 and Rk(5;3)≥982k−2+1R_k(5;3)\ge 98^{2^{k-2}}+1, and R(6,7;4)≥2001R(6,7;4)\ge 2001, R(7,7;4)≥12001R(7,7;4)\ge 12001 and R(8,8;4)≥588001R(8,8;4)\ge 588001. The colourings, and programs that verify them, accompany the paper as ancillary files.

Introduction

For integers t≥2t \ge2 and k1,…,kr>tk_1,\ldots,k_r > t, the hypergraph Ramsey number R(k1,…,kr;t)R(k_1,\ldots,k_r;t) is the least nn such that every colouring of the tt-subsets of an nn-set with the colours 1,…,r1,\ldots,r has, for some ii, a set of kik_i points all of whose tt-subsets have colour ii. We write Rr(k;t)R_r(k;t) when k1=⋯=kr=kk_1=\cdots=k_r=k. With two colours, which we call 0 and 1, a colouring of the tt-subsets of an nn-set with no kk points whose tt-subsets all have colour 0 and no ll points whose tt-subsets all have colour 1 is a (k,l;t)(k,l;t)-colouring of order nn; it proves R(k,l;t)≥n+1R(k,l;t) \ge n+1. We call the 3-subsets triples.

Very little is known about these numbers for t≥3t \ge3. The only nontrivial value known is R(4,4;3)=13R(4,4;3)=13, computed by McKay and Radziszowski [2]. Radziszowski’s dynamic survey [1, Section 7.1] lists the lower bounds R(4,5;3)≥35R(4,5;3) \ge35, due to Dybizbański [3], and R(4,6;3)≥63R(4,6;3) \ge63 and R(5,5;3)≥88R(5,5;3) \ge88, also due to Dybizbański [4]; these come from explicit colourings. Among the bounds that the survey obtains from recurrence relations and related methods [11, 12] are R(5,6;4)≥67R(5,6;4) \ge67, R(6,6;4)≥133R(6,6;4) \ge133 and R(6,6;5)≥72R(6,6;5) \ge72. Two data deposits of 2026 report further bounds: R(4,6;3)≥64R(4,6;3) \ge64 [6], and R(5,5;4)≥49R(5,5;4) \ge49 and R(5,6;4)≥159R(5,6;4) \ge159 [7]. The last two come from colourings of the projective line that are invariant under PSL⁡(2,q)\operatorname{PSL}(2,q); from the second of them and a recurrence, [7] also states R(6,6;4)≥317R(6,6;4) \ge317, without a colouring.

Theorem 1. R(4,5;3)≥38R(4,5;3) \ge38, R(4,6;3)≥71R(4,6;3) \ge71 and R(5,5;3)≥99R(5,5;3) \ge99.

Theorem 2. R(5,6;4)≥201R(5,6;4) \ge201 and R(6,6;4)≥601R(6,6;4) \ge601.

Theorem 3. R(6,6;5)≥84R(6,6;5) \ge84.

The proofs consist of explicit colourings. Those for Theorem 1, of orders 37, 70 and 98, are invariant under groups of affine maps of Zn\mathbb{Z}_n and are described in Section 2. Those for Theorem 2, of orders 200 and 600, are colourings of the 4-subsets of a projective line that are invariant under its group PSL⁡(2,q)\operatorname{PSL}(2,q) or PGL⁡(2,q)\operatorname{PGL}(2,q) (Section 3). The colouring for Theorem 3, of order 83, is invariant under all affine maps of Z83\mathbb{Z}_{83} (Section 4). Section 5 explains how the colourings were verified and how a reader can verify them again. Table 1 compares the bounds.

NumberPrevious lower boundsNew lower boundOrder of the colouring
R(4,5;3)R(4,5;3)35 [3]3837
R(4,6;3)R(4,6;3)63 [4]; 64 [6]7170
R(5,5;3)R(5,5;3)88 [4]9998
R(5,6;4)R(5,6;4)67 [1]; 159 [7]201200
R(6,6;4)R(6,6;4)133 [1]; 317 [7]601600
R(6,6;5)R(6,6;5)72 [1, 12]8483
R(5,5,5;3)R(5,5,5;3)7570 [1, 5]960598298^2
R(6,7;4)R(6,7;4)661 [1]; 1581†2001–
R(7,7;4)R(7,7;4)3961 [1]; 9481†12001–
R(8,8;4)R(8,8;4)194041 [1]; 464521†588001–

Table 1. Previous and new lower bounds. The first six rows are Theorems 1, 2 and 3; the last four are Corollaries 4 and 5, obtained from them by known constructions. The values marked † are not stated in [7]: we derive them from its bound R(5,6;4)≥159R(5,6;4) \ge159 by the recurrences of Section 6.

Two known constructions turn these bounds into further ones (Section 6). The survey notes that R(5,5;3)≥88R(5,5;3) \ge88 and a product construction of Bruce, Budden and Hiller [5] give R(5,5,5;3)≥7570R(5,5,5;3) \ge7570; the same construction applies to our colouring of order 98. And the recurrences of Song, Ye and Liu [11], from which the survey derives its bounds for R(p,q;4)R(p,q;4), apply to our bound for R(5,6;4)R(5,6;4).

Corollary 4. Rk(5;3)≥98k−2+1R_k(5;3) \ge98^{k-2}+1 for every k≥2k \ge2. In particular R(5,5,5;3)≥9605R(5,5,5;3) \ge9605.

Corollary 5. R(5,7;4)≥401R(5,7;4) \ge401, R(6,7;4)≥2001R(6,7;4) \ge2001, R(7,7;4)≥12001R(7,7;4) \ge12001 and R(8,8;4)≥588001R(8,8;4) \ge588001.

The colourings of triples

Let n≥2n \ge2 and let aa be a unit of Zn\mathbb{Z}_n of multiplicative order ee. We write

G(n,a)={x↦aix+b:0≤i<e, b∈Zn}G(n,a)=\{x\mapsto a^i x+b: 0\le i<e,\ b\in\mathbb{Z}_n\}

for the group of en affine permutations of Zn\mathbb{Z}_n generated by the translations and the multiplication by aa. We also let G(n,a)G(n,a) act on Zn∪{∞}\mathbb{Z}_n\cup\{\infty\}, with every map fixing the point ∞\infty. A colouring of the triples of the point set is G(n,a)G(n,a)-invariant if every map of the group preserves the colour of every triple. Such a colouring is constant on the orbits of the group on triples, so it is described by naming the orbits that receive colour 0.

We define three colourings.

  • C37C_{37} is a G(37,10)G(37,10)-invariant colouring of the triples of Z37\mathbb{Z}_{37}.

  • C70C_{70} is a G(69,4)G(69,4)-invariant colouring of the triples of Z69∪{∞}\mathbb{Z}_{69}\cup\{\infty\}.

  • C98C_{98} is a G(97,4)G(97,4)-invariant colouring of the triples of Z97∪{∞}\mathbb{Z}_{97}\cup\{\infty\}.

In each case colour 0 is the union of the orbits of the triples listed in Appendix § 10, and every other triple has colour 1. Table 2 gives the parameters.

C37C_{37}C70C_{70}C98C_{98}
PointsZ37\mathbb{Z}_{37}Z69∪{∞}\mathbb{Z}_{69}\cup\{\infty\}Z97∪{∞}\mathbb{Z}_{97}\cup\{\infty\}
Multiplier aa (its order)1010 (3)44 (11)44 (24)
Order of the group G(n,a)G(n,a)1117592328
Orbits of triples787472
by size66⋅111+12⋅3766\cdot111+12\cdot3772⋅759+69+2372\cdot759+69+2360⋅2328+8⋅1164+4⋅77660\cdot2328+8\cdot1164+4\cdot776
Orbits in colour 0322736
by size27⋅111+5⋅3727\cdot111+5\cdot3726⋅759+6926\cdot759+6930⋅2328+4⋅1164+2⋅77630\cdot2328+4\cdot1164+2\cdot776
Triples in colour 0318219 80376 048
Triples in colour 1458834 93776 048

Table 2. The three colourings of triples. A term m⋅dm\cdot d stands for mm orbits of size dd.

Proposition 6. C37C_{37} is a (4,5;3)(4,5;3)-colouring of order 37, C70C_{70} is a (4,6;3)(4,6;3)-colouring of order 70, and C98C_{98} is a (5,5;3)(5,5;3)-colouring of order 98.

Computational verification. By the exhaustive search described in § 5.

Theorem 1 follows at once from Proposition 6.

Remark 7 (a colour-reversing symmetry). The map x↦2xx\mapsto2x of Z97∪{∞}\mathbb{Z}_{97}\cup\{\infty\}, which fixes ∞\infty, exchanges the two colours of C98C_{98} on every triple. Since 2 generates the squares modulo 97 and 4 generates the fourth powers, the multiplications by fourth powers preserve C98C_{98} and the multiplications by the other squares reverse it. In particular the two colour classes of C98C_{98} are isomorphic, and each has (983)/2=76 048\binom{98}{3}/2=76\,048 triples.

Remark 8. C98C_{98} is not invariant under the projective map x↦−1/xx\mapsto-1/x of the line Z97∪{∞}\mathbb{Z}_{97}\cup\{\infty\}: that map preserves the colour of only 74 512 of the 152 096 triples. So C98C_{98} is not invariant under PSL⁡(2,97)\operatorname{PSL}(2,97) in its action on this line.

Colourings of the projective line

Let qq be a prime and let Lq=Fq∪{∞}L_q=\mathbb{F}_q\cup\{\infty\} be the projective line over the field with qq elements, a set of q+1q+1 points. The group PGL⁡(2,q)\operatorname{PGL}(2,q) acts on LqL_q by the maps x↦(αx+β)/(γx+δ)x\mapsto(\alpha x+\beta)/(\gamma x+\delta) with αδ−βγ≠0\alpha\delta-\beta\gamma\ne0. For four distinct points a,b,c,da,b,c,d of LqL_q the cross-ratio is

[a,b;c,d]=(a−c)(b−d)(a−d)(b−c)[a,b;c,d]=\frac{(a-c)(b-d)}{(a-d)(b-c)}

where the two factors that contain ∞\infty, if any, are cancelled against each other; for instance [a,b;c,∞]=(a−c)/(b−c)[a,b;c,\infty]=(a-c)/(b-c). The cross-ratio lies in Fq∖{0,1}\mathbb{F}_q\setminus\{0,1\} and is unchanged by every map of PGL⁡(2,q)\operatorname{PGL}(2,q). Reordering the four points replaces a value λ\lambda by one of

λ,1λ,1−λ,11−λ,λλ−1,λ−1λ,\lambda,\quad\frac{1}{\lambda},\quad1-\lambda,\quad\frac{1}{1-\lambda},\quad\frac{\lambda}{\lambda-1},\quad\frac{\lambda-1}{\lambda},

and we call this set of at most six values the class of λ\lambda. Since PGL⁡(2,q)\operatorname{PGL}(2,q) is sharply 3-transitive on LqL_q, two 4-subsets of LqL_q lie in one orbit of the group exactly when their cross-ratios lie in one class. Hence a PGL⁡(2,q)\operatorname{PGL}(2,q)-invariant colouring of the 4-subsets of LqL_q is the same thing as a function τ:Fq∖{0,1}→{0,1}\tau:\mathbb{F}_q\setminus\{0,1\}\to\{0,1\} that is constant on classes: the colour of {a,b,c,d}\{a,b,c,d\} is τ([a,b;c,d])\tau([a,b;c,d]). There are about q/6q/6 classes, so such a colouring is a short table.

Colourings of the 4-subsets of LqL_q that are invariant under the subgroup PSL⁡(2,q)\operatorname{PSL}(2,q) were used by Özdemir [7], with q=47q=47 for R(5,5;4)R(5,5;4) and q=157q=157 for R(5,6;4)R(5,6;4). We searched the PGL⁡(2,q)\operatorname{PGL}(2,q)-invariant colourings, for (5,6;4)(5,6;4) at larger qq and for (6,6;4)(6,6;4) directly, and define three colourings by their functions τ\tau.

  • D194D_{194} is a colouring of the 4-subsets of L193L_{193}; its τ\tau takes the value 0 on 15 of the 33 classes.

  • E500E_{500} is a colouring of the 4-subsets of L499L_{499}; its τ\tau takes the value 0 on 41 of the 84 classes.

  • E600E_{600} is a colouring of the 4-subsets of L599L_{599}; its τ\tau takes the value 0 on 51 of the 100 classes.

Appendix § 11 lists these classes. D194D_{194} has 26 059 632 of its 57 211 376 4-subsets in colour 0; E500E_{500} has 1 273 572 750 of 2 573 031 125; E600E_{600} has 2 740 245 300 of 5 346 164 850.

Proposition 9. D194D_{194} is a (5,6;4)(5,6;4)-colouring of order 194. E500E_{500} and E600E_{600} are (6,6;4)(6,6;4)-colourings of orders 500 and 600.

Computational verification. By the exhaustive searches described in § 5.

The second bound of Theorem 2 follows from E600E_{600}; the first is proved below, with a smaller group. We record E500E_{500} as well because its verification uses no symmetry at all.

Appendix § 12 records the primes qq at which our searches found colourings of these kinds, and those at which the solver reported that the family contains none.

The smaller group. The subgroup PSL⁡(2,q)\operatorname{PSL}(2,q) of PGL⁡(2,q)\operatorname{PGL}(2,q) consists of the maps x↦(αx+β)/(γx+δ)x\mapsto(\alpha x+\beta)/(\gamma x+\delta) for which αδ−βγ\alpha\delta-\beta\gamma is a nonzero square. It is the group used in [7]. Each orbit of PGL⁡(2,q)\operatorname{PGL}(2,q) on the 4-subsets of LqL_q is one orbit of the subgroup or splits into two, so the subgroup admits more invariant colourings. Let q≡3(mod4)q\equiv3\pmod{4}, so that −1-1 is not a square. For distinct a,b,c∈Fqa,b,c\in\mathbb{F}_q the map

g:x↦(c−a)(x−b)(c−b)(x−a)g:x\mapsto\frac{(c-a)(x-b)}{(c-b)(x-a)}

sends aa, bb, cc to ∞\infty, 00, 11 and any fourth point dd to [a,b;c,d][a,b;c,d], and its determinant is

Δ(a,b,c)=(b−a)(c−a)(c−b).\Delta(a,b,c)=(b-a)(c-a)(c-b).

If Δ(a,b,c)\Delta(a,b,c) is a square, gg lies in PSL⁡(2,q)\operatorname{PSL}(2,q). If not, the map x↦1/g(x)x\mapsto1/g(x) does, and it sends aa, bb, cc, dd to 00, ∞\infty, 11 and 1/[a,b;c,d]1/[a,b;c,d]. So every 4-subset of LqL_q lies in the orbit of a set {∞,0,1,λ}\{\infty,0,1,\lambda\}, and a PSL⁡(2,q)\operatorname{PSL}(2,q)-invariant colouring is known from the function σ\sigma on Fq∖{0,1}\mathbb{F}_q\setminus\{0,1\} for which σ(λ)\sigma(\lambda) is the colour of {∞,0,1,λ}\{\infty,0,1,\lambda\}: for distinct a,b,c∈Fqa,b,c\in\mathbb{F}_q and a fourth point dd of LqL_q,

the colour of {a,b,c,d}={σ([a,b;c,d])if Δ(a,b,c) is a square,σ(1/[a,b;c,d])otherwise.(1)\text{the colour of }\{a,b,c,d\}= \begin{cases} \sigma([a,b;c,d]) & \text{if }\Delta(a,b,c)\text{ is a square},\\ \sigma(1/[a,b;c,d]) & \text{otherwise}. \end{cases} \tag*{(1)}

The next lemma says which functions σ\sigma occur. We call the set of values that it describes the narrow class of λ\lambda.

Lemma 10. Let q≡3(mod4)q\equiv3\pmod{4} and λ∈Fq∖{0,1}\lambda\in\mathbb{F}_q\setminus\{0,1\}. The values μ\mu for which {∞,0,1,μ}\{\infty,0,1,\mu\} lies in the orbit of {∞,0,1,λ}\{\infty,0,1,\lambda\} under PSL⁡(2,q)\operatorname{PSL}(2,q) are λ\lambda, 1/(1−λ)1/(1-\lambda) and (λ−1)/λ(\lambda-1)/\lambda if −λ-\lambda and λ−1\lambda-1 are both squares, and all the values in the class of λ\lambda otherwise.

Proof. Write S={∞,0,1,λ}S=\{\infty,0,1,\lambda\}. The map x↦1/(1−x)x\mapsto1/(1-x) has determinant 11 and permutes ∞\infty, 00, 11 cyclically; it and its square send λ\lambda to 1/(1−λ)1/(1-\lambda) and to (λ−1)/λ(\lambda-1)/\lambda, so these values always occur. The maps x↦λ/xx\mapsto\lambda/x and x↦(x−λ)/(x−1)x\mapsto(x-\lambda)/(x-1) send SS to itself and have determinants −λ-\lambda and λ−1\lambda-1; with their product and the identity they form a group VV that permutes the four points of SS transitively.

Suppose that −λ-\lambda or λ−1\lambda-1 is not a square, so that some v∈Vv\in V lies outside PSL⁡(2,q)\operatorname{PSL}(2,q). If μ\mu lies in the class of λ\lambda, some h∈PGL⁡(2,q)h\in\operatorname{PGL}(2,q) sends SS to {∞,0,1,μ}\{\infty,0,1,\mu\}, and so does hvhv; one of the two lies in PSL⁡(2,q)\operatorname{PSL}(2,q). Suppose now that both are squares, so that VV lies in PSL⁡(2,q)\operatorname{PSL}(2,q), and let h∈PSL⁡(2,q)h\in\operatorname{PSL}(2,q) send SS to {∞,0,1,μ}\{\infty,0,1,\mu\}. Choosing v∈Vv\in V with hv(λ)=μhv(\lambda)=\mu, we obtain a map hvhv of PSL⁡(2,q)\operatorname{PSL}(2,q) that sends {∞,0,1}\{\infty,0,1\} to itself. The six maps of PGL⁡(2,q)\operatorname{PGL}(2,q) that do this are xx, 1/(1−x)1/(1-x) and (x−1)/x(x-1)/x, of determinant 11, and 1/x1/x, 1−x1-x and x/(x−1)x/(x-1), of determinant −1-1, which is not a square. So hvhv is one of the first three, and μ=hv(λ)\mu=hv(\lambda) is one of λ\lambda, 1/(1−λ)1/(1-\lambda) and (λ−1)/λ(\lambda-1)/\lambda. □\square

Hence, for q≡3(mod4)q\equiv3\pmod{4}, the PSL⁡(2,q)\operatorname{PSL}(2,q)-invariant colourings of the 4-subsets of LqL_q are given through (1) by the functions σ\sigma that are constant on narrow classes, and the orbits of the group on 4-subsets correspond to the narrow classes.

We define F200F_{200} as the PSL⁡(2,199)\operatorname{PSL}(2,199)-invariant colouring of the 4-subsets of L199L_{199} whose function σ\sigma takes the value 00 on the 20 narrow classes listed in Appendix B, out of 43, and the value 11 on the others. It has 27 909 750 of its 64 684 950 4-subsets in colour 0.

Proposition 11. F200F_{200} is a (5,6;4)(5,6;4)-colouring of order 200.

Computational verification. By the exhaustive search described in § 5. □\square

So R(5,6;4)≥201R(5,6;4)\geq201, which is the first bound of Theorem 2. The colouring D194D_{194} gives R(5,6;4)≥195R(5,6;4)\geq195 with the larger group.

A colouring of 5-subsets

Colourings with the full symmetry of a projective line cannot be used for R(6,6;5)R(6,6;5), for the following reason.

Lemma 12. Let a group GG act on a set XX, let t≥2t \ge2, and let SS be a set of t+1t+1 points of XX. If some subgroup of GG maps SS to itself and permutes its points transitively, then in every GG-invariant colouring of the tt-subsets of XX all tt-subsets of SS have the same colour. In particular there is then no GG-invariant (t+1,t+1;t)(t+1,t+1;t)-colouring of XX.

Proof. The tt-subsets of SS are the complements in SS of its points, so the subgroup permutes them transitively, and an invariant colouring gives them one colour.

For every prime q≥5q \ge5 the lemma applies to PGL⁡(2,q)\operatorname{PGL}(2,q) acting on LqL_q, with t=5t=5. For q=5q=5 the group permutes the six points of L5L_5 transitively. For q=7q=7 the maps x↦axx \mapsto ax with a≠0a \ne0 permute the six points 1,…,61,\ldots,6 transitively. For q≥11q \ge11 consider the subgroup that maps {0,1,∞}\{0,1,\infty\} to itself. It has six elements. Each of its three elements of order two fixes at most two points of LqL_q, and its two elements of order three, which are inverse to each other, fix the same points, at most two. So at most eight points are fixed by a non-identity element, and some point of LqL_q has an orbit of six points, on which the subgroup acts transitively. In each case Lemma 12 shows that no PGL⁡(2,q)\operatorname{PGL}(2,q)-invariant (6,6;5)(6,6;5)-colouring of LqL_q exists.

Let ApA_p be the group of all maps x↦ax+bx \mapsto ax+b of Zp\mathbb{Z}_p with a≠0a \ne0, for a prime p≥5p \ge5. It has p(p−1)p(p-1) elements. If p≡1(mod6)p \equiv1 \pmod{6}, the lemma applies to ApA_p as well: the six solutions of a6=1a^6=1 in Zp\mathbb{Z}_p are permuted transitively by the multiplications by these same six numbers. If p≡5(mod6)p \equiv5 \pmod{6}, it does not apply: a group that permutes six points transitively has an order divisible by 6, and 3 does not divide p(p−1)p(p-1). This is the case for p=83p=83, where p(p−1)=2⋅41⋅83p(p-1)=2 \cdot41 \cdot83.

The group ApA_p is sharply 2-transitive: for two points u≠vu \ne v the map x↦(x−u)/(v−u)x \mapsto(x-u)/(v-u) sends uu to 0 and vv to 1. So every 5-subset of Zp\mathbb{Z}_p can be moved to one that contains 0 and 1, and an ApA_p-invariant colouring of the 5-subsets is determined by its colours on the (p−23)\binom{p-2}{3} subsets that contain 0 and 1.

We define H83H_{83} as the A83A_{83}-invariant colouring of the 5-subsets of Z83\mathbb{Z}_{83} whose colours on the (813)=85 320\binom{81}{3}=85\,320 subsets through 0 and 1 are given in the ancillary file anc/R665_83_points_short.json. It has 14 500 183 of its 29 034 396 5-subsets in colour 0, and the 5-subsets fall into 4276 orbits of A83A_{83}.

Proposition 13. H83H_{83} is a (6,6;5)(6,6;5)-colouring of order 83.

Computational verification. By the exhaustive search described in § 5.

Theorem 3 follows.

Verification

The check. Let tt be the size of the subsets that are coloured, cc a colour and ss a size. A set of points all of whose tt-subsets have colour cc is called one-coloured. Our programs search for a one-coloured set of ss points by backtracking: a one-coloured set is extended by a point larger than all of its points, and the new point is accepted only if every tt-subset that consists of it and t−1t-1 points of the set has colour cc. The search is exhaustive, because every initial segment of a one-coloured set, in increasing order of its points, is one-coloured. A colouring is accepted as a (k,l;t)(k,l;t)-colouring only if the search finds no one-coloured set of kk points in colour 0 and none of ll points in colour 1. For the colourings of triples the sets so excluded number (374)=66 045\binom{37}{4}=66\,045 and (374)=435 897\binom{37}{4}=435\,897 for C37C_{37}; (704)=916 895\binom{70}{4}=916\,895 and (706)=131 115 985\binom{70}{6}=131\,115\,985 for C70C_{70}; and (985)=67 910 864\binom{98}{5}=67\,910\,864 for each colour of C98C_{98}.

Independent programs for the colourings of triples. Each of C37C_{37}, C70C_{70} and C98C_{98} was checked by several independently written programs, none of which shares code with the search that produced the colourings. One of them, anc/verify.py, accompanies this paper. It uses only the Python standard library and reads only a plain list of the triples with their colours, so it depends on no ordering convention. It was also run on altered colourings in which a one-coloured set had been planted, and reported it. On an ordinary laptop anc/verify.py needs a few seconds for each colouring.

From the paper to the files. The script anc/rebuild_from_rule.py rebuilds each colouring from its group and the representatives of Appendix § 10, and compares the result with the stored colouring. So the printed data and the ancillary files describe the same three objects. § 8 gives SHA-256 digests.

The colourings of 4-subsets. For D194D_{194}, E500E_{500} and E600E_{600} the colour of a 4-subset is computed from the table τ\tau and the cross-ratio of its points taken in increasing order, with ∞\infty as the last point. The program anc/verify_crossratio.c treats this as a plain function on 4-subsets and runs the search described above, with bit vectors, for 4-subsets in place of triples. It assumes nothing about the table and uses no symmetry.

  • For D194D_{194} it examined all 83 870 080 one-coloured sets of 5 points in colour 1; none extends to 6 points, and no 5 points are one-coloured in colour 0.

  • For E500E_{500} it examined 6 411 351 600 one-coloured sets of 5 points in colour 0 and 6 647 428 500 in colour 1; none extends to 6 points.

  • For E600E_{600} the program first confirmed, on each of the 5 346 164 850 4-subsets, that the map x↦x+1x \mapsto x+1 of L599L_{599}, which fixes ∞\infty, preserves the colour. Every set of at least two points contains a point other than ∞\infty and so has a translate through the point 0; the program then examined the 147 041 921 and 121 788 680 one-coloured sets of 5 points through 0 in the two colours, and none extends to 6 points.

Each run began with controls: a colouring known to be valid had to pass, and tables altered on purpose had to fail, among them one that x↦x+1x \mapsto x+1 does not preserve, which the program must refuse. On E318E_{318}, the analogous colouring for q=317q=317, the search through 0 and the search without symmetry gave the same answer.

D194D_{194} was checked a second time in a different way: the colouring was written out in full, one colour for each of its 57 211 376 4-subsets, and the program anc/verify_rank.c examined every one of the (1945)=2 174 032 288\binom{194}{5}=2\,174\,032\,288 sets of 5 points and of the (1946)=68 482 017 072\binom{194}{6}=68\,482\,017\,072 sets of 6 points. The two programs also agree on the number of 4-subsets in colour 0.

A second program for the tables τ\tau. The program anc/verify_projective.cpp was written independently of the first. It checks that a table is constant on the classes of cross-ratio values, so that the colouring is invariant under PGL⁡(2,q)\operatorname{PGL}(2,q), and then examines every set of the size in question that contains 00, 11 and ∞\infty. This is a complete check, because PGL⁡(2,q)\operatorname{PGL}(2,q) is 3-transitive on LqL_q: every one-coloured set of at least three points has a one-coloured image that contains these three points. For D194D_{194} the program examined (1912)=18 145\binom{191}{2}=18\,145 sets of 5 points and (1913)=1 143 135\binom{191}{3}=1\,143\,135 sets of 6 points; for E500E_{500}, (4973)=20 337 240\binom{497}{3}=20\,337\,240 sets of 6 points; and for E600E_{600}, (5973)=35 284 690\binom{597}{3}=35\,284\,690 sets of 6 points. None of them is one-coloured in a forbidden colour. The script anc/check_projective.py compiles the program and runs it on the three tables.

The colouring F200F_{200}. F200F_{200} was written out in full, one colour for each of its 64 684 95064\,684\,950 4-subsets, and anc/verify_rank.c examined every one of the (2005)=2 535 650 040\binom{200}{5}=2\,535\,650\,040 sets of 5 points and of the (2006)=82 408 626 300\binom{200}{6}=82\,408\,626\,300 sets of 6 points. This check uses no symmetry and no property of the group. The script anc/rebuild_psl_rule.py confirms that the function σ\sigma is constant on narrow classes, rebuilds all the colours from σ\sigma and (1), and compares the SHA-256 digest of the result with that of the colouring written out in full; so the description in Section 3 and the file that was checked are the same colouring. It also examines the (1972)=19 306\binom{197}{2}=19\,306 sets of 5 points and the (1973)=1 254 890\binom{197}{3}=1\,254\,890 sets of 6 points that contain ∞\infty, 00 and 11, and finds none that is one-coloured in a forbidden colour. Every set of at least four points of L199L_{199} has an image under PSL⁡(2,199)\operatorname{PSL}(2,199) that contains these three points, so this is a second complete check, by another program and another method.

The colouring of 5-subsets. H83H_{83} was written out in full from its short form, and anc/verify_rank.c examined every one of the (836)=377 447 148\binom{83}{6}=377\,447\,148 sets of 6 points, for each colour. The search program’s own check, written independently of it and using no symmetry, agrees. The script anc/rebuild_short_form.py rebuilds the full colouring from the short form and compares its SHA-256 digest.

Consequences

The following construction is the one of Bruce, Budden and Hiller [5] that the survey [1] uses; we include the short argument for completeness.

Lemma 14. Let k≥2k \ge2. Suppose that the triples of an NN-set XX can be coloured with kk colours so that no 5 points have all their triples in one colour. Then the triples of X×XX \times X can be coloured with k+1k+1 colours with the same property.

Proof. Let χ\chi be the given colouring, with colours 1,…,k1,\ldots,k. Colour a triple

T={(x1,y1),(x2,y2),(x3,y3)}T=\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}

of X×XX \times X as follows. If x1,x2,x3x_1,x_2,x_3 are distinct, TT gets the colour χ({x1,x2,x3})\chi(\{x_1,x_2,x_3\}). If x1=x2=x3x_1=x_2=x_3, then y1,y2,y3y_1,y_2,y_3 are distinct and TT gets the colour χ({y1,y2,y3})\chi(\{y_1,y_2,y_3\}). Otherwise exactly two of x1,x2,x3x_1,x_2,x_3 are equal, and TT gets the new colour k+1k+1.

Let SS be a set of 5 points of X×XX \times X whose triples all have the same colour cc. Suppose first that c≤kc \le k. If two points of SS have the same first coordinate and a third point has a different one, these three points form a triple of colour k+1k+1. So the first coordinates of the points of SS are either all distinct or all equal. In the first case they form 5 points of XX whose triples all have colour cc under χ\chi; in the second case the second coordinates do. Both contradict the assumption on χ\chi. Suppose now that c=k+1c=k+1. If three points of SS have distinct first coordinates, their triple

::: has a colour at most kk. Otherwise the 5 points of SS have at most two distinct first coordinates, so three of them share one, and their triple has a colour at most kk. In both cases we have a contradiction.

Proof of Corollary 4. By Proposition 6, the triples of a 98-set can be coloured with 2 colours so that no 5 points have all their triples in one colour. Applying Lemma 14 k−2k-2 times gives such a colouring with kk colours on 982k−298^{2^{k-2}} points. For k=3k=3 this is 982=960498^2=9604 points.

Proof of Corollary 5. The survey [1 Section 7.1] quotes two recurrences of Song, Ye and Liu [11]. We use them only in the following ranges:

R(p,q;4)≥2R(p−1,q;4)−1for p≥6, q≥5,R(p,q;4) \ge2R(p-1,q;4)-1 \qquad\text{for } p \ge6,\ q \ge5,
R(p,q;4)≥(p−1)R(p−1,q;4)−p+2for p≥6, q≥7.R(p,q;4) \ge(p-1)R(p-1,q;4)-p+2 \qquad\text{for } p \ge6,\ q \ge7.

Together with the symmetry R(p,q;4)=R(q,p;4)R(p,q;4)=R(q,p;4) and Theorem 2, the first gives R(7,5;4)≥2⋅201−1=401R(7,5;4) \ge2\cdot201-1=401. The second, applied to (p,q)=(6,7)(p,q)=(6,7), (7,7)(7,7), (8,7)(8,7) and (8,8)(8,8) in turn, gives R(6,7;4)≥5⋅401−4=2001R(6,7;4) \ge5\cdot401-4=2001, R(7,7;4)≥6⋅2001−5=12 001R(7,7;4) \ge6\cdot2001-5=12\,001, R(8,7;4)≥7⋅12 001−6=84 001R(8,7;4) \ge7\cdot12\,001-6=84\,001 and R(8,8;4)≥7⋅84 001−6=588 001R(8,8;4) \ge7\cdot84\,001-6=588\,001. The values 661, 3961 and 194 041 that the survey lists for R(6,7;4)R(6,7;4), R(7,7;4)R(7,7;4) and R(8,8;4)R(8,8;4) arise in the same way from R(5,6;4)≥67R(5,6;4) \ge67. From the bound R(5,6;4)≥159R(5,6;4) \ge159 of [7] the same steps give 1581, 9481 and 464 521; these are the values marked † in Table 1.

Remarks on the search

Method. The colourings of triples were found by exact search over invariant colourings. For a chosen group G(n,a)G(n,a), with or without a fixed point, there is one Boolean unknown for each orbit of triples. The group contains all translations, and every set of at least three points contains a point of Zn\mathbb{Z}_n, so it can be translated to a set that contains the point 0; hence it suffices to forbid the one-coloured sets of the relevant sizes that contain 0. The resulting formulas were given to the SAT solvers Glucose [9] and CaDiCaL [10] through the PySAT toolkit [8]. For C98C_{98} we required in addition that x↦2xx\mapsto2x exchange the colours (Remark 7), which leaves 36 unknowns; the solver answered in 14 seconds. C70C_{70} has 74 unknowns and took six minutes.

The tables τ\tau of § 3 were found in the same way, with one unknown for each class of cross-ratio values: since PGL⁡(2,q)\operatorname{PGL}(2,q) is 3-transitive, it suffices to forbid the one-coloured sets that contain 0, 1 and ∞\infty. For F200F_{200} there is one unknown for each narrow class, and the sets forbidden are those that contain ∞\infty, 0 and one of two further fixed points, a square and a non-square. For q≤499q\le499 the SAT solver answered at once. For E600E_{600} and for H83H_{83}, which has 4276 unknowns, we used a local search of the probSAT type [13] instead; it found E600E_{600} in about 6⋅1046\cdot10^4 steps and H83H_{83} in about 3⋅1083\cdot10^8. A local search can only find a colouring; what it finds is checked as in § 5.

What the search did not find. The following are reports of a SAT solver on the encoded families, or of a local search where that is said; no proof certificate was recorded. They describe the limits of these particular families, establish no upper bound, and say nothing about other colourings.

  • For R(5,5;3)R(5,5;3): on Z97\mathbb{Z}_{97} with two fixed points (99 points), the solver returned UNSAT for the G(97,4)G(97,4)-invariant family and for the G(97,2)G(97,2)-invariant family. For the larger G(97,16)G(97,16)-invariant family the search ended without an answer.

  • For R(4,6;3)R(4,6;3): on Z69\mathbb{Z}_{69} with two fixed points (71 points), the solver returned UNSAT for the G(69,4)G(69,4)-invariant family.

  • For R(4,5;3)R(4,5;3): on Z37\mathbb{Z}_{37} with one fixed point (38 points), the solver returned UNSAT for the G(37,10)G(37,10)-invariant family. The searches we ran on Z39\mathbb{Z}_{39} and Z43\mathbb{Z}_{43} ended without an answer.

  • For R(6,6;4)R(6,6;4): on L701L_{701} (702 points), neither the local search nor the SAT solver gave an answer in the time allowed.

  • For R(5,6;4)R(5,6;4): the solver returned UNSAT for the PGL⁡(2,q)\operatorname{PGL}(2,q)-invariant family at every prime qq with 197≤q≤331197 \le q \le331, and for the PSL⁡(2,q)\operatorname{PSL}(2,q)-invariant family at every prime qq with 211≤q≤331211 \le q \le331 (Appendix C).

  • For R(6,6;5)R(6,6;5): on Z83\mathbb{Z}_{83} with one fixed point (84 points), both with all multipliers and with the squares as multipliers, and on Z89\mathbb{Z}_{89} with all multipliers (89 points), the local search found no colouring. A local search cannot show that none exists.

Data availability

The colourings accompany this paper as ancillary files, which are listed in Table 3.

FileContent
anc/R453_37_points.json, .csvC37C_{37}
anc/R463_70_points.json, .csvC70C_{70}
anc/R553_98_points.json, .csvC98C_{98}
anc/R564_194_points_rule.jsonD194D_{194}
anc/R564_200_points_rule.jsonF200F_{200}: the table σ\sigma
anc/R564_200_points.txt.gzF200F_{200}, written out in full
anc/R664_500_points_rule.jsonE500E_{500}
anc/R664_600_points_rule.jsonE600E_{600}
anc/R665_83_points_short.jsonH83H_{83}
anc/verify.pythe check of Section 5, for triples
anc/rebuild_from_rule.pyrebuilds a colouring from Appendix A
anc/verify_crossratio.cthe check for D194D_{194}, E500E_{500}, E600E_{600}
anc/verify_projective.cppthe second check for the same three
anc/check_projective.pycompiles and runs it
anc/verify_rank.cexamines every set, for a colouring written out in full
anc/rebuild_short_form.pywrites H83H_{83} out in full
anc/rebuild_psl_rule.pyrebuilds F200F_{200} from σ\sigma and compares
anc/README.mdformats and usage

Table 3. The ancillary files.

  • Triples. Each of C37C_{37}, C70C_{70} and C98C_{98} comes in two forms: a JSON file that holds the colouring as a string of the characters 0 and 1, one for each triple of the points 0,…,n−10,\ldots,n-1 in lexicographic order, together with its group and orbit representatives; and a CSV file with one row for each triple, giving its three points and its colour. The point ∞\infty is the last point, numbered 69 in C70C_{70} and 97 in C98C_{98}.

  • 4-subsets. Each of D194D_{194}, E500E_{500} and E600E_{600} is a JSON file with its table τ\tau as a string of qq characters (the places 0 and 1 are not used) and the list of classes of colour 0. The points are 0,…,q−10,\ldots,q-1 and ∞\infty, which is the last point, numbered qq. F200F_{200} comes in two forms: a JSON file of the same kind, with its table σ\sigma and the list of narrow classes of colour 0; and a text file, compressed with gzip, with one character for each 4-subset of the points 0,…,1990,\ldots,199 in lexicographic order, the point ∞\infty being numbered 199.

  • 5-subsets. H83H_{83} is a JSON file with the colours of the 85 320 subsets through 0 and 1, in lexicographic order.

SHA-256 digests of the colouring strings of C37C_{37}, C70C_{70}, C98C_{98}, F200F_{200} and H83H_{83}, and of the tables τ\tau of D194D_{194}, E500E_{500} and E600E_{600}:

  • C37C_{37}: 995fb6bb93ca2b0be5809d981cefbaa72712ce8b1463809dd66376af9f6c0e16

  • C70C_{70}: f7c37ea5e0b72ad3773b13c0a291697f336998170931f208f6588352ce31c662

  • C98C_{98}: 53e042c9f44d870cdccd4d86b5e45003fadf981d7757580f863632a945f5e17d

  • D194D_{194}: 477e5506f17a2db541c806f9c57ca20c2e1d9adde4918dd01c29075d3092dbe7

  • F200F_{200}: 621a303b0e947fb3e52799288ba7f8ef883f3260f6a7e260c843eb902001602d

  • E500E_{500}: 3ed928e24dabb537c6d26c5da0251af9562e40f9be4c9a2f82b7ff55a97931a1

  • E600E_{600}: c4f4b30a65c395b1d7e8fd014a6cd17a31acb70672ef7294da95a934cf4a7a6f

  • H83H_{83}: b196450e13f22883d9e9c974c3f203b0a958db0560110c2cde73c5bd803daadb

Acknowledgments

The author thanks Stanisław P. Radziszowski for maintaining the dynamic survey on which this work relies. Computational searches were conducted using the author’s Solon research software. AI-based tools were used in the searches and in the preparation of this manuscript; the author is responsible for all of its content. The reported lower bounds are independently verifiable from the ancillary files.

Orbit representatives

For each colouring we list one triple from each orbit in colour 0; the triple listed is the lexicographically first of its orbit. Colour 0 is the union of the orbits of these triples under the group named, and every other triple has colour 1.

C37C_{37}: G(37,10)G(37, 10) on Z37\mathbb{Z}_{37}, 32 orbits. {0,1,2}\{0,1,2\}, {0,1,3}\{0,1,3\}, {0,1,4}\{0,1,4\}, {0,1,5}\{0,1,5\}, {0,1,6}\{0,1,6\}, {0,1,12}\{0,1,12\}, {0,1,14}\{0,1,14\}, {0,1,20}\{0,1,20\}, {0,1,21}\{0,1,21\}, {0,1,24}\{0,1,24\}, {0,1,25}\{0,1,25\}, {0,1,30}\{0,1,30\}, {0,1,33}\{0,1,33\}, {0,2,9}\{0,2,9\}, {0,2,14}\{0,2,14\}, {0,2,15}\{0,2,15\}, {0,2,18}\{0,2,18\}, {0,2,22}\{0,2,22\}, {0,2,23}\{0,2,23\}, {0,2,31}\{0,2,31\}, {0,2,32}\{0,2,32\}, {0,2,33}\{0,2,33\}, {0,3,6}\{0,3,6\}, {0,3,8}\{0,3,8\}, {0,3,9}\{0,3,9\}, {0,3,16}\{0,3,16\}, {0,3,19}\{0,3,19\}, {0,5,18}\{0,5,18\}, {0,5,21}\{0,5,21\}, {0,6,14}\{0,6,14\}, {0,6,29}\{0,6,29\}, {0,9,25}\{0,9,25\}.

C70C_{70}: G(69,4)G(69, 4) on Z69∪{∞}\mathbb{Z}_{69} \cup\{\infty\}, 27 orbits. {0,1,3}\{0,1,3\}, {0,1,5}\{0,1,5\}, {0,1,8}\{0,1,8\}, {0,1,9}\{0,1,9\}, {0,1,10}\{0,1,10\}, {0,1,13}\{0,1,13\}, {0,1,18}\{0,1,18\}, {0,1,20}\{0,1,20\}, {0,1,23}\{0,1,23\}, {0,1,28}\{0,1,28\}, {0,1,33}\{0,1,33\}, {0,1,36}\{0,1,36\}, {0,1,37}\{0,1,37\}, {0,1,42}\{0,1,42\}, {0,1,43}\{0,1,43\}, {0,1,44}\{0,1,44\}, {0,1,55}\{0,1,55\}, {0,1,60}\{0,1,60\}, {0,1,62}\{0,1,62\}, {0,2,39}\{0,2,39\}, {0,2,47}\{0,2,47\}, {0,2,48}\{0,2,48\}, {0,2,∞}\{0,2,\infty\}, {0,3,15}\{0,3,15\}, {0,3,21}\{0,3,21\}, {0,3,27}\{0,3,27\}, {0,23,∞}\{0,23,\infty\}.

C98C_{98}: G(97,4)G(97, 4) on Z97∪{∞}\mathbb{Z}_{97} \cup\{\infty\}, 36 orbits. {0,1,7}\{0,1,7\}, {0,1,10}\{0,1,10\}, {0,1,11}\{0,1,11\}, {0,1,12}\{0,1,12\}, {0,1,13}\{0,1,13\}, {0,1,15}\{0,1,15\}, {0,1,19}\{0,1,19\}, {0,1,20}\{0,1,20\}, {0,1,27}\{0,1,27\}, {0,1,29}\{0,1,29\}, {0,1,30}\{0,1,30\}, {0,1,31}\{0,1,31\}, {0,1,32}\{0,1,32\}, {0,1,33}\{0,1,33\}, {0,1,34}\{0,1,34\}, {0,1,36}\{0,1,36\}, {0,1,39}\{0,1,39\}, {0,1,40}\{0,1,40\}, {0,1,41}\{0,1,41\}, {0,1,46}\{0,1,46\}, {0,1,49}\{0,1,49\}, {0,1,∞}\{0,1,\infty\}, {0,2,10}\{0,2,10\}, {0,2,12}\{0,2,12\}, {0,2,15}\{0,2,15\}

{0,2,23}, {0,2,25}, {0,2,28}, {0,2,42}, {0,2,44}, {0,5,19}, {0,5,26}, {0,5,34}, {0,5,39}, {0,5,51}, {0,5,∞}.\{0,2,23\},\ \{0,2,25\},\ \{0,2,28\},\ \{0,2,42\},\ \{0,2,44\},\ \{0,5,19\},\ \{0,5,26\},\ \{0,5,34\},\ \{0,5,39\},\ \{0,5,51\},\ \{0,5,\infty\}.

Classes of cross-ratio values

For each colouring of Section 3 we list the classes on which τ\tau takes the value 0, each by its smallest element as an integer in {2,…,q−1}\{2,\ldots,q-1\}. On every other class τ\tau is 1. For F200F_{200} the function is σ\sigma and the classes are the narrow classes of Section 3.

D194D_{194}: q=193q=193, 15 of 33 classes. 2, 3, 5, 6, 9, 11, 12, 13, 15, 20, 21, 22, 31, 40, 68.

F200F_{200}: q=199q=199, the group PSL⁡(2,199)\operatorname{PSL}(2,199), 20 of 43 narrow classes. The function σ\sigma takes the value 0 on the narrow classes of the following values dd, so that colour 0 is the union of the orbits of the 4-subsets {∞,0,1,d}\{\infty,0,1,d\}: d=2d=2, 3, 7, 11, 12, 13, 15, 17, 24, 27, 29, 35, 37, 38, 41, 55, 68, 73, 81, 107.

E500E_{500}: q=499q=499, 41 of 84 classes. 3, 5, 6, 9, 10, 11, 12, 14, 15, 17, 19, 20, 24, 27, 32, 34, 39, 43, 47, 56, 63, 67, 71, 72, 75, 77, 82, 92, 110, 115, 116, 117, 119, 124, 144, 168, 172, 177, 191, 223, 224.

E600E_{600}: q=599q=599, 51 of 100 classes. 3, 4, 5, 10, 12, 14, 15, 16, 18, 20, 22, 23, 24, 33, 34, 35, 37, 38, 39, 42, 43, 49, 53, 55, 65, 66, 67, 69, 72, 79, 81, 84, 85, 90, 95, 103, 104, 106, 112, 115, 127, 138, 139, 143, 146, 147, 174, 197, 199, 241, 258.

Where the searches found colourings

This appendix records the primes qq at which our searches found colourings of LqL_q that are invariant under the group named. Unless it is said otherwise, the answers are those of a SAT solver, which decided each of these small formulas in both directions. No proof certificate was recorded for the answers UNSAT. They concern only the invariant family named and establish no upper bound.

(5, 6; 4), the group PGL⁡(2,q)\operatorname{PGL}(2,q). Among the 42 primes qq with 101≤q≤331101 \le q \le331, the solver found a colouring for q=101q=101, 103, 107, 109, 113, 127, 131, 137, 139, 151, 157, 163, 179, 191 and 193, and returned UNSAT for the other 27. For q=193q=193 it reported that the colouring is unique.

(5, 6; 4), the group PSL⁡(2,q)\operatorname{PSL}(2,q). Among the 30 primes qq with 163≤q≤331163 \le q \le331, the solver found a colouring for q=163q=163, 167, 179, 191, 193 and 199, and returned UNSAT for the other 24. For q=167q=167 and q=199q=199 the larger group PGL⁡(2,q)\operatorname{PGL}(2,q) admits none.

(6, 6; 4), the group PGL⁡(2,q)\operatorname{PGL}(2,q). Colourings were found for every prime qq with 7≤q≤1517 \le q \le151, and for q=157q=157, 199, 251, 317, 331, 337, 347, 349, 359, 397, 449, 499 and 599; the one for q=599q=599 was found by local search. For q=701q=701 neither the local search nor the solver gave an answer in the time allowed.

(5, 5; 4), the group PGL(2, qq). Among the primes qq with 7≤q≤1997 \le q \le199, the solver found a colouring for q=7q = 7, 13, 17, 23 and 47, each time unique up to exchanging the two colours, and returned UNSAT for the others. The case q=47q = 47 is a colouring of order 48; it agrees with the bound R(5,5;4)≥49R(5, 5; 4) \ge49 of [7], and we make no claim for it.

References

References

  1. [1]S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin., Dynamic Survey DS1, revision #18 (24 April 2026), https://doi.org/10.37236/21.
  2. [2]B. D. McKay and S. P. Radziszowski, The first classical Ramsey number for hypergraphs is computed, Proceedings of the Second Annual ACM–SIAM Symposium on Discrete Algorithms (SODA ’91), San Francisco, 1991, 304–308.DOI
  3. [3]J. Dybizbański, A lower bound on the hypergraph Ramsey number R(4, 5; 3), Contrib. Discrete Math. 13 (2018), no. 2, 112–115.
  4. [4]J. Dybizbański, personal communication to S. P. Radziszowski (2018), cited in [1]; addendum to [3] at https://inf.ug.edu.pl/ramsey.
  5. [5]M. Bruce, M. Budden, and J. Hiller, Lexicographic products of r-uniform hypergraphs and some applications to hypergraph Ramsey theory, Australas. J. Combin. 70 (2018), 390–401.
  6. [6]H. Yang, Three improved lower bounds for hypergraph Ramsey numbers, data deposit, Zenodo, 2026, https://doi.org/10.5281/zenodo.24301648.
  7. [7]K. Özdemir, Lower bounds for the hypergraph Ramsey numbers R(5, 5; 4) and R(5, 6; 4) from PSL(2, q)-invariant colourings, data deposit, Zenodo, 27 October 2026, https://doi.org/10.5281/zenodo.23689461.
  8. [8]A. Ignatiev, A. Morgado, and J. Marques-Silva, PuSAT: A Python toolkit for prototyping with SAT oracles, in: Theory and Applications of Satisfiability Testing – SAT 2018, Lecture Notes in Comput. Sci. 10929, Springer, 2018, 428–437.DOI
  9. [9]G. Audemard and L. Simon, Predicting learnt clauses quality in modern SAT solvers, in: Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), 399–404.
  10. [10]A. Biere, K. Fazekas, M. Fleury, and M. Heisinger, CaDiCaL, Kissat, Paracooba, Plingeling and Treengeling entering the SAT Competition 2020, in: Proceedings of SAT Competition 2020 – Solver and Benchmark Descriptions, Department of Computer Science Report Series B, vol. B-2020-1, University of Helsinki, 2020, 51–53.
  11. [11]E. Song, W. Ye, and Y. Liu, New lower bounds for Ramsey number R(p, q; 4), Discrete Math. 145 (1995), 343–346.DOI
  12. [12]S. C. Liu, Lower bounds for small Ramsey numbers on hypergraphs, preprint, 2019, arXiv:1906.00132.arxiv.org/abs/1906.00132
  13. [13]A. Balint and U. Schöning, Choosing probability distributions for stochastic local search and the role of make versus break, in: Theory and Applications of Satisfiability Testing – SAT 2012, Lecture Notes in Comput. Sci. 7317, Springer, 2012, 16–29.DOI

Paper details

vlnc:W_kqsbfk7v
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI-based tools

View statement
Looking for related papers…
Contents