Improved bounds on the size of the smallest representation of relation algebra 32_65

DOI10.1007/S00012-022-00791-4MaRDI QIDQ2159495zbMATH OpenOpenAlexFDO

Authors Jeremy F. Alm, Michael Levet, Saeed Moazami, Jorge Montero-Vallejo, Linda Pham, Dave Sexton, Xiaonan Xu

Publication date 1 August 2022

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.00620

zbMATH Keywords

flexible atomrelation algebrasrepresentationspectrum

Mathematics Subject Classification ID

Cylindric and polyadic algebras; relation algebras (03G15) Coloring of graphs and hypergraphs (05C15)

Review text

The conjecture that a finite symmetric integral relation algebra is finitely representable if it has a flexible atom has been proved whenever all the diversity atoms are flexible (because all cycles occur) or there is a minimal set of cycles that make an atom flexible. Probabilistic methods work in both cases but yield only large bounds. This paper reports significant progress on the size of representations of relation algebras with a minimally flexible atom. There is a spectacular improvement in the upper bound (from exponential to polynomial in the number of atoms) plus an improvement in the lower bound. The simplest example of a relation algebra with a minimally flexible atom is shown to have a representation on 1024 elements and a lower bound illustrated by a nice picture of 26 points connected by colored lines.

Recommendations

• Small representations of the relation algebra \(\mathcal E_{n+1}(1,2,3)\)
• scientific article; zbMATH DE number 3933071
• scientific article; zbMATH DE number 67031
• Minimal relation algebras
• Finite representations for two small relation algebras

Cites work

• A reduced upper bound for an edge-coloring problem from relation algebra
• Chromatic graphs, Ramsey numbers and the flexible atom conjecture
• Relation algebras
• Representations for small relation algebras
• Small representations of the relation algebra \(\mathcal E_{n+1}(1,2,3)\)
• Splitting in Relation Algebras

Cited in

(12)

• Minimal relation algebras
• Small representations of the relation algebra \(\mathcal E_{n+1}(1,2,3)\)
• Finite representations for two small relation algebras
• A reduced upper bound for an edge-coloring problem from relation algebra
• scientific article; zbMATH DE number 67031 (Why is no real title available?)
• Directed Ramsey and anti-Ramsey schemes and the Flexible Atom Conjecture
• Comer schemes, relation algebras, and the flexible atom conjecture
• Improved bounds on the size of the smallest representation of relation algebra $32_{65}$
• A finite representation of relation algebra \(1896_{3013}\)
• Monk algebras and representability
• Comer schemes, relation algebras, and the flexible atom conjecture
• Cyclic group spectra for some small relation algebras

This page was built for publication: Improved bounds on the size of the smallest representation of relation algebra \(32_{65}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2159495)