Almost every Latin square has a decomposition into transversals
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912182172647424 |
|---|---|
| author | Bowtell, Candida Montgomery, Richard |
| author_facet | Bowtell, Candida Montgomery, Richard |
| contents | In 1782, Euler conjectured that no Latin square of order $n\equiv 2\; \textrm{mod}\; 4$ has a decomposition into transversals. While confirmed for $n=6$ by Tarry in 1900, Bose, Parker, and Shrikhande constructed counterexamples in 1960 for each $n\equiv 2\; \textrm{mod}\; 4$ with $n\geq 10$. We show that, in fact, counterexamples are extremely common, by showing that if a Latin square of order $n$ is chosen uniformly at random then with high probability it has a decomposition into transversals. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_05438 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Almost every Latin square has a decomposition into transversals Bowtell, Candida Montgomery, Richard Combinatorics In 1782, Euler conjectured that no Latin square of order $n\equiv 2\; \textrm{mod}\; 4$ has a decomposition into transversals. While confirmed for $n=6$ by Tarry in 1900, Bose, Parker, and Shrikhande constructed counterexamples in 1960 for each $n\equiv 2\; \textrm{mod}\; 4$ with $n\geq 10$. We show that, in fact, counterexamples are extremely common, by showing that if a Latin square of order $n$ is chosen uniformly at random then with high probability it has a decomposition into transversals. |
| title | Almost every Latin square has a decomposition into transversals |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.05438 |