Parities in random Latin squares
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912591287156736 |
|---|---|
| author | Kwan, Matthew Petrova, Kalina Sawhney, Mehtaab |
| author_facet | Kwan, Matthew Petrova, Kalina Sawhney, Mehtaab |
| contents | In a Latin square, every row can be interpreted as a permutation, and therefore has a parity (even or odd). We prove that in a uniformly random $n\times n$ Latin square, the $n$ row parities are very well approximated by a sequence of $n$ independent unbiased coin flips: for example, the total variation error of this approximation tends to zero as $n\to\infty$. This resolves a conjecture of Cameron. In fact, we prove a generalisation of Cameron's conjecture for the joint distribution of the row parities, column parities and symbol parities (the latter are defined by the symmetry between rows, columns and symbols of a Latin square).
Along the way, we introduce several general techniques for the study of random Latin squares, including a new re-randomisation technique via `stable intercalate switchings', and a new approximation theorem comparing random Latin squares with a certain independent model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_13125 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parities in random Latin squares Kwan, Matthew Petrova, Kalina Sawhney, Mehtaab Probability Combinatorics 05B15, 05C80, 60B99, 05C65 In a Latin square, every row can be interpreted as a permutation, and therefore has a parity (even or odd). We prove that in a uniformly random $n\times n$ Latin square, the $n$ row parities are very well approximated by a sequence of $n$ independent unbiased coin flips: for example, the total variation error of this approximation tends to zero as $n\to\infty$. This resolves a conjecture of Cameron. In fact, we prove a generalisation of Cameron's conjecture for the joint distribution of the row parities, column parities and symbol parities (the latter are defined by the symmetry between rows, columns and symbols of a Latin square). Along the way, we introduce several general techniques for the study of random Latin squares, including a new re-randomisation technique via `stable intercalate switchings', and a new approximation theorem comparing random Latin squares with a certain independent model. |
| title | Parities in random Latin squares |
| topic | Probability Combinatorics 05B15, 05C80, 60B99, 05C65 |
| url | https://arxiv.org/abs/2509.13125 |