Kahn--Lovász-type inequalities for graph factors
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.20303
curl -X POST /api/v1/records/arxiv/2608.20303/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.20303/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'