Kahn–Lovász-type inequalities for graph factors

Our first main result extends Theorem 1.2 to $F$-factors for several classes of graphs $F$. In particular, we obtain an asymptotically sharp result for every Hamiltonian graph $F$.

The bound in Theorem 1.4 is asymptotically sharp. The extremal construction is given by disjoint unions of cliques satisfying suitable divisibility conditions; see Section 3.

Applying the AM-GM inequality to Theorem 1.4, we also obtain an asymptotically sharp Kruskal–Katona-type result for $F$-factors whenever $F$ is Hamiltonian. To state this result, let $N_{F}(n,m)$ denote the maximum number of $F$-factors in an $n$-vertex $m$-edge graph.

The lower bound of Corollary 1.6 is attained by disjoint unions of cliques, as described in Section 3.

We also prove an analogue of Corollary 1.6 for graphs $F$ that contain two vertex-disjoint cycles of equal length whose union spans $V(F)$. This follows from Theorem 1.4 and a multigraph analogue of the Kahn–Lovász theorem, established in Section 5.

We note that there exist many interesting non-Hamiltonian graph but contain a spanning disjoint union of two cycles of equal length, for instance, the Petersen graph. In other words, Theorem 1.4 and Corollary 1.6 do not apply to the Petersen graph, but Theorem 1.7 works for the Petersen graph.

We now give a high-level overview of the main ideas behind our proofs.

We first discuss Theorem 1.4. Let $F$ be a Hamiltonian graph on $\ell$ vertices. Since $F$ contains a spanning cycle $C_{\ell}$, a double-counting argument reduces the problem to bounding the number of embeddings of $C_{\ell}$-factors into a given host graph. To prove it, we partition $V(G)$ into $\ell$ equally sized classes $V_{0},\dots,V_{\ell-1}$ and count only those cycle factors whose vertices appear successively in these classes. If we ignore the cycle edges between one fixed pair of consecutive classes, the remaining edges form perfect matchings between the other consecutive pairs. Thus, the Brégman–Minc inequality (Theorem 1.1), gives an upper bound in terms of the numbers of neighbors that each vertex has in the next class.

We apply this estimate for each of the $\ell$ possible pairs of consecutive classes and take the geometric mean. Since every vertex contributes to exactly $\ell-1$ of the resulting estimates, this produces the exponent $1-1/\ell$ in Theorem 4.3, which corresponds to the exponent $1-1/|V(F)|$ in Theorem 1.4. We then sum over all equal partitions and apply Hölder’s inequality. The remaining task is to control a weighted sum over partitions, which is precisely the content of Lemma 4.4.

The main idea behind Lemma 4.4 is to reverse the order of counting. Recall that the Brégman–Minc inequality naturally gives a bound involving factorials of the relevant degrees. Using Stirling’s approximation, in particular Proposition 2.5, we replace these factorial terms, up to an arbitrarily small multiplicative error, by linear functions of the degrees. This linearization is crucial, as it allows us to interpret the resulting product in purely graph-theoretic terms. More precisely, replace every edge of $G$ by the two possible orientations and add a bounded number of directed loops at each vertex. For a fixed partition, the resulting product counts the number of ways to choose exactly one outgoing edge from every vertex, subject to the condition that each chosen non-loop edge goes from one class to the next. We instead first fix the resulting directed graph and count the number of partitions compatible with it.

Observe that each connected component of such a directed graph contains a unique directed cycle, and once the class of one vertex in a component is fixed, the classes of all other vertices are determined. Hence, if the directed graph has $k$ connected components, it is compatible with at most $\ell^{k}$ partitions. Lemma 4.5 shows that this additional weight can be absorbed into an arbitrarily small exponential loss: graphs with few components have small weight, while graphs with many components necessarily contain many small components and are correspondingly sparse. This proves Lemma 4.4, and hence Theorem 4.3 and Theorem 1.4.

The proof of Theorem 4.9, the general connected graph case, follows the same strategy. We choose a spanning tree $T$ of $F$ and reduce the problem to Theorem 4.10. After fixing an equal partition of $V(G)$, we root $T$ at one of its vertices and orient every edge towards the root. The resulting structure can again be counted using perfect matchings between appropriate pairs of classes. The Brégman–Minc inequality, geometric averaging over the choices of the root, and Hölder’s inequality then give the desired bound. The additional factor involving $a^{a}b^{b}$ comes from the two color classes of $T$, of sizes $a$ and $b$.

Finally, to prove Theorem 1.7, we first count factors consisting of cycles using Corollary 1.6. For a fixed cycle factor $H$, we construct an auxiliary loopless multigraph whose vertices correspond to the cycles of $H$, with multiplicities given by the numbers of edges of $G$ joining pairs of cycles. Perfect matchings in this multigraph correspond to ways to pair the cycles and add one joining edge to each pair. We therefore prove the multigraph Kahn–Lovász theorem, Theorem 5.1, using the entropy method. When the multiplicities are bounded, and the average degree is sufficiently large, the resulting error term is negligible, giving Corollary 5.2. Applying this to the auxiliary multigraph and then using Lemma 4.1 yields Theorem 1.7.

We write $[n]=\{1,\dots,n\}$ for each positive integer $n$. We use the notation $\beta\ll\alpha_{1},\dots,\alpha_{t}$ to mean that there exists a function $f$ such that $\beta\leq f(\alpha_{1},\dots,\alpha_{t})$. We do not attempt to specify the function $f$ explicitly.

Throughout the paper, we use standard notation from graph theory. All graphs and digraphs are considered simple unless otherwise stated. For a graph $G$, we denote its vertex set and edge set by $V(G)$ and $E(G)$, respectively, and write $v(G)\coloneqq|V(G)|$ and $e(G)\coloneqq|E(G)|$. For a vertex $v\in V(G)$, we denote by $N_{G}(v)$ and $d_{G}(v)$ the set of neighbors and degree of $v$ in $G$, respectively. We often omit the subscript when the underlying graph is clear from the context. For a digraph $D$ and a vertex $v\in V(D)$, we use analogous notation. In particular, we denote by $N^{+}_{D}(v)$ and $N^{-}_{D}(v)$ be out- and in-neighbors of $v$ in $D$, and refer their sizes as out- and in-degree of $v$, namely $d^{+}_{D}(v)$ and $d^{-}_{D}(v)$, respectively. Again, we omit the subscript when the underlying digraph is clear from the context. For a graph $G$ and two disjoint vertex subsets $X,Y\subseteq V(G)$, we write $G[X]$ the induced subgraph of $G$ induced by $X$, and $G[X,Y]$ the induced bipartite subgraph of $G$, where the edges of $G[X,Y]$ the edges whose endpoints are lies in both $X$ and $Y$.

In this paper, we also consider a loopless multigraph and a digraph with multi-loops in the proof of our theorems. We also consider loopless multigraphs and digraphs with multiple loops. For a loopless multigraph $M$ and a pair $e\in\binom{V(M)}{2}$, let $\mu(e)$ denote the multiplicity of $e$, and let $\mu(M)$ denote the maximum edge multiplicity of $M$. For $v\in V(M)$, we define $d_{M}(v)\coloneqq\sum_{u\in V(M)}\mu(uv)$, that is, the number of edges incident with $v$, counted with multiplicity. We say a digraph $D$ has multi-loops if some vertices of $D$ have multiple loops directed out and also into themselves. We write $\mathrm{Comp}(G)$ and $\mathrm{Comp}(D)$ for the set of connected components of $G$ and the set of connected components of the underlying graph of $D$, respectively. Note that all simple graphs and digraphs are also loopless multigraphs and digraphs with multi-loops.

For graphs $F$ and $G$, we denote by $N(F;G)$ the number of $F$ copies in $G$. We write $m\cdot F$ for the disjoint union of $m$ copies of $F$ for a positive integer $m$. With these notation, $N_{\mathrm{factor}}(F;G)$ is the same with $N\left(\frac{|V(G)|}{|V(F)|}\cdot F;G\right)$ whenever $|V(F)|$ divides $|V(G)|$. We say a function $\phi:V(F)\to V(G)$ is an embedding if $\phi$ is an injective homomorphism from $F$ to $G$. We write $\mathrm{Emb}(F;G)$ for the set of embeddings from $F$ to $G$. We note that

holds, where $\mathrm{Aut}(F)$ is the automorphism group of $F$.

We now introduce a new notation regarding the degree of a vertex in a given graph with respect to a certain vertex partition. Let $G$ be a graph and $v$ be a vertex of $G$. We define an $r$-partition $\mathcal{P}$ of $V(G)$ as an $r$-tuple $(V_{0},V_{1},\dots,V_{r-1})$, where the indices are members of the cyclic group $\mathbb{Z}_{r}$ such that $V_{i}\cap V_{j}=\emptyset$ whenever $i\neq j$ and $V(G)=\cup_{i\in\mathbb{Z}_{r}}V_{i}$. We say this partition is $r$-equipartition if $|V_{i}|=|V_{j}|$ for all $i,j\in\mathbb{Z}_{r}$. Consider a labelled digraph $D$ on the vertex set $\mathbb{Z}_{r}$. Without loss of generality, assume $v\in V_{0}$. Then we define the out-degree of $v$ with respect to the pair $(\mathcal{P},D)$, denoted by $d^{+}_{G}(v;(\mathcal{P},D))$, as

The notion of $d^{+}_{G}(v;(\mathcal{P},D))$ plays a crucial role in the proof of Theorem 1.4.

Lastly, throughout the paper, all the logarithms are taken base $e$ unless we indicate the base, and we consider $\log 0=0$.

We use an entropy method inspired by Radhakrishnan’s elegant proof [21] of the Brégman–Minc inequality to prove Theorem 5.1 in Section 5. Information entropy (Shannon’s entropy) is a very useful quantity to capture the randomness of a given discrete random variable that was introduced by Shannon in 1948. For a random variable $Z$ on a probability space $\mathcal{Z}$ and $z\in\mathcal{Z}$, we denote by $P_{Z}(z)$ the value $\Pr[Z=z]$. The following is the definition of information entropy.

We also need a conditional entropy defined as follows.

Equivalently, $H(X|Y)=\mathbb{E}_{Y}[H(X|Y=y)]$.

Rather than its definition itself, entropy has been used in many combinatorial problems because of its highly useful properties. We summarize basic properties of entropy that we need below.

For more properties on information entropy and its applications in combinatorics, we refer the readers to a survey of Galvin [11].

As we discussed in Section 1.2, our proof uses the Brégman–Minc inequality and the Kahn–Lovász theorem as black-box theorems. Both of them contain many factorials in the statements, and we approximate them with a polynomial to connect those quantities to the number of certain digraphs. To achieve this, we collect upper and lower bounds of factorials via Stirling’s approximation. Below is Stirling’s approximation.

As a consequence of the above inequality, we obtain the following useful inequality.

We prove Theorem 1.4 first. Together with Lemma 4.1, it suffices to show the cycle factor case. For later purposes, we state it not in terms of $N_{\mathrm{factor}}(C_{\ell};G)$ but in terms of the number of embeddings.

We note that $C_{2}$ is an edge. Keeping Theorem 4.3 in mind, the proof of Theorem 1.4 follows.

To prove Theorem 4.3, we consider pairs of partitions and digraphs as described in Section 1.2. For an integer $\ell\geq 2$, let $\overrightarrow{C_{\ell}}$ denote the labelled oriented cycle of length $\ell$ on the vertex set $\mathbb{Z}_{\ell}$ whose arcs are in the form of $i\to(i+1)$. Note that $\overrightarrow{C_{2}}$ is a $(\mathbb{Z}_{2})$-labelled digon.

Before proving Lemma 4.4, we establish the following weighted counting lemma for spanning subdigraphs of out-degree one.