Kahn–Lovász theorem extension problem for graph factors

For a fixed connected graph $F$ , let $G$ be a graph with $|V(F)|\mid |V(G)|$ , and let $\Phi_F(G)$ denote the number of spanning subgraphs of $G$ that are disjoint unions of $|V(G)|/|V(F)|$ copies of $F$ . Determine sharp upper bounds for $\Phi_F(G)$ in terms of the degree sequence of $G$ , extending the Kahn--Lovász inequality $\operatorname{pm}(G)\leq\prod_{v\in V(G)}(d_G(v)!)^{1/(2d_G(v))}$ for perfect matchings. In particular, determine asymptotically the extremal value $\max\{\Phi_F(G):|V(G)|=n,\ |E(G)|=m\}$ for general connected $F$ .

References

Primary source

arXiv

Additional references

Kahn--Lovász-type inequalities for graph factors — arXiv — Lee, Hyunwoo

extremal-graph-theory graph-factors

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed progress

A new preprint substantially extends the matching-count result, but the general graph-factor problem remains open.

The problem asks how far the sharp Kahn–Lovász bound for perfect matchings extends to counting spanning copies of a fixed graph $F$ . The August 2026 preprint establishes asymptotically sharp bounds for important classes, rather than resolving the extension for every connected $F$ .

August 2026 graph-factor extension

Lee, Hyunwoo proves an asymptotically sharp Kahn–Lovász-type inequality for $F$ -factors when $F$ is Hamiltonian, with disjoint unions of suitable cliques extremal. The work also derives Kruskal–Katona-type bounds, proves a multigraph analogue, and covers connected graphs containing two vertex-disjoint equal-length cycles spanning $V(F)$ , including the Petersen graph. For general connected $F$ , the stated bound can fail for some non-Hamiltonian graphs, and a considerable gap remains between upper and lower bounds. The author reports using ChatGPT 5.6 Pro/Sol only for exposition and proofreading; the mathematical ideas were developed independently.

Current status (as of August 2026): The extension is settled asymptotically for Hamiltonian factors and several broader classes, while the corresponding problem for every connected $F$ remains open.

Sources

arxiv.org

No solutions have been posted yet.