text:
\begin{document}
\title[Hamilton $\ell$-cycles]{Minimum codegree threshold for Hamilton $\ell$-cycles in $k$-uniform hypergraphs}
\thanks{The second author is partially supported NSA grant H98230-12-1-0283 and NSF grant DMS-1400073.}
\author{Jie Han}
\address[Jie Han and Yi Zhao]
{Department of Mathematics and Statistics,\newline
\indent Georgia State University, Atlanta, GA 30303}
\email[Jie Han]{jhan22@gsu.edu}
\author{Yi Zhao}
\email[Yi Zhao]{yzhao6@gsu.edu}
\date{\today}
\subjclass{Primary 05C65, 05C45}
\keywords{Hamilton cycle, hypergraph, absorbing method, regularity lemma}
\begin{abstract}
For $1\le \ell<k/2$, we show that for sufficiently large $n$, every $k$-uniform hypergraph on $n$ vertices with minimum codegree at least $\frac n{2 (k-\ell)} $ contains a Hamilton $\ell$-cycle. This codegree condition is best possible and improves on work of H\`an and Schacht who proved an asymptotic result.
\end{abstract}

\maketitle

\section{Introduction}
A well-known result of Dirac \cite{Dirac} states that every graph $G$ on $n\ge 3$ vertices with minimum degree $\delta(G)\ge n/2$ contains a Hamilton cycle.
In recent years, researchers have worked on extending this result to hypergraphs -- see recent surveys of \cite{KuOs14ICM, RR}.
Given $k\ge 2$, a $k$-uniform hypergraph (in short, \emph{$k$-graph}) consists of a vertex set
$V$ and an edge set $E\subseteq \binom{V}{k}$, where every edge is a $k$-element subset of $V$.
Given a $k$-graph $\h$ with a set $S$ of $d$ vertices (where $1 \le d \le k-1$) we define $\d_{\h} (S)$ to be the number of edges containing $S$ (the subscript $\h$ is omitted if it is clear from the context). The \emph{minimum $d$-degree $\delta _{d} (\h)$} of $\h$ is the minimum of $\d_{\h} (S)$ over all $d$-vertex sets $S$ in $\h$.  We refer to  $\delta _1 (\h)$ as the \emph{minimum vertex degree} and  $\delta _{k-1} (\h)$ the \emph{minimum codegree} of $\h$.
For $1\le \ell< k$, a $k$-graph is a called an \emph{$\ell$-cycle} if its vertices can be ordered cyclically such that each of its edges consists of $k$ consecutive vertices and every two consecutive edges (in the natural order of the edges) share exactly $\ell$ vertices. In $k$-graphs, a $(k-1)$-cycle is often called a \emph{tight} cycle while a $1$-cycle is often called a \emph{loose} cycle. We say that a $k$-graph contains a \emph{Hamilton $\ell$-cycle} if it contains an $\ell$-cycle as a spanning subhypergraph.
Since a $k$-uniform $\ell$-cycle on $n$ vertices contains exactly $n/(k - \ell)$ edges, a necessary condition for a $k$-graph on $n$ vertices to contain a Hamilton $\ell$-cycle is that $k- \ell$ divides $n$.

Confirming a conjecture of Katona and Kierstead \cite{KK}, R\"odl, Ruci\'nski and Szemer\'edi \cite{RRS06, RRS08} showed that for any fixed $k$, every $k$-graph $\h$ on $n$ vertices with $\delta_{k-1}(\h)\ge n/2 + o(n)$ contains a tight Hamilton cycle.
When $k-\ell$ divides both $k$ and $|V|$, a $(k-1)$-cycle on $V$ trivially contains an $\ell$-cycle on $V$. Thus the result in \cite{RRS08} implies that for all $1\le \ell<k$ such that $k- \ell$ divides $k$, every $k$-graph $\h$ on $n\in (k-\ell)\mathbb{N}$ vertices with $\delta_{k-1}(\h)\ge n/2 + o(n)$ contains a Hamilton $\ell$-cycle.
It is not hard to see that these results are best possible up to the $o(n)$ term -- see Concluding Remarks for more discussion.
With long and involved arguments, R\"odl, Ruci\'nski and Szemer\'edi  \cite{RRS11} determined the minimum codegree threshold for tight Hamilton cycles in 3-graphs for sufficiently large $n$.
(Unless stated otherwise, we assume that $n$ is sufficiently large throughout the paper.)

Loose Hamilton cycles were first studied by K\"uhn and Osthus \cite{KO}, who proved that
every 3-graph on $n$ vertices with $\delta_2(\h)\ge n/4 + o(n)$ contains a loose Hamilton cycle.
This was generalized to arbitrary $k$ and $\ell=1$ by Keevash, K\"uhn, Mycroft, and Osthus \cite{KKMO} and to arbitrary $k$ and arbitrary $\ell< k/2$ by H\`an and Schacht \cite{HS}.

\begin{theorem}\cite{HS}\label{thmHS}
Fix integers $k\ge 3$ and $1\le \ell <k/2$. Assume that $\gamma>0$ and $n\in (k-\ell)\mathbb N$ is sufficiently large. If $\h=(V, E)$ is a $k$-graph on $ n$ vertices such that $\delta_{k-1}(\h)\ge (\frac 1{2(k-\ell)}+\gamma)n$, then $\h$ contains a Hamilton $\ell$-cycle.
\end{theorem}

Later K\"uhn, Mycroft, and Osthus \cite{KMO} proved that whenever $k-\ell$ does not divide $k$, every $k$-graph on $n$ vertices with
$\delta_{k-1}(\h)\ge \frac{n}{\lceil \frac{k}{k-\ell} \rceil (k-\ell)} +o(n)$ contains a Hamilton $l$-cycle.
This generalizes Theorem~\ref{thmHS} because $\lceil k/(k-\ell) \rceil =2 $ when $\ell< k/2$.
R\"odl and Ruci\'nski \cite[Problem 2.9]{RR} asked for the exact minimum codegree threshold for Hamilton $\ell$-cycles in $k$-graphs. The $k=3$ and $\ell=1$ case was answered by Czygrinow and Molla \cite{CzMo} recently. In this paper we determine this threshold for all $k\ge 3$ and $\ell<k/2$.

\begin{theorem}[Main Result] \label{thmmain}
Fix integers $k\ge 3$ and $1\le \ell <k/2$. Assume that $n\in (k-\ell)\mathbb N$ is sufficiently large.
If $\h=(V, E)$ is a $k$-graph on $n$ vertices such that
\begin{equation}\label{eqdeg2}
\delta_{k-1}(\h) \ge \frac n{2 (k-\ell)},
\end{equation}
then $\h$ contains a Hamilton $\ell$-cycle.
\end{theorem}

The following simple construction \cite[Proposition 2.2]{KMO} shows that Theorem~\ref{thmmain} is best possible,
and the aforementioned results in \cite{HS, KKMO, KMO, KO} are asymptotically best possible.
Let $\h_0=(V, E)$ be an $n$-vertex $k$-graph in which $V$ is partitioned into sets $A$ and $B$ such that $|A| = \left\lceil \frac{n}{\lceil \frac{k}{k- \ell} \rceil (k- \ell)} \right\rceil - 1$. The edge set $E$ consists of all $k$-sets that intersect $A$. It is easy to see that $\delta_{k-1}(\h_0)= |A|$.
However, an $\ell$-cycle on $n$ vertices has $n/(k-\ell)$ edges and every vertex on such a cycle lies in at most $\lceil \frac{k}{k-\ell} \rceil$ edges. Since $\lceil \frac{k}{k-\ell} \rceil |A|< n/(k-\ell)$, $\h_0$ contains no Hamilton $\ell$-cycle.

A related problem was studied by Bu\ss, H\`an, and Schacht \cite{BHS}, who proved that every 3-graph $\h$ on $n$ vertices with minimum vertex degree $\delta_1(\h)\ge (\frac 7{16}+o(1))\binom n2$ contains a loose Hamilton cycle. Recently we \cite{HZ1} improved this to an exact result.

\smallskip
Using the typical approach of obtaining exact results, our proof of  Theorem~\ref{thmmain} consists of an \emph{extremal case} and a \emph{nonextremal case}.

\begin{definition}
Let $\Delta>0$, a $k$-graph $\h$ on $n$ vertices is called $\Delta$-extremal if there is a set $B\subset V(\h)$, such that $|B| = \lfloor \frac{2(k-\ell)-1}{2(k-\ell)}n \rfloor $ and $e(B)\le \Delta n^k$.
\end{definition}

\begin{theorem}[Nonextremal Case]\label {lemNE}
For any integer $k\ge 3$, $1\le \ell <k/2$ and $0<\Delta<1$ there exists $\r>0$ such that the following holds. Suppose that $\h$ is a $k$-graph on $n$ vertices such that $n\in (k-\ell)\mathbb N$ is sufficiently large. If $\h$ is not $\Delta$-extremal and satisfies $\delta_{k-1}(\h)\ge (\frac 1{2(k-\ell)}-\r)n$, then $\h$ contains a Hamilton $\ell$-cycle.
\end{theorem}

\begin{theorem}[Extremal Case]\label {lemE}
For any integer $k\ge 3$, $1\le \ell <k/2$ there exists $\Delta>0$ such that the following holds. Suppose $\h$ is a $k$-graph on $n$ vertices such that $n\in (k-\ell)\mathbb N$ is sufficiently large. If $\h$ is $\Delta$-extremal and satisfies \eqref{eqdeg2}, then $\h$ contains a Hamilton $\ell$-cycle.
\end{theorem}

Theorem \ref{thmmain} follows from Theorem \ref{lemNE} and \ref{lemE} immediately by choosing $\Delta$ from Theorem \ref{lemE}.

Let us compare our proof with those in the aforementioned papers.
There is no extremal case in \cite{HS,KKMO,KMO,KO} because only asymptotic results were proved. Our Theorem~\ref{lemE} is new and more general than \cite[Theorem 3.1]{CzMo}. Following previous work \cite{HS, KMO, RRS06, RRS08, RRS11}, we prove Theorem~\ref{lemNE} by using the absorbing method initiated by R\"odl, Ruci\'nski and Szemer\'edi. More precisely, we find the desired Hamilton $\ell$-cycle by applying the Absorbing Lemma (Lemma~\ref{lemA}), the Reservoir Lemma (Lemma~\ref{lemR}), and the Path-cover Lemma (Lemma~\ref{lemP}). In fact, when $\ell< k/2$, the Absorbing Lemma and the Reservoir Lemma are not very difficult and already proven in \cite{HS} (in contrast, when $\ell> k/2$, the Absorbing Lemma in \cite{KMO} is more difficult to prove).
Thus the main step is to prove the Path-cover Lemma.
As shown in \cite{HS,KMO}, after the Regularity Lemma is applied, it suffices to prove that the cluster $k$-graph $\K$ can be tiled almost perfectly by the $k$-graph $\F_{k,\ell}$, whose vertex set consists of disjoint sets $A_1, \dots, A_{a-1}, B$ of size $k-1$, and whose edges are all the $k$-sets of the form $A_i\cup \{b\}$ for $i=1, \dots, a-1$ and all $b\in B$, where $a=\lceil \frac{k}{k-\ell} \rceil (k-\ell)$.
In this paper we reduce the problem to tile $\K$ with a much simpler $k$-graph $\Y_{k, 2\ell}$, which consists of two edges sharing $2\ell$ vertices. Because of the simple structure of $\Y_{k, 2\ell}$, we can easily find an almost perfect $\Y_{k, 2\ell}$-tiling unless $\K$ is in the extremal case (thus the original $k$-graph $\h$ is in the extremal case).
Interestingly $\Y_{3, 2}$-tiling was studied in the very first paper \cite{KO} on loose Hamilton cycles but as a separate problem. Our recent paper \cite{HZ1} indeed used $\Y_{3, 2}$-tiling as a tool to prove the corresponding path-cover lemma.
On the other hand, the authors of \cite{CzMo} used a different approach (without the Regularity Lemma) to prove the Path-tiling Lemma (though they did not state such lemma explicitly).

The rest of the paper is organized as follows: we prove Theorem~\ref{lemNE} in Section 2 and Theorem~\ref{lemE} in Section 3, and give concluding remarks in Section 4.

\smallskip
\textbf{Notation.} Given an integer $k\ge 0$, a $k$-set is a set with $k$ elements. For a set $X$, we denote by $\binom{X}{k}$ the family of all $k$-subsets of $X$. Given a $k$-graph $\h$ and a set $A \subseteq V(\h)$, we denote by $e_{\h}(A)$ the number of the edges of $\h$ in $A$. We often omit the subscript that represents the underlying hypergraph if it is clear from the context.
Given a $k$-graph $\h$ with two vertex sets $S, R$ such that $|S|<k$, we denote by $\deg_{\h} (S, R)$ the number of $(k-|S|)$-sets $T\subseteq R$ such that $S\cup T$ is an edge of $\h$ (in this case $T$ is called a \emph{neighbor} of $S$).
We define $\overline{\deg}_{\h}(S, R) = \binom{ |R\setminus S| }{k - |S|} - \deg(S, R)$ as the number of \emph{non-edges} on $S\cup R$ that contain $S$. When $R= V(\h)$ (and $\h$ is obvious), we simply write $\deg(S)$ and $\overline\deg(S)$. When $S= \{v\}$, we use $\deg(v, R)$ instead of $\deg(\{v\}, R)$.

A $k$-graph $\mathcal P$ is an \emph{$\ell$-path} if there is an ordering $(v_1, \dots, v_{t})$ of its vertices such that every edge consists of $k$ consecutive vertices and two consecutive edges intersect in exactly $\ell$ vertices. Note that this implies that $k-\ell$ divides $t-\ell$.
In this case we write $\mathcal{P} = v_1 \cdots v_t$ and call two $\ell$-sets $\{v_1, \dots, v_{\ell}\}$ and $\{v_{t-\ell+1}, \dots, v_t\}$ \emph{ends} of $\mathcal P$.

\section{Proof of Theorem \ref{lemNE}}
In this section we prove Theorem \ref{lemNE} by following the approach in \cite{HS}.

\subsection{Auxiliary lemmas and Proof of Theorem \ref{lemNE}}

We need \cite[Lemma 5]{HS} and \cite[Lemma 6]{HS} of H\`an and Schacht, in which only a linear codegree condition is needed.
Given a $k$-graph $\h$ with an $\ell$-path $\mathcal P$ and a vertex set $U\subseteq V(\h)\setminus V(\mathcal{P})$ with $|U|\in (k-\ell)\mathbb N$ , we say that $\mathcal P$ \emph{absorbs} $U$ if there exists an $\ell$-path $\mathcal Q$ of $\h$ with $V(\mathcal Q) = V(\mathcal P)\cup U$ such that $\mathcal P$ and $\mathcal Q$ have exactly the same ends.

\begin{lemma}[Absorbing lemma, \cite{HS}] \label{lemA}
For all integers $k\ge 3$ and $1\le \ell<k/2$ and every $\r_1>0$ there exist $\eta>0$ and an integer $n_0$ such that the following holds. Let $\h$ be a $k$-graph on $n\ge n_0$ vertices with $\delta_{k-1}(\h)\ge \r_1 n$. Then $\h$ contains an absorbing $\ell$-path $\mathcal P$ with $|V(\mathcal P)|\le \r_1^5 n$ that can absorb  any subset $U\subset V(\h) \setminus V(\mathcal P)$ of size $|U|\le \eta n$ and $|U|\in (k-\ell)\mathbb N$.
\end{lemma}

\begin{lemma}[Reservoir lemma, \cite{HS}]\label{lemR}
For all integers $k\ge 3$ and $1\le \ell<k/2$ and every $0<d, \r_2<1$ there exists an $n_0$ such that the following holds. Let $\h$ be a $k$-graph on $n>n_0$ vertices with $\delta_{k-1}(\h)\ge dn$, then there is a set $R$ of size at most $\r_2 n$ such that for all $(k-1)$-sets $S\in \binom V{k-1}$ we have $\deg(S, R)\ge d\r_2 n/2$.
\end{lemma}

The main step in our proof of Theorem \ref{lemNE} is the following lemma, which is stronger than \cite[Lemma 7]{HS}. We defer its proof to the next subsection.

\begin{lemma}[Path-cover lemma]\label{lemP}
For all integers $k\ge 3$, $1\le \ell <k/2$, and every $\r_3, \a>0$ there exist integers $p$ and $n_0$ such that the following holds. Let $\h$ be a $k$-graph on $n>n_0$ vertices with $\delta_{k-1}(\h)\ge (\frac1{2(k-\ell)} - \r_3)n$, then there is a family of at most $p$ vertex disjoint $\ell$-paths that together cover all but at most $\a n$ vertices of $\h$, or $\h$ is $14\r_3$-extremal.
\end{lemma}

We can now prove Theorem \ref{lemNE} in a similar way as in \cite{HS}.

\begin{proof}[Proof of Theorem \ref{lemNE}]
Given $k\ge 3$, $1\le \ell <k/2$ and $0<\Delta<1$, let $\r =\min\{ \frac{\Delta}{43}, \frac{1}{4k^2}\}$ and $n\in (k-\ell)\mathbb N$ be sufficiently large. Suppose that $\h = (V, E)$ is a $k$-graph on $n$ vertices with $\delta_{k-1}(\h)\ge (\frac1{2(k-\ell)} - \r)n$. Since $\frac1{2(k-\ell)} - \r>\r$, we can apply Lemma \ref{lemA} with $\r_1=\r$ and obtain $\eta>0$ and an absorbing path $\mathcal P_0$ with ends $S_0, T_0$ such that $|V(\mathcal P_0)|\le \r^5 n$ and $\mathcal{P}_0$ can absorb any $u$ vertices outside $\mathcal{P}_0$ if $u\le \eta n$ and $u\in (k-\ell)\mathbb N$.

Let $V_1 = (V\setminus V(\mathcal P_0)) \cup S_0 \cup T_0$ and $\h_1=\h[V_1]$.
Note that $|V(\mathcal P_0)|\le \r^5 n$ implies that $\delta_{k-1}(\h_1)\ge (\frac1{2(k-\ell)} - \r)n - \r^5 n\ge \frac1{2k}n$ as $\r<\frac1{4k^2}$ and $\ell\ge 1$.
We next apply Lemma \ref{lemR} with $d=\frac1{2k}$ and $\r_2=\min\{\eta/2, \r\}$ to $\h_1$ and get a reservoir $R\subset V_1$ with $|R|\le \r_2 |V(\h_1)|\le \r_2 n$ such that for any $(k-1)$-set $S\subset V_1$, we have
\begin{equation}\label{eq:Res}
\deg(S, R)\ge d\r_2 |V_1|/2 \ge d\r_2n/4.
\end{equation}
Let $V_2 = V\setminus (V(\mathcal P_0)\cup R)$, $n_2=|V_2|$, and $\h_2 = \h[V_2]$. Note that $|V(\mathcal P_0)\cup R|\le \r_1^5 n +\r_2 n \le 2\r n$, so
\[
\delta_{k-1}(\h_2)\ge \left(\frac1{2(k-\ell)} - \r \right)n - 2\r n \ge \left(\frac1{2(k-\ell)} - 3\r \right)n_2.
\]
Applying Lemma \ref{lemP} to $\h_2$ with $\r_3=3\r$ and $\a=\eta/2$, we obtain at most $p$ vertex disjoint $\ell$-paths that cover all but at most $\a n_2$ vertices of $\h_2$, unless $\h_2$ is $14\r_3$-extremal. In the latter case, there exists $B'\subseteq V_2$ such that $|B'| = \lfloor \frac{2k-2\ell-1}{2(k-\ell)}n_2 \rfloor$ and $e(B')\le 42\r n_2^k$. Then we add at most $n - n_2 \le 2\r n$ vertices from $V\setminus B'$ to $B'$ and obtain a vertex set $B\subseteq V(\h)$ such that $|B| = \lfloor \frac{2k-2\ell-1}{2(k-\ell)}n \rfloor$ and
\[
e(B)\le 42\r n_2^k + 2\r n \cdot \binom{n-1}{k-1} \le 42 \r n^k+ \r n^k \le \Delta n^k,
\]
which means that $\h$ is $\Delta$-extremal, a contradiction. In the former case, denote these $\ell$-paths by $\{\mathcal P_i\}_{i\in [p']}$ for some $p'\le p$, and their ends by $\{S_i, T_i\}_{i\in [p']}$. Note that both $S_i$ and $T_i$ are $\ell$-sets for $\ell<k/2$.
We arbitrarily pick disjoint $(k-2\ell-1)$-sets $X_0, X_1, \dots, X_{p'} \subset R\setminus (S_0\cup T_0)$ (note that $k- 2\ell -1\ge 0$).
Let $T_{p'+1} = T_0$.
By \eqref{eq:Res}, as $d\r_2n/4 \ge k(p'+1)$, we may find $p'+1$ vertices $v_0, v_1, \dots, v_{p'}\in R$ such that $ S_i\cup T_{i+1} \cup X_i \cup \{v_i \}\in E(\h)$ for $0\le i\le p'$. We thus connect $\pp_0, \pp_1, \ldots, \pp_{p'}$ together and obtain an $\ell$-cycle $\mathcal C$.
Note that
\[
|V(\h)\setminus V(\mathcal C)|\le |R|+\a n_2\le \r_2 n + \a n\le \eta n
\]
and $k-\ell$ divides $|V\setminus V(\mathcal C)|$ because $k-\ell$ divides both $n$ and $|V(\mathcal{C})|$.
So we can use $\mathcal P_0$ to absorb all unused vertices in $R$ and uncovered vertices in $V_2$ thus obtaining a Hamilton $\ell$-cycle in $\h$.
\end{proof}

The rest of this section is devoted to the proof of Lemma \ref{lemP}.

\subsection{Proof of Lemma \ref{lemP}}

Following the approach in \cite{HS}, we use the Weak Regularity Lemma, which is a straightforward extension of Szemer\'edi's regularity lemma for graphs \cite{Sze}.

Let $\h = (V, E)$ be a $k$-graph and let $A_1, \dots, A_k$ be mutually disjoint non-empty subsets of $V$. We define $e(A_1, \dots, A_k)$ to be the number of
\emph{crossing} edges, namely, those with one vertex in each $A_i$, $i\in [k]$, and the density of $\h$ with respect to ($A_1, \dots, A_k$) as
\[
d(A_1,\dots, A_k) = \frac{e(A_1, \dots, A_k)}{|A_1| \cdots|A_k|}.
\]
We say a $k$-tuple ($V_1, \dots, V_k$) of mutually disjoint subsets $V_1, \dots, V_k\subseteq V$ is \emph{$(\e, d)$-regular}, for $\e>0$ and $d\ge 0$, if
\[
|d(A_1, \dots, A_k) - d|\le \e
\]
for all $k$-tuples of subsets $A_i\subseteq V_i$, $i\in [k]$, satisfying $|A_i|\ge \e |V_i|$. We say ($V_1, \dots, V_k$) is \emph{$\e$-regular} if it is $(\e, d)$-regular for some $d\ge 0$. It is immediate from the definition that in an $(\e, d)$-regular $k$-tuple ($V_1, \dots, V_k$), if $V_i'\subset V_i$ has size $|V_i'| \ge c|V_i|$ for some $c\ge \e$, then ($V_1', \dots, V_k'$) is $(\e/c, d)$-regular.

\begin{theorem}[Weak Regularity Lemma]
\label{thmReg}
Given $t_0\ge 0$ and $\e>0$, there exist $T_0 = T_0(t_0, \e)$ and $n_0 = n_0(t_0,\e)$ so that for every $k$-graph $\h = (V, E)$ on $n>n_0$ vertices, there exists a partition $V = V_0 \cup V_1 \cup \cdots \cup V_t$ such that
\begin{enumerate}
\item[(i)] $t_0\le t\le T_0$,
\item[(ii)] $|V_1| = |V_2| = \cdots = |V_t|$ and $|V_0|\le \e n$,
\item[(iii)] for all but at most $\e \binom tk$ $k$-subsets $\{i_1,\dots, i_k\} \subset [t]$, the $k$-tuple $(V_{i_1}, \dots, V_{i_k})$ is $\e$-regular.
\end{enumerate}
\end{theorem}

The partition given in Theorem \ref{thmReg} is called an \emph{$\e$-regular partition} of $\h$. Given an $\e$-regular partition of $\h$ and $d\ge 0$, we refer to $ V_i, i\in [t]$ as \emph{clusters} and define the \emph{cluster hypergraph} $\K = \K(\e,d)$ with vertex set $[t]$ and $\{i_1,\dots,i_k\}\subset [t]$ is an edge if and only if $(V_{i_1}, \dots, V_{i_k})$ is $\e$-regular and $d(V_{i_1}, \dots, V_{i_k}) \ge d$.

We combine Theorem \ref{thmReg} and \cite[Proposition 16]{HS} into the following corollary, which shows that the cluster hypergraph almost inherits the minimum degree of the original hypergraph.
Its proof is standard and similar as the one of \cite[Proposition 16]{HS} so we omit it.\footnote{Roughly speaking, the lower bound for $\deg_{\K}(S)$ contains $-d$ because when forming $\K$, we discard all $k$-tuple $(V_{i_1}, \dots, V_{i_k})$ of density less than $d$, contains $- \sqrt{\e}$ because at most $\e \binom tk$ $k$-tuple are not regular, and contains $-(k-1)$ because we discard all non-crossing edges of $\h$.}

\begin{corollary} \cite{HS}
\label{prop16old}
Given $c, \e, d>0$, integers $k\ge 3$ and $t_0$, there exist $T_0$ and $n_0$ such that the following holds. Let $\h$ be a $k$-graph on $n>n_0$ vertices with $\delta_{k-1}(\h)\ge c n$. Then $\h$ has an $\e$-regular partition $V_0 \cup V_1 \cup \cdots \cup V_t$ with $t_0\le t\le T_0$, and in the cluster hypergraph $\K = \K(\e,d)$, all but at most $\sqrt \e t^{k-1}$ $(k-1)$-subsets $S$ of $[t]$ satisfy $\deg_{\K}(S)\ge (c - d - \sqrt{\e})t - (k-1)$.
\end{corollary}

Let $\h$ be a $k$-partite $k$-graph with partition classes $V_1,\dots, V_k$. Given $1\le \ell <k/2$, we call an $\ell$-path $\pp$ with edges $\{e_1, \dots, e_q\}$ \emph{canonical} with respect to $(V_1,\dots, V_k)$ if
\[
e_i\cap e_{i+1}\subseteq \bigcup_{j\in [\ell]}V_j \quad\text{ or }\quad e_i\cap e_{i+1}\subseteq \bigcup_{j\in [2\ell]\setminus [\ell]}V_j
\]
for $i\in [q-1]$.
When $j> 2\ell$, all $e_1\cap V_j, \dots, e_q\cap V_j$ are distinct and thus
$|V(\pp) \cap V_j| = |(e_1\cup \cdots \cup e_q)\cap V_j| = q$. When $j\le 2\ell$, exactly one of $e_{i-1}\cap e_i$ and $e_i\cap e_{i+1}$ intersects $V_j$. Thus $|V(\mathcal P)\cap V_j |=\frac{q+1}2$ if $q$ is odd.

We need the following proposition from \cite{HS}.
\begin{proposition} \cite[Proposition 19]{HS}
\label{prop:lpath}
Suppose that $1\le \ell<k/2$ and $\h$ is a $k$-partite, $k$-graph with partition classes $V_1, \dots, V_k$ such that $|V_i|=m$ for all $i\in [k]$, and $|E(\h)|\ge d m^k$. Then there exists a canonical $\ell$-path in $\h$ with $t > \frac{d m}{2(k-\ell)}$ edges.
\end{proposition}

In \cite{HS} the authors used Proposition \ref{prop:lpath} to cover an $(\e,d)$-regular tuple $(V_1,\dots, V_k)$ of sizes $|V_1|= \cdots = |V_{k-1}| = (2k-2\ell-1)m$ and $|V_k|=(k-1)m$ with vertex disjoint $\ell$-paths.  Our next lemma shows that an $(\e,d)$-regular tuple $(V_1,\dots, V_k)$ of sizes $|V_1| = \cdots = |V_{2\ell}|= m$ and $|V_i| = 2m$ for $i> 2\ell$ can be covered with $\ell$-paths.

\begin{lemma}\label{lem:path}
Fix $k\ge 3$, $1\le \ell<k/2$ and $\e, d>0$ such that $d>2\e$. Let $m>\frac{k^2}{\e^2(d-\e)}$. Suppose $\mathcal V = (V_1, V_2,\dots, V_k)$ is an $(\e,d)$-regular $k$-tuple with
\begin{equation}
\label{eq:Vi}
|V_1| = \cdots = |V_{2\ell}|= m \quad \text{and} \quad |V_{2\ell+1}| = \cdots = |V_k|= 2m.
\end{equation}
Then there are at most $\frac{2k}{(d-\e)\e}$ vertex-disjoint $\ell$-paths that together cover all but at most $2k\e m$ vertices of $\mathcal V$.
\end{lemma}

\begin{proof}
We greedily find vertex-disjoint canonical $\ell$-paths of odd length by Proposition \ref{prop:lpath} in $\mathcal V$ until less than $\e m$ vertices are uncovered in $V_1$ as follows. Suppose that we have obtained $\ell$-paths $\mathcal P_1, \dots, \mathcal P_p$ for some $p\ge 0$. Let $q = \sum_{j=1}^p e(\mathcal{P}_j)$. Assume that  for all $j$, $\mathcal P_j$ is canonical with respect to $\mathcal V$ and $e(\mathcal{P}_j)$ is odd. Then $\bigcup_{j=1}^p \mathcal{P}_i$ contains $\frac{q+p}2$ vertices of $V_i$ for $i\in [2\ell]$ and $q$ vertices of $V_i$ for $i> 2\ell$.
For $i\in [k]$, let $U_i$ be the set of uncovered vertices of $V_i$ and assume that $|U_1|\ge \e m$.
Using \eqref{eq:Vi}, we derive that $|U_1| = \cdots = |U_{2\ell}|\ge \e m$ and
\begin{equation}
\label{eq:Ui}
|U_{2\ell+1}| = \cdots = |U_k|= 2|U_1| + p.
\end{equation}
We now consider a $k$-partite subhypergraph $\mathcal{V}'$ with arbitrary $|U_1|$ vertices in each $U_i$ for $i\in [k]$. By regularity, $\mathcal{V}'$ contains at least $(d-\e) |U_1|^k$ edges, so we can apply Proposition \ref{prop:lpath} and find an $\ell$-path of odd length at least $\frac{(d-\e) \e m}{2(k-\ell)}-1 \ge \frac{(d-\e) \e m}{2 k}$ (dismiss one edge if needed).
We continue this process until $|U_1|< \e m$. Let $\mathcal P_1, \dots, \mathcal P_p$ be the $\ell$-paths obtained in $\mathcal{V}$ after the iteration stops.
Since $|V_1\cap V(\mathcal{P}_j)|\ge \frac{(d-\e)\e m}{2k}$ for every $j$, we have
\[
p\le \frac{m}{\frac{(d-\e)\e m}{2k}}=\frac{2k}{(d-\e)\e}.
\]
Since $m> \frac{k^2}{\e^2(d-\e)}$,
it follows that $p(k-2\ell)< \frac{2k^2}{(d-\e)\e} < 2\e m$.
By \eqref{eq:Ui}, the total number of uncovered vertices in $\mathcal V$ is
\begin{align*}
\sum_{i=1}^k |U_i| &= |U_1| 2\ell+(2|U_1|+p)(k-2\ell) = 2(k-\ell) |U_1| + p(k-2\ell) \\
&< 2(k-1)\e m+2\e m = 2k\e m. \qedhere
\end{align*}
\end{proof}

\smallskip
Given $k\ge 3$ and $0\le b<k$, let $\Y_{k,b}$ be a $k$-graph with two edges that share exactly $b$ vertices. In general, given two (hyper)graphs $\G$ and $\h$, a \emph{$\G$-tiling} is a sub(hyper)graph of $\h$ that consists of vertex-disjoint copies of $\G$. A $\G$-tiling is \emph{perfect} if it is a spanning sub(hyper)graph of $\h$. The following lemma is the main step in our proof of Lemma \ref{lemP} and
we prove it in the next subsection. Note that it generalizes \cite[Lemma 3.1]{CDN} of Czygrinow, DeBiasio, and Nagle.

\begin{lemma}[$\Y_{k,b}$-tiling Lemma] \label{lem:F}
Given integers $k\ge 3$, $1\le b<k$ and constants $\r,\beta >0$, there exist $0<\e'<\r \beta$ and an integer $n'$ such that the following holds. Suppose $\h$ is a $k$-graph on $n>n'$ vertices with $\deg(S)\ge (\tfrac1{2k-b} - \gamma)n$ for all but at most $\e' n^{k-1}$ sets $S\in \binom V{k-1}$,
then there is a $\Y_{k,b}$-tiling that covers all but at most $\beta n$ vertices of $\h$ unless $\h$ contains a vertex set $B$ such that $|B|=\lfloor \frac{2k - b-1}{2k-b}n\rfloor$ and $e(B)<6\r n^k$.
\end{lemma}

Now we are ready to prove Lemma \ref{lemP}.
\begin{proof}[Proof of Lemma \ref{lemP}]
Fix integers $k,\ell$, $0<\r_3,\a<1$. Let $\e', n'$ be the constants returned from Lemma \ref{lem:F} with $b=2\ell$, $\r=2\r_3$, and $\beta=\a/2$. Thus $\e'<\r \beta=\r_3 \a$. Let $T_0$ be the constant returned from Corollary \ref{prop16old} with $c=\frac 1{2(k- \ell)} - \r_3$, $\e=(\e')^2/16$, $d=\r_3/2$ and
$t_0 > \max\{n', 4k/\r_3\}$. Furthermore, let $p= \frac{2T_0}{(d-2\e)\e}$.

Let $n$ be sufficiently large and let $\h$ be a $k$-graph on $n$ vertices with $\delta_{k-1}(\h) \ge (\frac 1{2(k-\ell)} - \r_3) n$. Applying Corollary \ref{prop16old} with the constants chosen above, we obtain an $\e$-regular partition and a cluster hypergraph $\K = \K(\e, d)$ on $[t]$ such that for all but at most $\sqrt \e t^{k-1}$ $(k-1)$-sets $S\in \binom{[t]}{k-1}$,
\[
\deg_{\K}(S)\ge \left(\frac 1{2(k-\ell)} - \r_3 - d - \sqrt\e \right)t - (k-1) \ge \left(\frac 1{2(k-\ell)} - 2\r_3 \right)t,
\]
because $d=\r_3/2$, $\sqrt\e=\e'/4<\r_3/4$ and $k-1< \r_3 t_0/4\le \r_3 t/4$.
Let $m$ be the size of clusters, then $(1-\e)\frac nt\le m\le \frac nt$. Applying Lemma \ref{lem:F} with the constants chosen above, we derive that
either there is a $\Y_{k,2\ell}$-tiling $\mathscr Y$ of $\K$ which covers all but at most $\beta t$ vertices of $\K$ or there exists a set $B\subseteq V(\K)$, such that $|B| = \lfloor \frac{2k-2\ell-1}{2(k-\ell)}t \rfloor $ and $e_{\K}(B)\le 12\r_3 t^{k}$. In the latter case, let $B'\subseteq V(\h)$ be the union of the clusters in $B$. By regularity,
\[
e_{\h}(B')\le e_{\K}(B)\cdot m^k + \binom tk \cdot d \cdot m^k + \e \cdot \binom tk \cdot m^k + t \binom m2 \binom n{k-2},
\]
where the right-hand side bounds the number of edges from regular $k$-tuples with high density, edges from regular $k$-tuples with low density, edges from irregular $k$-tuples and edges that lie in at most $k-1$ clusters.
Since $m\le \frac nt$, $\e < \r_3/ 16$, $d=\r_3/2$, and $t^{-1}< t_0^{-1}< \r_3/(4k)$, we obtain that
\begin{align*}
e_{\h}(B')\le 12\r_3 t^k \cdot \left( \frac nt \right)^k + \binom tk \frac{\r_3}{2}  \left( \frac nt \right)^k  + \frac{\r_3}{16} \binom tk \left( \frac nt \right)^k + t \binom{n/t}2 \binom n{k-2} <13\r_3 n^k.
\end{align*}
Note that $|B'|= \lfloor \frac{2k-2\ell-1}{2(k-\ell)}t \rfloor m \le \frac{2k-2\ell-1}{2(k-\ell)}t \cdot \frac nt= \frac{2k-2\ell-1}{2(k-\ell)} n$, and consequently $|B'|\le \lfloor \frac{2k-2\ell-1}{2(k-\ell)}n \rfloor$. On the other hand,
\begin{align*}
|B'| &= \left\lfloor \frac{2k-2\ell-1}{2(k-\ell)}t \right\rfloor m\ge \left( \frac{2k-2\ell-1}{2(k-\ell)}t-1 \right)(1-\e)\frac nt \ge \left( \frac{2k-2\ell-1}{2(k-\ell)}t - \e \frac{2k-2\ell-1}{2(k-\ell)}t - 1 \right)\frac nt\\
&\ge \left( \frac{2k-2\ell-1}{2(k-\ell)}t-\e t \right)\frac nt =\frac{2k-2\ell-1}{2(k-\ell)}n-\e n.
\end{align*}
By adding at most $\e n$ vertices from $V\setminus B'$ to $B'$, we get a set $B''\subseteq V(\h)$ of size exactly $\lfloor \frac{2k-2\ell-1}{2(k-\ell)}n \rfloor$, with $e(B'')\le e(B') + \e n \cdot n^{k-1}<14\r_3 n^k$. Hence $\h$ is $14\r_3$-extremal.

In the former case, let $m'=\lfloor m/2 \rfloor$. If $m$ is odd, we throw away one vertex from each cluster covered by $\mathscr Y$ (we do nothing if $m$ is even).
Thus, the union of the clusters covered by $\mathscr Y$ contains all but at most $\beta t m+|V_0| + t\le \a n/2 + 2\e n$ vertices of $\h$.
We take the following procedure to each member $\Y'\in \mathscr Y$.
Suppose that $\Y'$ has the vertex set $[2k-2\ell]$ with edges $\{1, \dots, k\}$ and $\{k-2\ell+1, \dots, 2k-2\ell\}$.
For $i\in [2k-2\ell]$, let $W_i$ denote the corresponding cluster in $\h$. We split each $W_i$, $i= k-2\ell+1, \dots, k$, into two disjoint sets $W_i^1$ and $W_i^2$ of equal size. Then each of the $k$-tuples $(W_{k-2\ell+1}^1, \dots, W_{k}^1, W_1,\dots, W_{k-2\ell})$ and $(W_{k-2\ell+1}^2, \dots, W_{k}^2, W_{k+1},\dots, W_{2k-2\ell})$ is
$(2\e ,d')$-regular for some $d'\ge d$ and of sizes $m', \dots, m'$, $2m', \dots, 2m'$. Applying Lemma \ref{lem:path} to these two $k$-tuples, we find a family of
at most $\frac{2k}{(d'- 2\e)2\e}\le \frac{k}{(d - 2\e)\e}$
disjoint loose paths in each $k$-tuple covering all but at most $2k (2\e) m' \le 2k\e m$ vertices.
Since $|\mathscr Y|\le \frac t{2k-2\ell}$, we thus obtain a path-tiling that consists of at most
$2 \frac t{2k-2\ell}\frac{k}{(d-2\e)\e} \le \frac{2T_0}{(d-2\e)\e} = p$ paths and covers all but at most
\[
2\cdot 2k\e m \cdot \frac{t}{2k-2\ell}+\a n/2+2\e n < 6\e n + \a n/2  < \a n
\]
vertices of $\h$, where we use $2k-2\ell>k$ and $\e=(\e')^2/16<(\r_3 \a)^2/16<\a/12$. This completes the proof.
\end{proof}

\subsection{Proof of Lemma \ref{lem:F}}
We first give an upper bound on the size of $k$-graphs containing no copy of $\Y_{k,b}$. In its proof, we use the concept of \emph{link (hyper)graph}: given a $k$-graph $\h$ with a set $S$ of at most $k-1$ vertices, the \emph{link graph} of $S$ is the $(k-|S|)$-graph with vertex set $V(\h)\setminus S$ and edge set $\{e\setminus S: e\in E(\h), S\subseteq e\}$. Throughout the rest of the paper, we frequently use the simple identity $\binom{m}{b} \binom{m-b}{k-b} = \binom{m}{k} \binom{k}{b}$, which holds for all integers $0\le b\le k\le m$.

\begin{fact}\label{fact:Y}
Let $0\le b< k$ and $m\ge 2k-b$. If $\h$ is a $k$-graph on $m$ vertices containing no copy of $\Y_{k,b}$, then $e(\h)< \binom m{k-1}$.
\end{fact}

\begin{proof}
Fix any $b$-set $S\subseteq V(\h)$ ($S=\emptyset$ if $b=0$) and consider its link graph $L_S$. Since $\h$ contains no copy of $\Y_{k,b}$, any two edges of $L_S$ intersect. Since $m\ge 2k-b$, the Erd\H{o}s--Ko--Rado Theorem \cite{EKR} implies that $|L_S|\le \binom{m-b-1}{k-b-1}$. Thus,
\begin{align*}
e(\h)&\le \frac1{\binom{k}{b}}\binom {m}{b} \cdot \binom{m-b-1}{k-b-1}= \frac1{\binom{k}{b}}\binom {m}{b} \binom{m-b}{k-b}\frac{k-b}{m-b}=\binom{m}{k} \frac{k-b}{m-b} \\
&= \binom{m}{k-1} \frac{k-b}{k} \, \frac{m- k+1}{m-b} < \binom{m}{k-1}. \qedhere
\end{align*}
\end{proof}

\smallskip
\begin{proof}[Proof of Lemma \ref{lem:F}]

Given $\r, \beta>0$, let $\e'=\frac{\r \beta^{k-1}}{(k-1)!}$ and let $n\in \mathbb{N}$ be sufficiently large. Let $\h$ be a $k$-graph on $n$ vertices that satisfies $\deg(S)\ge (\frac1{2k-b} - \r )n$ for all but at most $\e' n^{k-1}$ $(k-1)$-sets $S$. Let $\mathscr Y=\{\Y_1, \dots, \Y_m\}$ be a largest $\Y_{k,b}$-tiling in $\h$ (with respect to $m$) and write $V_i=V(\Y_i)$ for $i\in [m]$. Let $V'=\bigcup_{i\in [m]}V_i$ and $U=V(\h)\setminus V'$. Assume that $|U|>\beta n$ -- otherwise we are done.

Let $C$ be the set of vertices $v\in V'$ such that $\deg(v, U)\ge (2k-b)^2\binom{|U|}{k-2}$. We will show that $|C|\le \frac n{2k-b}$ and $C$ covers almost all the edges of $\h$, which implies that $\h[V\setminus C]$ is sparse and $\h$ is in the extremal case.
We first observe that every $\Y_i\in \mathscr Y$ contains at most one vertex in $C$. Suppose instead, two vertices $x,y\in V_i$ are both in $C$. Since $\deg(x, U)\ge (2k-b)^2\binom{|U|}{k-2}>\binom{|U|}{k-2}$, by Fact \ref{fact:Y}, there is a copy of $\Y_{k-1,b-1}$ in the link graph of $x$ on $U$, which gives rise to $\Y'$, a copy of $\Y_{k,b}$ on $\{x\}\cup U$.
Since the link graph of $y$ on $U\setminus V(\Y')$ has at least
\[
(2k-b)^2\binom{|U|}{k-2} - (2k-b-1)\binom{|U|}{k-2}>\binom{|U\setminus V(\Y')|}{k-2}
\]
edges, we can find another copy of $\Y_{k,b}$ on $\{y\}\cup (U\setminus V(\Y'))$ by Fact~\ref{fact:Y}. Replacing $\Y_i$ in $\mathscr Y$ with these two copies of $\Y_{k,b}$ creates a $\Y_{k,b}$-tiling larger than $\mathscr Y$, contradiction.
Consequently,
\begin{align}
\sum_{S\in \binom{U}{k-1}}\deg(S, V')&\le |C|\binom {|U|}{k-1} + |V'\setminus C| (2k-b)^2\binom{|U|}{k-2} \nonumber\\
&< |C|\binom {|U|}{k-1} + (2k-b)^2 n\binom{|U|}{k-2} \quad \text{because  } |V'\setminus C|< n \nonumber \\
&=\binom {|U|}{k-1}\left(|C| +\frac{(2k - b)^2 n (k-1)}{|U|-k+2} \right). \label{eq:C1}
\end{align}
Second, by Fact \ref{fact:Y}, $e(U)\le \binom{|U|}{k-1}$ since $\h[U]$ contains no copy of $\Y_{k,b}$, which implies
\begin{equation}\label{eq:C2}
\sum_{S\in \binom{U}{k-1}}\deg(S, U)\le k \binom{|U|}{k-1}.
\end{equation}
By the definition of $\e'$, we have
\[
\e' n^{k-1}=\frac{\r \beta^{k-1}}{(k-1)!} n^{k-1}< \frac{\r |U|^{k-1}}{(k-1)!}< 2\r \binom{|U|}{k-1}
\]
as $|U|$ is large enough. At last, by the degree condition, we have
\begin{align}
\sum_{S\in \binom{U}{k-1}}\deg(S)\ge \left(\binom{|U|}{k-1}-\e' n^{k-1}\right)\left(\frac1{2k - b} - \r \right)n
>(1-2\r)\binom{|U|}{k-1}\left(\frac1{2k - b} - \r \right)n, \label{eq:C3}
\end{align}
Since $\deg(S)=\deg(S, U)+\deg(S, V')$, we combine \eqref{eq:C1}, \eqref{eq:C2} and \eqref{eq:C3} and get
\[
|C|>(1-2\r)\left(\frac1{2k - b} - \r \right)n - k - \frac{(2k - b)^2 n (k-1)}{|U|-k+2}.
\]
Since $|U|>16 k^3/\r$, we get
\[
\frac{(2k - b)^2 n (k-1)}{|U|-k+2}<\frac{4k^3 n}{|U|/2} < \r n/2.
\]
Since $2\r^2 n>k$ and $2k-b\ge 4$, it follows that $|C|>\left(\frac1{2k-b} - 2\r \right)n$.

Let $I_C$ be the set of all $i\in [m]$ such that $V_i\cap C\neq \emptyset$. Since each $V_i$, $i\in I_C$, contains one vertex of $C$, we have
\begin{equation}\label{eq:IC}
    |I_C| = |C|\ge \left(\frac1{2k-b} - 2\r \right)n \ge m - 2\r n.
\end{equation}
Let $A = (\bigcup_{i\in I_C}V_i\setminus C) \cup U$.

\begin{claim}\label{clm:edge}
$\h[A]$ contains no copy of $\Y_{k,b}$, thus $e(A)< \binom n{k-1}$.
\end{claim}

\begin{proof}
The first half of the claim implies the second half by Fact \ref{fact:Y}. Suppose instead, $\h[A]$ contains a copy of $\Y_{k,b}$, denoted by $\Y_0$. Note that $V(\Y_0) \not\subseteq U$ because $\h[U]$ contains no copy of $\Y_{k,b}$.  Without loss of generality, suppose that $V_1, \dots, V_{j}$ contain the vertices of $\Y_0$ for some $j\le 2k - b$. For $i\in [j]$, let $c_i$ denote the unique vertex in $V_i\cap C$. We greedily construct vertex-disjoint copies of $\Y_{k,b}$ on $\{c_i\}\cup U$, $i\in [j]$ as follows. Suppose we have found $\Y'_1, \dots, \Y'_i$ (copies of $\Y_{k,b}$) for some $i<j$.
Let $U_0$ denote the set of the vertices of $U$ covered by $\Y_0, \Y'_1, \dots, \Y'_i$. Then $|U_0|\le (i+1) (2k-b-1)\le (2k-b)(2k-b-1)$. Since $\deg(c_{i+1}, U)\ge (2k-b)^2\binom{|U|}{k-2}$, the link graph of $c_{i+1}$ on $U\setminus U_0$ has at least
\[
(2k-b)^2\binom{|U|}{k-2} - |U_0| \binom{|U|}{k-2} >\binom{|U|}{k-2}
\]
edges. By Fact~\ref{fact:Y}, there is a copy of $\Y_{k,b}$ on $\{c_{i+1}\}\cup (U\setminus U_0)$. Let $\Y'_1, \dots, \Y'_j$ denote the copies of $\Y_{k,b}$  constructed in this way. Replacing $\Y_1,\dots, \Y_{j}$ in $\mathscr{Y}$ with $\Y_0, \Y'_1, \dots, \Y'_j$ gives a $\Y_{k,b}$-tiling larger than $\mathscr Y$, contradiction.
\end{proof}

Note that the edges not incident to $C$ are either contained in $A$ or intersect some $V_i$, $i\notin I_C$. By \eqref{eq:IC} and Claim \ref{clm:edge},
\begin{align*}
e(V\setminus C) &\le e(A) + (2k-b)\cdot 2\r n \binom {n-1}{k-1}  < \binom n{k-1}  + (4k - 2b)\r n \binom {n}{k-1} \\
& <4k\r n \binom {n}{k-1}<\frac{4k}{(k-1)!}\r n^k\le 6\r n^k,
\end{align*}
where the last inequality follows from $k\ge 3$. Since $|C|\le \frac n{2k - b}$, we can pick a set $B\subseteq V\setminus C$ of order $\lfloor \frac{2k - b-1}{2k-b}n\rfloor$ such that $e(B)<6\r n^k$.
\end{proof}

\section{The Extremal Theorem}
In this section we prove Theorem \ref{lemE}. Assume that $k\ge 3$, $1\le \ell < k/2$ and $0<\Delta\ll 1$.
Let $n\in (k - \ell) \mathbb{N}$ be sufficiently large. Let $\h$ be a $k$-graph on $V$ of $n$ vertices such that $\delta_{k-1}(\h) \ge \frac n{2 (k-\ell)}$. Furthermore, assume that $\h$ is $\Delta$-extremal, namely, there is a set $B\subseteq V(\h)$, such that $|B| =\lfloor \frac{(2k-2\ell-1)n }{2(k-\ell)}\rfloor$ and $e(B)\le \Delta n^k$. Let $A=V\setminus B$. Then $|A|= \lceil \frac{n}{2(k-\ell)} \rceil$.

The following is an outline of the proof. We denote by $A'$ and $B'$ the sets of the vertices of $\h$ that behave as typical vertices of $A$ and $B$, respectively. Let $V_0=V\setminus(A'\cup B')$. It is not hard to show that $A' \approx A$, $B' \approx B$, and thus $V_0 \approx \emptyset$.
In the ideal case when $V_0 = \emptyset$ and $|B'| = (2k - 2\ell -1) |A'| $, we assign a cyclic order to the vertices of $A'$, construct $|A'|$ copies of $\mathcal{Y}_{k, \ell}$ such that each copy contains one vertex of $A'$ and $2k - \ell -1$ vertices of $B'$, and any two consecutive copies of  $\mathcal{Y}_{k, \ell}$ share exactly $\ell$ vertices of $B'$. This gives rise to the desired Hamilton $\ell$-cycle of $\h$. In the general case, we first construct an $\ell$-path $\mathcal{Q}$ with ends $L_0$ and $L_1$ such that $V_0 \subseteq V(\Q)$ and $|B_1| = (2k - 2\ell - 1) |A_1| + \ell$, where $A_1 = A' \setminus V(\Q)$ and $B_1 = (B\setminus V(\Q)) \cup L_0 \cup L_1$. Next we complete the Hamilton $\ell$-cycle by constructing an $\ell$-path on $A_1 \cup B_1$ with ends $L_0$ and $L_1$.

For the convenience of later calculations, we let $\e_0 =2 k!e\Delta \ll 1$ and claim that $e(B)\le \e_0 \binom {|B|}k$.
Indeed, since $2(k-\ell)-1\ge k$, we have
\[
\frac1e\le \left(1-\frac{1}{2(k-\ell)} \right)^{2(k-\ell)-1}\le \left(1-\frac{1}{2(k-\ell)} \right)^{k}.
\]
Thus we get
\begin{equation}\label{eqB}
e(B)\le \frac{\e_0}{2k!e} n^k \le \e_0 \left(1-\frac{1}{2(k-\ell)} \right)^{k} \frac{n^k}{2k!} \le \e_0 \binom {|B|}k.
\end{equation}

In general, given two disjoint vertex sets $X$ and $Y$ and two integers $i, j\ge 0$, a set $S\subset X\cup Y$ is called an $X^i Y^j$-set if $|S\cap X|= i$ and $|S\cap Y| =j$. When $X, Y$ are two disjoint subsets of $V(\h)$ and $i+j=k$, we denote by $\h(X^i Y^j)$ the family of all edges of $\h$ that are $X^i Y^j$-sets, and let $e_{\h}(X^i Y^{j})= |\h(X^i Y^j)|$ (the subscript may be omitted if it is clear from the context).
We use $\overline{e}_{\h}(X^i Y^{k-i})$ to denote the number of non-edges among $X^i Y^{k-i}$-sets. Given a set $L\subseteq X\cup Y$ with $|L\cap X|=l_1\le i$ and $|L\cap Y|=l_2\le k-i$, we define $ \deg(L, X^i Y^{k-i})$ as the number of edges in $\h(X^i Y^{k-i})$ that contain $L$, and
$\overline \deg(L, X^i Y^{k-i})=\binom{|X|-l_1}{i-l_1} \binom{|Y|-l_2}{k-i-l_2} - \deg(L, X^i Y^{k-i})$. Our earlier notation $\deg(S, R)$ may be viewed as $\deg(S, S^{|S|} (R\setminus S)^{k- |S|})$.

\subsection{Classification of vertices}

Let $\e_1={\e_0}^{1/3} $ and $\e_2=2\e_1^2$. Assume that the partition $V(\h)=A\cup B$ satisfies that $|B| =\lfloor \frac{(2k-2\ell-1)n }{2(k-\ell)}\rfloor$ and \eqref{eqB}. In addition, assume that $e(B)$ is the smallest among all such partitions. We now define
\begin{align*}
&A':=\left\{ v\in V: \deg (v,B)\ge (1-\e_1)\binom{|B|}{k-1} \right\}, \\
&B':=\left\{ v\in V: \deg (v,B)\le \e_1\binom{|B|}{k-1} \right\}, \\
& V_0:=V\setminus(A'\cup B').
\end{align*}

\begin{claim}\label{clm:eB}
$A\cap B'\neq \emptyset$ implies that $B\subseteq B'$, and $B\cap A'\neq \emptyset$ implies that $A\subseteq A'$.
\end{claim}

\begin{proof}
First, assume that $A\cap B'\neq \emptyset$. Then there is some $u\in A$ such that $\deg(u,B)\le \e_1\binom{|B|}{k-1}$. If there exists some $v\in B\setminus B'$, namely, $\deg(v, B)>\e_1\binom{|B|}{k-1}$, then we can switch $u$ and $v$ and form a new partition $A''\cup B''$ such that $|B''|=|B|$ and $e(B'')<e(B)$, which contradicts the minimality of $e(B)$.

Second, assume that $B\cap A'\neq \emptyset$. Then some $u\in B$ satisfies that $\deg(u,B)\ge (1-\e_1)\binom{|B|}{k-1}$. Similarly, by the minimality of $e(B)$, we get that for any vertex $v\in A$, $\deg(v, B)\ge (1-\e_1)\binom{|B|}{k-1}$, which implies that $A\subseteq A'$.
\end{proof}

\begin{claim}\label{clm:size}
$\{|A\setminus A'|, |B\setminus  B'|, |A'\setminus  A|, |B'\setminus  B|\}\le \e_2|B|$ and $|V_0|\le 2\e_2|B|$.
\end{claim}

\begin{proof}
First assume that $|B\setminus B'|> \e_2|B|$. By the definition of $B'$, we get that
\[
e(B) > \frac 1k \e_1\binom {|B|}{k-1} \cdot \e_2 |B| > 2\e_0\binom {|B|}k,
\]
which contradicts \eqref{eqB}.

Second, assume that $|A\setminus A'|> \e_2|B|$. Then by the definition of $A'$, for any vertex $v\notin A'$, we have that $\overline \deg(v,B)> \e_1\binom{|B|}{k-1}$. So we get
\[
\overline e(AB^{k-1})> \e_2|B| \cdot \e_1 \binom{|B|}{k-1} = 2\e_0|B|  \binom{|B|}{k-1}.
\]
Together with \eqref{eqB}, this implies that
\begin{align*}
\sum_{S\in \binom B{k-1}}\overline\deg(S)&= k\overline{e}(B) + \overline{e}(AB^{k-1}) \\
                              &> k(1 - \e_0) \binom{|B|}k + 2\e_0|B| \binom{|B|}{k-1}  \\
                              &= ((1-\e_0)(|B|-k+1)+2\e_0|B|) \binom{|B|}{k-1} > |B|  \binom{|B|}{k-1}.
\end{align*}
where the last inequality holds because $n$ is large enough. By the pigeonhole principle, there exists a set $S\in \binom{B}{k-1}$, such that
$\overline\deg(S) > |B|=\lfloor \frac{(2k-2\ell-1)n }{2(k-\ell)}\rfloor$, contradicting \eqref{eqdeg2}.

Consequently,
\begin{align*}
&|A'\setminus A|=|A'\cap B|\le |B\setminus B'|\le \e_2|B|,   \\
&|B'\setminus B|=|A\cap B'|\le |A\setminus A'|\le \e_2|B|, \\
&|V_0|=|A\setminus A'|+|B\setminus B'|\le \e_2|B|+\e_2|B|=2\e_2 |B|. \qedhere
\end{align*}
\end{proof}

\subsection{Classification of $\ell$-sets in $B'$}
In order to construct our Hamilton $\ell$-cycle, we need to connect two $\ell$-paths. To make this possible, we want the ends of our $\ell$-paths to be $\ell$-sets in $B'$ that have high degree in $\h[A'B'^{k-1}]$. Formally, we call an $\ell$-set $L\subset V$ \emph{typical} if $\deg(L, B)\le \e_1 \binom{|B|}{k-\ell}$, otherwise \emph{atypical}. We prove several properties related to typical $\ell$-sets in this subsection.

\begin{claim}\label{fact:ltypical}
The number of atypical $\ell$-sets in $B$ is at most $\e_2\binom{|B|}{\ell}$.
\end{claim}

\begin{proof}
Let $m$ be the number of atypical $\ell$-sets in $B$. By \eqref{eqB}, we have
\[
\frac{m \e_1 \binom{|B|}{k-\ell}}{\binom{k}{\ell}} \le e(B)\le \e_0 \binom{|B|}{k},
\]
which gives that $m\le \frac{ \e_0 \binom{k}{l} \binom{|B|}{k}}{ \e_1 \binom{|B|}{k-\ell} } = \frac{\e_2}{2} \binom{|B| - k+ \ell}{\ell} <  \e_2\binom{|B|}{\ell}$.
\end{proof}

\begin{claim}\label{fact:typ_l}
Every typical $\ell$-set $L\subset B'$ satisfies $\overline\deg(L, A' B'^{k-1})\le 4k\e_1\binom{|B'|-\ell}{k-\ell-1} |A'|$.
\end{claim}

\begin{proof}
Fix a typical $\ell$-set $L\subset B'$ and consider the following sum,
\[
\sum_{L\subset D\subset B', |D|=k-1}\deg(D)=\sum_{L\subset D\subset B', |D|=k-1}(\deg(D, A') + \deg(D, B') + \deg(D, V_0)).
\]
By \eqref{eqdeg2}, the left hand side is at least $\binom{|B'|-\ell}{k-\ell-1}|A|$. On the other hand,
\[
\sum_{L\subset D\subset B', |D|=k-1}(\deg(D, B') + \deg(D, V_0)) \le (k-\ell) \deg(L, B') +\binom{|B'|-\ell}{k-\ell-1}|V_0|.
\]
Since $L$ is typical and $|B'\setminus B| \le \e_2 |B|$ (Claim \ref{clm:size}), we have
\begin{align*}
\deg(L, B') & \le \deg(L, B) + |B'\setminus B| \binom{|B'|-1}{k- \ell-1} \\
& \le \e_1 \binom{|B|}{k-\ell} + \e_2 |B| \binom{|B'|-1}{k- \ell-1}.
\end{align*}
Since $\e_2\ll \e_1$ and $| |B| - |B'| | \le \e_2 |B|$, it follows that
\[
(k-\ell) \deg(L, B') \le \e_1 |B| \binom{|B|-1}{k-\ell-1} + (k-\ell) \e_2 |B| \binom{|B'|-1}{k- \ell-1} \le 2\e_1 |B|\binom{|B'|- \ell}{k-\ell-1}.
\]
Putting these together and using Claim \ref{clm:size}, we obtain that
\begin{align*}
\sum_{L\subset D\subset B', |D|=k-1}\deg(D, A') &\ge \binom{|B'|-\ell}{k-\ell-1}\left(|A| - |V_0|\right) -2\e_1 |B|\binom{|B'|- \ell}{k-\ell-1} \\
&\ge \binom{|B'|-\ell}{k-\ell-1} \left(|A'| - 3\e_2 |B| - 2\e_1 |B|\right).
\end{align*}
Note that $\deg(L, A' B'^{k-1})= \sum_{L\subset D\subset B', |D|=k-1}\deg(D, A') $.
Since $|B|\le (2k- 2\ell -1)|A|\le (2k-2\ell) |A'|$, we finally derive that
\[
\deg(L, A' B'^{k-1})\ge  \binom{|B'|-\ell}{k-\ell-1} (1 - (2k- 2\ell)( 3\e_2 + 2\e_1))|A'| \ge
 (1 - 4k\e_1)\binom{|B'|-\ell}{k-\ell-1} |A'|.
\]
as desired.
\end{proof}

We next show that we can connect any two disjoint typical $\ell$-sets of $B'$ with an $\ell$-path of length two while avoiding any given set of $\frac n{4(k-\ell)}$ vertices of $V$.

\begin{claim}\label{clm:conn}
Given two disjoint typical $\ell$-sets $L_1,L_2$ in $B'$ and a vertex set $U \subseteq V$ with $|U|\le \frac n{4(k-\ell)}$, there exist a vertex $a\in A'\setminus U$ and a $(2k- 3\ell-1)$-set $C\subset B'\setminus U$ such that $L_1\cup L_2\cup \{a\}\cup C$ spans an $\ell$-path (of length two) ended at $L_1, L_2$.
\end{claim}

\begin{proof}
Fix two disjoint typical $\ell$-sets $L_1,L_2$ in $B'$. Using Claim~\ref{clm:size}, we obtain that $|U|\le \frac n{4(k-\ell)}\le \frac{|A|}{2}< \frac23 |A'|$ and
\[
\frac{n}{4(k-\ell)} \le \frac{|B|+1}{2(2k- 2\ell -1)} \le \frac{ (1+ 2\e_2) |B'|}{2k}< \frac{|B'|}{k}.
\]
Thus $|A'\setminus U| > \frac {|A'|}3$ and $|B'\setminus U|> \frac{k-1}{k}|B'|$. Consider a $(k-\ell)$-graph $\G$ on $(A'\cup B')\setminus U$ such that
an $A' B'^{k-\ell-1}$-set $T$ is an edge of $\G$ if and only if $T\cap U = \emptyset$ and
$T$ is a common neighbor of $L_1$ and $L_2$ in $\h$. By Claim \ref{fact:typ_l}, we have
\begin{align*}
\overline{e}({\G}) &\le
2\cdot 4k\e_1\binom{|B'|-\ell}{k-\ell-1} |A'| < 8k\e_1 \binom{\frac{k}{k-1}|B' \setminus U|}{k-\ell-1} \cdot 3 |A'\setminus U|\\
&\le 24 k\e_1 \left(\frac{k}{k-1}\right)^{k-1} \binom{|B'\setminus U|}{k-\ell-1} |A'\setminus U|.
\end{align*}
Consequently $e(\G)> \frac12 \binom{|B'\setminus U|}{k-\ell-1} |A'\setminus U|$. Hence there exists a vertex $a\in A'\setminus U$ such that $\deg_{\G}(a) > \frac12 \binom{|B'\setminus U|}{k-\ell-1} > \binom{|B'\setminus U|}{k-\ell-2}$. By Fact \ref{fact:Y}, the link graph of $a$ contains a copy of $\Y_{k-\ell-1, \ell-1}$ (two edges of the link graph sharing $\ell -1$ vertices). In other words, there exists a $(2k- 3\ell-1)$-set $C\subset B'\setminus U$ such that $C\cup \{a\}$ contains two edges of $\G$ sharing $\ell$ vertices. Together with $L_1, L_2$, this gives rise to the desired $\ell$-path (in $\h$) of length two ended at $L_1, L_2$.
\end{proof}

The following claim shows that we can always extend a typical $\ell$-set to an edge of $\h$ by adding one vertex from $A'$ and $k- \ell -1$ vertices from $B'$ such that
every $\ell$-set of these $k - \ell - 1$ vertices is typical. This can be done even when at most $\frac n{4(k-\ell)}$ vertices of $V$ are not available.

\begin{claim}\label{clm:extend}
Given a typical $\ell$-set $L\subseteq B'$ and a set $U\subseteq V$ with $|U|\le \frac{n}{4(k-\ell)}$, there exists an $A'B'^{k-\ell-1}$-set $C\subset V\setminus U$ such that $L\cup C$ is an edge of $\h$ and every $\ell$-subset of $C\cap B'$ is typical.
\end{claim}

\begin{proof}
First, since $L$ is typical in $B'$, by Claim \ref{fact:typ_l}, $\overline\deg(L, A' B'^{k-1})\le 4k\e_1\binom{|B'|-\ell}{k-\ell-1} |A'|$. Second, note that a vertex in $A'$ is contained in $\binom{|B'|}{k-\ell -1}$ $A' B'^{k-\ell-1}$-sets, while a vertex in $B'$ is contained in $|A'| \binom{|B'|-1}{k-\ell-2}$ $A' B'^{k-\ell-1}$-sets. It is easy to see that $|A'| \binom{|B'|-1}{k-\ell-2} < \binom{|B'|}{k-\ell -1}$  (as $|A'|\approx \frac{n}{2k-2\ell}$ and $|B'| \approx \frac{ 2k - 2\ell -1}{2k- 2\ell} n$). We thus derive that
at most
\[|U|\binom{|B'|}{k-\ell-1}\le \frac{n}{4(k-\ell)}\binom{|B'|}{k-\ell-1}
 \]
$A'B'^{k-\ell-1}$-sets intersect $U$. Finally, by Claim \ref{fact:ltypical}, the number of atypical $\ell$-sets in $B$ is at most $\e_2 \binom{|B|}{\ell}$. Using Claim~\ref{clm:size},
we derive that the number of atypical $\ell$-sets in $B'$ is at most
\[
\e_2 \binom{|B|}{\ell} + |B'\setminus B| \binom{|B'|-1}{\ell-1}\le 2\e_2 \binom{|B'|}{\ell} + \e_2 |B|\binom{|B'|-1}{\ell-1}<  3\ell \e_2 \binom{|B'|}{\ell}.
\]
Hence at most $3\ell \e_2 \binom{|B'|}{\ell} |A'| \binom{|B'|-\ell}{k-2\ell-1}$ $A'B'^{k-\ell-1}$-sets contain an atypical $\ell$-set. In summary, at most
\[
4k\e_1\binom{|B'| - \ell}{k-\ell-1} |A'| +\frac{n}{4(k-\ell)}\binom{|B'|}{k-\ell-1} + 3\ell \e_2 \binom{|B'|}{\ell}\binom{|B'|-\ell}{k-2\ell-1}|A'|
\]
$A'B'^{k-\ell-1}$-sets fail some of the desired properties. Since $\e_1, \e_2\ll 1$ and $|A'|\approx \frac{n}{2(k-\ell)}$, the desired $A'B'^{k-\ell-1}$-set always exists.
\end{proof}

\subsection{Building a short path $\mathcal Q$}
First, by the definition of $B$, for any vertex $b\in B'$, we have
\begin{align}
\label{eq:analeft}
\deg \left(b, B' \right)&\le \deg \left(b,B \right)+|B'\setminus B|\binom{|B'|-1}{k-2}  \nonumber    \\
                                & \le \e_1 \binom {|B|}{k-1} + \e_2 |B| \binom{|B'|-1}{k-2}< 2\e_1 \binom {|B|}{k-1}.
\end{align}

The following claim is the only place where we used the exact codegree condition \eqref{eqdeg2}.
\begin{claim}\label{clm:Bpath}
Suppose that $|A\cap B'|=q>0$. Then there exists a family $\mathcal P_1$ of $2q$ vertex-disjoint edges in $B'$, each of which contains two disjoint typical $\ell$-sets.
\end{claim}

\begin{proof}
Let $|A\cap B'|=q>0$. Since $A\cap B'\neq \emptyset$, by Claim \ref{clm:eB}, we have $B\subseteq B'$, and consequently $|B'|=\lfloor \frac{2k-2\ell-1 }{2(k-\ell)}n\rfloor+q$. By Claim \ref{clm:size}, we have $ q \le |A\setminus A'|\le \e_2|B|$.

Let $\mathcal B$ denote the family of the edges in $B'$ that contain two disjoint typical $\ell$-sets. We derive a lower bound for $|\mathcal{B}|$ as follows. We first pick a $(k-1)$-subset of $B$ (recall that $B\subseteq B'$) that contains no atypical $\ell$-subset. Since $2\ell\le k-1$, such a $(k-1)$-set contains two disjoint typical $\ell$-sets. By Claim \ref{fact:ltypical}, there are at most $\e_2 \binom{|B|}{\ell}$ atypical $\ell$-sets in $B\cap B'=B$ and in turn, there are at most $\e_2 \binom{|B|}{\ell} \binom{|B|-\ell }{k- \ell -1}$ $(k-1)$-subsets of $B$ that contain an atypical $\ell$-subset. Thus there are at least
\[
\binom{|B|}{k-1} - \e_2\binom{|B|}{\ell}\binom{|B|-\ell}{k-\ell-1} =  \left(1 - \binom{k-1}{\ell}\e_2 \right) \binom{|B|}{k-1}
\]
$(k-1)$-subsets of $B$ that contain no atypical $\ell$-subset. After picking such a $(k-1)$-set $S\subset B$, we find
a neighbor of $S$ by the codegree condition.  Since $|B'|=\lfloor \frac{2k-2\ell-1}{2(k-\ell)}n\rfloor+q$, by \eqref{eqdeg2}, we have $\deg \left(S, B'\right) \ge q$. We thus derive that
\[
|\mathcal{B}| \ge \left(1 - \binom{k-1}{\ell}\e_2 \right) \binom{|B|}{k-1} \frac{q}{k},
\]
in which we divide by $k$ because every edge of $\mathcal{B}$ is counted at most $k$ times.

We claim that $\mathcal B$ contains $2q$ disjoint edges. Suppose instead, a maximum matching in $\mathcal B$ has $i<2q$ edges.
By \eqref{eq:analeft}, at most $2q k \cdot 2\e_1 \binom {|B|}{k-1}$ edges of $B'$ intersect the $i$ edges in the matching. Hence, the number of edges of $\mathcal{B}$ that are disjoint from these $i$ edges is at least
\begin{align*}
\frac{q}{k} \left(1 - \binom{k-1}{\ell}\e_2 \right) \binom{|B|}{k-1}-   4k\e_1 q \binom {|B|}{k-1}\ge \left(\frac{1}{k} - (4k+1)\e_1 \right) q\binom {|B|}{k-1} > 0,
\end{align*}
as $\e_2 \ll \e_1\ll 1$. We may thus obtain a matching of size $i+1$, a contradiction.
\end{proof}

\begin{claim}\label{clm:path}
There exists a non-empty $\ell$-path $\mathcal Q$ in $\h$ with the following properties:
\begin{itemize}
\item $V_0\subseteq V(\mathcal Q)$,
\item $|V(\mathcal Q)|\le 10k \e_2 |B|$,
\item the two ends $L_0, L_1$ of $\mathcal Q$ are typical $\ell$-sets in $B'$,
\item $|B_1|= (2k-2\ell-1)|A_1| + \ell$, where $A_1=A'\setminus V(\mathcal Q)$ and $B_1= (B'\setminus V(\mathcal Q))\cup L_0 \cup L_1$.
\end{itemize}
\end{claim}

\begin{proof}
We split into two cases here.

\smallskip
\noindent\textbf{Case 1.} $A\cap B'\neq \emptyset$.
\smallskip

By Claim \ref{clm:eB}, $A\cap B'\neq \emptyset$ implies that $B\subseteq B'$.
Let $q=|A\cap B'|$. We first apply Claim \ref{clm:Bpath} and find a family $\mathcal P_1$ of vertex-disjoint $2q$ edges in $B'$. Next we associate each vertex of $V_0$ with $2k - \ell -1$ vertices of $B$ (so in $B'$) forming an
$\ell$-path of length two such that these $|V_0|$ paths are pairwise vertex-disjoint, and also vertex-disjoint from the paths in $\mathcal P_1$, and all these paths have typical ends. To see it, let $V_0=\{x_1,\dots, x_{|V_0|}\}$.
Suppose that we have found such $\ell$-paths for $x_1, \dots, x_{i-1}$ with $i \le |V_0|$.
Since $B\subseteq B'$, it follows that $A\setminus A'=(A\cap B')\cup V_0$.
Hence $|V_0|+q=|A\setminus A'|\le \e_2 |B|$ by Claim \ref{clm:size}. Therefore
\[
(2k-\ell-1)(i -1) + | V(\pp_1) | < 2k|V_0|+2kq\le 2k \e_2|B|
\]
and consequently at most $2k\e_2 |B| \binom{|B|-1}{k-2} < 2k^2\e_2 \binom{|B|}{k-1}$ $(k-1)$-sets of $B$ intersect the existing paths (including $\mathcal P_1$).
By the definition of $V_0$, $\deg(x_{i}, B)> \e_1\binom{|B|}{k-1}$. Let $\G_{x_{i}}$ be the $(k-1)$-graph on $B$ such that $e\in \G_{x_{i}}$ if
\begin{itemize}
\item $\{x_{i}\}\cup e \in E(\h)$,
\item $e$ does not contain any vertex from the existing paths,
\item $e$ does not contain any atypical $\ell$-set.
\end{itemize}
By Claim \ref{fact:ltypical},
the number of $(k-1)$-sets in $B$ containing at least one atypical $\ell$-set is at most $\e_2\binom{|B|}{\ell} \binom{|B|-\ell}{k-\ell-1}=\e_2\binom{k-1}{\ell}\binom{|B|}{k-1}$. Thus, we have
\[
e(\G_{x_i})\ge \e_1\binom{|B|}{k-1} - 2k^2\e_2 \binom{|B|}{k-1} - \e_2\binom{k-1}{\ell}\binom{|B|}{k-1} >\frac{\e_1}{2} \binom{|B|}{k-1}>\binom{|B|}{k-2},
\]
because $\e_2 \ll \e_1$ and $|B|$ is sufficiently large.
By Fact \ref{fact:Y}, $\G_{x_i}$ contains a copy of $\Y_{k-1, \ell-1}$, which gives the desired $\ell$-path of length two containing $x_i$.

Denote by $\mathcal P_2$ the family of $\ell$-paths we obtained so far. Now we need to connect paths of $\mathcal P_2$ together to a single $\ell$-path. For this purpose, we apply Claim \ref{clm:conn} repeatedly to connect the ends of two $\ell$-paths while avoiding previously used vertices. This is possible because $|V(\mathcal P_2)|= (2k-\ell)|V_0|+2kq$ and $(2k-3\ell)(|V_0|+2q-1)$ vertices are needed to connect all the paths in $\pp_2$ -- the set $U$ (when we apply Claim \ref{clm:conn}) thus satisfies
\[
|U| \le (4k- 4\ell) |V_0| + (6k- 6\ell) q - 2k + 3\ell \le 6(k-\ell) \e_2 |B| -2k + 3\ell.
\]
Let $\mathcal P$ denote the resulting $\ell$-path.  We have $|V(\mathcal P)\cap A'|= |V_0|+2q-1$ and
\begin{align*}
|V(\mathcal P)\cap B'| &= k\cdot 2q+ (2k-\ell-1)|V_0| +(2k-3\ell-1)(|V_0|+2q-1)  \\
&=2(2k- 2\ell-1) |V_0| + 2(3k - 3\ell -1)q - (2k - 3\ell -1).
\end{align*}
Let $s= (2k-2\ell-1)|A'\setminus V(\mathcal P)| - |B'\setminus V(\mathcal P)|$. We have
\begin{align*}
s &= (2k - 2\ell - 1)(|A'| - |V_0| - 2q + 1) - |B'| +  2(2k- 2\ell-1) |V_0| + 2(3k - 3\ell -1)q - (2k - 3\ell -1) \\
 &= (2k - 2\ell -1) |A'| - |B'| + (2k- 2\ell-1) |V_0| + (2k - 2\ell)q + \ell.
\end{align*}
Since $|A'| + |B'| + |V_0| = n$, we have
\begin{equation}\label{eq:s}
    s= (2k - 2\ell) (|A'| + |V_0| + q) - n + \ell.
\end{equation}
Note that $|A'| + |V_0| + q = |A|$ and
\begin{equation}\label{eq:An}
    (2k - 2\ell) |A| - n =
    \begin{cases} 0, & \mbox{if } \frac{n}{k-\ell} \mbox{ is even} \\ k- \ell, & \mbox{if } \frac{n}{k-\ell} \mbox{ is odd}. \end{cases}
\end{equation}
Thus $s= \ell$ or $s=k$. If $s=  k$, then we extend $\pp$ to an $\ell$-path $\mathcal Q$ by applying Claim \ref{clm:extend}, otherwise let $\mathcal Q=\mathcal P$. Then
\[
|V(\mathcal Q)| \le |V(\mathcal P)|+ (k- \ell) \le 6k \e_2 |B|,
\]
and $\mathcal{Q}$ has two typical ends $L_0, L_1\subset B'$. We claim that
\begin{equation}\label{eq:ABQ}
(2k-2\ell-1)|A'\setminus V(\mathcal Q)| - |B'\setminus V(\mathcal Q)| = \ell.
\end{equation}
Indeed, when $s= \ell$, this is obvious; when $s=k$, $V(\Q)\setminus V(\pp)$ contains one vertex of $A'$ and $k-\ell-1$ vertices of $B'$ and thus
\[
(2k-2\ell-1)|A'\setminus V(\mathcal Q)| - |B'\setminus V(\mathcal Q)|=s - (2k-2\ell-1) + (k-\ell-1) =\ell.
\]
Let $A_1=A'\setminus V(\mathcal Q)$ and $B_1= (B'\setminus V(\mathcal Q))\cup L_0\cup L_1$. We derive that $|B_1|=(2k-2\ell-1)|A_1| + \ell$ from \eqref{eq:ABQ}.

\smallskip
\noindent\textbf{Case 2.} $A\cap B'= \emptyset$.
\smallskip

Note that $A\cap B'= \emptyset$ means that $B'\subseteq B$. Then we have
\begin{equation}\label{eq:A'B'}
|A'| + |V_0| = |V\setminus B'| = |A| + |B\setminus B'|.
\end{equation}

If $V_0\neq \emptyset$, we handle this case similarly as in Case 1 except that we do not need to construct $\mathcal P_1$.
By Claim \ref{clm:size}, $|B\setminus B'|\le \e_2|B|$ and thus for any vertex $x\in V_0$,
\begin{align}
\deg(x, B')&\ge \deg(x,B)-|B\setminus B'|\cdot \binom{|B|-1}{k-2} \nonumber \\
&\ge \e_1\binom{|B|}{k-1} - (k-1)\e_2\binom{|B|}{k-1}>\frac{\e_1}{2}\binom{|B'|}{k-1}. \label{eq:medium}
\end{align}
As in Case 1, we let $V_0=\{x_1,\dots, x_{|V_0|}\}$ and cover them with vertex-disjoint $\ell$-paths of length two. Indeed, for each $i  \le |V_0|$, we construct $\G_x$ as before and show that $e(\G_{x_i})\ge \frac{\e_1}{4} \binom{|B'|}{k-1}$. We then apply Fact \ref{fact:Y} to $\G_{x_i}$ obtaining a copy of $\Y_{k-1, \ell-1}$, which gives an $\ell$-path of length two containing $x_i$.
As in Case 1, we connect these paths to a single $\ell$-path $\mathcal P$ by applying Claim \ref{clm:conn} repeatedly. Then $|V(\mathcal P)|=(2k-\ell)|V_0|+(2k-3\ell)(|V_0|-1)$. Define $s$ as in Case~1. Thus \eqref{eq:s} holds with $q=0$. Applying \eqref{eq:A'B'} and \eqref{eq:An}, we derive that
\begin{equation}\label{eq:s2}
s = 2(k-\ell) (|A|+ |B\setminus B'|) - n +\ell =
\begin{cases} \ell + 2(k-\ell)|B\setminus B'|, & \mbox{if } \frac{n}{k-\ell} \mbox{ is even} \\
k+ 2(k-\ell)|B\setminus B'|, & \mbox{if } \frac{n}{k-\ell} \mbox{ is odd}, \end{cases}
\end{equation}
which implies that $s\equiv \ell \mod (k-\ell)$. We extend $\mathcal P$ to an $\ell$-path $\mathcal Q$ by applying Claim \ref{clm:extend} $\frac{s-\ell}{k-\ell}$ times. Then
\[
|V(\mathcal Q)|=|V(\mathcal P)|+s-\ell \le (4k - 4\ell)|V_0| - 2k+ 3\ell + k- \ell + 2(k-\ell)|B\setminus B'|\le 10k \e_2 |B|
\]
by Claim \ref{clm:size}. Note that $\mathcal{Q}$ has two typical ends
$L_0, L_1\subset B'$. Since $V(\Q)\setminus V(\pp)$ contains $\frac{s-\ell}{k-\ell}$ vertices of $A'$ and $\frac{s-\ell}{k-\ell}(k-\ell-1)$ vertices of $B'$, we have
\[
(2k-2\ell-1)|A'\setminus V(\mathcal Q)| - |B'\setminus V(\mathcal Q)|=s - \frac{s-\ell}{k-\ell}(2k-2\ell-1) + \frac{s-\ell}{k-\ell}(k-\ell-1) =\ell.
\]
We define $A_1$ and $B_1$ in the same way and similarly we have $|B_1|=(2k-2\ell-1)|A_1| + \ell$.

When $V_0=\emptyset$, we pick an arbitrary vertex $v\in A'$ and form an $\ell$-path $\mathcal{P}$ of length two with typical ends such that $v$ is in the intersection of the two edges. This is possible by the definition of $A'$. Define $s$ as in Case~1. It is easy to see that \eqref{eq:s2} still holds. We then extend $\mathcal P$ to $\mathcal Q$ by applying Claim \ref{clm:extend} $\frac{s-\ell}{k-\ell}$ times. Then
$|V(\mathcal{Q})|= 2k- \ell + s- \ell\le 2k \e_2 |B|$ because of \eqref{eq:s2}. The rest is the same as in the previous case.
\end{proof}

\begin{claim}
The $A_1, B_1$ and $L_0, L_1$ defined in Claim~\ref{clm:path} satisfy the following properties:
\begin{enumerate}
\item $|B_1|\ge (1- \e_1) |B|$,
\item for any vertex $v\in A_1$, $\overline{\deg}(v, B_1)<3 \e_1 \binom{|B_1|}{k-1}$,
\item for any vertex $v\in B_1$, $\overline{\deg}(v, A_1 B_1^{k-1})\le 3k\e_1 \binom{|B_1|}{k-1}$,
\item $\overline{\deg}(L_0, A_1B_1^{k-1}) \le 5k\e_1\binom{|B_1|}{k-\ell}$, $\overline{\deg}(L_1, A_1B_1^{k-1}) \le 5k\e_1\binom{|B_1|}{k-\ell}$.
\end{enumerate}
\end{claim}

\begin{proof}
Part (1): By Claim \ref{clm:size}, we have $|B_1\setminus B|\le |B'\setminus B|\le \e_2 |B|$. Furthermore,
\[
|B_1|\ge |B'| - |V(\mathcal Q)| \ge |B| - \e_2 |B|- 10k \e_2 |B| \ge (1-\e_1)|B|.
\]

Part (2): For a vertex $v\in A_1$, since $\overline{\deg}(v, B)\le \e_1 \binom{|B|}{k-1}$, we have
\begin{align*}
\overline{\deg}(v, B_1) &\le \overline{\deg}(v, B) + |B_1\setminus B| \binom{|B_1|-1}{k-2} \\
&\le \e_1 \binom{|B|}{k-1} + \e_2 |B| \binom{|B_1|-1}{k-2} \\
&< \e_1 \binom{|B|}{k-1} + \e_1 \binom{|B_1|}{k-1} <3 \e_1 \binom{|B_1|}{k-1},
\end{align*}
where the last inequality follows from Part~(1).

Part~(3): Consider the sum $\sum\deg(S\cup \{v\})$ taken over all $S\in \binom{B'\setminus \{v\}}{k-2}$. Since $\delta_{k-1}(\h)\ge |A|$, we have $\sum\deg(S\cup \{v\})\ge \binom{|B'|-1}{k-2}|A|$. On the other hand,
\begin{align*}
\sum\deg(S\cup \{v\}) &= \deg(v, A' B'^{k-1}) + \deg(v, V_0 B'^{k-1}) + (k-1) \deg(v, B').
\end{align*}
We thus derive that
\[
\deg(v, A' B'^{k-1}) \ge \binom{|B'|-1}{k-2}|A| -\deg(v, V_0 B'^{k-1}) - (k-1) \deg(v, B').
\]
By Claim~\ref{clm:size} and \eqref{eq:analeft}, it follows that
\begin{align*}
\deg(v, A' B'^{k-1}) &\ge \binom{|B'|-1}{k-2}(|A'|-\e_2|B|) - 2\e_2 |B| \binom{|B'|-1}{k-2} - 2(k-1)\e_1 \binom{|B|}{k-1} \\
&\ge \binom{|B'|-1}{k-2}|A'| - 2k\e_1 \binom{|B|}{k-1}.
\end{align*}
By Part~(1), we now have
\[
\overline{\deg}(v, A_1 B_1^{k-1})\le \overline{\deg}(v, A' B'^{k-1})\le 2k\e_1 \binom{|B|}{k-1}\le 3k\e_1 \binom{|B_1|}{k-1}.
\]

Part (4): By Claim~\ref{fact:typ_l}, for any typical $L\subseteq B'$, we have $\overline\deg(L, A' B'^{k-1})\le 4k\e_1\binom{|B'|-\ell}{k-\ell-1} |A'|$. Thus,
\[
\overline{\deg}(L_0, A_1B_1^{k-1})\le \overline\deg(L_0, A' B'^{k-1})\le 4k\e_1\binom{|B'|-\ell}{k-\ell-1} |A'| \le 5k\e_1\binom{|B_1|}{k-\ell},
\]
where the last inequality holds because $|B'|\le |B_1| +|V(\Q)| \le (1+ \e_1) |B_1|$. The same holds for $L_1$.
\end{proof}

\subsection{Completing the Hamilton cycle}

We finally complete the proof of Theorem \ref{lemE} by applying the following lemma with $X=A_1$, $Y=B_1$, $\rho=5k\e_1$, and $L_0, L_1$.

\begin{lemma}\label{lem:H}
Fix $1\le \ell < k/2$. Let $0<\rho\ll 1$ and $n$ be sufficiently large.
Suppose that $\h$ is a $k$-graph with a partition $V(\h)=X\cup Y$ and the following properties:
\begin{itemize}
\item $|Y| = (2k - 2\ell -1)|X| + \ell$,
\item for every vertex $v\in X$, $\overline \deg(v, Y)\le \rho\binom{|Y|}{k-1}$ and for every vertex $v\in Y$, $\overline \deg (v, XY^{k-1})\le \rho \binom{|Y|}{k-1}$,
\item there are two disjoint $\ell$-sets $L_0, L_1\subset Y$ such that
\begin{equation}\label{eq:L01}
\overline{\deg}(L_0, X Y^{k-1}), \,\overline{\deg}(L_1, X Y^{k-1})\le \rho\binom{|Y|}{k-\ell}.
\end{equation}
\end{itemize}
Then $\h$ contains a Hamilton $\ell$-path with $L_0$ and $L_1$ as ends.
\end{lemma}

In order to prove Lemma \ref{lem:H}, we apply two results of Glebov, Person, and Weps \cite{GPW}. Given $1\le j \le k-1$ and $0\le \rho\le 1$, an ordered set $(x_1,\dots, x_{j})$ is $\rho$-\emph{typical} in a $k$-graph $\G$ if for every $i\in [j]$,
\[
\overline\deg_{\G}( \{x_1, \dots, x_i\} ) \le \rho^{k-i}\binom {|V(\G)| - i}{k-i}.
\]
It was shown in \cite{GPW} that every $k$-graph $\G$ with very large minimum vertex degree contains a tight Hamilton cycle. The proof of \cite[Theorem 2]{GPW} actually shows that we can obtain a tight Hamilton cycle
by extending any fixed tight path of constant length with two typical ends. This implies the following theorem that we will use.

\begin{theorem}\cite{GPW}
\label{thm:GPW}
Given $1\le j\le k$ and $0<\a \ll 1$, there exists an $m_0$ such that the following holds. Suppose that $\G$ is a $k$-graph on $V$ with $|V|= m\ge m_0$ and $\delta_1(\G)\ge (1 - \a)\binom{m-1}{k-1}$. Then given any two disjoint $(22\a)^{\frac1{k-1}}$-typical ordered $j$-sets $(x_1,\dots, x_{j})$ and $(y_1,\dots, y_{j})$, there exists a tight Hamilton path $\mathcal P= x_{j}x_{j-1}\cdots x_1 \cdots \cdots y_1y_2\cdots y_{j}$ in $\G$.
\end{theorem}

We also use \cite[Lemma 3]{GPW}, in which $V^{2k-2}$ denotes the set of all $(2k-2)$-tuples $(v_1, \dots, v_{2k-2})$ such that $v_i\in V$ ($v_i$'s are not necessarily distinct).

\begin{lemma}\cite{GPW}
\label{lem:GPW}
Let $\G$ be the $k$-graph given in Lemma \ref{thm:GPW}. Suppose that $(x_1, \dots, x_{2k-2})$ is selected uniformly at random from $V^{2k-2}$. Then the probability that all $x_i$'s are pairwise distinct and $(x_1, \dots, x_{k-1}), (x_{k}, \dots, x_{2k-2})$ are $(22\a)^{\frac1{k-1}}$-typical is at least $\frac{8}{11}$.
\end{lemma}

\begin{proof}[Proof of Lemma \ref{lem:H}]
In this proof we often write the union $A\cup B\cup \{x\}$ as $A B x$, where $A, B$ are sets and $x$ is an element.

Let $t= |X|$. Our goal is to write $X$ as $\{ x_1, \dots, x_{t} \}$ and partition $Y$ as $\{L_i, R_i, S_i, R_i': i\in [t] \}$ with $|L_i|=\ell$, $|R_i|=|R_i'|=k-2\ell$, and $|S_i|=\ell-1$ such that
\begin{equation}
\label{eq:xiH}
L_{i} R_{i} S_i x_i, \ S_i x_i R_{i}' L_{i+1}\in E(\h)
\end{equation}
for all $i\in [t]$, where $L_{t+1}=L_0$. Consequently
\[
L_1\, R_1\, S_1\, x_1\, R'_1\, L_2\, R_2\, S_2\, x_2\, R'_2\, \cdots \, L_{t}\, R_{t}\, S_t\, x_{t}\, R'_{t}\, L_{t+1}
\]
is the desired Hamilton $\ell$-path of $\h$.

Let $\G$ be the $(k-1)$-graph on $Y$ whose edges are all $(k-1)$-sets $S\subseteq Y$ such that $\deg_{\h}(S, X)> (1-\sqrt{\rho})t$. The following is an outline of our proof. We first find a small subset $Y_0\subset Y$ with a partition $\{L_i, R_i, S_i, R_i': i\in [t_0] \}$ such that for every $x\in X$, we have $L_{i} R_{i} S_i x, S_i x R_{i}' L_{i+1} \in E(\h)$ for many $i\in [t_0]$. Next we apply Theorem~\ref{thm:GPW} to $\G[Y\setminus Y_0]$ and obtain a tight Hamilton path, which, in particular, partitions $Y\setminus Y_0$ into $\{L_i, R_i, S_i, R_i': t_0< i\le t \}$ such that
$L_i R_i S_i, \ S_i R'_i L_{i+1} \in E(\G)$ for $t_0< i\le t$. Finally we apply the Marriage Theorem to find a perfect matching between $X$ and $[t]$ such that \eqref{eq:xiH} holds for all matched $x_i$ and $i$.

We now give details of the proof.  First we claim that
\begin{equation}\label{eq:dG}
\delta_1(\G) \ge (1- 2\sqrt{\rho}) \binom{|Y|-1}{k-2},
\end{equation}
and consequently,
\begin{equation}\label{eq:eG}
\overline{e}(\G)\le 2\sqrt{\rho} \binom{|Y|}{k-1}.
\end{equation}
Suppose instead, some vertex $v\in Y$ satisfies $\overline \deg_\G(v)> 2\sqrt{\rho} \binom{|Y|-1}{k-2}$. Since every non-neighbor $S'$ of $v$ in $\G$ satisfies $\overline \deg_\h(S' v, X)\ge \sqrt{\rho} t$, we have
$\overline \deg_{\h}(v, XY^{k-1}) > 2\sqrt{\rho} \binom{|Y|-1}{k-2} \sqrt{\rho} t$.
Since $|Y| = (2k- 2\ell -1)t + \ell$, we have
\[
\overline \deg_{\h}(v, XY^{k-1}) > 2\rho\frac{|Y|-\ell}{2k-2\ell-1} \binom{|Y|-1}{k-2}
> \rho \frac{|Y|}{k-1} \binom{|Y|-1}{k-2} = \rho \binom{|Y|}{k-1},
\]
contradicting our assumption (the second inequality holds because $|Y|$ is sufficiently large).

Let $Q$ be a $(2k-\ell-1)$-subset of $Y$.  We call $Q$  \emph{good} (otherwise \emph{bad}) if every $(k-1)$-subset of $Q$ is an edge of $\G$ and every $\ell$-set $L\subset Q$ satisfies
\begin{equation}
\label{eq:degGL}
\overline\deg_\G(L) \le \rho^{1/4}\binom{|Y|-\ell}{k-\ell-1}.
\end{equation}
Furthermore, we say $Q$ is \emph{suitable} for a vertex $x\in X$ if $x\cup T\in E(\h)$ for every $(k-1)$-set $T\subset Q$. Note that if a $(2k-\ell-1)$-set is good, by the definition of $\G$, it is suitable for at least $(1- \binom{2k- \ell-1}{k-1}\sqrt{\rho})t$ vertices of $X$. Let $Y'= Y\setminus (L_0\cup L_1)$.

\begin{claim}\label{clm:suitablesets}
For any $x\in X$, at least $(1-\rho^{1/5} )\binom{|Y|}{2k-\ell-1}$ $(2k-\ell-1)$-subsets of $Y'$ are good and suitable for $x$.
\end{claim}

\begin{proof}
Since $\rho + \rho^{1/2} + 3\binom{2k-\ell-1}{\ell} \rho^{1/4}\le \rho^{1/5}$, the claim follows from the following three assertions:
\begin{itemize}
\item At most $2\ell \binom{|Y|-1}{2k - \ell -2}\le \rho \binom{|Y|}{2k- \ell -1}$ $(2k-\ell-1)$-subsets of $Y$ are not subsets of $Y'$.
\item Given $x\in X$, at most $\rho^{1/2} \binom{|Y|}{2k-\ell-1}$ $(2k-\ell-1)$-sets in $Y$ are not suitable for $x$.
\item At most $3\binom{2k-\ell-1}{\ell} \rho^{1/4} \binom{|Y|}{2k-\ell-1}$ $(2k-\ell-1)$-sets in $Y$ are bad.
\end{itemize}

The first assertion holds because $|Y\setminus Y'|= 2\ell$. The second assertion follows from the degree condition of $\h$, namely, for any $x\in X$, the number of $(2k-\ell-1)$-sets in $Y$ that are not suitable for $x$ is at most ${\rho}\binom{|Y|}{k-1}\binom{|Y|-k+1}{k-\ell}\le \sqrt{\rho}\binom{|Y|}{2k-\ell-1}$.

To see the third one, let $m$ be the number of $\ell$-sets $L\subseteq Y$ that fail \eqref{eq:degGL}.
By \eqref{eq:eG},
\[
m \frac{\rho^{1/4}\binom{|Y|-\ell}{k-\ell-1} }{ \binom{k-1}{\ell} }\le  \overline{e}(\G)\le 2\sqrt{\rho} \binom{|Y|}{k-1},
\]
which implies that $m\le 2\rho^{1/4} \binom{|Y|}{\ell}$.
Thus at most
\[
2\rho^{1/4}\binom{|Y|}{\ell}\cdot \binom{|Y| - \ell}{2k-2\ell-1}
\]
$(2k - \ell -1)$-subsets of $Y$ contain an $\ell$-set $L$ that fails \eqref{eq:degGL}.
On the other hand, by \eqref{eq:eG}, at most
\[
\overline{e}(\G) \binom{ |Y|-k+1 }{k- \ell} \le 2\sqrt{\rho} \binom{|Y|}{k-1} \binom{ |Y|-k+1 }{k- \ell}
\]
$(2k - \ell -1)$-subsets of $Y$ contain a non-edge of $\G$. Putting these together, the number of bad $(2k-\ell-1)$-sets in $Y$ is at most
\[
2\rho^{1/4}\binom{|Y|}{\ell} \binom{|Y|-\ell}{2k-2\ell-1} + 2\sqrt{\rho} \binom{|Y|}{k-1} \binom{ |Y|-k+1 }{k- \ell}  \le 3\binom{2k-\ell-1}{\ell}\rho^{1/4} \binom{|Y|}{2k-\ell-1},
\]
as $\rho\ll 1$.
\end{proof}

Let $\F_0$ be the set of good $(2k-\ell-1)$-sets in $Y'$.
We will pick a family of disjoint good $(2k-\ell-1)$-sets in $Y'$ such that for any $x\in X$, many members of this family are suitable for $x$. To achieve this, we pick a family $\mathcal F$ by selecting each member of $\F_0$ randomly and independently with probability $p=6\sqrt{\rho} |Y|/\binom{|Y|}{2k-\ell-1}$.
Then $|\F|$ follows the binomial distribution $B(|\F_0|, p)$ with expectation $\mathbb{E}(|\F|) = p |\F_0| \le p\binom{|Y|}{2k - \ell - 1}$.
Furthermore, for every $x\in X$, let $f(x)$ denote the number of members of $\F$ that are suitable for $x$. Then $f(x)$ follows the binomial distribution $B(N, p)$ with $N\ge (1-\rho^{1/5} )\binom{|Y|}{2k-\ell-1}$ by Claim \ref{clm:suitablesets}. Hence $\mathbb{E}(f(x))\ge p(1-\rho^{1/5} )\binom{|Y|}{2k-\ell-1}$.
Since there are at most $\binom{|Y|}{2k-\ell-1}\cdot (2k-\ell-1)\cdot \binom{|Y|-1}{2k-\ell-2}$ pairs of intersecting $(2k-\ell-1)$-sets in $Y$,
the expected number of intersecting pairs of $(2k-\ell-1)$-sets in $\mathcal F$ is at most
\[
p^2 \binom{|Y|}{2k-\ell-1}\cdot (2k-\ell-1)\cdot \binom{|Y|-1}{2k-\ell-2}=36(2k-\ell-1)^2 {\rho} |Y|.
\]

By Chernoff's bound (the first two properties) and Markov's bound (the last one), we can find a family $\mathcal F$ of good $(2k-\ell-1)$-subsets of $Y'$ that satisfies
\begin{itemize}
\item
$|\mathcal F|\le 2p \binom{|Y'|}{2k-\ell-1} \le 12\sqrt{\rho} |Y|$,
\item
for any vertex $x\in X$, at least
$\frac{p}2 (1- \rho^{1/5})\binom{|Y|}{2k-\ell-1}  \ge 2\sqrt{\rho}|Y|$
members of $\mathcal F$ are suitable for $x$.
\item
the number of intersecting pairs of $(2k-\ell-1)$-sets in $\mathcal F$ is at most $72(2k-\ell-1)^2 {\rho} |Y|$.
\end{itemize}
After deleting one $(2k-\ell-1)$-set from each of the intersecting pairs from $\F$, we obtain a family $\mathcal F'\subseteq \F$ consisting of at most $12\sqrt{\rho} |Y|$ disjoint good $(2k-\ell-1)$-subsets of $Y'$ and for each $x\in X$, at least
\begin{equation}\label{eq:F'}
2\sqrt{\rho}|Y| - 72(2k-\ell-1)^2 {\rho} |Y|\ge \frac32\sqrt{\rho}|Y|
\end{equation}
members of $\mathcal F'$ are suitable for $x$.

Denote $\F'$ by $\{Q_2, Q_4, \dots, Q_{2q} \}$ for  some $q\le 12\sqrt{\rho} |Y|$. We arbitrarily partition each $Q_{2i}$ into $L_{2i} \cup P_{2i} \cup L_{2i+1}$ such that $|L_{2i}| = |L_{2i+1}|= \ell$ and $|P_{2i}| =2k - 3\ell -1$.
Since $Q_{2i}$ is good, both $L_{2i}$ and $L_{2i+1}$ satisfy \eqref{eq:degGL}. We claim that $L_0$ and $L_1$ satisfy \eqref{eq:degGL} as well. Let us show this for $L_0$. By the definition of $\G$, the number of $XY^{k-\ell-1}$-sets $T$ such that $T\cup L_0\not\in E(\h)$ is at least $\overline\deg_\G(L_0) \sqrt{\rho}t$. Using \eqref{eq:L01}, we derive that $
 \overline\deg_\G(L_0) \sqrt{\rho}t \le \rho \binom{|Y|}{k- \ell}$. Since $|Y|\le (2k- 2\ell)t$, it follows that
$\overline\deg_\G(L_0)\le 2\sqrt{\rho} \binom{|Y| -1}{k- \ell - 1}\le  {\rho}^{1/4} \binom{|Y| -\ell}{k- \ell - 1}$.

Next we greedily find disjoint $(2k- 3\ell -1)$-sets $P_1, P_3, \dots, P_{2q-1}$ from $Y'\setminus \bigcup_{i=1}^q Q_{2i}$ such that for each $i\in [q]$, every $(k- \ell -1)$-subset of $P_{2i-1}$ is a common neighbor of $L_{2i-1}$ and $L_{2i}$ in $\G$.
Suppose that we have found $P_1, P_3, \dots, P_{2i-1}$ for some $i<q$.
Since both $L_{2i-1}$ and $L_{2i}$ satisfy \eqref{eq:degGL}, at most
\[
2 \cdot {\rho}^{1/4}\binom{|Y|-\ell}{k-\ell-1} \binom{|Y| - k +1}{k- 2\ell}
\]
$(2k- 3\ell -1)$-subsets of $Y$ contain a non-neighbor of $L_{2i-1}$ or $L_{2i}$.
Thus, the number of $(2k- 3\ell -1)$-sets that can be chosen as $P_{2i+1}$ is at least
\[
\binom{|Y'| - (2k- 2\ell-1)2q}{2k - 3\ell - 1} - 2 \cdot {\rho}^{1/4}\binom{|Y|-\ell}{k-\ell-1} \binom{|Y| - k +1}{k- 2\ell} > 0,
\]
as $q\le 12\sqrt{\rho} |Y|$ and $\rho\ll 1$.

Let $Y_1= Y' \setminus  \bigcup_{i=1}^q ( P_{2i-1} \cup Q_{2i}) $ and $\G'=\G[Y_1]$. Then $|Y_1|=|Y'|-(2k-2\ell-1)2q$. Since $\overline \deg_{\G'}(v)\le \overline \deg_\G(v)$ for every $v\in Y_1$, we have, by \eqref{eq:dG},
\[
\delta_1(\G') \ge \binom{|Y_1|-1}{k-2} -  2\sqrt{\rho} \binom{|Y|-1}{k-2}\ge (1-3\sqrt{\rho})\binom{|Y_1|-1}{k-2}.
\]

Let  $\a=3\sqrt{\rho}$ and $\rho_0=(22\a)^{\frac1{k-1}}$.
We want to find two disjoint $\rho_0$-typical ordered $(k-\ell-1)$-subsets $(x_1,\dots, x_{k-\ell-1})$ and $(y_1,\dots, y_{k-\ell-1})$ of $Y_1$ such that
\begin{equation}\label{eq:endG}
L_{2q+1} \cup \{x_1,\dots, x_{k-\ell-1}\}, \ L_0 \cup \{y_1,\dots, y_{k-\ell-1}\} \in E(\G).
\end{equation}
To achieve this, we choose $(x_1,\dots, x_{k-1}, y_1,\dots, y_{k-1})$ from ${Y_1}^{2k-2}$ uniformly at random. By Lemma \ref{lem:GPW}, with probability at least $\frac8{11}$,  $(x_1,\dots, x_{k-\ell-1})$ and $(y_1,\dots, y_{k-\ell-1})$ are two disjoint
ordered $\rho_0$-typical $(k-\ell-1)$-sets. Since $L_0$ satisfies \eqref{eq:degGL}, at most $(k-\ell -1)! \rho^{1/4} \binom{|Y|-\ell}{k-\ell-1}$ ordered $(k-\ell-1)$-subsets of $Y$ are not neighbors of $L_0$ (the same holds for $L_{2q+1}$). Thus  \eqref{eq:endG} fails with probability at most $2(k-\ell -1)! \rho^{1/4}$, provided that $x_1,\dots, x_{k-\ell-1}$, $y_1,\dots, y_{k-\ell-1}$ are all distinct. Therefore the desired $(x_1,\dots, x_{k-\ell-1})$ and $(y_1,\dots, y_{k-\ell-1})$ exist.

Next we apply Theorem \ref{thm:GPW} to $\G'$ and obtain a tight Hamilton path
\[
\mathcal{P}= x_{k-\ell-1}x_{k-\ell-2}\cdots x_1 \cdots \cdots y_1y_2\cdots y_{k-\ell-1}.
\]
Following the order of $\mathcal{P}$, we partition $Y_1$ into
\[
R_{2q+1}, S_{2q+1}, R_{2q+1}', L_{2q+2},\dots, L_t, R_{t}, S_{t}, R_{t}'
\]
such that $|L_i|=\ell$, $|R_i|=|R_i'|=k-2\ell$, and $|S_i|=\ell-1$. Since $\mathcal{P}$ is a tight path in $\G$, we have
\begin{equation}\label{eq:goodQ}
L_i R_i S_i, \ S_i R'_i L_{i+1} \in E(\G)
\end{equation}
for $2q+2\le i\le t-1$. Letting $L_{t+1}= L_0$, by \eqref{eq:endG}, we also have \eqref{eq:goodQ} for $i=2q+1$ and $i=t$.

We now arbitrarily partition $P_i$, $1\le i\le 2q$ into $R_i \cup S_i\cup R'_i$ such that $|R_i|=|R_i'|=k-2\ell$, and $|S_i|=\ell-1$. By the choice of $P_i$,  \eqref{eq:goodQ} holds for $1\le i \le 2q$.

Consider the bipartite graph $\Gamma$ between $X$ and $Z := \{z_1, z_2, \dots, z_{t}\}$ such that $x\in X$ and $z_i\in Z$ are adjacent if and only if $L_i R_i S_i x, x S_i R'_i L_{i+1}\in E(\h)$. For every $i\in [t]$, since \eqref{eq:goodQ} holds, we have $\deg_{\Gamma} (z_i) \ge (1 - 2\sqrt \rho)t$ by the definition of $\G$. Let $Z'= \{z_{2q+1}, \dots, z_{t}\}$ and $X_0$ be the set of $x\in X$ such that $\deg_{\Gamma}(x, Z')\le |Z'|/2$. Then
\[
|X_0| \frac{|Z'|}2 \le \sum_{x\in X} \overline{\deg}_{\Gamma}(x, Z') \le 2 \sqrt \rho t\cdot |Z'|,
\]
which implies that
$|X_0| \le 4 \sqrt\rho t = 4 \sqrt{\rho} \frac{|Y|-\ell}{2k-2\ell-1}\le \frac{4}{3} \sqrt\rho |Y|$ (note that $2k-2\ell-1\ge k\ge 3$).

We now find a perfect matching between $X$ and $Z$ as follows.
\begin{enumerate}
\item[Step 1:]
Each $x\in X_0$ is matched to some $z_{2i}$, $i\in [q]$ such that the corresponding $Q_{2i}\in \F'$ is suitable for $x$ (thus $x$ and $z_{2i}$ are adjacent in $\Gamma$) -- this is possible because of \eqref{eq:F'} and
$|X_0| \le\frac43 \sqrt\rho |Y|$.
\item[Step 2:]
Each of the unused $z_{i}$, $i\in [2q]$ is matched to a vertex in $X\setminus X_0$ -- this is possible because $\deg_{\Gamma} (z_i) \ge (1 - 2\sqrt \rho)t \ge |X_0| + 2q$.
\item[Step 3:]
Let $X'$ be the set of the remaining vertices in $X$. Then $|X'|= t - 2q = |Z'|$.
Now consider the induced subgraph $\Gamma'$ of $\Gamma$ on $X' \cup Z'$. Since $\delta(\Gamma')\ge |X'|/2$, the Marriage Theorem provides a perfect matching in $\Gamma'$.
\end{enumerate}
The perfect matching between $X$ and $Z$ gives rise to the desired Hamilton path of $\h$.
\end{proof}

\section{Concluding Remarks}

Let $h^{\ell}_d(k, n)$ denote the minimum integer $m$ such that every $k$-graph $\h$ on $n$ vertices with minimum $d$-degree $\delta_d(\h) \ge m$ contains a Hamilton $\ell$-cycle (provided that $k- \ell$ divides $n$). In this paper we determined $h^{\ell}_{k-1}(k, n)$ for all $\ell<k/2$ and sufficiently large $n$. Unfortunately our proof does not give $h^{\ell}_{k-1}(k, n)$ for all $k, \ell$ such that $k-\ell$ does not divide $k$ even though we believe that $h^{\ell}_{k-1}(k, n)= \frac{n}{\lceil \frac{k}{k-\ell} \rceil (k-\ell)}$. In fact, when $k-\ell$ does not divide $k$, if we can prove a path-cover lemma similar to Lemma~\ref{lemP}, then we can follow the proof in \cite{KMO} to solve the nonextremal case. When $\ell \ge k/2$, we cannot define $\Y_{k,2\ell}$ so the current proof of Lemma~\ref{lemP} fails. In addition, when $\ell \ge k/2$, the extremal case becomes complicated as well.

The situation is quite different when $k-\ell$ divides $k$.
When $k$ divides $n$, one can easily construct a $k$-graph $\h$ such that
$\delta_{k-1}(\h)\ge \frac{n}{2} - k$ and yet $\h$ contains no perfect matching and consequently no Hamilton $\ell$-cycle for any $\ell$ such that $k-\ell$ divides $k$. A construction in \cite{MaRu} actually shows that $h_{k-1}^{\ell}(k,n)\ge \frac n2-k$ whenever $k-\ell$ divides $k$, even when $k$ does not divide $n$.
The exact value of $h^{\ell}_d(k, n)$,
when $k-\ell$ divides $k$, is not known except for $h_2^2(3,n)= \lfloor n/2 \rfloor$ given in \cite{RRS11}.
In the forthcoming paper \cite{HZk2}, we determine $h^{k/2}_d(k, n)$ exactly for even $k$ and any $d\ge k/2$.

Let $t_d(n, F)$ denote the minimum integer $m$ such that every $k$-graph $\h$ on $n$ vertices with minimum $d$-degree $\delta_d(\h) \ge m$ contains a perfect $F$-tiling.
One of the first results on hypergraph tiling was $t_2(n, \Y_{3,2})= n/4 + o(n)$ given by K\"uhn and Osthus \cite{KO}. The exact value of $t_2(n, \Y_{3,2})$ was determined recently by Czygrinow, DeBiasio, and Nagle \cite{CDN}. We \cite{HZ3} determined $t_1(n, \Y_{3,2})$ very recently.
The key lemma in our proof, Lemma~\ref{lem:F}, shows that every $k$-graph $\h$ on $n$ vertices with $\delta_{k-1}(\h)\ge  (\frac{1}{2k-b} - o(1)) n$ either contains an almost perfect $\Y_{k,b}$-tiling or is in the extremal case. Naturally this raises a question: what is $t_{k-1}(n, \Y_{k,b})$?
Mycroft \cite{My14} recently proved a general result on tiling $k$-partite $k$-graphs, which implies that $t_{k-1}(n, \Y_{k,b})= \frac{n}{2k-b} + o(n)$.
The lower bound comes from the following construction. Let $\h_0$ be the $k$-graph on $n\in (2k-b)\mathbb N$ vertices such that $V(\h_0)=A\cup B$ with $|A|=\frac{n}{2k-b} - 1$, and $E(\h_0)$ consists of all $k$-sets intersecting $A$ and some $k$-subsets of $B$ such that $\h_0[B]$ contains no copy of $\Y_{k,b}$.
Thus, $\delta_{k-1}(\h_0)\ge \frac{n}{2k-b}-1$. Since every copy of $\Y_{k,b}$ contains at least one vertex in $A$, there is no perfect $\Y_{k,b}$-tiling in $\h_0$.
We believe that one can find a matching upper bound by the absorbing method (similar to the proof in \cite{CDN}). In fact, since we already proved Lemma~\ref{lem:F}, it suffices to prove an absorbing lemma and the extremal case.

\section*{Acknowledgement}
We thank two referees for their valuable comments that improved the presentation of this paper.

\bibliographystyle{plain}
\bibliography{Jan2014}

\end{document}


TITLE: How many ways can you distribute $10$ identical balls into $5$ distinguishable boxes so that the sum total of balls in the first two boxes equals $6$?
QUESTION [0 upvotes]: How many ways can you distribute $10$ identical balls into $5$ distinguishable boxes so that the sum total of balls in the first two boxes equals $6$?
This is probability/Combinatorics
What I have so far:
$$\frac{6!}{2!(6-2)!} + \frac{4!}{3!(4-3)!} = 19$$
Does this look correct?

REPLY [1 votes]: *Hint:
For problems of identical balls into distinguishable boxes, you must be familiar with stars and bars:
The problem needs to be broken into $2$ parts: $6$ balls in the first two boxes, $4$ balls in the next three, apply stars and bars for each, and then apply the multiplication principle.
For the first part, taking zero balls in boxes to be permissible, the number of ways = $\binom{6+2-1}{2-1} = 7$, you can verify the formula for this simple case by enumeration.
Proceed.....

REPLY [1 votes]: You have two disjoint problems:  divide six balls between the first two boxes (how many ways?) and divide the other four between the remaining three boxes.  As they are independent, you multiply the results for the two problems.  As $19$ is prime, it is unlikely to be the correct answer.


TITLE: Prove that $1\le a_{n} \le 2$ for the following sequence
QUESTION [4 upvotes]: Suppose $a_n$ is the sequence satisfying $a_1 = 1 = a_2$ and $a_n = {1\over2}\left(a_{n-1} + {2 \over a_{n-2}}\right)$ for $n \ge3$. Prove that $1\le a_n\le2$ for all $n \in \mathbb{N}$.
My attempt: I decided to proceed by strong induction
Base cases:
Suppose $n = 1$. Then $a_1 = 1$, as required.
Suppose $n = 2$. Then $a_2 = 2$ as required.
Induction Hypothesis: Assume $1\le a_i \le 2$ for $i = 1, 2, 3, \ldots, k$ for some $k \in \mathbb{N}$.
Induction step: assume $n = k+1$. Then,
$a_{k+1} = {1\over2}\left(a_{k} + {2 \over a_{k-1}}\right) = {a_k\over2} + {1\over a_{k-1}}$
By the IH, $1 \le a_k \le 2$. therfore, ${1\over 2}\le{a_k\over2}\le 1$ and ${1\over 2} \le{1\over a_{k-1}} \le 1 $. Hence, $1 \le {a_k\over2} + {1\over a_{k-1}} \le 2$.
Is this correct?

REPLY [0 votes]: This looks correct. Wording quibble: by "assume $n=k+1$" you really mean "let $n=k+1$".


TITLE: How to find an argument of $ z=1-\cos\varphi-i\sin\varphi $?
QUESTION [0 upvotes]: How to find an argument of this complex number?
  $$
z=1-e^{i\varphi}=1-\cos\varphi-i\sin\varphi
$$

I know I should try to make $z$ equal to $r(\cos\psi+i\sin\psi)$. And then $Arg(z)=\psi$. But I don't really understand how to do that.
I tried something like that:
$$
z=2\sin^2\frac{\varphi}{2}-2i\sin\frac{\varphi}{2}\cos\frac{\varphi}{2}=2\sin\frac{\varphi}{2}\left(\sin\frac{\varphi}{2}-i\cos\frac{\varphi}{2}\right)
$$
But obviously it didn't help much.

REPLY [1 votes]: I think you're on the right track:
\begin{align*}
z&=2\sin\frac{\varphi}{2}\left(\sin \frac{\varphi}{2}-i\cos\frac{\varphi}{2}\right)\\
&=2\sin\frac{\varphi}{2}\left(-ie^{i\varphi/2}\right)\\
&=2\sin\frac{\varphi}{2}\left(e^{-i\pi/2}e^{i\varphi/2}\right)\\
&=\dots
\end{align*}


TITLE: Set of small numbers with distinct $k$-sums
QUESTION [4 upvotes]: Let $A$ be a set of $n$ positive integers with distinct $k$-sums. In other words, if $a_1\le\cdots\le a_k$ and $b_1\le\cdots\le b_k$ are elements of $A$ such that $a_1+\cdots+a_k=b_1+\cdots+b_k$, then $a_i=b_i$, $i=1,\ldots,k$. How small can $\max A$ be?
Let $S(n,k)$ be the smallest possible value of $\max A$.
Some trivial attempts: The construction $A=\lbrace 1,k,k^2,\ldots,k^{n-1}\rbrace$ gives $S(n,k)\le k^{n-1}$. On the other hand, there are ${k+n-1\choose n-1}$ sequences $a_1\le\cdots\le a_k$, which correspond to distinct $k$-sums whose values are at most $k\cdot\max(A)$. Thus $S(n,k)\ge\frac1k{k+n-1\choose n-1}$.
Additional question: How to explicitly construct the set $A$ so that $\max A$ is small? Thomas Bloom asserted below that $S(n,k)\asymp n^k$, but I will be satisfied with a construction where $\max A$ is a polynomial of $n$ (of order possibly larger than $k$).

REPLY [4 votes]: These are commonly known as $B_k$ sets. It is known that the order of magnitude of a $B_k$ set in $[1,N]$ is around $N^{1/k}$ so that, in your notation
$$ S(n,k) \asymp n^k $$
where the implicit constants can depend on $k$.
A paper of Bose and Chowla (Theorems in the additive theory of numbers. Comment. Math. Helv. 37 1962/1963 141–147) shows that
$$ S(n,k) \leq (1+o(1))n^k $$
as $n\to\infty$. This generalises a result of Singer in the $k=2$ case.
When $k=2$ this is sharp, as shown in a paper of Erdos and Turan (On a problem of Sidon in additive number theory, and on some related problems.
J. London Math. Soc. 16, (1941). 212–215)
For recent progress on lower bounds for $k\geq 3$ see "New upper bounds for finite Bh sequences" by J. Cilleruelo (Adv. Math. 159 (2001), no. 1, 1–17). For large $k$ these are roughly of the shape $k^{-2k^2}$.
Edit: here's a simple explicit construction that almost gives $n^k$. Equivalently, we want to find a $B_k$ set in $[1,N]$ of size almost $N^{1/k}$. Suppose that $N+1$ is a prime. Let $P$ be the set of all primes at most $N^{1/k}$. Let
$$ A = \{ 1\leq n\leq N : \theta^n\in P\} $$
for some primitive root $\theta$ of $N+1$. Then
$$ x_1+\cdots+x_k=y_1+\cdots+y_k $$
if and only if, letting $p_i=\theta^{x_i}$ and $q_i=\theta^{y_i}$,
$$ p_1\cdots p_k =q_1\cdots q_k \pmod{N+1} $$
But since these terms are less than $N+1$ this congruence is a genuine equality, and we're done by the fundamental theorem of arithmetic. This gives a construction of a $B_k$ set in $[1,N]$ of size about $kN^{1/k}/\log N$, and we're done.


TITLE: Frequency computation
QUESTION [2 upvotes]: I generate pulses using microcontroller with following method:

Set $A=0$
With frequency $F$ execute the following code:
2.1. Add $S$ to $A$
2.2. If $A\ge N$ then produce a pulse and substract $N$ from $A$

Here $A, S, N\in \mathbb N$, and $S\le N$.
It's easy to see that period between the pulses may be not constant, but let's call the frequency $f$ of the pulses the limit of number of pulses per time $T$ divided to $T$ when $T\to \infty$.
How to compute $f$? I can compute it for concrete numeric examples, but I need general symbolic solution.

REPLY [1 votes]: As mentioned in the comments, at $T\to\infty, f=\frac{FS}{N}$ for $N>S$ and for $N\leq S$ your code will start double pulsing periodically.
However, that's the the limit. If you aren't looking at long term behavior, this is what you'll follow:
Define $r\equiv N\pmod{S}$. (i.e. $r$ is the remainder after dividing $N$ by $S$.) The number generation will be cyclic over $S$ pulses. So every $S$ pulses, you have the same pattern again. However, in this cycle, some of the pulses will be $F$ longer than the rest. Denote $P=\lfloor \frac{N}{S}\rfloor$. You will have $S-r$ pulses of length $\frac{P}{F}$ and $r$ pulses of length $\frac{P+1}{F}$. However, the longer pulses will be evenly spaced out in the cycle.
For example: take $N=30$ and $S=7$. We know $r=2$ and $P=4$.
Here is the cycle:
$$7,14,21,28,35$$
$$12,19,26,33$$
$$10,17,24,31$$
$$8,15,22,29,36$$
$$13,20,27,34$$
$$11,18,25,32$$
$$9,16,23,30$$
$$\vdots$$
You have a cycle of length $7$ where $7-2=5$ of them are of length $P$ and $r=2$ of them of length $P+1$.
However, for fast enough $F$, it will be hard to notice the difference between this "varying" frequency pulse pattern and a pulse sequence of frequency $\frac{FS}{N}$.


TITLE: prove $\prod_{i=0}^{n}x-\frac{i}{n}\le\frac{n!}{4n^{n+1}}$ for any $x\in[0,1]$ and $n>2$
QUESTION [3 upvotes]: prove $\prod_{i=0}^{n}x-\frac{i}{n}\le\frac{n!}{4n^{n+1}}$ for any $x\in[0,1]$ and natural $n>2$.
I tried using AM-GM, but found nothing interesting.
I was looking also for a Taylor series. no luck

REPLY [3 votes]: Let $(\sigma_0,\ldots,\sigma_n)$ be a permutation of $(0,\ldots,n)$ such that $$|x-\tfrac{\sigma_0}{n}| \le |x-\tfrac{\sigma_1}{n}| \le \cdots \le |x-\tfrac{\sigma_{n-1}}{n}| \le |x-\tfrac{\sigma_n}{n}|.$$ In other words, of the points $\{\tfrac{0}{n},\tfrac{1}{n},\ldots,\tfrac{n-1}{n},\tfrac{n}{n}\}$, $\tfrac{\sigma_0}{n}$ is the closest to $x$, $\tfrac{\sigma_1}{n}$ is the 2nd closest to $x$, ..., and $\tfrac{\sigma_n}{n}$ is the farthest from $x$, with ties broken arbitrarily.
If $x = \tfrac{k}{n}$ for some $k = 0,\ldots,n$, then $\prod_{i = 0}^{n}|x-\tfrac{i}{n}| = 0 \le \tfrac{n!}{4n^{n+1}}$ holds trivially.
Now, suppose $x \in (\tfrac{k-1}{n},\tfrac{k}{n})$ for some $k = 1,\ldots,n$. Then $\{\sigma_0,\sigma_1\} = \{k-1,k\}$, and thus, $$\left|x-\tfrac{\sigma_0}{n}\right| \cdot \left|x-\tfrac{\sigma_1}{n}\right| = (x-\tfrac{k-1}{n})(\tfrac{k}{n}-x) \le \left(\dfrac{(x-\tfrac{k-1}{n})+(\tfrac{k}{n}-x)}{2}\right)^2 = \dfrac{1}{4n^2}.$$
Also, for $i = 2,\ldots,n$, we have $|x-\tfrac{\sigma_i}{n}| \le \tfrac{i}{n}$ since at least $i+1$ of the points $\{\tfrac{0}{n},\tfrac{1}{n},\ldots,\tfrac{n-1}{n},\tfrac{n}{n}\}$ are within $\tfrac{i}{n}$ of the point $x$. Hence, $$\prod_{i = 0}^{n}|x-\tfrac{i}{n}| = \prod_{i = 0}^{n}|x-\tfrac{\sigma_i}{n}| = \left|x-\tfrac{\sigma_0}{n}\right| \cdot \left|x-\tfrac{\sigma_1}{n}\right| \cdot \prod_{i = 2}^{n}\left|x-\tfrac{\sigma_i}{n}\right| \le \dfrac{1}{4n^2}\prod_{i = 2}^{n}\dfrac{i}{n} = \dfrac{n!}{4n^{n+1}}.$$

REPLY [3 votes]: Let $f(x)=\prod_{i=0}^n\left|x-\frac{i}{n}\right|$. Since $f$ is continuous on the compact interval $[0,1]$, it attains its max at some $y\in[0,1]$. As $f(x)=f(1-x)$, we may assume WLOG that $y\in[0,1/2]$.
If $y>1/n$, then
$$f\left(y-\frac{1}{n}\right)=\left(1-\frac{1}{n}-y\right)\cdot\prod_{i=0}^{n-1}\left|y-\frac{1}{n}-\frac{i}{n}\right| > y\cdot\prod_{i=1}^n\left|y-\frac{i}{n}\right|=f(y).$$
So we must have $0\leq y\leq\frac{1}{n}$. Then by AM-GM, $y\left(\frac{1}{n}-y\right)\leq\frac{1}{4n^2}$, so
$$f(y)=y\left(\frac{1}{n}-y\right)\cdot\prod_{i=2}\left(\frac{i}{n}-y\right)\leq\frac{1}{4n^2}\cdot\prod_{i=2}^n\frac{i}{n}=\frac{n!}{4n^{n+1}}.$$


TITLE: Why can't we have charge field?
QUESTION [1 upvotes]: I learnt that everything is made of field, there is the electron field that occupy the entire universe and it will produce an electron which is an excitation of the field. This electron interacts with the higgs field that give it it's mass and it also carries a negative electric charge, I am wondering why can't an electron through interaction with a say charge field instead? I also know there is the electric field but you need to have a charge to create an electric field just like a mass creating gravitational field.

REPLY [2 votes]: Charge and mass are very different properties because charge originates from a fundamental symmetry while mass does not. Indeed a non-zero mass breaks a fundamental symmetry. This difference is why we believe the two properties have different origins.
Charge arises from a symmetry of the Dirac Lagrangian This is nicely described by JamalS's answer to What is charge actually? How to define it? In the Standard model it is associated with the $U(1)$ symmetry. Any theory with this symmetry will inevitably have a property homologous to electric charge. No external mechanism is needed to produce it.
By contrast mass is not a fundamental property and is not required by any symmetries. Indeed the $SU(2)$ symmetry of the Standard Model is only possible when all particles are massless. So we believe that all particles are fundamentally massless and mass only exists because there is some external mechanism to produce it. That of course being the Higgs mechanism.
So at least in quantum field theory the answer to your question is that no, charge is not produced by a mechanism akin to the Higgs.


TITLE: What is the equation of the line with the property that the shortest distance between that line and the parabola is 1?
QUESTION [1 upvotes]: What is the equation of the line with the property that the shortest distance between that line and the parabola is 1?

The parabola is $y=x^2$ and the linear pass (2,0). The shortest distance between that linear and the parabola is 1.
Normally, linear & parabola calculus problem will ask the equation of linear that touch the parabola at specific (x,y) point. I can solve that problem by finding the derivative of the parabola. Then put the x value into the derivative function to find the slope of the linear. After that, it isn't hard to find the equation of the linear.
But this question is different. It ask the equation of linear that have the shortest distance between that linear and the parabola is 1. I don't know how solve it. I know that the linear y=ax-2a since it pass (2,0) but don't know the next step.
I try plotting graph in Desmos. I think $a \approx 6\pm1$ but don't know the exact value.

REPLY [3 votes]: At the point $(x_0,x_0^2)$ the parabola $y=x^2$ has tangent line $y = 2x_0(x-x_0) + x_0^2 = 2x_0x - x_0^2$.
If we slide over the line $y = ax-2a$ by the right amount, this line should become a tangent line. To find the right amount to make the normal distance equal to one, use the perpendicular slope of $-\frac{1}{a}$ and draw a right triangle with side 1, which should give you $\sqrt{\frac{a^2+1}{a^2}}$. Then the translated line has formula $y = ax - (2a - a\sqrt{\frac{a^2+1}{a^2}})$
That means we have two equations for the same tangent line, which yields $a = 2x_0$ and $2a - a \sqrt{\frac{a^2+1}{a^2}} = x_0^2$.
That gives a quartic for $a$, and WolframAlpha gives $a = 3.8685$ or $a = 0.64851$, or the degenerate $a = -0.53086$ or $a = 12.014$, which should get you the equation for the line.


TITLE: Topological Vector Space
QUESTION [9 upvotes]: Show:

Let $\{U_{\lambda}: \lambda \in L\}$ be a base of neighbourhoods at $0$ in a topological vector space $\mathcal{X}$. Then $\{U_{\lambda}+ U_{\lambda}: \lambda \in L\}$ is also a base of neighbourhoods.

I have an intuition that this is to proved using the continuity of the "+" operator, but am not able to proceed.

REPLY [8 votes]: Your intuition is correct! Let $U$ be a neighbourhood at $0$, since $+: X\times X\to X$ is a continuous map then $+^{-1}(U)$ is open and $(0,0)\in +^{-1}(U)$. By definition of the product topology there are $\lambda_1, \lambda_2$ so that $U_{\lambda_1}\times U_{\lambda_2}\subseteq +^{-1}(U)$. Using the fact that $U_{\lambda_1}\cap U_{\lambda_2}$ is a neighbourhood at $0$ we can find a $\lambda$ such that $U_{\lambda}\subseteq U_{\lambda_1}\cap U_{\lambda_2}$. It follows that $U_\lambda\times U_\lambda\subseteq +^{-1}(U)$, in other words $U_\lambda+ U_\lambda=+(U_\lambda\times U_\lambda)\subseteq U.$


TITLE: Solving for $A$ in $Ax = b$
QUESTION [3 upvotes]: How does one solve for the matrix $A$ in the system $$ Ax = b$$ when say, $A$ is a $3\times 3$ matrix and $x$ and $b$ are both $3 \times 1$. $x$ and $b$ are obviously known.
The obvious approach would be to Multiply $A$ and $x$ and compare coefficients. How does one solve this in a general setting.

REPLY [2 votes]: Write the $m\times n$ matrix $A$ as
$$
A=\begin{bmatrix}a_1^T\\\vdots\\a_m^T\end{bmatrix},
$$
so $a_i^T$ are the rows of $A$. Then $Ax=b$ is equivalent to
$$
x^Ta_i=b_i,\quad i=1,\ldots,m,
$$
that is
$$
\begin{bmatrix}
x^T &        &     \\
    & \ddots &     \\
    &        & x^T
\end{bmatrix}
\begin{bmatrix}
a_1\\\vdots\\a_m
\end{bmatrix}
=b.
$$
This can be written in a compact form using the Kronecker product as
$$\tag{1}
(I_m\otimes x^T)a=b,
$$
where $a^T=[a_1^T,\ldots,a_m^T]$. So finding $A$ such that $Ax=b$ for given $x$ and $b$ is equivalent to solving (1).
The system (1) does not have a solution if $x=0$ and $b\neq 0$. Otherwise, it is solvable.
In addition, if $n>1$, the solution is not uniquely determined as the rank of the $m\times mn$ matrix $I_m\otimes x^T$ is $m$ an hence its nullity is $m(n-1)$. In fact, if $A_0x=b$ for some $A_0$, then $Ax=b$ for any $A$ in the form $A=A_0+Z(I-xx^{\dagger})$, where $x^{\dagger}=\frac{x^T}{x^Tx}$ and $Z$ is arbitrary $m\times n$.


TITLE: Prove that $\lim \limits _{n \to \infty} \left( n - \frac 1 {e^{\frac 1 n} - 1} \right) = \frac 1 2$
QUESTION [3 upvotes]: Limit of reciprocal of nth root of e minus 1 is linear
I somehow got around to needing to know the value of $\frac 1 {e^{\frac 1 n}  -1}$, and noticed that it seems very linear:

And that the difference from $n$ seems to go to $\frac 1 2$:

Thus I would like to see a proof of this fact, which I was unable to prove:
$$\lim \limits _{n \to \infty} \left( n - \frac 1 {e^{\frac 1 n} - 1} \right) = \frac 1 2$$

REPLY [2 votes]: $$\lim \limits _{n \to \infty} \left( n - \frac 1 {e^{\frac 1 n} - 1} \right)=\lim \limits _{m \to 0} \left(\frac 1m - \frac 1 {e^m - 1} \right)=\lim \limits _{m \to 0}\frac{e^m-1-m}{m(e^m-1)}$$
Now from $e^m=1+m+\frac {m^2}{2!}+\frac{m^2}{3!}+o(m^3)$ we get
$$\lim \limits _{m \to 0}\frac{e^m-1-m}{m(e^m-1)}=\lim \limits _{m \to 0}\frac{m^2(\frac12+\frac{m}{3!}+....)}{m^2(1+\frac m2+....)}=\lim \limits _{m \to 0}\frac{\frac12+\frac{m}{3!}+....}{1+\frac m2+....}=\frac12 $$


TITLE: Inequality for the expected value of the sum of Bernoulli random variables
QUESTION [0 upvotes]: I'm stuck with this seemingly simple inequality.

Suppose that $X_1,X_2,\ldots$ are Bernoulli random variables and denote $S_n=X_1+\ldots+X_n$. Let $n_k=\inf\{n:\operatorname ES_n\ge k^2\}$ for $k\ge1$. Show that the inequality
  $$
k^2\le\operatorname ES_{n_k}\le k^2+1
$$
  is valid for $k\ge1$.

The first inequality follows from the definition of $n_k$, but how can we make sure that the second inequality is valid? We have that
$$
\operatorname ES_{n_k}=\operatorname EX_1+\ldots+\operatorname EX_{n_k}\le n_k
$$
since $\operatorname EX_m\le 1$ for $m\ge1$, but we only know that $n_k\ge k^2$.
Any help is much appreciated!

REPLY [1 votes]: As you say, the left inequality follows from the definition of $n_k$.  Suppose the right inequality were false.  That is, suppose $$E[S_{n_k}]>k^2+1$$
Then, since $E[X_{n_k}]≤1$ we must have $E[S_{n_k-1}]>k^2$  whence we have found an integer smaller than $n_k$ which satisfies the defining inequality for $n_k$, a contradiction.