Counting spanning subgraphs in dense hypergraphs

Abstract

We give a simple method to estimate the number of distinct copies of some classes of spanning subgraphs in hypergraphs with a high minimum degree. In particular, for each $k\geq 2$ and $1\leq \ell \leq k-1$, we show that every $k$-graph on $n$ vertices with minimum codegree at least

\begin{equation*} \left \{\begin {array}{l@{\quad}l} \left (\dfrac {1}{2}+o(1)\right )n & \text { if }(k-\ell )\mid k,\\[5pt] \left (\dfrac {1}{\lceil \frac {k}{k-\ell }\rceil (k-\ell )}+o(1)\right )n & \text { if }(k-\ell )\nmid k, \end {array} \right . \end{equation*}

contains $\exp\!(n\log n-\Theta (n))$ Hamilton $\ell$-cycles as long as $(k-\ell )\mid n$. When $(k-\ell )\mid k$, this gives a simple proof of a result of Glock, Gould, Joos, Kühn, and Osthus, while when $(k-\ell )\nmid k$, this gives a weaker count than that given by Ferber, Hardiman, and Mond, or when $\ell \lt k/2$, by Ferber, Krivelevich, and Sudakov, but one that holds for an asymptotically optimal minimum codegree bound.

1. Introduction

A central problem in extremal graph theory is to find sufficient degree conditions that force the containment of a given spanning subgraph, and here a classical result of Dirac [10] from 1952 states that every graph on $n\geq 3$ vertices with minimum degree at least $n/2$ contains a Hamilton cycle. In 1995, Bollobás [4] and Bondy [5] asked for estimates of the number of distinct Hamilton cycles in graphs satisfying Dirac’s condition. Sárközy, Selkow, and Szemerédi [32] used the regularity method in 2003 to show that every graph with $n\geq 3$ vertices and minimum degree at least $n/2$ contains at least $c^nn!$ Hamilton cycles, for some constant $c\gt 0$ . This cannot be improved to any $c\gt 1/2$ , as for fixed $p\gt 1/2$ , the typical random graph $G(n,p)$ satisfies Dirac’s condition and has $(1-o(1))^np^nn!$ distinct Hamilton cycles (see [16]). In 2009, Cuckler and Kahn [8] obtained precise estimates of the number of distinct Hamilton cycles in terms of the minimum degree of the host graph. In particular, they showed that every $n$ -vertex graph with minimum degree at least $n/2$ contains at least $(\frac 12-o(1))^nn!$ distinct Hamilton cycles, thus matching the bound given by random graphs.

Our purpose here is to introduce a simple method to bound below the number of copies of many different spanning subgraphs in graphs and hypergraphs with a high minimum degree and apply this to give new counting results in dense hypergraphs (Theorems 1.2–1.4). However, let us already illustrate this method as it would apply to Hamilton cycles in an $n$ -vertex graph $G$ with minimum degree $\delta (G)\geq (\frac{1}{2}+\varepsilon )n$ with $\varepsilon \gt 0$ fixed and $n$ large. Set $r=\mu n$ with $1/n\ll \mu \ll \varepsilon$ , and partition $V(G)=V_1\cup \ldots \cup V_r$ by choosing the location of each vertex independently and uniformly at random. With probability at least $e^{-n}$ , the minimum degree of each subgraph $G[V_i]$ will be at least $(\frac{1}{2}+\frac{\varepsilon }{2})|V_i|$ , and there will be a disjoint collection of $r$ edges in $G$ connecting the sets $V_1,\ldots,V_r$ in a cycle in order and connecting $V_r$ to $V_1$ (see Fig. 1). Applying classical methods to find a Hamilton path through each subgraph $G[V_i]$ to connect these edges creates a Hamilton cycle of $G$ which passes through each of the sets $V_1,\ldots,V_r$ in order. As we will prove later, even though the probability of success here is small, only at least $e^{-n}$ , for this to be true, it is easy to show that $G$ must contain at least $c^nn!$ distinct Hamilton cycles (for some fixed $0\lt c\ll \varepsilon$ ).

Figure 1. A Hamilton cycle passing through the sets $V_1,V_2,\ldots,V_r$ in order.

For each $i\in [r]$ in the above argument, we should expect $\delta (G[V_i])\geq (\frac{1}{2}+\frac{\varepsilon }{2})|V_i|$ with some constant probability close to 1 (as $\mu \ll \varepsilon$ ), and so we would expect this to hold for all $i\in [r]$ with probability at least $2^{-r}\geq e^{-n}$ (say) for $n$ large. Because of the dependencies here, this is not straightforward to prove, but we do this with an iterative partitioning argument inspired by a technical aspect of the iterative absorption techniques introduced by Barber, Lo, Kühn, and Osthus [2]. The result of this argument in the graph case for Hamilton cycles is much weaker than what is already known, but this argument can be used easily in hypergraphs if the subgraph sought can be constructed from pieces like the cycle in Fig. 1. This allows counting results to be inferred from the extremal minimal degree for these pieces applied to each hypergraph induced on the sets $V_i$ in the partition (with some modification to make the required connections).

Dirac’s theorem has been generalised to give minimum degree conditions implying the containment of many other spanning subgraphs, including $F$ -factors [15, 25], trees with bounded degree [7, 19, 21], powers of Hamilton cycles [22, 20], and, more generally, graphs with bounded degree and sublinear bandwidth [6] (see also the excellent surveys [24, 31]). For hypergraphs, much less is known, but we will recall the progress made for Hamilton $\ell$ -cycles, powers of tight cycles, and factors (in Section 1.1), before discussing previous counting results and our main theorems (in Section 1.2). Our technique may be applicable to other spanning subgraphs, and in particular, we note that recent work of Gupta, Hamann, Müyesser, Parczyk, and Sgueglia [14] classifies some hypergraphs our techniques may apply to.

1.1 Dirac-type problems in hypergraphs

A $k$ -uniform hypergraph (or $k$ -graph) is a hypergraph where every edge consists of exactly $k$ vertices. For a $k$ -graph $H$ and a subset of vertices $S\subset V(H)$ , the degree of $S$ , denoted $d_H(S)$ , is the number of edges in $H$ containing $S$ . For $1\le d\le k-1$ , the minimum $d$ -degree of $H$ , denoted $\delta _d(H)$ , is the minimum of $d_H(S)$ over all subsets $S\subseteq V(H)$ with $|S|=d$ . When $d=k-1$ , this is the minimum codegree, $\delta (H)=\delta _{k-1}(H)$ .

The first subgraphs we consider in hypergraphs are the Hamilton $\ell$ -cycles, a well-studied generalisation of Hamilton cycles to hypergraphs. For $k\geq 2$ and $0\le \ell \le k-1$ , say that a $k$ -graph $C$ is an $\ell$ -cycle if there is a cyclic ordering $v_1,\ldots, v_t$ of $V(C)$ such that every edge of $C$ consists of $k$ consecutive vertices and every two consecutive edges intersect in exactly $\ell$ vertices. If $\ell =k-1$ , then $C$ is called a tight cycle, and if $\ell =0$ , then $C$ is a matching. A $k$ -graph $H$ contains a Hamilton $\ell$ -cycle if there is an $\ell$ -cycle $C\subseteq H$ with $V(C)=V(H)$ (where it can only exist if $k-\ell$ divides $|H|$ ).

The asymptotic minimum codegree required to guarantee a Hamilton $\ell$ -cycle in an $n$ -vertex $k$ -graph is known due to Rödl, Ruciński, and Szemerédi [30] if $(k-\ell )|\ell$ and to Kühn, Mycroft, and Osthus [23] if $(k-\ell )\nmid k$ , whose results together give the following theorem.

Theorem 1.1. For each $\gamma \gt 0$ , $k\geq 2$ , and $1\leq \ell \lt k$ , there exists $n_0$ such that the following holds for all $n\geq n_0$ with $(k-\ell )\mid n$ . If $H$ is an $n$ -vertex $k$ -graph with $\delta (H)\geq (\delta _{k,\ell }+\gamma )n$ , where

(1.1) \begin{equation} \delta _{k,\ell }\;:\!=\;\left \{\begin{array}{l@{\quad}l} \dfrac{1}{2} & \text{ if }(k-\ell )\mid k, \\[5pt] \dfrac{1}{\lceil \frac{k}{k-\ell }\rceil (k-\ell )} & \text{ if }(k-\ell )\nmid k, \end{array} \right . \end{equation}

then $H$ contains a Hamilton $\ell$ -cycle.

Due to Theorem 1.1, we say the minimum codegree threshold for a $k$ -graph to contain a Hamilton $\ell$ -cycle is $\delta _{k,\ell }$ . Note that a Hamilton tight cycle contains a Hamilton $\ell$ -cycle for every $\ell$ with $(k-\ell )\mid k$ . The results in Theorem 1.1 are tight in every case up to the ‘error term’ of $\gamma n$ . For more discussion of this, and the seemingly much more difficult problem for other degree bounds $\delta _d(H)$ , $d\lt k-1$ , see the survey by Kühn and Osthus [26].

We will also consider the powers of Hamilton tight cycles, where for each $t\geq k\geq 2$ , a $k$ -graph $C$ is the $(t-k+1)$ th power of a tight cycle if there is a cyclic ordering $v_1,\ldots,v_s$ of $V(C)$ so that $\{v_i,\ldots,v_{i+t-1}\}$ spans a $k$ -uniform clique for all $i\in [s]$ (working modulo $s$ ). When $k=2$ , this coincides with the usual definition of powers of cycles in graphs, where for each $t\geq 2$ , the minimum degree threshold for the containment of the $(t-1)$ th power of a Hamilton cycle was famously shown to be $\frac{t-1}{t}$ by Komlós, Sárközy, and Szemerédi [22, 20]. In 2020, Bedenknecht and Reiher [3] proved that $3$ -graphs with minimum codegree at least $(4/5+o(1))n$ contain the square of a tight Hamilton cycle (which corresponds to $t=k+1$ and $k=3$ ), where it is known that the constant $4/5$ cannot be reduced below $3/4$ for all $n$ . This was recently widely extended by Pavez-Signé, Sanhueza-Matamala, and Stein [28], who showed that, with $\gamma \gt 0$ fixed, if an $n$ -vertex $k$ -graph $H$ has minimum codegree

(1.2) \begin{equation} \delta (H)\geq \left (1-\frac{1}{\binom{t-1}{k-1}+\binom{t-2}{k-2}}+\gamma \right )n, \end{equation}

then $H$ contains the $(t-k+1)$ th power of a tight Hamilton cycle, provided that $n$ is sufficiently large. It is not known whether the bounds given in (1.2) are tight up to $\gamma n$ , though this is true for the cases $t\geq k=2$ and $t=k\geq 2$ which were already known [30, 22].

Finally, we will consider factors in hypergraphs. For a $k$ -graph $F$ , a $k$ -graph $H$ contains an $F$ -factor if it contains a collection of vertex-disjoint copies of $F$ covering every vertex in $H$ . Thus, a necessary condition for an $F$ -factor in $H$ is that $|F|$ divides $|H|$ . For $1\le d\le k-1$ , then, let $\mu _{k,d}(F)$ be the smallest number such that for every $\gamma \gt 0$ , there is $n_0$ such that if $H$ is an $n$ -vertex graph with $n\geq n_0$ divisible by $|F|$ and $\delta _d(H)\geq (\mu _{k,d}(F)+\gamma )\binom{n}{k-d}$ , then $H$ contains an $F$ -factor. In contrast to the graph case, where the threshold is known (with moreover a much stronger error term) for all fixed $F$ due to Komlós, Sárközy, and Szemerédi [15] and Kühn and Osthus [25], for most cases, we do not have good bounds even in the case $d=k-1$ (see the survey by [33] and references therein).

1.2 Counting spanning hypergraphs

As in Cuckler and Kahn’s work on Hamilton cycles [8], it is reasonable to believe that an $n$ -vertex $k$ -graph $H$ with $\delta (H)\geq \delta n$ , for $(k-\ell )\mid n$ and $\delta \gt \delta _{k,\ell }$ , should contain at least

(1.3) \begin{equation} (1-o(1))^n\cdot \Psi _{k,\ell }(n,\delta ) \end{equation}

distinct Hamilton $\ell$ -cycles, where $\Psi _{k,\ell }(n,\delta )$ denotes the expected number of distinct Hamilton $\ell$ -cycles in the binomial random $k$ -graph on $n$ vertices with edge probability $\delta$ . In 2016, Ferber, Krivelevich, and Sudakov [12] showed that the lower bound (1.3) is correct for every $\delta \gt 1/2$ and $1\le \ell \le k/2$ and asked if this can be extended to $1\le \ell \le k-1$ and $\delta \gt \delta _{k,\ell }$ . This was partially answered by Glock, Gould, Joos, Kühn, and Osthus [13], who showed that for every $\delta \gt 1/2$ and $1\le \ell \le k-1$ , the number of distinct Hamilton $\ell$ -cycles is $\exp\!(n\log n-\Theta (n))$ , which is tight up to the $\Theta (n)$ error term in the exponent. This result was recently improved by Ferber, Hardiman, and Mond [11], who proved that the lower bound (1.3) holds for every $\delta \gt 1/2$ and $1\le \ell \le k-2$ , thus settling the problem for every $1\le \ell \le k-2$ such that $(k-\ell )\mid k$ . Our contribution is to use the simple method outlined above to get a bound matching that in [13] that holds for any $\delta \gt \delta _{k,\ell }$ (with $\delta _{k,\ell }$ as defined in [1.1]), thus giving a new result when $(k-\ell )\nmid k$ and $\ell \gt k/2$ , as follows.

Theorem 1.2. For each $k\geq 2$ , $1\leq \ell \leq k-1$ , and $\gamma \gt 0$ , there exist $n_0$ and $C$ such that the following holds for any $n\geq n_0$ with $(k-\ell )\mid n$ . Any $n$ -vertex $k$ -graph $H$ with $\delta (H)\geq (\delta _{k,\ell }+\gamma )n$ (see [1.1]) contains at least $\exp\!(n\log n-Cn)$ distinct Hamilton $\ell$ -cycles.

No previous bounds on the count of powers of Hamilton tight cycles in hypergraphs with large codegree have been shown (including in graphs), and here, we use our technique to similarly get a bound tight up to $\Theta (n)$ error term in the exponent, as follows.

Theorem 1.3. For each $t\geq k\geq 2$ and $\gamma \gt 0$ , there exist $n_0$ and $C$ such that the following holds for any $n\geq n_0$ . Any $n$ -vertex $k$ -graph $H$ satisfying (1.2) contains at least $\exp\!(n\log n-Cn)$ distinct copies of the $(t-k+1)$ th power of a Hamilton tight cycle.

Finally, we consider counting $F$ -factors in dense hypergraphs. When $F$ is a single edge and $k|n$ , the number of $F$ -factors in a $k$ -graph $H$ with $n\geq 3k$ vertices is equal to the number of Hamilton 0-cycles multiplied by a factor of $((n/k)-1)!/2$ . Thus, from the results of Ferber, Krivelevich, and Sudakov [12] described above, if $k\mid n$ , then any $n$ -vertex $k$ -graph $H$ with $\delta (H)\geq \delta n$ has at least $(1-o(1))^n \Psi _{k,\ell }(n,\delta )/(n/k)!$ $F$ -factors (with $\Psi _{k,\ell }(n,\delta )$ as defined in [1.3]). In each case as part of wider work, for $1\le d\le k-1$ , Kang, Kelly, Kühn, Osthus, and Pfenninger [18] and Pham, Sah, Sawhney, and Simkin [29] showed that if $F$ is again a single edge, and $k\mid n$ , then any $n$ -vertex $k$ -graph $H$ with $\delta _d(H)\geq (\mu _{k,d}(F)+\gamma )\binom{n}{k-d}$ contains at least $c^{-n}\exp\!((1-1/k)n\log n)$ $F$ -factors where $c\ll \gamma$ is fixed, and this result is tight up to the constant $c$ . When $d=k-1$ , Kang, Kelly, Kühn, Osthus, and Pfenninger [18] even managed to remove the error term in the minimum degree condition.

In the graph case ( $k=2$ ), Pham, Sah, Sawhney, and Simkin [29] very recently showed that if $F=K_t$ is the $t$ -vertex complete graph, and $t\mid n$ , then any $n$ -vertex graph $G$ with $\delta (G)\geq (1-1/t)n$ contains $c^{-n}\exp\!((1-1/t)n\log n)$ $F$ -factors for some fixed constant $c$ . The degree bound here is the famously tight Hajnal-Szemerédi bound from [15], and the bound on the number of $F$ -factors is tight up to the constant $c$ . This proved a recent conjecture of Allen, Böttcher, Corsten, Davies, Jenssen, Morris, Roberts, and Skokan [1].

Here, our contribution again is to apply our methods to easily match these weaker bounds of $c^{-n}\exp\!((1-1/|F|)n\log n)$ under the stronger approximate minimum degree condition but to do this for $F$ -factors for any fixed graph $F$ and all degree bounds, as follows.

Theorem 1.4. For each $k\geq 2$ , $1\le d\le k-1$ , and each $k$ -graph $F$ on $t\geq k$ vertices, there exists $n_0$ and $C$ such that the following holds for any $n\geq n_0$ with $t\mid n$ . Any $n$ -vertex $k$ -graph $H$ with $\delta _d(H)\geq (\mu _{k,d}(F)+\gamma )\binom{n}{k-d}$ contains at least $\exp \big ((1-\frac{1}{t})n\log n-Cn\big )$ distinct $F$ -factors.

2. Proofs

A $k$ -graph $H$ has vertex set $V(H)$ and edge set $E(H)$ and $|H|=|V(H)|$ . For any $U,S\subset V(H)$ with $|U|\le k-1$ , $d(U,S)$ is the degree of $U$ in $S$ , that is, the number of edges of $H$ containing $U$ whose vertices not in $U$ are all in $S$ . The hypergraph $H[S]$ induced by $S\subset V(H)$ has vertex set $S$ and edge set consisting of all those edges in $H$ contained in $S$ . For a set $X$ and $1\le \ell \le |X|$ , let $\binom{X}{\ell }$ denote the collection of subsets of $X$ of size $\ell$ , and let $(X)_\ell$ denote the set of tuples $\mathbf x=(x_1,\ldots,x_\ell )\in X^\ell$ of distinct elements in $X$ . We will use bold letters to denote elements from $(X)_{\ell }$ or $X^\ell$ . For $a,b\in (0,1]$ , we will write $a\ll b$ to denote that, given $b$ , we can choose $a$ sufficiently small so that the subsequent statements hold.

2.1 Our main partitioning lemma

Here we prove our main lemma, showing that in any linear (in $|H|$ ) minimum degree hypergraph $H$ , there are many partitions of $V(H)$ into sets with chosen sizes whose induced subgraphs from $H$ have high minimum degree relative to their sizes (see Lemma 2.3). We need a slightly stronger condition to connect the subgraphs than found in these induced subgraphs, which motivates the following definition of a good partition.

Definition 2.1. Let $k\geq 2$ , $\delta \in [0,1]$ , and $\mathbf{n}=(n_1,\dots, n_r)\in \mathbb N^r$ . For an $n$ -vertex $k$ -graph $H$ , we say that a partition $V(H)=V_1\cup \ldots \cup V_r$ is $(\mathbf{n},\delta )$ -good if (working modulo $r$ in the indices) we have

1. P1 $|V_i|=n_i$ for each $i\in [r]$ , and

2. P2 for each $i\in [r]$ and $U\subseteq V_{i-1}\cup V_i\cup V_{i+1}$ with $|U|=k-1$ , $d(U,V_i)\geq \delta |V_i|$ .

To find many good partitions, we will choose an appropriate distribution $\mathbf{n}$ for the size of the subsets and partition $V(H)=V_1\cup \ldots \cup V_r$ uniformly at random subject to P1 . We then show (for the parameters we use and with $n$ large) that P2 holds with probability at least $e^{-n}$ , a relatively small probability but still enough to show that many partitions are good. For any fixed $i\in [r]$ , P2 will hold with constant probability, and the only difficulty here is to show that (despite many dependencies) this is true for all $i\in [r]$ with probability at least $e^{-n}$ . To do this, we form the random partition iteratively, each time dividing the subsets in two and tracking how the minimum degree condition (or more precisely something akin to P2 ) changes in the subgraphs induced on the sets. This is inspired by part of the analysis in the work by Barber, Lo, Kühn, and Osthus [2] introducing iterative absorption, and we use some similar calculations to those in [2].

For our analysis, we need the following standard concentration result for hypergeometric random variables (see, e.g. [17] for the standard definition of such a variable with parameters $N$ , $n$ , and $m$ ).

Theorem 2.2 (see, e.g. Theorem 2.10 in [17]). Let $X$ be a hypergeometric random variable with parameters $N$ , $n$ , and $m$ . Then, for any $t\gt 0$ ,

\begin{equation*} {\mathbb {P}}(|X-{\mathbb {E}} X|\geq t)\leq 2e^{-2t^2/n}. \end{equation*}

We can now state and prove our key lemma (see also Lemma 2.11 for a stronger result for $\ell =0$ ).

Lemma 2.3. Let $1\le \ell \lt k$ and let $1/n\ll 1/m\ll \delta,\gamma,1/k$ satisfy $(k-\ell )\mid n$ . Then, there exists a tuple $\mathbf{n}=(n_1,\dots,n_r)$ with $\sum _{i\in [r]}n_i=n$ and, for each $i\in [r]$ , $m\le n_i\le 5m$ and $(k-\ell )\mid n_i$ , such that the following holds. If $H$ is an $n$ -vertex $k$ -graph with $\delta (H)\geq (\delta +\gamma )n$ , then the number of $(\mathbf n,\delta +\gamma/2)$ -good partitions of $V(H)$ is at least $e^{-n}\binom{n}{n_1,\ldots, n_r}$ .

Proof. Let $s$ satisfy $2m\leq n/2^s\lt 4m$ and let $r=2^s$ . Since $(k-\ell )\mid n$ , we can choose integers $n_i$ , $i\in [r]$ , so that $m\leq n_i\leq 5m$ and $(k-\ell )|n_i$ , for each $i\in [r]$ , $\sum _{i\in [r]}n_i=n$ , and $|n_i-n_j|\le 2k$ for all $1\le i\lt j\le r$ . We will show that the lemma holds with $\mathbf{n}\;:\!=\;(n_1,\ldots,n_r)$ , so let $H$ be any $n$ -vertex $k$ -graph with $\delta (H)\geq (\delta +\gamma )n$ .

We start by iteratively partitioning $V(H)$ in 2 at random. For each $0\leq i\leq s$ , let $r_i=2^i$ , and for each $0\leq i\leq s$ and $j\in [r_i]$ , let

(2.1) \begin{equation} m_{i,j}=\sum _{i'=(j-1)\cdot 2^{s-i}+1}^{j\cdot 2^{s-i}}n_{i'}. \end{equation}

Let $V_{0,1}=V(H)$ . Iteratively, do the following for each $i\in [s]$ . For each $j\in [r_{i-1}]$ , uniformly at random divide $V_{i-1,j}$ into two sets $V_{i,2j-1}$ and $V_{i,2j}$ so that $|V_{i,2j-1}|=m_{i,2j-1}$ and $|V_{i,2j}|=m_{i,2j}$ , noting that

\begin{align*} |V_{i-1,j}|&=m_{i-1,j}=\sum _{i'=(j-1)\cdot 2^{s-i+1}+1}^{j\cdot 2^{s-i+1}}n_{i'} =\sum _{i'=(2j-2)\cdot 2^{s-i}+1}^{(2j-1)\cdot 2^{s-i+1}}n_{i'}+\sum _{i'=(2j-1)\cdot 2^{s-i}+1}^{2j\cdot 2^{s-i+1}}n_{i'}=m_{i,{2j-1}}+m_{i,2j}. \end{align*}

Note that this process ends with the partition $V(H)=V_{s,1}\cup V_{s,2}\cup \ldots \cup V_{s,r}$ with $|V_{s,i}|=m_{s,i}=n_i$ for each $i\in [r]$ , whose distribution is that of a partition of $V(H)$ chosen uniformly at random subject to these set sizes.

Now, for each $0\leq i\leq s$ and $j\in [r_{i}]$ , let $E_{i,j}$ be the event where, for every $U\subset V_{i,j-1}\cup V_{i,j}\cup V_{i,j+1}$ (with, as in later occurrences, addition modulo $r_i$ in the second subscript), if $|U|=k-1$ , then

(2.2) \begin{equation} d(U,V_{i,j})\geq \Big (\delta +\gamma -2m_{i,j}^{-1/4}\Big )m_{i,j}. \end{equation}

For each $0\leq i\leq s$ , let $E_i$ be the event that $E_{i,j}$ holds for all $j\in [r_i]$ , noting that $E_0$ holds because $\delta (H)\geq (\delta +\gamma )n$ . We will now show that the lemma is implied by the following claim.

Claim 2.4. For each $i\in [s]$ , ${\mathbb{P}}(E_i|E_{i-1})\geq \exp\!(\!-\!r_{i-1})$ .

Note that if $E_s$ holds, then $(V_{s,1},\ldots,V_{s,r})$ is $(\mathbf{n}, \delta +\gamma/2)$ -good as $m_{s,i}=n_i\geq m$ for each $i\in [r]$ and $1/m\ll \gamma$ . Thus, considering the distribution of the random partition $V(H)=V_{s,1}\cup V_{s,2}$ $\cup \ldots \cup V_{s,r}$ , the number of $(\mathbf{n}, \delta +\gamma/2)$ -good partitions of $V(H)$ is at least ${\mathbb{P}}(E_s)\cdot \frac{n!}{n_1!\ldots n_r!}$ so that the lemma follows from the claim as

\begin{equation*} {\mathbb {P}}(E_s)\geq \prod _{i\in [s]}{\mathbb {P}}(E_i|E_{i-1})\geq \exp \Big (\!-\!\sum _{i\in [s]}r_{i-1}\Big )\geq \exp\!(\!-\!r_s)=\exp\!(\!-\!2^s)\geq \exp\!(\!-\!n/2m)\geq \exp\!(\!-\!n).\end{equation*}

Thus, it is only left to prove the claim.

Proof of Claim 2.4. Fix $i\in [s]$ . For each $j\in [r_{i-1}]$ , let $F_{i-1,j}$ be the event that, for every $U\subset V_{i-1,j-1}\cup V_{i-1,j}\cup V_{i-1,j+1}$ with $|U|=k-1$ , we have

\begin{equation*} d(U,V_{i,2j-1})\geq (\delta +\gamma -2m_{i,2j-1}^{-1/3})m_{i,2j-1}\;\;\text { and }\;\;d(U,V_{i,2j})\geq (\delta +\gamma -2m_{i,2j}^{-1/3})m_{i,2j}. \end{equation*}

Note that, for each $j\in [r_{i-1}]$ , as $V_{i-1,j}=V_{i,2j-1}\cup V_{i,2j}$ , if $F_{i-1,j}$ holds, then both $E_{i,2j-1}$ and $E_{i,2j}$ hold. Furthermore, once we have chosen the partition $V(H)=V_{i-1,1}\cup V_{i-1,2}\cup \ldots \cup V_{i-1,r_{i-1}}$ , the events $F_{i-1,j}$ , $j\in [r_{i-1}]$ , are independent. We will show that if we choose a partition $V(H)=V_{i-1,1}\cup V_{i-1,2}\cup \ldots \cup V_{i-1,r_{i-1}}$ for which $E_{i-1}$ holds, then, for each $j\in [r_{i-1}]$ , the probability that $F_{i-1,j}$ holds is at least $e^{-1}$ , and thus the probability that every such $F_{i-1,j}$ , $j\in [r_{i-1}]$ , and hence $E_{i}$ holds is at least $\exp\!(\!-\!r_{i-1})$ . If this holds for every partition $V(H)=V_{i-1,1}\cup V_{i-1,2}\cup \ldots \cup V_{i-1,r_{i-1}}$ for which $E_{i-1}$ holds, we then have that ${\mathbb{P}}(E_i|E_{i-1})\geq \exp\!(\!-\!r_{i-1})$ , as required.

Suppose then that we have chosen our partition $V(H)=V_{i-1,1}\cup V_{i-1,2}\cup \ldots \cup V_{i-1,r_{i-1}}$ and that $E_{i-1}$ holds, and let $j\in [r_{i-1}]$ . Let $U\subset V_{i-1,j-1}\cup V_{i-1,j}\cup V_{i-1,j+1}$ satisfy $|U|=k-1$ . Note that $d(U,V_{i,2j-1})$ has a hypergeometric distribution with parameters $N'\;:\!=\;m_{i-1,j}$ , $n'\;:\!=\;m_{i,2j-1}$ , and $m'\;:\!=\;d(U,V_{i-1,j})$ . Furthermore, as $E_{i-1}$ , and hence $E_{i-1,j}$ holds, we have that

\begin{equation*}{\mathbb {E}} [d(U,V_{i,2j-1})]=\frac {m_{i,2j-1}}{m_{i-1,j}}\cdot d(U,V_{i-1,j})\overset {(2.2)}{\geq } \Big (\delta +\gamma -2m_{i-1,j}^{-1/4}\Big )m_{i,2j-1}.\end{equation*}

Therefore, by Theorem 2.2, we have

(2.3) \begin{equation} {\mathbb{P}}\Big (d(U,V_{i,2j-1})\leq \Big (\delta +\gamma -2m_{i-1,j}^{-1/4}\Big )m_{i,2j-1}-m_{i,2j-1}^{2/3}\Big )\leq 2\exp\!(\!-\!2m_{i,2j-1}^{1/3}). \end{equation}

Now, for each $i',j'\in [s]$ , we have $|n_{i'}-n_{j'}|\leq 2k\leq n_{i'}/10$ and hence $n_{i'}\leq 11n_{j'}/10$ . Thus, by (2.1) we have $m_{i,2j-1}\leq 11 m_{i-1,j}/20$ and hence

(2.4) \begin{equation} 2m_{i-1,j}^{-1/4}\cdot m_{i,2j-1}+m_{i,2j-1}^{2/3}\leq (\tfrac{11}{20})^{1/4}\cdot 2 m_{i,2j-1}^{3/4}+m_{i,2j-1}^{2/3}\leq 2m_{i,2j-1}^{3/4}, \end{equation}

as $m_{i,2j-1}\geq m$ and $1/m\ll 1$ . In combination, (2.3) and (2.4) give us that

\begin{equation*} {\mathbb {P}}\Big (d(U,V_{i,2j-1})\leq \Big (\delta +\gamma -2m_{i,2j-1}^{-1/4}\Big )m_{i,2j-1}\Big )\leq 2\exp \Big (\!-\!2m_{i,2j-1}^{1/3}\Big ). \end{equation*}

Similarly, this holds with $V_{i,2j}$ and $m_{i,2j}$ in place of $V_{i,2j-1}$ and $m_{i,2j-1}$ . Furthermore, from (2.1) and that $n_{i'}\leq 11n_{j'}/10$ for all $i',j'\in [s]$ , it follows that $|V_{i-1,j-1}\cup V_{i-1,j}\cup V_{i-1,j+1}|\leq 66m_{i,2j-1}/10$ and $\leq 66m_{i,2j}/10$ . Therefore, using a union bound over all $U\subset V_{i-1,j-1}\cup V_{i-1,j}\cup V_{i-1,j+1}$ satisfying $|U|=k-1$ , we have that $F_{i-1,j}$ holds with probability at least

\begin{equation*} 1-(7m_{i,2j-1})^{k-1}\cdot 2\exp\!(\!-\!2m_{i,2j-1}^{1/3})-(7m_{i,2j})^{k-1}\cdot 2\exp\!(\!-\!2m_{i,2j}^{1/3})\geq e^{-1}, \end{equation*}

as required, where we have used that $m_{i,2j-1},m_{i,2j}\geq m$ and $1/m\ll 1$ .

2.2 Counting Hamilton $\ell$ -cycles

We say that a $k$ -graph $P$ with $t$ vertices is an $\ell$ -path, where $1\le \ell \lt k$ , if $(k-\ell )\mid (t-\ell )$ , and there exists an ordering $v_1,\ldots, v_t$ of $V(P)$ such that every edge of $P$ consists of $k$ consecutive vertices and such that every two consecutive edges intersect in exactly $\ell$ vertices. We will usually identify an $\ell$ -path $P$ with a corresponding ordering $v_1,\ldots, v_t$ . The ends of an $\ell$ -path $P=v_1\ldots v_t$ are the tuples $\mathbf{v}=(v_1,\ldots,v_\ell )$ and $\mathbf{v}'=(v_{t-\ell +1},\ldots, v_t)$ , in which case we say that $\mathbf{v}$ and $\mathbf{v}'$ are $\ell$ -connected by $P$ . We say that a $k$ -graph $H$ contains a Hamilton $\ell$ -path if there is an $\ell$ -path $P$ in $H$ with $V(P)=V(H)$ .

Definition 2.5. A $k$ -graph $H$ is Hamilton $\ell$ -path connected if, for any pair of vertex-disjoint tuples $\mathbf u,\mathbf v\in (V(H))_\ell$ , there is a Hamilton $\ell$ -path in $H$ which $\ell$ -connects $\mathbf u$ with $\mathbf v$ .

The next lemma states that $k$ -graphs with large minimum codegree which satisfies the natural divisibility conditions are Hamilton $\ell$ -path connected. The proof of Lemma 2.6 is a very straightforward modification of the original argument of Kühn, Mycroft, and Osthus [23] for finding Hamilton $\ell$ -cycles via the absorption method (as can be seen in the special case when $(k-\ell )\mid k$ , where this was done by Glock, Gould, Joos, Kühn, and Osthus as [13, Lemma 3.7]). For completion, however, we include a proof in an appendix.

Lemma 2.6. Let $1\leq \ell \lt k$ and let $1/n\ll \gamma,1/k$ satisfy $(k-\ell )\nmid (n-\ell )$ . If $H$ is an $n$ -vertex $k$ -graph with $\delta (H)\geq (\delta _{k,\ell }+\gamma )n$ (see [1.1]), then $H$ is Hamilton $\ell$ -path connected.

Now we are ready for the proof of our first main result.

Proof of Theorem 1.2. Let $\delta =\delta _{k,\ell }$ and let $m$ be such that every $k$ -graph on $m'\geq m/2$ vertices with minimum codegree at least $(\delta +\gamma/4)m'$ is Hamilton $\ell$ -path connected (using Lemma 2.6) and such that $1/m\ll \delta,\gamma,1/k$ . Let $n_0$ and $C$ be such that, for every $n\geq n_0$ , $1/n\ll 1/C\ll 1/m$ . Let $H$ be an $n$ -vertex $k$ -graph with $\delta (H)\geq (\delta +\gamma )n$ . By Lemma 2.3, there exist a tuple $\mathbf{n}=(n_1,\dots, n_r)$ with $\sum _{i\in [r]}n_i=n$ and, for each $i\in [r]$ , $m\le n_i\le 5m$ and $(k-\ell )\mid n_i$ , such that $V(H)$ has at least $e^{-n}\binom{n}{n_1,\ldots,n_r}$ partitions that are $(\mathbf{n},\delta +\gamma/2)$ -good.

Now, given a partition $\mathcal P=(V_1,\ldots,V_r)$ of $V(H)$ , say that a Hamilton $\ell$ -cycle $Q$ is $\mathcal P$ -respecting if, for each $i\in [r]$ (for some direction and working modulo $r$ in the subscript), all the vertices in $V_i$ appear concurrently on $Q$ , and the interval of vertices in $V_i$ on $Q$ is just before the interval of vertices in $V_{i+1}$ on $Q$ . (See Fig. 1 for a Hamilton cycle that is $(V_1,\ldots,V_r)$ -respecting.)

Claim 2.7. For each $(\mathbf{n},\delta +\gamma/2)$ -good partition $\mathcal P=(V_1,\ldots,V_r)$ , $H$ has a $\mathcal P$ -respecting Hamilton $\ell$ -cycle.

Before proving Claim 2.7, let us show how to deduce the theorem from it. Note that any Hamilton $\ell$ -cycle in $H$ respects at most $2n$ partitions $(V_1,\ldots,V_r)$ of $V(H)$ with $|V_i|=n_i$ for each $i\in [r]$ , as choosing a direction and the first vertex of $V_1$ specifies the ordered partition. Then, by Claim 2.7 and our bound on the number of $(\mathbf{n},\delta +\gamma/2)$ -good partitions of $V(H)$ , the number of Hamilton $\ell$ -cycles in $H$ is at least

(2.5) \begin{equation} \frac{e^{-n}}{2n}\cdot \binom{n}{n_1,\ldots,n_r}= \frac{e^{-n}}{2n}\cdot \frac{n!}{\prod _{i\in [r]}{n_i!}}\geq \frac{e^{-n}}{2n}\cdot \frac{n!}{(5m)!^{n/m}}\geq \exp\!(n\log n-Cn), \end{equation}

using Stirling’s formula and that $1/n\ll 1/C\ll 1/m$ .

Therefore, it is left only to prove Claim 2.7.

Proof of Claim 2.7. Let $\mathcal P=(V_1,\ldots,V_r)$ be an $(\mathbf{n},\delta +\gamma/2)$ -good partition. For each $i\in [r]$ , using that $|V_i|\geq m\geq \ell$ , pick an arbitrary $\ell$ -tuple $\mathbf v_i=(v_{i,1},v_{i,2},\ldots,v_{i,\ell })\in (V_i)_{\ell }$ . For each $i\in [r]$ , let $H_i=H[V_i\cup \{v_{i-1,1},\ldots,v_{i-1,\ell }\}]$ (working modulo $r$ in the indices) so that, as $\mathcal P$ is $(\mathbf{n},\delta +\gamma/2)$ -good, we have that $\delta (H_i)\geq (\delta +\gamma/2)|V_{i}|\geq (\delta +\gamma/4)|H_i|$ . Moreover, $|H_i|-\ell =n_i$ is divisible by $k-\ell$ . Therefore, by Lemma 2.6, there is a Hamilton $\ell$ -path in $H_i$ with vertex sequence $v_{i-1,1}v_{i-1,2}\ldots v_{i-1,\ell }L_i v_{i,1}\ldots v_{i,\ell }$ for some sequence $L_i$ . Then, the ordering $L_1v_{1,1}\ldots v_{1,\ell }L_2v_{2,1}\ldots v_{2,\ell }L_3\ldots v_{r-1,1}\ldots v_{r-1,\ell }L_rv_{r,1}\ldots v_{r,\ell }$ is an ordering of the vertices of $H$ which gives a Hamilton $\ell$ -cycle respecting the partition $(V_1,\ldots,V_r)$ , as required.

2.3 Counting powers of tight Hamilton cycles

For Theorem 1.3, we use the following definitions. Let $t\geq k\geq 2$ and let $H$ be a $k$ -graph. The $t$ -clique graph of $H$ , denoted $K_t(H)$ , is the $t$ -graph with vertex set $V(K_t(H))=V(H)$ where $\{v_1,\ldots, v_t\}$ is an edge of $K_t(H)$ if and only if $H[\{v_1,\ldots, v_t\}]$ is a $k$ -uniform clique in $H$ .

Our proof of Theorem 1.3 is very similar to the proof of Theorem 1.2, so we do not repeat it here and only state the differences. The main thing is to note that, given

• a partition $V(H)=V_1\cup \ldots \cup V_r$ and distinct vertices $v_{i,1},\ldots,v_{i,t-1}\in V_i$ , $i\in [r]$ , such that, for each $i\in [r]$ , $H[\{v_{i,1},\ldots,v_{i,t-1}\}]$ is a $(t-1)$ -clique, and

• orderings $L_i$ , $i\in [r]$ , of the vertices in $V_i\setminus \{v_{i,1},\ldots,v_{i,t-1}\}$ where $v_{i-1,1},\ldots,v_{i-1,t-1}L_iv_{i,1},\ldots,v_{i,t-1}$ is the ordering of a Hamilton tight path in $K_t(H[V_i\cup \{v_{i-1,1},\ldots,v_{i-1,t-1}\}])$ for each $i\in [r]$ ,

the ordering $L_1v_{1,1}\ldots v_{1,t-1}L_2v_{2,1}\ldots v_{2,t-1}L_3\ldots v_{r-1,1}\ldots v_{r-1,t-1}L_rv_{r,1}\ldots v_{r,t-1}$ is an ordering of the vertices of $H$ which gives a $(t-k+1)$ th power of a Hamilton tight cycle respecting the partition $(V_1,\ldots,V_r)$ . Thus, the proof of Theorem 1.3 follows identically to that of Theorem 1.2 using the following proposition to select the vertices $v_{i,1},\ldots,v_{i,t-1}\in V_i$ , $i\in [r]$ , in place of the vertices $v_{i,1},\ldots,v_{i,\ell }\in V_i$ , $i\in [r]$ , and the following lemma in place of Lemma 2.6.

Proposition 2.8. Let $t\geq k\geq 2$ and let $1/n\ll \gamma, 1/t$ . If $H$ is an $n$ -vertex $k$ -graph satisfying (1.2), then $H$ contains a $t$ -vertex $k$ -uniform clique.

Lemma 2.9. Let $t\geq k\geq 2$ and let $1/n\ll \gamma, 1/t$ . If $H$ is an $n$ -vertex $k$ -graph satisfying (1.2), then for every pair of disjoint tuples $\mathbf{v},\mathbf{v'}\in (V(H))_{t-1}$ whose vertices support a $(t-1)$ -vertex $k$ -uniform clique in $H$ , there is a Hamilton tight path in $K_t(H)$ with ends $\mathbf{v}$ and $\mathbf{v'}$ .

Proposition 2.8 can be proved simply by picking the vertices of the clique greedily, where the codegree bound used is comfortably sufficient for this. The proof of Lemma 2.9 follows the same ideas as the proof of Lemma 2.6 but uses the results of Pavez-Signé, Sanhueza-Matamala, and Stein [28] in place of those by Kühn, Mycroft, and Osthus [23]. We comment further on this in the appendix.

2.4 Counting $F$ -factors

To count factors, we no longer need to connect the different parts of a good partition, but we do wish to have conditions for different degrees than just the codegree, motivating the following definition.

Definition 2.10. Let $k,d\in \mathbb N$ satisfy $1\le d\le k-1$ . Let $\mu \gt 0$ and $\mathbf{n}=(n_1,\dots, n_r)\in \mathbb N^r$ . For an $n$ -vertex $k$ -graph $H$ , say that a partition $V(H)=V_1\cup \ldots \cup V_r$ is $(\mathbf{n},d,\mu )$ -good if, for each $i\in [r]$ , $|V_i|=n_i$ and $\delta _d(H[V_i])\geq \mu \binom{n_i}{k-d}$ .

With only minor modifications, including using McDiarmid’s inequality (see Lemma 1.2 in [27]) to bound similar events to the events $E_{i,j}$ , the proof of Lemma 2.3 can be adapted to prove the following.

Lemma 2.11. Let $1\le d\le k-1$ and let $1/n\ll 1/m\ll \gamma,\mu,1/k,1/t$ satisfy $t\mid n$ . Then, there exists a tuple $\mathbf{n} =(n_1,\ldots, n_r)\in \mathbb N^r$ , with $\sum _{i\in [r]}n_i=n$ , and $m\le n_i\le 5m$ and $t\mid n_i$ for each $i\in [r]$ , such that the following holds. If $H$ is an $n$ -vertex $k$ -graph with $\delta _d(H)\geq (\mu +\gamma )\binom{n}{k-d}$ , then the number of $(\mathbf{n},d,\mu +\gamma/2)$ -good partitions in $H$ is at least $e^{-n}\binom{n}{n_1,\ldots, n_r}$ .

Recalling that $\mu _{k,d}(F)$ is defined at the end of Section 1.1, we are now ready for the proof of Theorem 1.4.

Proof of Theorem 1.4. Let $1\le d\le k-1$ and let $F$ be a fixed $k$ -graph on $t$ vertices. Let $m$ be such that every $k$ -graph on $m'\geq m$ vertices, with $t\mid m'$ , and minimum $d$ -degree at least $(\mu _{k,d}(F)+\gamma/2)\binom{m'}{k-d}$ , contains an $F$ -factor (using the definition of $\mu _{k,d}(F)$ ). Let $n_0$ and $C$ be such that, for every $n\geq n_0$ , $1/n\ll 1/C\ll 1/m$ , and let $H$ be an $n$ -vertex $k$ -graph with $\delta _d(H)\geq (\mu _{k,d}(F)+\gamma )n^{k-d}$ . By Lemma 2.11, there is a tuple $\mathbf{n}=(n_1,\ldots, n_r)$ , with $\sum _{i\in [r]}n_i=n$ , and $m\le n_i\le 5m$ and $t\mid n_i$ for each $i\in [r]$ , such that the number of $(\mathbf{n},d,\mu _{k,d}(F)+\gamma/2)$ -good partitions of $V(H)$ is at least $e^{-n}\binom{n}{n_1,\ldots, n_r}$ .

For each $(\mathbf{n},d,\mu _{k,d}(F)+\gamma/2)$ -good partition $\mathcal P=(V_1,\ldots, V_r)$ , by the definition of $m$ , there is an $F$ -factor in $H[V_i]$ for each $i\in [r]$ , and therefore, $H$ has an $F$ -factor, $G$ , say, where $G[V_i]$ is an $F$ -factor of $H[V_i]$ for each $i\in [r]$ . On the other hand, given an $F$ -factor $G$ , the number of possible partitions $\mathcal P=(V_1,\ldots, V_r)$ , such that $G[V_i]$ is an $F$ -factor of $H[V_i]$ and $|V_i|=n_i$ for each $i\in [r]$ , is at most $(n/t)^{n/t}\leq \exp\!((n\log n)/t)$ . Therefore, the number of distinct $F$ -factors in $H$ is (similarly to [2.5]) at least

\begin{align*} &e^{-n}\cdot \exp\!(\!-\!(n/t)\log n)\cdot \binom {n}{n_1,\ldots, n_r} \geq e^{-n}\cdot \exp\!(\!-\!(n/t)\log n)\cdot \frac {n!}{(5m)!^{n/m}}\\[5pt] &\quad \geq \exp \big ((1-\tfrac {1}t)n\log n-Cn\big ),\end{align*}

as required, where we have used Stirling’s formula and that $1/n\ll 1/C\ll 1/m$ .