Disconnected Cliques in Derangement Graphs

Autor:	Anderson, Sara, Casper, W. Riley, Fleyshman, Sam, Rathbun, Matt
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Computer Science - Discrete Mathematics Mathematics - Representation Theory 05C69 05C40 20C30
Druh dokumentu:	Working Paper
Popis:	We obtain a correspondence between pairs of $N\times N$ orthogonal Latin squares and pairs of disconnected maximal cliques in the derangement graph with $N$ symbols. Motivated by methods in spectral clustering, we also obtain modular conditions on fixed point counts of certain permutation sums for the existence of collections of mutually disconnected maximal cliques. We use these modular obstructions to analyze the structure of maximal cliques in $X_N$ for small values of $N$. We culminate in a short, elementary proof of the nonexistence of a solution to Euler's $36$ Officer Problem. Comment: 15 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2407.14155 Zobrazit plný text záznamu View this record from Arxiv