We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Directed Ramsey and anti-Ramsey schemes and the Flexible Atom Conjecture.
- Authors
Alm, Jeremy F.; Levet, Michael
- Abstract
In this paper, we shed new light on the Flexible Atom Conjecture. We first give finite representation results for relation algebras 3 3 3 7 , 3 5 3 7 , 7 7 8 3 , 7 8 8 3 , 8 0 8 3 , 8 2 8 3 , 8 3 8 3 , 1 3 1 0 1 3 1 6 , 1 3 1 3 1 3 1 6 , 1 3 1 5 1 3 1 6 and 1 3 1 6 1 3 1 6 . Prior to our paper, only 8 3 8 3 and 1 3 1 6 1 3 1 6 were known to be finitely representable. We accomplish this by generalizing the notion of a relation algebra generated by a Ramsey scheme to the directed (antisymmetric) setting, and then showing that each of these algebras embeds into a finite directed anti-Ramsey scheme. The notion of a directed anti-Ramsey scheme may be of independent interest. We complement our upper bounds with some lower bounds. Namely, we show that any square representation of 3 1 3 7 requires at least 14 points, any square representation of 3 3 3 7 requires at least 11 points, and any square representation of 3 5 3 7 requires at least 12 points. Our technique adapts previous work of Alm et al. [Algebra Univ. (2022)], in that we examine the combinatorial structure induced by the flexible atom.
- Subjects
RELATION algebras; LOGICAL prediction; FLEXIBLE structures; ATOMS; ALGEBRA; DIRECTED graphs; RAMSEY numbers
- Publication
International Journal of Algebra & Computation, 2023, Vol 33, Issue 8, p1571
- ISSN
0218-1967
- Publication type
Article
- DOI
10.1142/S0218196723500595