Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs

Alexander Divoux; Tantan Dai; Tom Kelly

arxiv: 2506.17652 · v2 · pith:ZHL4F6WInew · submitted 2025-06-21 · 🧮 math.CO

Entropy Bounds for Perfect Matchings in Bipartite Hypergraphs

Tantan Dai , Alexander Divoux , Tom Kelly This is my paper

Pith reviewed 2026-05-22 00:24 UTC · model grok-4.3

classification 🧮 math.CO

keywords perfect matchingsbipartite hypergraphsentropy boundsLatin squarestransversalshypergraph edge coloringscodegree

0 comments

The pith

Uniform bipartite hypergraphs with small maximum codegree have bounded numbers of A-perfect matchings, implying Latin squares of certain orders have at most (n/e^{2.117})^n transversals.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes an upper bound on the number of A-perfect matchings in k-uniform bipartite hypergraphs with bipartition (A, B) when the maximum codegree is small relative to the degree. This bound is obtained via an entropy argument that accounts for limited overlaps among edges due to the codegree condition. The authors apply the bound to the hypergraph representation of Latin squares, showing that when n is odd and n is divisible by 3 there exist order-n Latin squares with at most (n/e^{2.117})^n transversals. A parallel application yields an upper bound on the number of proper q-edge-colorings of k-uniform D-regular hypergraphs when q is asymptotically D and the codegree is o(q).

Core claim

In a k-uniform bipartite hypergraph with parts (A, B), |A| = n, uniform degree D on A and maximum codegree sufficiently small, the number of A-perfect matchings is at most a quantity controlled by an entropy expression involving D, k and e; specializing the hypergraph to the one whose perfect matchings are the transversals of a Latin square yields the stated (n/e^{2.117})^n bound for appropriate n, while the same machinery bounds proper edge-colorings by ((1+o(1))q/e^k)^{Dn/k}.

What carries the argument

Entropy bound on the count of A-perfect matchings in a uniform bipartite hypergraph, with the maximum codegree serving as the parameter that limits edge overlaps in the entropy calculation.

If this is right

There exist order-n Latin squares with at most (n/e^{2.117})^n transversals whenever n is odd and n ≡ 0 mod 3.
k-uniform D-regular hypergraphs on n vertices admit at most ((1+o(1))q/e^k)^{Dn/k} proper q-edge-colorings when q ≈ D and maximum codegree is o(q).
The entropy method supplies a general technique for upper-bounding perfect matchings once codegree is controlled.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The explicit constant 2.117 may be improvable by tightening the entropy estimate or optimizing auxiliary parameters.
Analogous entropy arguments could be tested on the minimum number of transversals across all Latin squares of a given order.
The same codegree-controlled bound might extend to counting perfect matchings in nearly uniform hypergraphs arising from other combinatorial designs.

Load-bearing premise

The hypergraph must be uniform and its maximum codegree must be small enough relative to the degree parameters for the entropy calculation to control overlaps between edges.

What would settle it

A k-uniform bipartite hypergraph with maximum codegree o(D) whose number of A-perfect matchings exceeds the entropy-derived upper bound would show the main matching theorem false.

Figures

Figures reproduced from arXiv: 2506.17652 by Alexander Divoux, Tantan Dai, Tom Kelly.

**Figure 1.** Figure 1: Edges in X, S(X), and T(X) are shown in black, blue, and red, respectively. Nevertheless, we can show that under the hypotheses of Theorem 1.2, these sets of bad edges are not too large, as follows. Lemma 3.3. Let H be a (k + 1)-uniform bipartite hypergraph with bipartition (A, B). If X is an A-perfect matching of H, then X a∈A |Sa(X)| = |S(X)| ≤ |A| k 2 (∆2(H) − 1), and if every vertex of B has degree… view at source ↗

read the original abstract

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)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a new entropy upper bound on A-perfect matchings in uniform bipartite hypergraphs with small codegree and uses it for a concrete (n/e^{2.117})^n transversal bound on certain Latin squares.

read the letter

Hi, the main takeaway is that they bound the number of A-perfect matchings from above in uniform bipartite hypergraphs when the maximum codegree is small, then apply the bound to show some order-n Latin squares (odd n divisible by 3) have at most (n/e^{2.117})^n transversals and to get a coloring bound for regular hypergraphs when q is roughly the degree. The entropy method controls overlaps via the codegree hypothesis and produces the numerical constant in the Latin-square case. That constant and the specific matching bound do not seem to be in the earlier literature they cite, so the counting result is new. The coloring application follows directly once the matching theorem is available. The work is straightforward and uses standard entropy inequalities plus hypergraph counting lemmas without circularity. The central argument holds up on its own terms. The soft spot is the codegree condition when they specialize to Latin squares. The natural 3-partite hypergraph has codegree linear in n, so the o(1) terms only disappear if they have a special family of squares where the induced codegree is small enough relative to the degree. The abstract claims such squares exist for the stated n, but the derivation of the exact constant 2.117 depends on that control being uniform. If the paper verifies the error terms carefully, the bound is fine; otherwise the constant might need adjustment. Minor issue overall, not load-bearing for the matching theorem itself. This is for people working on asymptotic hypergraph matchings and combinatorial designs. A reader interested in refined counting bounds for transversals or edge-colorings would get something concrete from it. The paper shows clear thinking and honest use of the literature. I would send it to a serious referee to check the entropy calculation and the codegree verification in the applications. Recommendation: put it through peer review.

Referee Report

2 major / 2 minor

Summary. The paper proves an upper bound on the number of A-perfect matchings in uniform bipartite hypergraphs with small maximum codegree, derived via entropy inequalities and standard hypergraph counting lemmas. It applies the bound to establish that there exist order-n Latin squares (odd n ≡ 0 mod 3) with at most (n/e^{2.117})^n transversals, and shows that k-uniform D-regular hypergraphs have at most ((1+o(1))q/e^k)^{Dn/k} proper q-edge-colorings when q=(1+o(1))D and maximum codegree is o(q).

Significance. If the central matching bound holds with the stated error control, the work supplies a new entropy-based tool for upper-bounding matchings and colorings in hypergraphs, yielding an explicit numerical constant in the Latin-square application. The derivation avoids ad-hoc parameters and relies on standard lemmas, which strengthens the internal consistency when the codegree hypothesis is verified.

major comments (2)

[Main matching theorem] Main matching theorem (entropy bound for A-perfect matchings): the derivation controls pairwise edge overlaps via maximum codegree Δ and invokes Δ = o(q) to absorb error terms in the conditional entropy or mutual information, yielding the (1+o(1)) factor. When specializing to the Latin-square hypergraph, the paper must exhibit that the chosen construction (existing only for odd n ≡ 0 mod 3) achieves codegree sufficiently smaller than the nominal degree to justify the concrete exponent 2.117; otherwise the o(1) terms do not vanish uniformly.
[Latin-square application] Latin-square application: the 3-partite hypergraph on rows/columns/symbols has codegree Θ(n) in the generic case, so the claim that there exist Latin squares attaining the bound (n/e^{2.117})^n transversals requires an explicit argument that the induced codegree satisfies the o(q) hypothesis with room for the error terms; without this verification the numerical constant cannot be recovered from the general theorem.

minor comments (2)

[Abstract] Abstract: the uniformity degree k is used in the coloring bound but not stated explicitly in the opening sentence; adding it improves readability.
[Introduction] Notation: the bipartition (A,B) and the parameter q are introduced without a forward reference to their precise definitions in the hypergraph setting; a brief clarification would help.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comments point by point below. We agree that explicit verification of the codegree condition is needed for the Latin-square application and will revise the manuscript accordingly.

read point-by-point responses

Referee: [Main matching theorem] Main matching theorem (entropy bound for A-perfect matchings): the derivation controls pairwise edge overlaps via maximum codegree Δ and invokes Δ = o(q) to absorb error terms in the conditional entropy or mutual information, yielding the (1+o(1)) factor. When specializing to the Latin-square hypergraph, the paper must exhibit that the chosen construction (existing only for odd n ≡ 0 mod 3) achieves codegree sufficiently smaller than the nominal degree to justify the concrete exponent 2.117; otherwise the o(1) terms do not vanish uniformly.

Authors: We agree that the (1+o(1)) factor requires Δ = o(q) for the error terms to be absorbed. Our application uses a specific algebraic construction of Latin squares that exists precisely when n is odd and n ≡ 0 (mod 3). For this construction the associated hypergraph satisfies Δ = O(1) while the degree parameter q ∼ n, so Δ/q → 0 uniformly. This justifies both the (1+o(1)) factor and the explicit constant 2.117. We will insert a short subsection that recalls the construction, computes the codegree explicitly, and confirms the o(q) hypothesis. revision: yes
Referee: [Latin-square application] Latin-square application: the 3-partite hypergraph on rows/columns/symbols has codegree Θ(n) in the generic case, so the claim that there exist Latin squares attaining the bound (n/e^{2.117})^n transversals requires an explicit argument that the induced codegree satisfies the o(q) hypothesis with room for the error terms; without this verification the numerical constant cannot be recovered from the general theorem.

Authors: The referee is right that a generic tripartite 3-uniform hypergraph would have codegree Θ(n). The hypergraphs we consider, however, arise from a structured algebraic construction of Latin squares rather than a generic one. In this construction any two vertices from distinct parts lie in at most a bounded number of edges, yielding Δ = O(1) = o(q) with q ∼ n. We will add an explicit paragraph (or short subsection) that states the codegree bound for the construction, verifies Δ = o(q) with room for the error terms, and thereby recovers the numerical constant 2.117 from the main theorem. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation uses entropy inequalities and standard hypergraph lemmas

full rationale

The central upper bound on A-perfect matchings is obtained from entropy calculations that bound overlaps using the maximum codegree assumption, followed by application to Latin square transversals for odd n ≡ 0 mod 3. No equation or step reduces by construction to a fitted parameter or self-citation that carries the main claim; the codegree condition is an explicit hypothesis rather than a derived output. The Latin-square specialization follows directly from the general theorem without redefining inputs in terms of the target count.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard combinatorial axioms such as the definition of uniformity and codegree, plus entropy inequalities from information theory applied to the distribution of matchings. No free parameters are introduced beyond the o(1) asymptotic notation, and no new entities are postulated.

axioms (2)

domain assumption Entropy inequalities for counting matchings in hypergraphs with bounded codegree
Invoked to derive the main upper bound on the number of A-perfect matchings.
standard math Standard properties of uniform hypergraphs and Latin squares as hypergraphs
Used to specialize the matching bound to transversals and edge-colorings.

pith-pipeline@v0.9.0 · 5694 in / 1594 out tokens · 41963 ms · 2026-05-22T00:24:15.719216+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

30 extracted references · 30 canonical work pages · 1 internal anchor

[1]

Alon and J

N. Alon and J. H. Spencer, The probabilistic method, 4th ed., Wiley Publishing, 2016

work page 2016
[2]

R. A. Brualdi and H. J. Ryser, Combinatorial matrix theory , Cambridge University Press, 1991

work page 1991
[3]

T. M. Cover and J. A. Thomas, Elements of information theory , second ed., John Wiley & Sons, 2006

work page 2006
[4]

Cutler and A

J. Cutler and A. J. Radcliffe, An entropy proof of the Kahn-Lov´ asz theorem, Electron. J. Combin. 18 (2011), Paper 10, 9

work page 2011
[5]

Davies, M

E. Davies, M. Jenssen, and W. Perkins, A proof of the upper matching conjecture for large graphs , J. Combin. Theory Ser. B 151 (2021), 393–416

work page 2021
[6]

Eberhard, F

S. Eberhard, F. Manners, and R. Mrazovi´ c,Additive triples of bijections, or the toroidal semiqueens problem , J. Eur. Math. Soc. (JEMS) 21 (2019), 441–463

work page 2019
[7]

, Transversals in quasirandom latin squares , Proc. Lond. Math. Soc. (3) 127 (2023), 84–115

work page 2023
[8]

Egan and I

J. Egan and I. M. Wanless, Latin squares with restricted transversals , J. Combin. Des. 20 (2012), 124–141

work page 2012
[9]

G. P. Egorychev, The solution of van der Waerden’s problem for permanents , Adv. in Math. 42 (1981), 299–305

work page 1981
[10]

D. I. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix , Mat. Zametki 29 (1981), 931–938, 957

work page 1981
[11]

Friedland, E

S. Friedland, E. Krop, and K. Markstr¨ om,On the number of matchings in regular graphs , Electron. J. Combin. 15 (2008), Research Paper 110, 28

work page 2008
[12]

Ghafari and I

A. Ghafari and I. M. Wanless, Latin squares whose transversals share many entries , arxiv:2412.12466 (2024)

work page arXiv 2024
[13]

Glebov and Z

R. Glebov and Z. Luria, On the maximum number of Latin transversals , J. Combin. Theory Ser. A 141 (2016), 136–146

work page 2016
[14]

Kahn, Asymptotically good list-colorings, J

J. Kahn, Asymptotically good list-colorings, J. Combin. Theory Ser. A 73 (1996), 1–59

work page 1996
[15]

Keevash, Counting designs, J

P. Keevash, Counting designs, J. Eur. Math. Soc. (JEMS) 20 (2018), 903–927

work page 2018
[16]

Kwan, Almost all Steiner triple systems have perfect matchings , Proc

M. Kwan, Almost all Steiner triple systems have perfect matchings , Proc. Lond. Math. Soc. (3) 121 (2020), 1468–1495

work page 2020
[17]

Linial and Z

N. Linial and Z. Luria, An upper bound on the number of Steiner triple systems , Random Structures Algorithms 43 (2013), 399–406

work page 2013
[18]

New bounds on the number of n-queens configurations

Z. Luria, New bounds on the number of n-queens configurations , arxiv:1705.05225 (2017)

work page internal anchor Pith review Pith/arXiv arXiv 2017
[19]

B. D. McKay, J. C. McLeod, and I. M. Wanless, The number of transversals in a Latin square , Des. Codes Cryptogr. 40 (2006), 269–284

work page 2006
[20]

AproofoftheRyser-Brualdi-Steinconjectureforlargeeven n

R. Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large even n, arxiv:2310.19779 (2023)

work page arXiv 2023
[21]

Montgomery, Transversals in Latin squares, Surveys in combinatorics 2024, London Math

R. Montgomery, Transversals in Latin squares, Surveys in combinatorics 2024, London Math. Soc. Lecture Note Ser., vol. 493, Cambridge Univ. Press, Cambridge, 2024, 131–158

work page 2024
[22]

Pippenger and J

N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs , J. Combin. Theory Ser. A 51 (1989), 24–42

work page 1989
[23]

Ryser, Neuere probleme der kombinatorik , Vortr¨ age ¨ uber Kombinatorik, Oberwolfach (1967), 69–91

H. Ryser, Neuere probleme der kombinatorik , Vortr¨ age ¨ uber Kombinatorik, Oberwolfach (1967), 69–91

work page 1967
[24]

Simkin, The number of n-queens configurations , Advances in Mathematics 427 (2023), 109127

M. Simkin, The number of n-queens configurations , Advances in Mathematics 427 (2023), 109127

work page 2023
[25]

S. K. Stein, Transversals of Latin squares and their generalizations , Pacific J. Math. 59 (1975), 567–575. 10 ENTROPY BOUNDS FOR PERFECT MATCHINGS IN BIPARTITE HYPERGRAPHS

work page 1975
[26]

A. A. Taranenko, Multidimensional permanents and an upper bound on the number of transversals in Latin squares, J. Combin. Des. 23 (2015), 305–320

work page 2015
[27]

Vardi, Computational recreations in Mathematica , Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1991

I. Vardi, Computational recreations in Mathematica , Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1991

work page 1991
[28]

V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz (1964), 25–30

work page 1964
[29]

I. M. Wanless, Transversals in Latin squares , Quasigroups Related Systems 15 (2007), 169–190

work page 2007
[30]

, Transversals in Latin squares: a survey , Surveys in combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, 403–437

work page 2011

[1] [1]

Alon and J

N. Alon and J. H. Spencer, The probabilistic method, 4th ed., Wiley Publishing, 2016

work page 2016

[2] [2]

R. A. Brualdi and H. J. Ryser, Combinatorial matrix theory , Cambridge University Press, 1991

work page 1991

[3] [3]

T. M. Cover and J. A. Thomas, Elements of information theory , second ed., John Wiley & Sons, 2006

work page 2006

[4] [4]

Cutler and A

J. Cutler and A. J. Radcliffe, An entropy proof of the Kahn-Lov´ asz theorem, Electron. J. Combin. 18 (2011), Paper 10, 9

work page 2011

[5] [5]

Davies, M

E. Davies, M. Jenssen, and W. Perkins, A proof of the upper matching conjecture for large graphs , J. Combin. Theory Ser. B 151 (2021), 393–416

work page 2021

[6] [6]

Eberhard, F

S. Eberhard, F. Manners, and R. Mrazovi´ c,Additive triples of bijections, or the toroidal semiqueens problem , J. Eur. Math. Soc. (JEMS) 21 (2019), 441–463

work page 2019

[7] [7]

, Transversals in quasirandom latin squares , Proc. Lond. Math. Soc. (3) 127 (2023), 84–115

work page 2023

[8] [8]

Egan and I

J. Egan and I. M. Wanless, Latin squares with restricted transversals , J. Combin. Des. 20 (2012), 124–141

work page 2012

[9] [9]

G. P. Egorychev, The solution of van der Waerden’s problem for permanents , Adv. in Math. 42 (1981), 299–305

work page 1981

[10] [10]

D. I. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix , Mat. Zametki 29 (1981), 931–938, 957

work page 1981

[11] [11]

Friedland, E

S. Friedland, E. Krop, and K. Markstr¨ om,On the number of matchings in regular graphs , Electron. J. Combin. 15 (2008), Research Paper 110, 28

work page 2008

[12] [12]

Ghafari and I

A. Ghafari and I. M. Wanless, Latin squares whose transversals share many entries , arxiv:2412.12466 (2024)

work page arXiv 2024

[13] [13]

Glebov and Z

R. Glebov and Z. Luria, On the maximum number of Latin transversals , J. Combin. Theory Ser. A 141 (2016), 136–146

work page 2016

[14] [14]

Kahn, Asymptotically good list-colorings, J

J. Kahn, Asymptotically good list-colorings, J. Combin. Theory Ser. A 73 (1996), 1–59

work page 1996

[15] [15]

Keevash, Counting designs, J

P. Keevash, Counting designs, J. Eur. Math. Soc. (JEMS) 20 (2018), 903–927

work page 2018

[16] [16]

Kwan, Almost all Steiner triple systems have perfect matchings , Proc

M. Kwan, Almost all Steiner triple systems have perfect matchings , Proc. Lond. Math. Soc. (3) 121 (2020), 1468–1495

work page 2020

[17] [17]

Linial and Z

N. Linial and Z. Luria, An upper bound on the number of Steiner triple systems , Random Structures Algorithms 43 (2013), 399–406

work page 2013

[18] [18]

New bounds on the number of n-queens configurations

Z. Luria, New bounds on the number of n-queens configurations , arxiv:1705.05225 (2017)

work page internal anchor Pith review Pith/arXiv arXiv 2017

[19] [19]

B. D. McKay, J. C. McLeod, and I. M. Wanless, The number of transversals in a Latin square , Des. Codes Cryptogr. 40 (2006), 269–284

work page 2006

[20] [20]

AproofoftheRyser-Brualdi-Steinconjectureforlargeeven n

R. Montgomery, A proof of the Ryser-Brualdi-Stein conjecture for large even n, arxiv:2310.19779 (2023)

work page arXiv 2023

[21] [21]

Montgomery, Transversals in Latin squares, Surveys in combinatorics 2024, London Math

R. Montgomery, Transversals in Latin squares, Surveys in combinatorics 2024, London Math. Soc. Lecture Note Ser., vol. 493, Cambridge Univ. Press, Cambridge, 2024, 131–158

work page 2024

[22] [22]

Pippenger and J

N. Pippenger and J. Spencer, Asymptotic behavior of the chromatic index for hypergraphs , J. Combin. Theory Ser. A 51 (1989), 24–42

work page 1989

[23] [23]

Ryser, Neuere probleme der kombinatorik , Vortr¨ age ¨ uber Kombinatorik, Oberwolfach (1967), 69–91

H. Ryser, Neuere probleme der kombinatorik , Vortr¨ age ¨ uber Kombinatorik, Oberwolfach (1967), 69–91

work page 1967

[24] [24]

Simkin, The number of n-queens configurations , Advances in Mathematics 427 (2023), 109127

M. Simkin, The number of n-queens configurations , Advances in Mathematics 427 (2023), 109127

work page 2023

[25] [25]

S. K. Stein, Transversals of Latin squares and their generalizations , Pacific J. Math. 59 (1975), 567–575. 10 ENTROPY BOUNDS FOR PERFECT MATCHINGS IN BIPARTITE HYPERGRAPHS

work page 1975

[26] [26]

A. A. Taranenko, Multidimensional permanents and an upper bound on the number of transversals in Latin squares, J. Combin. Des. 23 (2015), 305–320

work page 2015

[27] [27]

Vardi, Computational recreations in Mathematica , Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1991

I. Vardi, Computational recreations in Mathematica , Addison-Wesley Publishing Company, Advanced Book Program, Redwood City, CA, 1991

work page 1991

[28] [28]

V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz (1964), 25–30

work page 1964

[29] [29]

I. M. Wanless, Transversals in Latin squares , Quasigroups Related Systems 15 (2007), 169–190

work page 2007

[30] [30]

, Transversals in Latin squares: a survey , Surveys in combinatorics 2011, London Math. Soc. Lecture Note Ser., vol. 392, Cambridge Univ. Press, Cambridge, 2011, 403–437

work page 2011