A new mathematical preprint extends Kahn–Lovász-type counting bounds beyond perfect matchings. It gives an upper bound on the number of F-factors—collections of copies of a chosen graph pattern that cover a host graph—when F is Hamiltonian, meaning it contains a cycle through all its vertices. It also gives a related upper bound for perfect matchings in loopless multigraphs.
This is a theorem-proving analysis, not an experiment or survey. It ranges over all eligible host graphs rather than an empirical sample, and its conclusions are conditional on the structural, density, divisibility and multiplicity assumptions stated for each result. There are no statistical error estimates.
The Hamiltonian case
For Hamiltonian F, the main degree-sequence result gives an epsilon-controlled upper bound on the number of F-factors in every eligible n-vertex host graph. In plain language, the graph’s list of vertex degrees is enough to impose a ceiling on the number of coverings by F that it can contain.
The authors state that this Hamiltonian bound is asymptotically sharp: disjoint unions of cliques satisfying the required divisibility conditions provide a construction that matches it at large scale.
The same line of work answers an edge-budget version of the question. When n and m are positive integers, n is divisible by the number of vertices in F, and m is at least C times n, it gives the maximum number of F-factors among n-vertex, m-edge graphs for Hamiltonian F.
A wider, less complete reach
A related edge-constrained bound covers connected F containing two vertex-disjoint cycles of equal length whose union spans all the vertices of F. The theorem is restricted to that particular structural class beyond the Hamiltonian setting.
The broader connected-graph picture remains unsettled. One central inequality fails for some non-Hamiltonian graphs, including highly unbalanced bipartite examples, while the paper’s general connected-graph result uses a different upper bound based on a spanning tree whose two bipartition classes have sizes a and b.
The authors report a considerable gap between upper and lower bounds in general, both for degree-sequence bounds and for the related Kruskal–Katona-type edge-counting problem. The preprint therefore leaves the full counting problem for general connected graphs open.
Repeated edges, new bounds
A separate result treats loopless multigraphs—graphs with repeated edge copies but no loops—and assumes they have no isolated vertices. It bounds perfect matchings using an upper degree parameter d_v for each vertex and a maximum edge-multiplicity parameter μ_v.
For an n-vertex, m-edge loopless multigraph with m at least C times n and every edge multiplicity at most μ, a further corollary gives an asymptotic bound on the number of perfect matchings. The constant depends on the multiplicity bound and on epsilon.
How the bounds are obtained
The proofs rely on combinatorial counting. In the Hamiltonian case, the argument partitions the vertices into equal classes, reduces cycle-factor counting to perfect matchings between consecutive classes, and applies the Bregman–Minc inequality. The multigraph proof uses an entropy method following the approach attributed to Radhakrishnan.
The work is posted as an arXiv preprint, version 1. It presents the Hamiltonian result as asymptotically sharp, while acknowledging that a substantial upper/lower-bound gap remains for general connected graphs.
Paper data and sources
Original title: Kahn--Lovász-type inequalities for graph factors
Authors: Hyunwoo Lee
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-20
DOI: Not available
Original paper · Full text