Kahn--Lovász-type inequalities for graph factors

Abstract

The Kahn--Lovász theorem gives a sharp upper bound on the number of perfect matchings in a graph in terms of its degree sequence, extending the classical Brégman--Minc inequality for bipartite graphs. In this paper, we establish an asymptotically sharp extension of the Kahn--Lovász theorem to $F$-factors for every Hamiltonian graph $F$. As a consequence, we asymptotically determine the maximum number of $F$-factors in an $n$-vertex $m$-edge graph, yielding an $F$-factor analogue of Kruskal--Katona-type theorems. We also prove a multigraph analogue of the Kahn--Lovász theorem. Combining this with our results for Hamiltonian graphs, we obtain an asymptotically sharp Kruskal--Katona-type bound for a further class of connected graphs $F$, including those containing two vertex-disjoint cycles of equal length whose union spans $V(F)$.

Disclosure

“em 1.4 and a multigraph analogue of the Kahn–Lovász theorem. In Section 5, we establish this multigraph extension and then prove Theorem 1.7. We conclude the paper with some remarks and open problems. Statement of AI use. We used ChatGPT 5.6 Pro/Sol to improve the exposition and proof- read the manuscript. Apart from this, no AI tools were used. All mathematical ideas were developed independently by the author, who takes full responsibility for this article. 2 Prelim”

PDF page 6

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-22T03:17:27.667123Z

Structural counts