Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs
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_ | 1866913146853130240 |
|---|---|
| author | Dai, Tantan Divoux, Alexander Kelly, Tom |
| author_facet | Dai, Tantan Divoux, Alexander Kelly, Tom |
| contents | A hypergraph is \textit{bipartite with bipartition $(A, B)$} if every edge has exactly one vertex in $A$, and a matching in such a hypergraph is \textit{$A$-perfect} if it saturates every vertex in $A$. We prove an upper bound on the number of $A$-perfect matchings in uniform hypergraphs with small maximum codegree. Using this result, we prove that there exist order-$n$ Latin squares with at most $(n/e^{2.117})^n$ transversals when $n$ is odd and $n \equiv 0\pmod 3$. We also show that $k$-uniform $D$-regular hypergraphs on $n$ vertices have at most $((1+o(1))q/e^k)^{Dn/k}$ proper $q$-edge-colorings when $q = (1+o(1))D$ and the maximum codegree is $o(q)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_17652 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs Dai, Tantan Divoux, Alexander Kelly, Tom Combinatorics 05D40, 05B15, 05C15 A hypergraph is \textit{bipartite with bipartition $(A, B)$} if every edge has exactly one vertex in $A$, and a matching in such a hypergraph is \textit{$A$-perfect} if it saturates every vertex in $A$. We prove an upper bound on the number of $A$-perfect matchings in uniform hypergraphs with small maximum codegree. Using this result, we prove that there exist order-$n$ Latin squares with at most $(n/e^{2.117})^n$ transversals when $n$ is odd and $n \equiv 0\pmod 3$. We also show that $k$-uniform $D$-regular hypergraphs on $n$ vertices have at most $((1+o(1))q/e^k)^{Dn/k}$ proper $q$-edge-colorings when $q = (1+o(1))D$ and the maximum codegree is $o(q)$. |
| title | Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs |
| topic | Combinatorics 05D40, 05B15, 05C15 |
| url | https://arxiv.org/abs/2506.17652 |