A New Method that can Generate Ramsey Colourings for Eight and Thirteen Colours

1. Introduction

• The problem is to colour the edges of a complete graph using a finite set of colours while satisfying specified triangle conditions.The colouring is required to use every colour, as stated in the formal setup.Source: §1 · p. 1
• A Ramsey colouring has no monochromatic triangles, and every permitted non-monochromatic triangle must appear everywhere it can.The latter condition requires every vertex to meet every colour and each permitted pair of colours around an edge to occur at a vertex.Source: §1 · p. 1
• The authors report the first colourings for 8 and 13 colours using an approach adapted from Comer’s finite-field method.The passage describes the approach as general-purpose.Source: §1 · p. 1

2. Related Work

• Alm and Manske [1] and Kowalski published computational investigations of finite-field constructions using Comer’s method.Source: §2 · p. 2
• The authors depart from those investigations by fusing pairs of cyclotomic classes into coarser relations.They use “fusion” for combining relations, following Bannai and Ito.Source: §2 · p. 2
• They also test colouring non-isomorphism using an incidence-graph reduction and nauty/Traces [5].Source: §2 · p. 2

3. Background

• For a prime power q, F_q is the field with q elements, and its nonzero elements form a cyclic multiplicative group.When q ≡ 1 (mod r), the subgroup H = ⟨g^r⟩ gives r cosets.Source: §3 · p. 2
• For p = 449, the example takes q = p, primitive root g = 3, and r = 16.The fine cosets are given as C_a = {g^(a+16t) : t ∈ Z, 0 ≤ t < (q − 1)/16}.Source: §3 · p. 2
• The method calls each C_a a fine set and fuses fine cosets into coarser sets to form partitions suitable for the colourings.Source: §3 · p. 2

4. FBF Method: Adapting Comer’s Finite-Field Method for 8 and 13 Colours

• The search uses r = 2n fine cosets and fuses them in pairs to form n coarse sets, each of size (q − 1)/n.More generally, r = sn allows blocks of s cosets; the paper focuses on pairs.Source: §4 · p. 2
• A candidate pair-fusion must satisfy inverse closure and the condition D_a,b + D_a,b = F_p \ D_a,b for monochromatic admissibility.The sumset condition encodes the absence of monochromatic triangles and the existence of permitted triangles containing two edges of the same colour.Source: §4 · p. 3
• The compatibility graph links disjoint surviving fused pairs when their sumset is F_p \ {0}; an n-clique supplies a collection of candidate colour classes.Source: §4 · p. 3

4.1. Reduction to index differences and mixed pairings.

• Multiplication by a field element reduces an individual pair D_a,b to D_0,b−a, so its index difference captures the pair’s monochromatic admissibility.The index difference alone does not establish compatibility between distinct fused pairs.Source: §4.1 · p. 3
• Because fused pairs are unordered, δ and −δ represent the same orbit, leaving n unoriented difference classes to test.Source: §4.1 · pp. 3–4
• A perfect matching of H_adm covers all 2n fine cosets with individually admissible pairs; each matching then undergoes pairwise sumset compatibility checks.Source: §4.1 · p. 4
• A perfect matching is only a necessary condition, not proof that the corresponding fusion is a Ramsey colouring.Cross-pair compatibility remains to be checked; Figure 1 illustrates mixed difference-2 and difference-5 pairings that depart from the uniform standard construction.Source: Figure 1 · p. 4, §4.1 · p. 5

• The reported search considered only primes smaller than 2 · 10^3.Source: §5 · p. 5
• The FBF construction gives finite representations for 8 and 13 colours over F449 and F1613, respectively.Source: §5 · p. 5
• In both cases, the fused sets partition the nonzero field elements and satisfy the required inverse-closure and sumset conditions.Source: §5 · p. 5

• New fused-pairs colourings are reported as non-isomorphic to previously found colourings using Comer’s method.Source: §6 · p. 5
• Monochromatic-subgraph canonical-label multisets provide a quick preliminary sufficient test, but matching multisets do not generally establish isomorphism.Source: §6 · pp. 5–6
• Table 1 compares previously known Comer-method prime values with FBF values for 2–13 colours; a dash marks cases where FBF finds no colouring.Source: Table 1 · p. 6, §6 · p. 6
• An incidence-graph test using nauty/Traces establishes isomorphism where applicable.Source: §6 · p. 7
• Colour-relabelling isomorphisms preserve the multiset of coloured-triangle counts, so differing multisets provide a sufficient non-isomorphism test.Source: §6 · p. 7
• 3,028 orbit representatives at n = 9 and p = 397 produced pairwise distinct coloured-triangle-count multisets, establishing pairwise non-isomorphism even under colour relabelling.Source: §6 · p. 7

• Gretton discovered FBF; Pennifold developed the SageMath scripts that formed the basis of its first implementation and found several reported colourings.Source: §7 · p. 7
• Kowalski brought the colouring problem to the authors’ attention, found multiple reported colourings, and noticed FBF’s non-isomorphic results.Source: §7 · p. 7
• Christopher identified the index-difference symmetry, which can permit direct construction, though mixed-difference pairings may still require search and compatibility checks.Source: §7 · pp. 7–8

8. Future Work

• The authors remain interested in general-purpose combinatorial search to optimize the size of colourings and discover combinatorial objects with extensive symmetry.Source: §8 · p. 8
• Starting from colourings produced by their method, general-purpose SAT solvers can find smaller clique colourings corresponding to Ramsey colourings.Source: §8 · p. 8
• Optimizing colouring size with such search is beyond this short paper, which focuses on announcing the 8- and 13-colourings and their method.Source: §8 · p. 8