Matching statistics in regular hypergraphs and applications

For fixed $k\ge3$, we determine the first sublinear correction to the logarithm of the matching partition function for a class of $n$-vertex $d$-regular $k$-uniform hypergraphs, uniformly for activities in each fixed compact interval of $(0,\infty)$.Our hypotheses include every regular linear hypergraph of polynomial degree and a class of nonlinear hypergraphs described by higher codegrees and intersection patterns, which we introduce here. The weighted counting estimate implies an averaged version of Kahn's conjecture: under the uniform measure, the expected number of uncovered vertices is $(1+o(1))nd^{-1/k}$, with concentration and large deviations on this scale. The proof combines a novel variant of random greedy counting, based on short stages and regular completions, with a new entropy method that uses intersection patterns to control reconstruction after deleting matching edges. We highlight the following applications. (i) Partial transversals in Latin squares. Every Latin square of order $n$ has $(n/e^2)^n\exp((3+o(1))n^{2/3})$ partial transversals. Also, almost all partial transversals have $(1+o(1))n^{2/3}$ missing cells. (ii) Linear $3$-uniform hypergraphs. There are $(n/e^2)^{n^2/6}\exp((1/2+o(1))n^{5/3})$ linear $3$-uniform hypergraphs on $[n]$, and almost all have $n^2/6-(1/6+o(1))n^{5/3}$ edges. (iii) Matroids of fixed rank. For each fixed $r\ge4$, the number $m(n,r)$ of rank-$r$ matroids on $[n]$ satisfies $\log m(n,r)=\frac{n^{r-1}}{r!}(\log n-r+1)+\left(\frac1{(r-1)!}+o(1)\right)n^{r-1-1/r}$, refining the estimates of van der Hofstad, Pendavingh and van der Pol.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-12
DOI
https://doi.org/10.48550/arxiv.2611.17197
Primary Topic
Limits and Structures in Graph Theory
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Matching statistics in regular hypergraphs and applications

Hyunwoo Lee
arXiv (Cornell University)
Limits and Structures in Graph Theory
preprint

Matching statistics in regular hypergraphs and applications

Hyunwoo Lee
preprint en

Abstract

For fixed $k\ge3$, we determine the first sublinear correction to the logarithm of the matching partition function for a class of $n$-vertex $d$-regular $k$-uniform hypergraphs, uniformly for activities in each fixed compact interval of $(0,\infty)$.Our hypotheses include every regular linear hypergraph of polynomial degree and a class of nonlinear hypergraphs described by higher codegrees and intersection patterns, which we introduce here. The weighted counting estimate implies an averaged version of Kahn's conjecture: under the uniform measure, the expected number of uncovered vertices is $(1+o(1))nd^{-1/k}$, with concentration and large deviations on this scale. The proof combines a novel variant of random greedy counting, based on short stages and regular completions, with a new entropy method that uses intersection patterns to control reconstruction after deleting matching edges. We highlight the following applications. (i) Partial transversals in Latin squares. Every Latin square of order $n$ has $(n/e^2)^n\exp((3+o(1))n^{2/3})$ partial transversals. Also, almost all partial transversals have $(1+o(1))n^{2/3}$ missing cells. (ii) Linear $3$-uniform hypergraphs. There are $(n/e^2)^{n^2/6}\exp((1/2+o(1))n^{5/3})$ linear $3$-uniform hypergraphs on $[n]$, and almost all have $n^2/6-(1/6+o(1))n^{5/3}$ edges. (iii) Matroids of fixed rank. For each fixed $r\ge4$, the number $m(n,r)$ of rank-$r$ matroids on $[n]$ satisfies $\log m(n,r)=\frac{n^{r-1}}{r!}(\log n-r+1)+\left(\frac1{(r-1)!}+o(1)\right)n^{r-1-1/r}$, refining the estimates of van der Hofstad, Pendavingh and van der Pol.

arXiv (Cornell University)
Limits and Structures in Graph Theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon