Metraipolis › archive › dc_6350bb92eb15

Perfect Partitions of Regular Bipartite Graphs — arXiv:2611.07118

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.07118
License (as archived)
CC0-1.0
Archived
2026-11-06T14:52:38.596Z
SHA-256 of the archived text
c591b8d2d1b22f91d1ffb18887e26d9300f282aefaa4c07a3b4cd98093fc9fc1
Stable URL of this page
https://metraipolis.com/documento/dc_6350bb92eb15

How to cite

Perfect Partitions of Regular Bipartite Graphs — arXiv:2611.07118 — arXiv (en), https://arxiv.org/abs/2611.07118 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_6350bb92eb15 (Metraipolis archive dc_6350bb92eb15, sha256 c591b8d2d1b22f91d1ffb18887e26d9300f282aefaa4c07a3b4cd98093fc9fc1)
BibTeX
@misc{dc6350bb92eb15,
  title = {Perfect Partitions of Regular Bipartite Graphs — arXiv:2611.07118},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.07118},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_6350bb92eb15; sha256 c591b8d2d1b22f91d1ffb18887e26d9300f282aefaa4c07a3b4cd98093fc9fc1},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07118. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Let $I_{n,n}$ be a fixed perfect matching of the complete bipartite graph $K_{n,n}$, and let $L_{n,1}=K_{n,n}-I_{n,n}$. A perfect set of $L_{n,1}$ is a $1$-factorization of $L_{n,1}$, that is, a set of $n-1$ pairwise edge-disjoint perfect matchings whose union is $E(L_{n,1})$; a perfect partition of $L_{n,1}$ is a partition of the set of all perfect matchings of $L_{n,1}$ into perfect sets. Brualdi, Chiang, and Li (2005) asked whether $L_{n,1}$ admits a perfect partition. Identifying both sides of the bipartition with $[n]=\{1,2,\ldots ,n\}$, the perfect matchings of $L_{n,1}$ are exactly the derangements of $[n]$, the perfect sets correspond bijectively to the reduced Latin squares of order $n$, and the perfect partitions are exactly the perfect matchings of the $(n-1)$-uniform hypergraph whose vertices are the derangements of $[n]$ and whose edges are the perfect sets. We first give, for every $n$, a constructive lower bound on the maximum number of pairwise disjoint perfect sets of $L_{n,1}$. We then show that $L_{5,1}$ has exactly $42$ distinct perfect partitions and that $L_{6,1}$ has at least $82$ distinct perfect partitions; these are the first examples demonstrating that perfect partitions need not be unique. Finally, we exhibit two distinct perfect partitions of $L_{7,1}$, resolving the $n=7$ open problem raised by Brualdi et al.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2611.07118 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:24:27.837Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).