A Reduced Upper Bound for an Edge-coloring Problem from Relation Algebra

2015/04/27 by Jeremy F. Alm, Alm, Jeremy F., David A. Andrews +1
Mathematics · #03G15 #05C15 #Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO) #Rings and Algebras (math.RA) #math.CO #math.LO #math.RA #msc:03G15 #msc:05C15

paper · pdf · doi:10.48550/arxiv.1504.07290

arxiv created 2015/04/27 · arxiv updated 2015/04/29

Abstract

We construct an edge-coloring of K_N (for N = 3432) in colors red, dark blue, and light blue, such that there are no monochromatic blue triangles and such that the coloring satisfies a certain strong universal-existential property. The edge-coloring of K_N depends on a cyclic coloring of K₁₇ whose two color classes are K₄-, K_4,3-, and K_5,2-free. This construction yields the smallest known representation of the relation algebra 32₆₅, reducing the upper bound from 8192 to 3432.

Related

• Qualitative representations of chromatic algebras
• Edge-coloring K_{n, n} with no 2-colored C_2k
• Ramsey-type problem for an almost monochromatic K₄
• An explicit edge-coloring of K_n with six colors on every K₅
• Monochromatic triangle packings in red-blue graphs