Abstract
Starting with the Johnson scheme J(14, 7), 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_{17}\) whose two color classes contain no monochromatic \(K_{4}\), \(K_{4,3}\), or \(K_{5,2}\) subgraphs. This construction yields the smallest known representation of the relation algebra \(32_{65}\), reducing the upper bound from 8192 to 3432.
Similar content being viewed by others
References
Alm, J., Andrews, D., Manske, J., Sexton, D.: Relation-algebraic sumset problems in abelian groups. (In progress)
Alm, J., Maddux, R., Manske, J.: Chromatic graphs, Ramsey numbers and the flexible atom conjecture. Electron. J. Combin. 15(1), Research paper 49, 8 (2008). http://www.combinatorics.org/Volume_15/Abstracts/v15i1r49.html
Dodd, L., Hirsch, R.: Improved lower bounds on the size of the smallest solution to a graph colouring problem, with an application to relation algebra. J. Relat. Methods Comput. Sci. 2, 18–26 (2013)
Jipsen, P., Maddux, R.D., Tuza, Z.: Small representations of the relation algebra \( \cal{E}_{n+1}(1,2,3)\). Algebra Universalis 33(1), 136–139 (1995)
Lyndon, R.C.: Relation algebras and projective geometries. Michigan Math. J. 8(1), 21–28 (1961)
Maddux, R.D.: Relation Algebras, Studies in Logic and the Foundations of Mathematics, vol. 150. Elsevier B. V, Amsterdam (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Alm, J.F., Andrews, D.A. A reduced upper bound for an edge-coloring problem from relation algebra. Algebra Univers. 80, 19 (2019). https://doi.org/10.1007/s00012-019-0592-6
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00012-019-0592-6