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 [Reference Dirac10] 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 [Reference Bolobás4] and Bondy [Reference Bondy5] asked for estimates of the number of distinct Hamilton cycles in graphs satisfying Dirac’s condition. Sárközy, Selkow, and Szemerédi [Reference Simonovits and Szemerédi32] 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 [Reference Janson16]). In 2009, Cuckler and Kahn [Reference Cuckler and Kahn8] 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$
).
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 [Reference Barber, Kühn, Lo and Osthus2]. 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 [Reference Hajnal and Szemerédi15, Reference Kühn and Osthus25], trees with bounded degree [Reference Csaba, Levitt, Nagy-György and Szemeredi7, Reference Komlós, Sárközy and Szemerédi19, Reference Komlós, Sárközy and Szemerédi21], powers of Hamilton cycles [Reference Komlós, Sárközy and Szemerédi22, Reference Komlós, Sárközy and Szemerédi20], and, more generally, graphs with bounded degree and sublinear bandwidth [Reference Böttcher, Schacht and Taraz6] (see also the excellent surveys [Reference Kühn, Mycroft and Osthus24, Reference Rödl, Szemerédi and Ruciński31]). 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 [Reference Gupta, Hamann, Müyesser, Parczyk and Sgueglia14] 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 [Reference Pham, Sah, Sawhney and Simkin30] if
$(k-\ell )|\ell$
and to Kühn, Mycroft, and Osthus [Reference Komlós, Sárközy and Szemerédi23] 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
\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 [Reference Kühn and Osthus26].
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 [Reference Komlós, Sárközy and Szemerédi22, Reference Komlós, Sárközy and Szemerédi20]. In 2020, Bedenknecht and Reiher [Reference Bedenknecht and Reiher3] 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 [Reference McDiarmid28], who showed that, with
$\gamma \gt 0$
fixed, if an
$n$
-vertex
$k$
-graph
$H$
has minimum codegree
\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 [Reference Pham, Sah, Sawhney and Simkin30, Reference Komlós, Sárközy and Szemerédi22].
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 [Reference Hajnal and Szemerédi15] and Kühn and Osthus [Reference Kühn and Osthus25], for most cases, we do not have good bounds even in the case
$d=k-1$
(see the survey by [Reference Sárközy, Selkow and Szemerédi33] and references therein).
1.2 Counting spanning hypergraphs
As in Cuckler and Kahn’s work on Hamilton cycles [Reference Cuckler and Kahn8], 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
\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 [Reference Ferber, Krivelevich and Sudakov12] 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 [Reference Glock, Gould, Joos, Kühn and Osthus13], 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 [Reference Ferber, Hardiman and Mond11], 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 [Reference Glock, Gould, Joos, Kühn and Osthus13] 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 [Reference Ferber, Krivelevich and Sudakov12] 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 [Reference Kang, Kelly, Kühn, Osthus and Pfenninger18] and Pham, Sah, Sawhney, and Simkin [Reference Pavez-Signé, Sanhueza-Matamala and Stein29] 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 [Reference Kang, Kelly, Kühn, Osthus and Pfenninger18] even managed to remove the error term in the minimum degree condition.
In the graph case (
$k=2$
), Pham, Sah, Sawhney, and Simkin [Reference Pavez-Signé, Sanhueza-Matamala and Stein29] 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 [Reference Hajnal and Szemerédi15], 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 [Reference Allen, Böttcher, Corsten, Davies, Jenssen, Morris, Roberts and Skokan1].
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
-
P1
$|V_i|=n_i$
for each
$i\in [r]$
, and
-
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 [Reference Barber, Kühn, Lo and Osthus2] introducing iterative absorption, and we use some similar calculations to those in [Reference Barber, Kühn, Lo and Osthus2].
For our analysis, we need the following standard concentration result for hypergeometric random variables (see, e.g. [Reference Janson, uczak and Rucinski17] for the standard definition of such a variable with parameters
$N$
,
$n$
, and
$m$
).
Theorem 2.2 (see, e.g. Theorem 2.10 in [Reference Janson, uczak and Rucinski17]). 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
\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
\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
\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
\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 [Reference Komlós, Sárközy and Szemerédi23] 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 [Reference Glock, Gould, Joos, Kühn and Osthus13, 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
\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 [Reference McDiarmid28] in place of those by Kühn, Mycroft, and Osthus [Reference Komlós, Sárközy and Szemerédi23]. 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 [Reference Kühn and Osthus27]) 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$
.
Funding statement
This is supported by the European Research Council (ERC) under the European Union Horizon 2020 research and innovation programme (grant agreement no. 947978) and the Leverhulme Trust. Matías Pavez-Signé research is supportedby Agencia Nacional de Investigación y Desarrollo (ANID) Basal Grant CMM FB210005 and ANID Regular grant no. 1241398.
Appendix A. Proof of Lemmas 2.6 and 2.9
Here we provide a proof for Lemma 2.6. The proof is a straightforward modification of the original argument by Kühn, Mycroft, and Osthus [Reference Komlós, Sárközy and Szemerédi23] for finding Hamilton
$\ell$
-cycles in dense hypergraphs via the absorption method.
Definition A.1.
Let
$1\le \ell \lt k$
and let
$H$
be a
$k$
-graph. Say that an
$\ell$
-path
$P$
in
$H$
, with ends
$\mathbf{a},\mathbf{b}\in (V(H))_\ell$
, can absorb a collection of pairwise disjoint
$(k-\ell )$
-sets
$S_1,\ldots, S_t$
if
-
(i)
$P$
contains no vertex from
$\bigcup _{i\in [t]}S_i$
and
-
(ii) there is an
$\ell$
-path
$Q$
with vertex set
$V(Q)=V(P)\cup \bigcup _{i\in [t]}S_i$
and with ends
$\mathbf{a}$
and
$\mathbf{b}$
.
In this case, we say that
$P$
is an absorbing path for
$S_1,\ldots,S_t$
.
We may use a similar definition of absorbing paths that works for powers of tight cycles (for Lemma 2.9), in which case the absorbing paths are tight paths in the
$t$
-clique graph
$K_t(H)$
that can absorb vertices rather than
$(k-\ell )$
-sets (see Definition 7.1 in [Reference McDiarmid28]).
Definition A.2.
Let
$1\le \ell \lt k$
and let
$H$
be an
$n$
-vertex
$k$
-graph. Say that a
$(k-\ell )$
-set
$S\subset V(H)$
is
$(\beta,t)$
-good if
$H$
contains at least
$\beta n^t$
absorbing paths for
$S$
, each with exactly
$t$
vertices. If
$S$
is not
$(\beta,t)$
-good, we then say that
$S$
is
$(\beta,t)$
-bad.
The following result states that most
$(k-\ell )$
-sets are good in
$k$
-graphs with linear minimum codegree.
Lemma A.3 (Lemma 6.2 in [Reference Komlós, Sárközy and Szemerédi23]). Let
$k\geq 3$
and
$1\le \ell \lt k$
satisfy
$(k-\ell )\nmid k$
, and let
$1/n\ll \beta \ll \theta \ll \mu,1/k$
. There exists a constant
$t=t(k,\ell )$
such that if
$H$
is an
$n$
-vertex
$k$
-graph with
$\delta (H)\geq \mu n$
, then the number of
$(\beta,t)$
-bad
$(k-\ell )$
-sets in
$H$
is at most
$\theta n^{k-\ell }$
.
The next lemma says that we can find a short path
$P$
which can absorb any collection of
$o(n)$
pairwise disjoint good sets and, moreover, every vertex outside
$P$
belongs to only a few bad sets.
Lemma A.4 (Lemma 6.3 in [Reference Komlós, Sárközy and Szemerédi23]). Let
$k\geq 3$
and
$1\leq \ell \lt k$
satisfy
$(k-\ell )\nmid k$
, and let
$1/n\ll \alpha \ll \beta \ll \theta \ll \mu,1/k$
. If
$H$
is an
$n$
-vertex
$k$
-graph with
$\delta (H)\geq \mu n$
and
$t=t(k,\ell )$
from Lemma A.3
, then
$H$
contains an
$\ell$
-path
$P$
on at most
$\mu n$
vertices such that
-
(i) every vertex of
$H-V(P)$
lies in at most
$\theta n^{k-\ell -1}$
$(\beta,t)$
-bad
$(k-\ell )$
-sets and
-
(ii)
$P$
can absorb any collection of at most
$\alpha n$
disjoint
$(\beta,t)$
-good
$(k-\ell )$
-sets of vertices of
$H-V(P)$
.
For proving Lemma 2.9, we can show an analogue result in the spirit of Lemma A.4 for the
$t$
-clique graph
$K_t(H)$
using Lemma 7.3 in [Reference McDiarmid28] and Step 1 in the proof of Theorem 1.1 in [Reference McDiarmid28].
Next, we have a lemma for when any two disjoint ordered
$\ell$
-sets can be connected by a short
$\ell$
-path, as follows.
Lemma A.5 (Corollary 5.4 in [Reference Komlós, Sárközy and Szemerédi23]). Let
$k\geq 3$
and
$1\leq \ell \leq k-1$
satisfy
$(k-\ell )\nmid k$
, and let
$1/n\ll \mu,1/k$
. If
$H$
is an
$n$
-vertex
$k$
-graph with
$\delta (H)\geq \mu n$
, then for any two disjoint ordered
$\ell$
-sets
$\mathbf{a},\mathbf{b}\in (V(H))_\ell$
, there exists an
$\ell$
-path
$P$
with ends
$\mathbf{a}$
and
$\mathbf{b}$
that contains at most
$8k^5$
vertices.
We have a similar statement in the vein of Lemma A.5 for the clique graph (see [Reference McDiarmid28, Lemma 4.1]), which states that any two disjoint
$(t-1)$
-sets that support
$(t-1)$
-cliques in
$H$
can be connected in
$K_t(H)$
by many short tight paths.
The last two ingredients we need are, first, that the degree conditions are preserved by taking random subsets and, second, that hypergraphs with large vertex degree have perfect matchings.
Lemma A.6 (Lemma 8.1 in [Reference Komlós, Sárközy and Szemerédi23]). Let
$1\leq d\lt k$
and let
$1/n\ll \alpha,\mu,1/k$
. Let
$H$
be an
$n$
-vertex
$k$
-graph with
$\delta _d(H)\geq \mu \binom{n}{k-d}$
, and let
$R\subset V(H)$
be a random subset of size
$\alpha n$
. Then, with probability
$1-o(1)$
, we have
$|N_H(S)\cap \binom{R}{k-d}|\geq \mu \binom{\alpha n}{k-d}-n^{k-d-\frac{1}{3}}$
for every
$S\in \binom{V(H)}{d}$
.
Theorem A.7 (Perfect matching theorem [Reference Daykin and Häggkvist9]). Let
$n,k\geq 2$
such that
$k\mid n$
. If
$H$
is an
$n$
-vertex
$k$
-graph with
$\delta _1(H)\geq \frac{k-1}{k}(\binom{n-1}{k-1}-1)$
, then
$H$
contains a perfect matching.
Now we are ready for the proof of Lemma 2.6.
Proof of Lemma 2.6. We begin by choosing constants
\begin{align*} 1/n\ll \alpha \ll \beta \ll \theta \ll \theta '\ll \gamma \ll \mu \ll 1/k, \end{align*}
and let
$t=t(k,\ell )$
from Lemma A.3. Given disjoint
$\ell$
-tuples
$\mathbf{a}=(a_1,\ldots, a_\ell )$
and
$\mathbf{b}=(b_1,\ldots, b_\ell )$
in
$V(H)$
, set
$H'=H-\{a_1,\ldots,a_\ell,b_1,\ldots,b_\ell \}$
and
$n'=|H'|=n-2\ell$
, and note that
$\delta (H')\geq (\delta _{k,\ell }+\gamma/2)n'$
as
$1/n\ll 1/k$
. Using Lemma A.4, find an absorbing
$\ell$
-path
$P_0$
in
$H'$
with at most
$\gamma n'/16$
vertices which can absorb any collection of at most
$2\alpha n'$
pairwise disjoint
$(\beta,t)$
-good
$(k-\ell )$
-sets in
$V(H')$
(here we have used that
$\delta (H')\geq \gamma n'/16$
). Let
$G$
be an auxiliary
$(k-\ell )$
-graph with
$V(G)=V(H')$
and edge set consisting of all those
$(k-\ell )$
-sets in
$H'$
which are
$(\beta,t)$
-good. By Lemma A.3, for every
$v\in V(G)\setminus V(P_0)$
, we have
\begin{align*} d_{G(v)} \geq \binom{n'}{k-\ell -1}-{\theta }{n'}^{k-\ell -1}\geq (1-{{\theta }'})\binom{n'}{k-\ell -1}. \end{align*}
Let
$R\subset V(H')$
be a random subset of size
$\alpha n'$
. Then, by Lemma A.6, with probability
$1-o(1)$
,
-
(i)
$d_G(v,R)\geq (1-2\theta ')\binom{|R|}{k-\ell -1}$
for every
$v\in V(G)\setminus V(P_0)$
, and -
(ii)
$d_H(S,R)\geq (\delta _{k,\ell }+\gamma/4)|R|$
for every
$S\in \binom{V(H)}{k-1}$
.
Moreover, as
${\mathbb{E}}[|R\cap V(P_0)|]=\alpha |P_0|$
, Lemma 2.2 implies that
$|R\cap V(P_0)|\le 2\alpha |P_0|\le \alpha \gamma n'/8$
with probability
$1-o(1)$
. Therefore, there is a choice of
$R$
such that, letting
$R'=R\setminus V(P_0)$
, we have
-
R1
$\alpha n'\geq |R'|\geq (1-\mu )\alpha n'$
, -
R2
$d_G(v,R')\geq (1-\mu )\binom{|R'|}{k-\ell -1}$
for every
$v\in V(G)\setminus V(P_0)$
, and -
R3
$d_H(S,R')\geq (\delta _{k,\ell }+\gamma/8)|R'|$
for every
$S\in \binom{V(H)}{k-1}$
.
Let
$V'\subseteq V(H')\setminus (R'\cup V(P_0))$
be a subset obtained by removing at most
$k-\ell$
vertices so that
$|V'|$
is divisible by
$k-\ell$
. We write
$H''=H[V']$
and note that
$\delta (H'')\geq (\delta _{k,\ell }+\gamma/16)|H''|$
. Use Theorem 1.1 to find a Hamilton
$\ell$
-cycle in
$H''$
, and hence
$H''$
contains an
$\ell$
-path
$P$
with
$|P|\geq |H''|-2k$
. Let
$\mathbf x'=(x'_{\!\!1},\ldots,x'_{\!\!\ell})$
and
$\mathbf y'=(y'_{\!\!1},\ldots,y'_{\!\!\ell})$
be the ends of
$P_0$
, and let
$\mathbf x=(x_1,\ldots,x_\ell )$
and
$\mathbf y=(y_1,\ldots,y_\ell )$
be the ends of
$P$
. Using Lemma A.5 and R3, we find sequences of vertices
$L_{\mathbf{ax'}}, L_{\mathbf{y'x}}$
, and
$L_{\mathbf{yb}}$
such that
-
$|L_{\mathbf{ax'}}|,|L_{\mathbf{y'x}}|, |L_{\mathbf{yb}}|\le 8k^5$
,
-
$L_{\mathbf{ax'}}, L_{\mathbf{y'x}}$
and
$L_{\mathbf{yb}}$
are pairwise disjoint and contain vertices only from
$R'$
, and
-
$P_{\mathbf{ax'}}=a_1\ldots a_\ell L_{\mathbf{ax'}} x'_{\!\!1}\ldots x'_{\!\!\ell}$
,
$P_{\mathbf{y'x}}=y'_{\!\!1}\ldots y'_{\!\!\ell} L_{\mathbf{y'x}}x_1\ldots x_\ell$
, and
$P_{\mathbf{yb}}=y_1\ldots y_\ell L_{\mathbf{yb}} b_1\ldots b_\ell$
are
$\ell$
-paths.
Therefore, the sequence
\begin{align*} Q={a}_{1} \ldots{a}_{\ell } L_{\mathbf{ax}'} P_0 L_{\mathbf{y}'\mathbf{x}} P L_{\mathbf{yb}} b_1 \ldots b_{\ell } \end{align*}
is an
$\ell$
-path in
$H$
connecting
$\mathbf{a}$
with
$\mathbf{b}$
and using at most
$24k^5$
vertices from
$R'$
. Let
$X=V(H)\setminus V(Q)$
and note that, because of
R1
and
R2
, every vertex
$v\in X$
satisfies
\begin{equation} d_G(v,X)\geq (1-\mu )\binom{|R'|}{k-\ell -1}-25k^5\cdot |X|^{k-\ell -2}\geq (1-2\mu )\binom{|X|}{k-\ell -1}, \end{equation}
where we have used that
$|X\setminus R'|\le 24k^5+2k+(k-\ell )\le 25k^5$
and
$1/n\ll 1/k$
. Then, by (A.1) and Theorem A.7,
$G[X]$
contains a perfect matching
$S_1,\dots, S_j$
, which is a collection of at most
$|X|\le |R'|+2k+(k-\ell )\le 2\alpha n$
pairwise disjoint
$(\beta,t)$
-good
$(k-\ell )$
-sets. Finally, using Lemma A.4, we can absorb all the vertices from
$\bigcup _{i\in [j]} S_i$
which concludes the proof.
The proof of Lemma 2.9 follows a similar strategy. Let us sketch the main steps of the proof here. Given two disjoint tuples
$\mathbf{a}={(a_1,\ldots, a_{t-1})}$
and
$\mathbf{b}=(b_1,\ldots, b_{t-1})$
that support
$(t-1)$
-cliques in
$H$
, set
$H'=H-{\{a_1,\ldots, a_{t-1}, b_1,\ldots, b_{t-1}\}}$
. The proof of Lemma 2.9 consists of the following steps:
-
Find a short absorbing path
$P_0$
in
$K_t(H')$
capable of absorbing any collection of
$o(n)$
vertices. -
Set aside a reservoir
$R$
in
$H'- V(P_0)$
, and find a Hamilton tight path in
$K_t(H'-(V(P_0)\cup R))$
(this can be done as
$H'-(V(P_0)\cup R)$
satisfies (1.2) with a slightly worse error term). -
Using a corresponding connecting lemma ([Reference McDiarmid28, Lemma 4.1]) and the properties of the reservoir, find an almost spanning path
$Q$
with ends
$\mathbf{a}$
and
$\mathbf{b}$
which contains
$P_0$
. -
Finish the embedding using the properties of the absorbing path.
The main difference with the proof of Lemma 2.6 is that, in this case, we do not need to use any matching result in the absorption step as
$H$
contains no bad vertices (see [Reference McDiarmid28, Lemma 7.2]).
