The lattice of definable equivalence relations in homogeneous \(n\)-dimensional permutation structures

Samuel Braunfeld¹

¹Rutgers Univeristy

The electronic journal of combinatorics, Tome 23 (2016) no. 4

Résumé

In Homogeneous permutations, Peter Cameron [Electronic Journal of Combinatorics 2002] classified the homogeneous permutations (homogeneous structures with 2 linear orders), and posed the problem of classifying the homogeneous $n$-dimensional permutation structures (homogeneous structures with $n$ linear orders) for all finite $n$. We prove here that the lattice of $\emptyset$-definable equivalence relations in such a structure can be any finite distributive lattice, providing many new imprimitive examples of homogeneous finite dimensional permutation structures. We conjecture that the distributivity of the lattice of $\emptyset$-definable equivalence relations is necessary, and prove this under the assumption that the reduct of the structure to the language of $\emptyset$-definable equivalence relations is homogeneous. Finally, we conjecture a classification of the primitive examples, and confirm this in the special case where all minimal forbidden structures have order 2.

Détail

DOI : 10.37236/5980

Classification : 05A05
Mots-clés : countable homogeneous, Fraïssé theory, infinite permutations