Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs
Abstract
A hypergraph is bipartite with bipartition $(A, B)$ if every edge has exactly one vertex in $A$, and a matching in such a hypergraph is $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)$.
Fields of Study & Subjects
graph theory and CDMA systems
Limits and Structures in Graph Theory
Advanced Graph Theory Research
Publication details
- Journal / source
- The Electronic Journal of Combinatorics
- Publisher
- The Electronic Journal of Combinatorics
- Volume
- 33
- Issue
- 2
- Publication date
- 23 April 2026
- Language
- EN