
\documentclass[11pt]{article}
\usepackage{e-jc}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{epsf}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{defn}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{state}[theorem]{Statement}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{conjecture}[theorem]{Conjecture}
%\addtolength{\oddsidemargin}{-.875in}
%\addtolength{\evensidemargin}{-.875in}
%\addtolength{\textwidth}{1.75in}
%\pagestyle{plain}


\begin{document}

\title{Tight co-degree condition for perfect matchings in 4-graphs}
\author{Andrzej Czygrinow\thanks{School of Mathematical and Statistical Sciences, Arizona State University, Tempe, AZ 85287. Research partially supported  by NSA grant H98230-08-1-0046.}, Vikram Kamat\thanks{Department of Computer Science \& Automation, Indian Institute of Science, Bangalore -- 560 012, India.}}

\maketitle
\begin{abstract}
We will give a tight minimum co-degree condition for a 4-uniform hypergraph to contain a perfect matching.
\end{abstract}


\section{Introduction}

A $k$-graph $H$ is a pair $(V, E)$ such that $E$ is a family of $k$-subsets of $V$.
For a $k$-graph $H=(V,E)$, $1\leq i < k$,  and $S \subset V$ with $|S|=i$ we set $L(S) =  \{ A\in {[n] \choose k - i} | S \cup A\in E\}$, write  $L(u)$ for $L(\{u\})$, $L(u,v)$ for $L(\{u, v\})$, and define $\delta_i(H) := \min \{|L(S)| : S\subset V, |S|=i\}.$
A {\it matching} in $H=(V,E)$ is a subset $M$ of $E$ such that every two distinct  edges in $M$ are disjoint. A matching $M$  is called {\it perfect} if $V(M)=V(H)$.  For $k\in Z^+$ and $n$ divisible by $k$, let $m_i(k,n)$ be the minimum positive integer such that every $k$-graph $H$ on $n$ vertices
that satisfies $\delta_i(H) \geq m_i(k,n)$ has a perfect matching. Function $m_i(k,n)$ has been subject of intensive studies. In the case of graphs, Dirac's theorem gives $m_1(2,n) = n/2$.  On the other hand, for  $k> 2$  the behavior of $m_i(k,n)$ is much more elusive. The exact values of $m_i(k,n)$ are known only for very few values of $i$ and $k$ and even the asymptotic value of $m_i(k,n)$ is not well understood. For general $k>2$ only $m_{k-1}(k,n)$ has been determined exactly. In  \cite{RRS}, 
 R\"{o}dl, Ruci\'{n}ski,  Szmer\'{e}di proved the following impressive result:
 \begin{equation}
 m_{k-1}(k,n) = \left\{
	\begin{array}{ll}
		n/2 + 3 -k  & \mbox{if $k/2$ is even and $n/k$ is odd}\\
		n/2+5/2 - k & \mbox{if $k$ is odd and $(n-1)/2$ is odd}\\
		n/2 + 3/2 -k & \mbox{if $k$ is odd and $(n-1)/2$ is even}\\
		n/2+2 - k & \mbox{otherwise}.
	\end{array}
\right.
 \end{equation}
%Note that $\delta_{i}(H) \geq \frac{n-i}{k-i} \delta_{i+1}(H)$ and so a lower bound for $\delta_{k-1}(H)$ gives  lower bounds for all $\delta_i(H)$ with $i< k-1$.  The weakest possible minimum degree condition that can be imposed on $H$ is for $\delta_1(H)$ and this line of studies has attracted a lot of attention.
In  \cite{Schacht}, H. H\'{a}n, Y. Person, and M. Schacht  found the asymptotic value of  $m_1(3, n)$ and offered the following conjecture.
\begin{conjecture}\label{conj1}
For all $1\leq i\leq k-1$,
$$m_i(k,n) = \left(1+ o(1)\right) \max\left\{\frac{1}{2}, 1 - \left(\frac{k-1}{k}\right)^{k-i}\right\}{n - i \choose k- i}.$$
\end{conjecture}
 Subsequently, I. Khan \cite{khanmatching} and independently K\"{u}hn, Osthus, and Treglown  \cite{KOT} proved that  $m_1(3,n) = { n-1 \choose 2} - {2n/3 \choose 2}+1 $. In addition, I. Khan \cite{khan}  showed that $m_1(4,n)={n -1 \choose 3} - {3n/4 \choose 3} +1$ and  in a recent paper Alon et al. \cite{alon} proved a general result on the fractional matching number and used it to find asymptotic values  of $m_2(5,n), m_1(5,n)$, $m_2(6,n), m_3(7,n)$.

As suggested by  Conjecture \ref{conj1}, the function $m_i(k,n)$ behaves differently when $i\geq k/2$. This is indeed the case as proved by  Pikhurko in \cite{pikhurko}: 
\begin{equation}\label{pihurko}
 m_i(k, n) = \left(1+ o(1)\right) \frac{1}{2} {n - i \choose k - i}.
\end{equation}

In this paper we give exact value of $m_2(4,n)$. 
%From (\ref{pihurko}) $m_2(4,n) = \left(\frac{1}{2}+o(1)\right){n -2 \choose 2}$ and we prove the following.
\begin{theorem}\label{main}
 There is $n_0\in \mathcal{N}$ such that every 4-graph $H$ on $n \geq n_0$ vertices with $4|n$ that satisfies
 \begin{equation}\label{degree-condition}
\delta_2(H) \geq \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil + 1,
\end{equation}
 has a perfect matching.
\end{theorem}
Recently and independently, $m_2(4,n)$ was found by Traglow and Zhao in \cite{Zhao}.

Note that  (\ref{pihurko}) gives $m_2(4,n) = \left(\frac{1}{2}+o(1)\right){n -2 \choose 2}$ and the expression in (\ref{degree-condition}) is obtained by rounding  $\frac{1}{2}{n -2 \choose 2} -  \frac{\sqrt{n-3}}{2}$ . 
%\frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil +1,
In addition to the upper bound from  Theorem \ ref{main} we show that (\ref{degree-condition}) is tight.
\begin{theorem}\label{lower}
For every $m_0$ there is $m\geq m_0$ and a 4-graph $H$ on $n=4m$ vertices with $\delta_2(H) = \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil$ that has no perfect matching.
\end{theorem}
As in the case of   \cite{Schacht}, \cite{khanmatching}, \cite{khan}, \cite{KOT}
we use  the absorbing method from \cite{RRS}. Specifically, we prove that it is possible to find a large matching in $H$ and extend it to a perfect one using an absorbing structure unless $H$ has a special structure and approximately one of the two extremal 4-graphs in Figure \ref{fig-extremal}. The first of the extremal configurations, $H_1$, is a 4-graph on $n=4m$ vertices of which can be partitioned into two sets $A$ and  $B$,  with $|A|=|B|= 2m$ so that
$E(H_1) = { A \choose 4} \cup {B \choose 4} \cup {A \choose 2} \times {B \choose 2}.$ The second extremal 4-graph, $H_2$ is the complement of $H_1$ (see Figure 1). Although $H_1, H_2$  have their $\delta_2$ larger than the bound in (\ref{degree-condition}) a small modification of them can be used to verify Theorem \ref{lower}.
\begin{figure}\label{fig-extremal}
\begin{center}
\epsfxsize=5in
\epsffile{extremal.eps}
\caption{The extremal case.}
\end{center}
\end{figure}

Before proceeding to the next section, we fix some notation. Let $H=(V,E)$ be a 4-graph.  For $Z \subseteq V$, we write ${Z \choose k}$ to denote the set of $k$-subsets of $Z$. In addition, for pairwise disjoint sets $X_1, \dots, X_l \subseteq V$, we use ${X_1 \choose i_1} \times \cdots \times {X_l \choose i_l}$ to denote $\{S \subseteq V| \forall_j |S\cap X_j| = i_j\}$. For $Z \subseteq {V(H) \choose 3}$ and $v \in V(H)$,
 $deg(v, Z):= |L(v) \cap Z|$. In the case $G$ is a graph we use $deg_G(v)$ to denote the degree of a vertex $v$ in $G$ and if $D$ is a digraph, then $deg^-(v), deg^+(v)$ are used to denote the in-degree and out-degree of $v$ in $D$. For two $4$-graphs $H$ and $G$ with $V(H)=V(G)$ we use
$H \oplus G$ to denote the 4-graph on $V(H)$ with $E(H\oplus G)$ equal to the symmetric difference of $E(H)$ and $E(G)$.

The rest of the paper is structured as follows. In Section \ref{lower-section} we prove Theorem \ref{lower}. In Section \ref{extremal-section} we show that if $H$ is close to $H_1$ or $H_2$ and satisfies (\ref{degree-condition}), then it has a perfect matching.
In Section \ref{absorbing-section}, we prove an absorbing lemma which in connection with Section \ref{large-section}, which shows the existence of a large matching,  establishes Theorem \ref{main}.

\section{Lower bound}\label{lower-section}
We will consider two families of $4$-graphs $\mathcal{H}_1$ and $\mathcal{H}_2$. Let $n, k\in \mathcal{N}$ be such that $4|n$ and $k \ll n$. The family $\mathcal{H}_1$ contains all 4-graphs $H$ such that $V(H)$ can be partitioned into two sets $A, B$ so that $|A| = \frac{n}{2} -2k +1, |B|= \frac{n}{2} +2k-1$ and $E(H)={A \choose 4} \cup {B \choose 4} \cup {A \choose 2} \times {B \choose 2}$. Note that since $|A|$ is odd, $H$ does not contain a perfect matching. The family $\mathcal{H}_2$ contains $4$-graphs $H$ such that $V(H)$ can be partitioned into two sets $A, B$ so that $|A|= \frac{n}{2} -k, |B|= \frac{n}{2} +k$ and $E(H)= \left({A \choose 3} \times B\right)  \cup \left({B \choose 3} \times A\right)$. Note that some 4-graphs in $\mathcal{H}_2$ contain perfect matching. For $X, Y \in \{A,B\}$, we use $\delta_{XY}$ to denote $\min_{x \in X, y\in Y, x\neq y}|L(x,y)|.$
We have the following fact.
\begin{fact}\label{fact-degfamily}
There exists $n_0 \in \mathcal{N}$ such that if $H \in \mathcal{H}_1 \cup \mathcal{H}_2$ is a 4-graph on $n\geq n_0$ vertices, then $\delta_2(H) \leq \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil$.
\end{fact}
{\bf Proof.} Let $H \in \mathcal{H}_1$. If $k \geq \frac{3 + \sqrt{n-3}}{4}$, then $\delta_{AB} = (|A|-1)(|B|-1) \leq \frac{n^2-5n}{4} - \frac{\sqrt{n-3} -3}{2}$ and since the left hand side is an integer, $\delta_{AB} \leq \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil$. If $k \leq  \frac{3 + \sqrt{n-3}}{4}$, then $\delta_{BB} = {|B| -2 \choose 2} + {|A| \choose 2} \leq  \frac{n^2-5n}{4} - \frac{\sqrt{n-3} -3}{2}$. Now let  $H \in \mathcal{H}_2$. If $k \geq \frac{-1 + \sqrt{n-3}}{2}$, then $\delta_{AA} = (|A|-2)|B| \leq
 \frac{n^2-5n}{4} - \frac{\sqrt{n-3} -3}{2}$ and if $k \leq \frac{-1 + \sqrt{n-3}}{2}$, then $\delta_{AB} = {|A|-1 \choose 2} + {|B|-1 \choose 2} \leq  \frac{n^2-5n}{4} - \frac{\sqrt{n-3} -3}{2}$.\\
 {\bf Proof of Theorem \ref{lower}.}  For a positive integer $k$,  let $m =4k^2 -6k +3$, $n= 4m$ and take $H \in \mathcal{H}_1$ with parameters $k$ and $n$. Then $k = \frac{3+ \sqrt{n-3}}{4}$, $\frac{\sqrt{n-3} -3}{2} =2k -3$ and $\delta_2(H) = \frac{n^2-5n}{4} - 2k+ 3$.  As mentioned before $H$ does not have a perfect matching.

 Note that a different example can be constructed by considering an appropriate $4$-graph from $\mathcal{H}_2$.

\section{The Extremal Case}\label{extremal-section}

We say that $H=(V,E)$ is $\beta$-extremal of {\it Type 1} if it is possible to partition $V$ into two sets $A, B$ so that
$\min\{|A|, |B|\} \geq (1/2 -\beta) n$ and
$$\left|E \cap \left( {A \choose 3} \times B \cup A \times {B \choose 3}\right)\right| \leq \beta n^4.$$
We say that $H$ is $\beta$-extremal of {\it Type 2} if it is possible to partition $V$ into two sets $A, B$ so that
$\min\{|A|, |B|\} \geq (1/2 -\beta) n$ and
$$\left|E \cap \left( {A \choose 2} \times {B \choose 2} \cup {A \choose 4} \cup {B \choose 4}\right) \right|\leq \beta n^4.$$ In  $H$ is $\beta$-extremal of Type 1 then $|H \oplus H_1| \leq \beta n^4$ and if $H$ is $\beta$-extremal of Type 2 then  $|H \oplus H_2| \leq \beta n^4$. We say that $H$ is $\beta$-extremal if it is $\beta$-extremal of Type 1 or Type 2.
In this section we prove that if $H$ is $\beta$-extremal for $\beta$ sufficiently small, then $H$ contains a perfect matching.
\begin{lemma}\label{extremal-case}
There is $n_0 \in \mathcal{N}$ and $0<\beta<1$ such that if $H$ is a 4-graph on $n> n_0$ vertices with $4|n$ such that
$H$ is $\beta$-extremal and
$$\delta_2(H) \geq \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil +1,$$
then $H$ has a perfect matching.
\end{lemma}
First, we will establish the following lemma.
\begin{lemma}\label{match-lem}
For every $0<\xi \leq 1/(100)^2$ there is $k_0$ such that  for  a 4-graph  $H$ on $X \cup Y$ with $|X|=|Y|=4k > k_0$ the following holds. If $H$  satisfies the following two conditions
\begin{itemize}
\item for every $x \in X$ at least $(1- \xi)|Y|$ vertices $y \in Y$ are such that $|L(x,y) \cap {Y \choose 2}| \geq (1- \xi)|Y|^2/2$,
\item for every $y \in Y$ at least $(1- \xi)|X|$ vertices $x \in X$ are such that $|L(x,y) \cap {X \choose 2}| \geq (1- \xi) |X|^2/2$,
\end{itemize}
then $H$ has a perfect matching.
\end{lemma}
{\bf Proof.}
Consider the following bipartite digraph $D$.
For $x \in X, y \in Y$, put $\overrightarrow{xy}$ if $|L(x,y) \cap {Y \choose 2}| \geq (1- \xi)|Y|^2/2$ and $\overrightarrow{yx}$ if $|L(x,y) \cap {X \choose 2}| \geq (1- \xi) |X|^2/2$. Note that for every $x \in X$,
$deg^{+}(x) \geq (1- \xi)|Y|$ and for every $y \in Y$, $deg^{+}(y) \geq (1- \xi) |X|$. As a result, for at least $(1- 2\xi)|X||Y|$ pairs $(x,y)\in X \times Y$ we have $\overrightarrow{xy} \in D$ and $\overrightarrow{yx} \in D$. Let $G$ be the bipartite graph on $X \cup Y$ with $xy \in G$ if
$\overrightarrow{xy} \in D$ and $\overrightarrow{yx} \in D$. For $Z \in \{X,Y\}$, let $Z^*= \{z \in Z| deg_G(z)\leq (1- \sqrt{2\xi})4k\}$. Simple computations show that for $Z \in \{X,Y\}$, $|Z^*| \leq \sqrt{2\xi} |Z|$. First, we will find a matching that uses all vertices from $X^* \cup Y^*$ and so we can assume that $|X^*|=|Y^*|$ and $|X^*|$ is even. Say $X^*=\{x_1, \dots, x_{2l}\}$ and $Y^*=\{y_1, \dots, y_{2l}\}$. Find a matching $M^*$
that uses all vertices from $X^* \cup Y^*$ using the step by step procedure: In the $i$th step, let $x,x' \in X\setminus X^*$, $y, y' \in Y \setminus Y^*$ be four vertices not previously used and such that $\{x, x'\} \in L(x_{2i-1}, y_{2i-1})$, $\{y, y'\} \in L(x_{2i}, y_{2i})$.  Add $\{x,x', x_{2i-1}, y_{2i-1}\}, \{y,y' , x_{2i}, y_{2i}\}$ to $M^*$. Let $Z'= Z \setminus V(M^*)$ and note that $|Z'| = 4(k-l) \geq 4k(1- 2\sqrt{2\xi})$ and $\delta(G[X', Y']) \geq 4k(1- 3\sqrt{2\xi}) \geq 2k$.  Let $M_G$ be a perfect matching in $G[X',Y']$, say $M_G=\{\{x_i, y_i\}| i =1, \dots, 4(k-l)\}$. Then 
$$\min\{|L(x_i,y_i) \cap {X' \choose 2}|, |L(x_i, y_i) \cap {Y' \choose 2}|\} \geq (1- 6 \sqrt{\xi}) |X'|^2/2.$$ Consider hypergraph $F$ on $[4(k-l)]$ with $\{p,q,r,s\} \in E(F)$ if $H[\{x_p,x_q, x_r, x_s, y_p, y_q, y_r, y_s\}]$ contains a matching of size two. For $\{p,q\} \subset V[H']$, $\min\{|L(x_p,y_p) \cap {X' \choose 2}|, |L(x_q, y_q) \cap {Y' \choose 2}|\} \geq (1- 6\sqrt{\xi}) |X'|^2/2$, and so for at least
$(1- 12\sqrt{\xi})|X'|^2/2$ pairs $\{i,j\} \in { [4(k-l)] \choose 2}$, $\{x_i, x_j\} \in L(x_p, y_p), \{y_i, y_j\} \in L(x_q, y_q).$ Thus
$\delta_2(F) \geq (1- 12 \sqrt{\xi}){|V(F)| \choose 2}$ and $F$ has a perfect matching which gives a perfect matching in $H[X', Y']$.\\
{\bf Proof of Lemma \ref{extremal-case}.}
Let  $\beta>0$ be a small constant and let $n$ be sufficiently large.
Suppose that   $H$ is a $\beta$-extremal  4-graph on $n$ vertices which satisfies (\ref{degree-condition}).
 Recall that for $X\in \{A,B\}$ we have $(1/2 -\beta)n \leq |X|\leq (1/2+ \beta)n$ and define
\begin{equation}\label{gamma-case1}
\gamma = \sqrt[3]{800 \beta}.
\end{equation}
{\it Case 1:  $H$ is $\beta$-extremal of Type 1.}\\
A vertex $v\in A \cup B$ is called {\it $\rho$-good} for $A$ if the following two conditions are satisfied:
\begin{itemize}
\item  For at least $(1-\rho) |A|$ vertices $a\in A$,
$|L(v,a) \cap {A \choose 2}| \geq (1-\rho) {|A| \choose 2}$.
\item For at least $(1-\rho) |B|$ vertices $b\in B$, $|L(v,b) \cap A \times B| \geq (1-\rho) |A||B|.$
\end{itemize}
Simple computations show that if $v$ is $\rho$-good for $A$, $\rho \leq 0.5$ and $\{A', B'\}$ is a partition of $V$ such that 
$|A \oplus A'| \leq \alpha n, |B \oplus B'| \leq \alpha n$,  then $v$ is $(\rho + 10\alpha)$-good for $A'$. Indeed, to check the first condition, the number of vertices  in $A'$ that do not satisfy the condition for $A$ is at most
$\rho |A| + \alpha n \leq \rho |A'| + \rho \alpha n + \alpha n < (\rho +10 \alpha)|A'|$ and for each vertex $a$ in $A'$ that satisfies the original condition, we have $|L(v,a) \cap {A' \choose 2}| \geq (1-\rho) {|A| \choose 2} - \alpha n |A| \geq (1- \rho) {|A| \choose 2} - 2.1\alpha  |A|(|A|-1) \geq (1- \rho - 4.2 \alpha){|A| \choose 2} \geq (1- \rho - 4.1\alpha) 
(1- 2.1\alpha)^2 {|A'| \choose 2} \geq (1- \rho -10 \alpha)  {|A'| \choose 2} .$ The second condition can be verified in the same way.

A vertex $v$ is called {\it $\rho$-acceptable} for $A$ if  $|L(v) \cap {A \choose 3}| \geq \rho n^3$
and is called {\it $\rho$-bad} for $A$ if it is not $\rho$-good. In the analogous way we define good, acceptable, and bad vertices for $B$. Let $Bad_X$ be the set of vertices in $X$ that are $\gamma$-bad for $X$.
\begin{claim}
$|Bad_A \cup Bad_B | < \gamma n$.
\end{claim}
{\bf Proof.} Assume that $|Bad_A| \geq \gamma n/2$ and suppose that for at least $\gamma n/4$ vertices  $a \in Bad_A$, there are at least $\gamma |A|$ vertices $a' \in A$ such that $|L(a, a') \cap {A \choose 2} | < (1-\gamma){|A| \choose 2} \leq (1-\gamma) (1+2\beta)^2 n^2/8$. Since $|L(a, a') \cap {B \choose 2}| <  (1+2\beta)^2 n^2/8$,  we have $|L(a, a') \cap A \times B| > \gamma n^2/16$. Consequently
$$\left|E(H) \cap {A \choose 3} \times B\right| \geq \gamma^3 |A| n^3 /(6\cdot 64)> \gamma^3 n^4/800$$
contradicting the definition of $\gamma$ in (\ref{gamma-case1}). Similarly, if for at least $\gamma n/4$ vertices $a\in Bad_A$,
there are at least $\gamma |B|$ vertices $b\in B$ such that $|L(a,b) \cap A \times B| < (1- \gamma) |A||B|$, then
$$\left|E(H) \cap\left({A \choose 3} \times B \cup {B \choose 3} \times A\right)\right| > \gamma^3 n^4/800.$$
Now we will show how to find a perfect matching in $H$. The argument is split into two cases.

First suppose that there is a vertex $v \in V$ such that either
\begin{itemize}
\item $\min \{deg(v, {A \choose 3}), deg(v, {B \choose 3}) \}\geq 5\gamma n^3$ or
\item $\min\{deg(v, {A \choose 2} \times B), deg(v, {B \choose 2} \times A) \}\geq 5\gamma n^3.$
\end{itemize}
Add $v$ to $A$ and keep it aside. Find a matching $M'$ of size at most $\gamma n$ that contains all vertices from $(Bad_A \cup Bad_B) \setminus \{v\}$. Let $A' = A \setminus  V(M'), B'= B \setminus V(M')$ and
let $|A'| =4p + r_A, |B'|= 4q + r_B$ where $0 \leq r_A, r_B \leq 3$, and either $r_A+ r_B=0$ or $r_A+r_B=4$.  Note that by definition of $\gamma$-good vertices, for every $a \in A'\setminus \{v\}$, $deg_A(a) \geq (1-\gamma)^2 {|A| \choose 3}$ and $|A\setminus A'| \leq 4\gamma n$. Since $\gamma$ is sufficiently small and $m_1(4, n) \sim \frac{37}{64}{n \choose 3}$ by the already mentioned result from \cite{khan} (or \cite{alon}), $H[A']$ ($H[B']$) has a perfect matching provided  the divisibility condition is satisfied and $v$ is taken care of.
We will guarantee that this is the case by selecting a matching of size at most three in $H[A' \cup B']$. 
%Note that in the case when $\min \{deg(v, {A \choose 3}), deg(v, {B \choose 3}) \}\geq 5\gamma n^3$ there is an edge in $H[A']$ that contains $v$.

\begin{itemize}
\item {\it Case: $r_A=r_B$}. If $r_A=r_B=2$, then we  take a hyperedge from $E(H) \cap \left({A' \choose 2} \times {B' \choose 2}\right)$ which contains $v$ in the case $\min\{deg(v, {A \choose 2} \times B), deg(v, {B \choose 2} \times A)\} \geq 5\gamma n^3$. If $r_A=r_B=2$ and $\min \{deg(v, {A \choose 3}), deg(v, {B \choose 3}) \}\geq 5\gamma n^3$, then we take an edge from ${A' \choose 4}$ that contains $v$, one edge from ${B' \choose 4}$, and an edge from ${A' \choose 2} \times {B' \choose 2}$ to obtain sets of size divisible by four. If $r_A=r_B=0$ and $\min\{deg(v, {A \choose 2} \times B), deg(v, {B \choose 2} \times A)\} \geq 5\gamma n^3$, then we take two independent edges $f_1, f_2$ from $E(H) \cap \left({A' \choose 2} \times {B' \choose 2}\right)$ such that $v\in f_1$ and if $\min \{deg(v, {A \choose 3}), deg(v, {B \choose 3}) \}\geq 5\gamma n^3$, then we take $f_1$ from $E(H) \cap {A \choose 4}$ that contains $v$.
\item {\it Case: $r_A \neq r_B$}. In this case $r_A \in \{1, 3\}$. We move $v$ to $B$ and apply the argument from the previous case.
\end{itemize}
Now suppose that no such $v$ exists. 

We claim that every vertex in $V$  is either $(10\gamma)$-acceptable for $A$ or $(10\gamma)$-acceptable for $B$. Indeed, if $v \in V$ and $\max\{|L(v) \cap {B \choose 3}| ,|L(v) \cap {A \choose 3}| \}< 10\gamma n^3$, then $\min\{deg(v, {A \choose 2} \times B), deg(v, {B \choose 2} \times A)\} \geq 5\gamma n^3$ as
$deg_H(v) = \frac{1}{3} \sum_{w \in V(H)\setminus \{v\}} |L(v,w)|\geq \frac{(n-1)}{3}\delta_2(H).$ 

In addition, note that if $v\in X$ is not
$(10\gamma)$-acceptable for $X$, then $v \in Bad_X$ and so there are at most $\gamma n$ vertices in $X$ that are not  $(10\gamma)$-acceptable for $X$. Distribute vertices from $Bad_A \cup Bad_B$ as follows. If $v \in Bad_A$ is $(10\gamma)$-acceptable for $B$, then move $v$ to $B$. Note that at most $\gamma n$ vertices will be moved from $A$ and so if $a$ is in $A$ after the distribution, then $deg_A(a) \geq 10\gamma n^3 -  \gamma n {|A| \choose 2} > 9 \gamma n^3$, that is, $a$ is $(9\gamma)$-acceptable for $A$. In addition, if $a \in A$ is $(10\gamma)$-good for $A$ before the distribution, then it is $(20\gamma)$-good after the distribution. Consequently, after the distribution, there are at most $\gamma n$, $(20\gamma)$-bad vertices in $A$ and each is $(9\gamma)$-acceptable for $A$.  The same applies to $B$. Suppose that $|A| \leq |B|$. 

If $|A| \bmod 2 = 0$, then proceed as follows. If  $|A| \bmod 4 = 2$, then let $f$ be an edge from $
{A \choose 2} \times {B \choose 2}$ and if $|A| \bmod 4 = 0$, then let $f= \emptyset$.  Find greedily a matching $M'$ in $H[A\setminus f]$ of size at most $\gamma n$ that contains all $(20\gamma)$-bad vertices. As a result $|A \setminus (V(M')\cup f)|$ has size divisible by four and all vertices are $(60\gamma)$-good.

If $|A| \bmod 2 = 1$ and there is an edge $f\in E(H) \cap \left(A \times {B \choose 3} \cup B \times {A \choose 3}\right)$, then add $f$ to the matching and note that $|A\setminus f | \bmod 2 = 0$. Consequently, we can proceed as in the previous case.

If  $E(H) \cap \left(A \times {B \choose 3} \cup B \times {A \choose 3}\right)$ is empty, then $H$ is a sub-hypergraph of a 4-graph  from $\mathcal{H}_1$ and, by Fact \ref{fact-degfamily}, $\delta_2(H) \leq \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil$ which contradicts  (\ref{degree-condition}).
 \\
{\it Case 2: $H$ is $\beta$-extremal of Type 2.}\\
A vertex $v \in A \cup B$ is called
{\it $\rho$-good for $A$} if at least $(1-\rho) |B|$ vertices $b\in B$ are such that $|L(v,b) \cap {A \choose 2}|  \geq (1-\rho) {|A| \choose 2}$.  A vertex $v$ is called {\it ${ \rho}$-acceptable} for $A$ if $|L(v) \cap {A \choose 2} \times B|  \geq \rho n^3$. If a vertex is not $\rho$-good, then it is called {\it $\rho$-bad}. Let $Bad_A$ be the set of vertices in $A$ that are $\gamma$-bad for $A$ and let $Bad_B$ be defined analogously.
\begin{claim}
$|Bad_A \cup Bad_B | < \gamma n$.
\end{claim}
{\bf Proof.} Let $a \in Bad_A$ and let $b$ be such that for at least $\gamma {|A| \choose 2} > \gamma n^2/10$ pairs $\{a_1, a_2\} \in {A \choose 2}$, $\{a_1,a_2, a, b\} \notin E(H)$. Then
$$|L(a,b) \setminus A \times B| < {|A| -1 \choose 2} + {|B| -1 \choose 2} - \gamma n^2/10 < \left(\frac{1}{4} - \gamma/20\right) n^2$$
and so in view of (\ref{degree-condition}), for sufficiently large $n$, $|L(a,b) \cap A \times B| > \gamma n^2/30$.
If $|Bad_A| > \gamma n/2$, then $\left|E(H) \cap {A \choose 2} \times {B \choose 2}\right| > \gamma^3 n^3|B|/240 > \gamma^3 n^4/500$ contradicting the definition of $\gamma$.

Observe that every vertex $v\in A \cup B$ is either $(20\gamma)$-acceptable  for $A$ or $(20\gamma)$-acceptable for $B$. Indeed, suppose that $v$ is neither. Then
 $\left|L(v) \cap \left({A \choose 2} \times B \cup {B \choose 2} \times A\right)\right| \leq  40 \gamma n^3$
and so
 $$deg_H(v) \leq {|A| \choose 3} + {|B| \choose 3} +40 \gamma n^3 < \frac{n-1}{3} \delta_2(H)$$
 which is not possible. Note that if $v$ is not $(20\gamma)$-acceptable for $A$ then $v \in Bad_A$. Distribute vertices from $Bad_A \cup Bad_B$ so that every vertex in $X\in \{A,B\}$ is $(18\gamma)$-acceptable for $X$. 
 
 Suppose that there is an edge $f \in \left({A \choose 2} \times {B \choose 2}\right) \cup {A \choose 4} \cup {B \choose 4}$.
  Find greedily matching $M'$ of size at most $\gamma n$ that contains all vertices from $(Bad_A \cup Bad_B) \setminus f$. Let $A'= A \setminus V(M'), B'= B \setminus V(M')$. Since at most $\gamma n$ vertices were moved when distributing $Bad_A \cup Bad_B$ and $|M'| \leq \gamma n$ , $(1/2 - 6\gamma )n \leq |A'|, |B'| \leq (1/2 + 2 \gamma)n$. 
 
Now find matching $M''$ using the following procedure.
Assume that  $|A'| \geq |B'| +2$.  Take $a\in A' \setminus f$, $b \in B' \setminus f$,   $a_1, a_2 \in A'\setminus f$ so that $\{a,b,a_1, a_2\} \in E(H)$ and add $\{a,b,a_1,a_2\}$  to  $M''$. Update sets $A':= A' \setminus \{a,a_1, a_2\}, B':= B' \setminus \{b\}.$  As a result, after at most $4\gamma n$ steps we have $0 \leq |A'|-|B'| \leq 1$.  Since $|M' \cup M''|$ is divisible by four, $|A'|=|B'|$ and  $|A'| \bmod 4 \in \{0, 2\}$.

If $|A'| \bmod 4 = 0$ and  $f \in {A \choose 2} \times {B \choose 2}$, then take two edges from $A' \times {B' \choose 3}$ and two edges from $B' \times {A' \choose 3}$ that contain vertices from $f$ and add them to $M''$. This is possible as $a\in f \cap A$ is $(18\gamma)$-acceptable for $A$  and $|A'| \geq |A| - 16\gamma n$. Consequently $a$ is $\gamma$-acceptable for $A'$.

If $|A'| \bmod 4 = 0$  and $f \in  {A \choose 4} \cup {B \choose 4}$, then take four edges in $A' \times {B' \choose 3}$  and four in $B' \times {A' \choose 3}$  that contain vertices from $f$.

If $|A'| \bmod 4 = 2$, then add $f$ to $M''$. If $f \in {A \choose 4}$, then in addition, add two edges from  $A' \times {B' \choose 3}$ to $M''$. Apply Lemma \ref{match-lem} to the rest of the 4-graph. 

Finally suppose that no such $f$ exists and $|A|\leq |B|$. Then $|B|- |A|$ is even and $H$ is a sub-hypergraph of a 4-graph from  $\mathcal{H}_2$.

\section{Absorbing Lemma}\label{absorbing-section}
In this section we will  show that one can find an absorbing structure in $H$ provided $H$ is not $\beta$-extremal ($\beta$-non-extremal). Let $\beta_0$  be such that Lemma \ref{extremal-case} holds for sufficiently large $n$. For the rest of this section we will assume that $H$ is a $\beta_0$-non-extremal 4-graph on $4n \geq n_0$ vertices that satisfies $\delta_2(G) \geq  \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil +1 = (1 -o(1))n^2/4$.
\begin{lemma}[Absorbing Lemma]\label{absorbing-lemma}
For every $\gamma>0$ and $\beta_0>0$, there is $\alpha>0$ and $n_0$ such that  a $\beta_0$-non-extremal 4-graph $H$ on $4n> n_0$ vertices that satisfies $\delta_2(G) \geq  \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil +1$ contains a matching $M$ such that $|M| \leq \gamma n$ with the following property. For every set $W$ with  $|W| =4l \leq \alpha n$  for some integer $l$, there is a matching $M'$ in $H$ with $V(M') = V(M) \cup W$.
\end{lemma}
\begin{defn}
An 8-tuple $(w_1, \dots, w_8)$ {\it absorbs} $\{v_1, \dots, v_4\}$ if
$\{w_1, \dots, w_4\} \in E(H)$, 

 $\{w_5, \dots, w_8\}\in E(H)$, and $H[\{w_1, \dots, w_8\} \cup \{v_1, \dots, v_4\}]$ contains a matching of size three.
\end{defn}
 First, we show that for every set $U$ of four vertices there are $\Omega(n^8)$ 8-tuples that absorb $U$.
Then Lemma \ref{absorbing-lemma} can be established using a simple probabilistic argument (similar to the one in \cite{Schacht}).
\begin{lemma}\label{absorbing-set}
For every $\beta_0>0$ there is $\alpha>0$ and $n_0$ such that if $H$ is a $\beta_0$-non-extremal 4-graph on $4n \geq n_0$ vertices that satisfies $\delta_2(G) \geq  \frac{n^2-5n}{4} -\lceil \frac{\sqrt{n-3} -3}{2} \rceil +1$, then for every $U \subseteq V(H)$ of size four there are at least $\alpha n^8$ 8-tuples that absorb $U$.
\end{lemma}
To prove Lemma \ref{absorbing-set} we will use the stability theorem from \cite{simon}.

\begin{lemma}[Stability Theorem]\label{stability}
For every $\alpha>0$ there is $\eta>0$ such that if $G=(V,E)$ is a triangle-free graph with $|E| \geq (1/4 - \eta)|V|^2$, then
$|G \oplus K_{\lfloor{|V|/2}\rfloor, \lceil |V|/2 \rceil}| \leq \alpha |V|^2$.
\end{lemma}
In addition, we will use the regularity lemma of Szem\'{e}redi \cite{szem}. For a bipartite graph $G=(U,W)$ we define the density of $(U,W)$ as $d(U,W)= \frac{e(U,W)}{|U||W|}$ where $e(U,W)$ is the number of edges in $G$. 

The pair $(U,W)$ is called {\it $\epsilon$-regular} if for every $U' \subseteq U$ such that $|U'|\geq \epsilon |U|$ and every $W'\subseteq W$ such that $|W'| \geq \epsilon |W|$, $|d(U',W') - d(U,W)| \leq \epsilon$. 

For a graph $G=(V,E)$ a partition $V_0 \cup V_1 \cup \cdots \cup V_t$ of $V$ is called {\it $\epsilon$-regular} if $|V_0| \leq \epsilon |V|$, $|V_i|=|V_j|$ for $i,j\geq 1$, and all but at most $\epsilon t^2$  pairs $(V_i, V_j)$ are $\epsilon$-regular. 

The celebrated lemma of Szem\'{e}redi \cite{szem} states that every graph admits an $\epsilon$-regular partition into a bounded number of classes.
\begin{lemma}[Regularity Lemma of Szem\'{e}redi]
\label{reglemma}
For every $0<\epsilon<1$ and every $t$ there exist integers $n_0$ and $T$ such that every graph on at least $n_0$ vertices admits an $\epsilon$-regular partition with the number of partition classes $l$ satisfying $t \leq l \leq T$.
\end{lemma}
The regularity lemma is often applied to obtain the so-called reduced graph. Specifically, given $\epsilon>0$ and $\delta>0$ let $V_0, \dots, V_l$ be an $\epsilon$-regular partition of $G$. The reduced graph of $G$, $R(G)$, is the graph with $V(R(G))= \{1, \dots, l\}$ and with $\{i,j\}$ in $E(R(G))$ if and only if $(V_i, V_j)$ is $\epsilon$-regular  and $d(V_i,V_j)\geq\delta$. 
Straightforward computations show that  when $\epsilon \ll \delta$, then  $|E(R(G))| \geq (1- 2\delta) \frac{|E(G)| l^2}{n^2}$. In addition note that if $V_0, \dots, V_l$ is an $\epsilon$-regular partition of $G$, then $V_0, \dots, V_l$ is an $\epsilon$-regular partition of the complement of $G$.\\

Although the proof of Lemma \ref{absorbing-set} requires some computations the underlying idea is extremely simple. Fix a set $U=\{u_1, u_2, u_3, u_4\}$ such that $|U|=4$. The set $U$ can be easily absorbed if it is possible to find augmenting paths from $\{u_1, u_2\}$ to $\{u_3, u_4\}$ with an odd number of edges in which two consecutive edges intersect in two vertices. It turns out that paths exist unless sets $L(u_1, u_2)$ and $L(u_3, u_4)$ are either almost disjoint or almost identical. This leads to an auxiliary 2-coloring of the edges of a complete graph on $n$ vertices. We show that for every hyperedge $h$ in $H$ no matter how we partition $h$ into two pairs $e_1, e_2$ the colors of
$e_1, e_2$ must have a specific pattern (in one case both have the same color, in the other they have distinct colors). Finally we show that this is possible only if one of the colors induces a graph which is approximately bipartite. \\

\noindent{\bf Proof of Lemma \ref{absorbing-set}.}
The constant $\alpha$ depends on $\beta_0$ and is obtained by applying Lemma \ref{stability} and Lemma \ref{reglemma} with appropriate parameters (in addition we assume that $\alpha$ is sufficiently small).  Specifically, the following constants will determine $\alpha$.  Let $\gamma>0$ be the constant from Lemma \ref{stability} with the property that if $R=(W, F)$ is a triangle-free graph with $|F| \geq (1/4 - \gamma)|W|^2$, then $|R \oplus K_{\lfloor{|W|/2}\rfloor, \lceil |W|/2 \rceil}| \leq \beta_0 |W|^2/4$. Let $0< \delta \leq \gamma/10$ and let $\epsilon \ll \delta$. Let $T=T(\epsilon)$ be the constant from Lemma \ref{reglemma}. Then the constant $\alpha=\Omega(\delta^8/T^{16})$ and we have
$$0< \alpha \ll \epsilon \ll \delta \ll \gamma \ll \beta_0.$$
 
Assume that $H$ is a $\beta_0$-non-extremal 4-graph with $\delta_2(H) \geq (1 - o(1))n^2/4 \geq (1- \alpha) n^2/4$.
Let $U=\{v_1, v_2, v_3, v_4\} \subset V(H)$, $e_1=\{v_1, v_2\}, e_2=\{v_3, v_4\}$, and let
$L_1 = L(e_1), L_2=L(e_2)$.
For $e\in L_1$ such that $e \cap U = \emptyset$, if $e' \in L(e) \cap L_2$ and $e' \cap U = \emptyset$, then  $e_1 \cup e, e \cup e', e' \cup e_2$ are in $E(H)$ and $U$ can be absorbed by $e\cup e'$. Therefore, 
if more than $\sqrt{\alpha} n^2$, $e\in L(e_1)$ are such that $|L(e) \cap L(e_2)| > \sqrt{\alpha} n^2$, then the number of 8-tuples that absorb $U$ is more than $\alpha n^8/3$.
 Consequently, we can assume that all but at most $\sqrt{\alpha} n^2$ pairs $e\in L(e_1)$ are such that
 \begin{equation}\label{eq1-abs}
|L(e) \cap L(e_2)| \leq \sqrt{\alpha} n^2
\end{equation}
and the same is true for $L(e_2)$. \\
{\it Case 1:} Assume that $|L(e_1) \cap L(e_2)| \geq \sqrt{\alpha} n^2$. \\
If $|L(e_1) \cup L(e_2)| \geq (1/4 + \sqrt{\alpha})n^2$, then  for any $e\in L(e_1) \cap L(e_2)$, $|L(e) \cap (L(e_1) \cup L(e_2))| \geq \sqrt{\alpha} n^2/2$ and we have $\alpha n^8/6$ absorbing 8-tuples. Thus assume otherwise.

Then $|L(e_1) \cap L(e_2)| \geq (1/4 - 2\sqrt{\alpha}) n^2$ and all but at most $\sqrt{\alpha}n^2$ pairs 
$e\in  L(e_1) \cap L(e_2)$ are such that  $|L(e) \cap (L(e_1) \cup L(e_2))| < \sqrt{\alpha} n^2$.
 Consider the following coloring $c: {V(H) \choose 2} \rightarrow \{1,2\}$. For  $e \in {V(H) \choose 2}$, $c(e)= 1$ if $e \in L(e_1) \cap L(e_2)$ and $c(e)=2$ otherwise. Let $G_i= (V(H), c^{-1}(i))$ and note that for $i \in \{1, 2\}$,
 \begin{equation}\label{eq2-abs}
 (1/4 - 2\sqrt{\alpha})n^2\leq  |E(G_i)| \leq (1/4 + 2\sqrt{\alpha})n^2.
\end{equation}
\begin{claim}\label{count-cyc}
Let $S$ be a subset of $\{ \{u_1, u_2, u_3, u_4\} | \{u_1,u_2\} \in E(G_1), \{u_3,u_4\} \in E(G_2)\}$. If $|S| \geq 4\alpha^{1/4} n^4$, then $|S\cap E(H)| \geq 9\sqrt{\alpha} n^4$.
\end{claim}
{\bf Proof.}
Let $S_1 \subseteq E(G_1)$ be the set of pairs $\{u, u'\}$ such that $\{u, u', v, v'\} \in S$ for at least $4{\alpha}^{1/4} n^2$ pairs $\{v,v'\}$ in $E(G_2)$. If $|S_1| < 4 {\alpha}^{1/4} n^2$, then $|S|< 2 {\alpha}^{1/4} n^4 +2{\alpha}^{1/4} n^4 = 4 {\alpha}^{1/4} n^4$ and so $|S_1| \geq 4{\alpha}^{1/4} n^2$.  Consequently, by (\ref{eq1-abs}), for at least $ (4{\alpha}^{1/4} -\sqrt{\alpha})n^2\geq 3\alpha^{1/4}n^2$ pairs $e\in S_1$, we have $|L(e) \cap E(G_1)| < \sqrt{\alpha} n^2$. For each such $e\in E(G_1)$, $|L(e) \cap E(G_2)| \geq (1/4 - 2 \sqrt{\alpha})n^2 $ and, since $|E(G_2)| \leq (1/4 + 2\sqrt{\alpha}) n^2$, at least $3{\alpha}^{1/4}n^2$ pairs $e' \in E(G_2)$ are such that $e \cup e' \in S$ and $e' \in L(e)$. Thus $|S \cap E(H)| \geq 9 \sqrt{\alpha}n^4$. $\Box$

\begin{claim}\label{coloredmatching}
If there are at least $9\sqrt{\alpha} n^4$ edges $f\in E(H)$ such that $f=e_1' \cup e_2'$ where $c(e_1')=c(e_2')$, then the number of 8-tuples that absorb $U$ is at least $\alpha n^8$.
\end{claim}
{\bf Proof.}  First note that if there are at least $\sqrt{\alpha} n^4$ edges $f\in E(H)$ such that $f= e_1'\cup e_2'$ where $e_1' , e_2' \in L(e_1) \cap L(e_2)$, then we have $\sqrt{\alpha} n^8/3$ absorbing $8$-tuples. Consequently, the number of edges $f= e_1'\cup e_2'$ such that $c(e_1')=c(e_2')=1$ is less than $\sqrt{\alpha} n^4$.
%Indeed $e_1 \cup e_1'$, $f$, and $e_2'\cup e_2$ are all edges in $H$ and for given $f$ there are at least $|E(H)| - 4$ edges $f'$ with $f' \cap f = \emptyset$.

Suppose that for at least $8\sqrt{\alpha} n^4$ edges $f\in E(H)$ we have $f= e_1'\cup e_2'$ where  $e_1', e_2' \in E(G_2)$.
Call a  pair $e\in E(G_2)$ {\it useful}  if $|L(e) \cap E(G_1)| \geq 10 {\alpha}^{1/4} n^2$ and let $m$ be the number of pairs that are not useful. We will count the number of hyperedges $h=e_1' \cup e_2'$ such that $e_1' \in E(G_1)$, $e_2' \in E(G_2)$. On one hand, in view of   (\ref{eq1-abs}) and (\ref{eq2-abs}), this number is at least
$$|E(G_1)| (\delta_2(H) - \sqrt{\alpha}n^2) \geq \left(\frac{1}{4} -2 \sqrt{\alpha}\right)^2n^4.$$
On the other hand, the number is less than
$$10{\alpha}^{1/4}n^2 m + (|E(G_2)| -m)|E(G_1)| \leq \left(\frac{1}{4} + 2\sqrt{\alpha}\right)^2n^4 - \left(\frac{1}{4}-12{\alpha}^{1/4}\right) m n^2.$$
Therefore,
$$\left(\frac{1}{4}-12{\alpha}^{1/4}\right) m < 2 \sqrt{\alpha} n^2$$
and so there are at most $9\sqrt{\alpha}n^2$  pairs in $E(G_2)$ that are not useful. Therefore the number of edges $f=e_2' \cup e_2''$ in $E(H)$ such that $e_2', e_2''\in G_2$ and at least one of $e_2'$, $e_2''$ is not useful, is at most $9 \sqrt{\alpha} n^2 |E(G_2)| <  7 \sqrt{\alpha} n^4$.
As a result, there are at least $9{\alpha}^{1/4}\cdot 9{\alpha}^{1/4} n^4 \cdot \sqrt{\alpha} n^4> \alpha n^8$ tuples $(w_1, w_2, \dots, w_8)$ such that $\{w_1, \cdots, w_8\} \cap (e_1 \cup e_2) = \emptyset$, all $w_i$'s are distinct, and $\{w_1, w_2\} \in L(e_1)$, $\{w_7, w_8\} \in L(e_2)$, $\{w_1, w_2, w_3, w_4\}, \{w_3, w_4, w_5, w_6\}, \{w_5, w_6, w_7, w_8\}\in E(H)$. Each such 8-tuple absorbs $U$. $\Box$


 \begin{claim}\label{eps-cyc}
 Let $0 <\xi< 1$ and let $0<\epsilon < 2\delta \leq 1$.
 Let $G$ be a 4-partite graph with partition classes $Y_1, Y_2, Y_3, Y_4$ such that: $|Y_i| \geq \xi n$, $|Y_i|=|Y_j|$,  $(Y_1,Y_2), (Y_3, Y_4)$ are $\epsilon$-regular pairs with density at least $\delta$, and $d(Y_2, Y_3), d(Y_1, Y_4) \geq 1/2$. Then $G$ has  at least $\delta^2 \xi^4 n^4/1024$ $4$-cycles $C$  such that $V(C)\cap Y_i \neq \emptyset$ for every $i=1, \dots, 4$.
 \end{claim}
 {\bf Proof.} Note that at least $|Y_1|/4$ vertices $y \in Y_1$ have $deg(y, Y_4) \geq |Y_4|/4$ and at least $|Y_2|/4$ vertices $y \in Y_2$ have $deg(y, Y_3) \geq |Y_3|/4$. Since $(Y_1, Y_2)$ is $\epsilon$-regular with $d(Y_1,Y_2)\geq \delta$, there are at least
 $(\delta-\epsilon) |Y_1| |Y_2|/16$ edges $\{y_1, y_2\} \in G[Y_1, Y_2]$ such that $deg(y_1, Y_4) \geq |Y_4|/4$ and $deg(y_2, Y_3) \geq |Y_3|/4$. Since $(Y_3, Y_4)$ is $\epsilon$-regular with $d(Y_3,Y_4)\geq \delta$, each $\{y_1, y_2\}$ is in $(\delta-\epsilon) |Y_3| |Y_4|/16$ cycles $C$ that intersect every $Y_i$. Consequently, there are at least $(\delta-\epsilon)^2 \xi^4 n^4/256$ cycles $\{y_1, \dots, y_4\}$ in $G$ with $y_i \in Y_i$. $\Box$

 We will now analyze the structure of $G_1$ and $G_2$.
 Let $\gamma$ be such that if $R=(W, F)$ is a triangle-free graph with $|F| \geq (1/4 - \gamma)|W|^2$, then
 $|R \oplus K_{\lfloor{|W|/2}\rfloor, \lceil |W|/2 \rceil}| \leq \beta_0 |W|^2/4$. Let $\epsilon \ll \delta \ll \gamma$ be such that there is an $\epsilon$-regular partition of $G$ that satisfies: 
 $|E(R(G_i))| \geq (1/4 - \gamma)|V(R(G_i))|^2$ for $i=1,2$, and  $|V_0| \leq \beta_0 n/5$.
 
 Recall that $V(R(G_1))=V(R(G_2))$ and assume that the reduced graph $R(G_1)$ has a triangle $T_1 = (X_{11}, X_{21}, X_{31})$.  If every triangle in $R(G_2)$ contains one of $X_{11}, X_{21}, X_{31}$, then we can make $R(G_2)$ triangle-free by moving these three sets to $V_0$. Therefore, we may assume that $|V_0| \leq \beta_0 n/4$ and   $T_1 = (X_{11}, X_{21}, X_{31}), T_2 = (X_{12}, X_{22}, X_{32})$ are vertex-disjoint triangles in $R(G_1)$ and $R(G_2)$.These two independent triangles will let us find cycles of length four that have exactly three edges monochromatic.  Some of these cycles will span edges of $H$ (Claim \ref{count-cyc}) and at the same time will satisfy the property of Claim \ref{coloredmatching}. 

 We have   $|X_{1i}|= |X_{2i}| =|X_{3i}| = \xi n \geq n/(2T)$, where $T=T(\gamma)$ follows from Lemma \ref{reglemma}. Without loss of generality, assume  $d_1(X_{11}, X_{12}), d_1(X_{21}, X_{22}) \geq 1/2$. Then, by Claim \ref{eps-cyc}, there are at least $\delta^2 \xi^4 n^4/1024$ cycles $\{x_1, x_2, x_3, x_4\}$ with $c(\{x_1, x_2\})= c(\{x_2, x_3\})= c(\{x_1, x_4\})=1$ and $c(\{x_3, x_4\})=2$. If
 $\alpha^{1/4} \leq \delta^2 \xi^4/4096$, then from Claim \ref{count-cyc} at least $9 \sqrt{\alpha} n^4$ of such cycles are edges in $H$. Consequently, by Claim \ref{coloredmatching}, there are at least $\alpha n^8$ absorbing 8-tuples.
If on the other hand, $R(G_1)$ is triangle-free, then  by Lemma \ref{stability}, $|R(G_1) \oplus E(K_{l/2, l/2})| \leq \beta_0 l^2/4$ and $|G_1 \oplus K_{n/2, n/2}| \leq \beta_0 n^2/2$.

 Let $A, B$ be partition classes of $G_1$ such that $|G_1[A, B] \oplus E(K_{n/2, n/2})| \leq \beta_0 n^2/2$. Then, in view of Claim \ref{coloredmatching} there are at least $\beta_0^4 n^8$ absorbing 8-tuples or $| E(H) \cap \left({A\choose 4} \cup {B \choose 4} \cup {A \choose 2} \times {B \choose 2}\right)| \leq \beta_0 n^4$  and $H$ is $\beta_0$-extremal of Type 2.\\
{\it Case 2:} Assume that $|L(e_1) \cap L(e_2)| < \sqrt{\alpha} n^2$. \\
Recall that for every $e \in {V(H) \choose 2}$, $|L(e)|\geq (1/4 - \alpha)n^2$ and so
$$|L(e_i)| \leq \left(\frac{1}{4} + 2\sqrt{\alpha} \right) {n^2}.$$ If there are at least $3\sqrt{\alpha} n^2$ pairs $e\in L(e_i)$ such that $e \cup e' \in E(H)$ for at least $\sqrt{\alpha} n^2$ pairs $e'\in L(e_{3-i})$, then there are at least $\alpha n^8$ absorbing 8-tuples. Otherwise, all but at most $3\sqrt{\alpha} n^2$ pairs $e \in L(e_i)$ have
$|L(e) \cap L(e_{3-i})| < \sqrt{\alpha} n^2$. Consequently, for all but at most $3\sqrt{\alpha} n^2$ pairs $e \in L(e_i)$,
\begin{equation}\label{eq3-abs}
|L(e) \cap L(e_i)| \geq \left(\frac{1}{4} - 2\sqrt{\alpha} \right) {n^2}.
\end{equation}
 Consider the following coloring $c: {V(H) \choose 2} \rightarrow \{1,2\}$. For  $e \in {V(H) \choose 2}$, $c(e)= 1$ if $e \in L(e_1)$ and $c(e)=2$ otherwise. Let $G_i=(V, c^{-1}(i))$.
 \begin{claim}\label{count-cyc-2}
Let $i \in [2]$, and let $S\subseteq \{ \{u_1, u_2, u_3, u_4\} | \{u_1,u_2\} \in E(G_i), \{u_3,u_4\} \in E(G_i)\}$. If $|S| \geq 11\alpha^{1/4} n^4$, then $|S\cap E(H)| \geq 3\sqrt{\alpha} n^4/12$.
\end{claim}
{\bf Proof.}  Let  $q$ be the number of pairs $e\in E(G_i)$ such that $e\cup e' \in S$ for at least ${\alpha}^{1/4}n^2$ pairs $e'\in E(G_i)$. If $q < 20{\alpha}^{1/4} n^2$, then
$|S| < {\alpha}^{1/4} n^4/2 + q \cdot n^2/2 <  11 {\alpha}^{1/4} n^2$
 and so $q\geq 20{\alpha}^{1/4}n^2$.  Every pair $e\in E(G_1)$ is in $L(e_1)$ and all but at most $2\sqrt{\alpha}n^2$ pairs $e\in E(G_2)$ are in $L(e_2)$. Therefore, for at least $q- 5\sqrt{\alpha}n^2>19\alpha^{1/4}n^2$ pairs in $E(G_i)\cap L(e_i)$, (\ref{eq3-abs}) holds, and for each such $e$,
$$|L(e) \cap L(e_i)| \geq |L(e_i)| -  4\sqrt{\alpha} n^2.$$
Fix $e$  with the above property. Since all but at most $2\sqrt{\alpha}n^2$ pairs $e'\in E(G_i)$ are not $L(e_i)$, at least $(\alpha^{1/4}-2\sqrt{\alpha})n^2$ pairs $e'$ are such that $e\cup e' \in S$ and $e' \in L(e_i)$. As a result, at least $(\alpha^{1/4}-6\sqrt{\alpha})n^2> 18\alpha^{1/4}n^2/19$ of such pairs $e'$ are in $L(e)$. Therefore,  for at least $19{\alpha}^{1/4}n^2$ pairs $e\in E(G_i)$, there are at least $18{\alpha}^{1/4}n^2/19$ pairs $e' \in L(e)$ such that $e \cup e' \in S$.
Thus $|S \cap E(H)|\geq  3\sqrt{\alpha} n^4$. $\Box$

 \begin{claim}\label{abs-lem-color}
 If there are at least $3\sqrt{\alpha}n^4$  hyperedges $f \in E(H)$ such that $f=e_1' \cup e_2'$ where $c(e_1') \neq c(e_2')$, then there are at least $\alpha n^8$ absorbing 8-tuples.
 \end{claim}
 {\bf Proof.} Note that there are at least $3\sqrt{\alpha}n^2$ pairs $e_1'$ with $c(e_1')=1$ and such that
 $|L(e_1') \cap E(G_2)| \geq 3\sqrt{\alpha} n^2$. Indeed, otherwise, the number of edges $f=e_1' \cup e_2'$  such that $c(e_1') \neq c(e_2')$ is less than
 $$3\sqrt{\alpha} n^4/2 + 3 \sqrt{\alpha}n^2 \cdot n^2/2  = 3\sqrt{\alpha}n^4.$$
 For each such $e_1'$ there are at least $\sqrt{\alpha}n^2$ pairs $e_2' \in L(e_1') \cap L(e_2)$.
 Thus the number of absorbing 8-tuples is at least $3\sqrt{\alpha}n^2 \cdot \sqrt{\alpha} n^2 \cdot n^2/3 = \alpha n^8$. $\Box$

 Now we proceed in the same fashion as in Case 1.
 Let $\gamma$ be such that if $R=(W, F)$ is a triangle-free graph with $|F| \geq (1/4 - \gamma)|W|^2$, then
 $|R \oplus K_{\lfloor{|W|/2}\rfloor, \lceil |W|/2 \rceil}| \leq \beta_0 |W|^2/4$. Let $\epsilon \ll \delta \ll \gamma$ and  assume that $T_1 = (X_{11}, X_{21}, X_{31}), T_2 = (X_{12}, X_{22}, X_{32})$ are vertex-disjoint triangles in the reduced graphs $R(G_1), R(G_2)$. Then
  $|X_{1i}|= |X_{2i}| =|X_{3i}| = \xi n \geq n/(2T)$, where $T=T(\gamma)$ follows from Lemma \ref{reglemma}.
 Without loss of generality,  we have $d_1(X_{11}, X_{12}), d_1(X_{21}, X_{22}) \geq 1/2$. Thus by Claim \ref{eps-cyc} there are at least $\delta^2 \xi^4 n^4/1024$ cycles
 $\{x_1, x_2, x_3, x_4\}$ with $c(\{x_1, x_2\})= c(\{x_2, x_3\})= c(\{x_1, x_4\})=1$ and $c(\{x_3, x_4\})=2$. As long as $11\alpha^{1/4} \leq \delta^2 \xi^4/1024$, by  Claim \ref{count-cyc-2}, at least $3\sqrt{\alpha}n^4$ of such $C_4$'s span edges of $H$. Then, by Claim \ref{abs-lem-color}, there are at least $\alpha n^8$ absorbing 8-tuples. 
 
 If $l:=|V(R(G_i))|$  and one of $R(G_i)$'s is  such that $|R(G_i) \oplus E(K_{l/2, l/2})| \leq \beta_0 l^2/4$, then $|G_i \oplus K_{n/2, n/2}| \leq \beta_0 n^2/2$. In view of Claim \ref{abs-lem-color} we either have $\beta_0^4n^8$ absorbing 8-tuples or
  $H$ is $\beta_0$-extremal of Type 1.\\
{\bf Proof of Lemma \ref{absorbing-lemma}.}
Proof is analogous to the proofs of corresponding statements in  \cite{RRS} and \cite{Schacht}.
For a set $U \subset V(H)$ of size four let $\mathcal{T}$$(U)$ be the set of all $S\in {V(H) \choose 8}$ such that
at least one of the 8-tuples  obtained from $S$ absorbs $U$. Then, by Lemma \ref{absorbing-set}, there is $\alpha>0$ such that  $|\mathcal{T}(U)| \geq \alpha {n \choose 8}.$ Take a family $\mathcal{F}$ of sets of size eight selecting each independently  from ${V(H) \choose 8}$ with probability $p= \alpha n/(300 {n \choose 8})$. By Chernoff's bound with probability $1- o(1)$, the following two conditions hold:
$|\mathcal{F}| \leq 2p {n \choose 8} \leq \alpha n/150$ and
for every $U$ of size four, $|\mathcal{T}(U) \cap \mathcal{F}| \geq \frac{\alpha p}{2} { n \choose 8}= \frac{\alpha^2n}{600} .$
The expected number of pairs $\{S_1, S_2\} \subset  \mathcal{F}$ such that  $S_1 \cap S_2 \neq \emptyset$ is at most
$$8 {n \choose 8} {n \choose 7} p^2 <\alpha^2n/1400$$
and so by Markov's inequality, with probability at least $1/2$, the number of intersecting pairs  is at most
$\alpha^2n/700$. Thus with positive probability there is a family $\mathcal{F}$ such that
$|\mathcal{F}| \leq  \alpha n/150$, for every $U$ of size four, $|\mathcal{T}(U) \cap \mathcal{F}| \geq\frac{\alpha^2n}{600} ,$ and the number of intersecting pairs of sets  is at most $\alpha^2n/700$. Let $\mathcal{F}'$ be obtained from $\mathcal{F}$ by deleting intersecting sets and sets that do not absorb any $U \in {V(H) \choose 4}$. Then for every $U$ of size four,
$|\mathcal{T}(U) \cap \mathcal{F}'| \geq\frac{\alpha^2n}{4200}$ and so any set $W$ of size
at most $\frac{\alpha^2n}{1050}$ and such that $4||W|$  can be absorbed by $\mathcal{F}'$.
\section{An almost perfect matching}\label{large-section}
In this section, we prove that  $H$ contains a matching that covers all but a constant number of vertices even when $\delta_2(H)$  is much smaller than the bound in (\ref{degree-condition}).  In what follows we did not try to optimize the constant as any leftover set of size $o(|V(H)|)$ is sufficiently small for our purposes.
%Let $H$ be a $4$-uniform hypergraph on $n$ vertices and let $0< \epsilon <1/320$.


\begin{lemma}\label{large-matching}
There is an $\epsilon>0$ and $n_0$ such that if $H$ is a 4-graph on $n> n_0$ vertices for which  $\delta_2(H) \geq \left(1- \epsilon\right) n^2/4$, then $H$ contains a matching $M$ such that
$$|V(H)\setminus V(M)| < \frac{2}{\epsilon} +1.$$
\end{lemma}
{\bf Proof.}
Since in the proof, in addition to $H$, we consider certain auxiliary graphs, we will refer to edges of $H$ as 4-edges. Set $\alpha := 0.4$, $\epsilon := 0.002$ and
let $M$ be a maximum matching in $H$. Let  $L=: V(H) \setminus V(M)$, $k:= |L|$, and $m:=|M| = \frac{n-k}{4}$. Note that if $k < 2/\epsilon +1$, then we are done and so assume otherwise. It is not difficult to see that $|L| \leq \epsilon n$. Indeed, let $H'$ be obtained from $H$ by adding a set $V'$ of $\epsilon n$ "new" vertices to $V(H)$ and adding all 4-sets from ${V' \cup V(H) \choose 4}$ that contain a vertex from $V'$. Then $|V(H')| = (1+\epsilon)n$ and $\delta_2(H') \geq (1-\epsilon)n^2/4 +\epsilon n(n-2) > (1 + \epsilon/2) |V(H')|^2/4$ and so $H'$ contains a perfect matching $M'$ by (\ref{pihurko}). Deleting edges in $M'$ that contain a vertex from $V'$ gives a matching $M$ in $H$ with $|L| \leq 3|V'|$. Consequently we may assume that $k \leq 3\epsilon n$.
%For four, not necessarily distinct, subsets $U_1, U_2, U_3, U_4 \subseteq V$, we use $h(U_1, U_2, U_3, U_4)$ to denote the number of $4$-edges $f$ in $H$ such that $e=\{u_1, u_2, u_3, u_4\}$ and $u_i \in U_i$.
Since $M$ is maximum, we have $E(H) \cap {L \choose 4} = \emptyset$. In addition
\begin{equation}\label{h1}
\left|E(H) \cap \left({L \choose 3} \times (V \setminus L)\right)\right|\leq n {k \choose 3} \leq \epsilon n^2 {k \choose 2}.
\end{equation}
Also, the number of 4-edges $e \in E(H)$ such that $|e \cap L | =2$ and
such that for some $f \in M$, $|e\cap f| =2$ is at most
\begin{equation}\label{h2}
 {k \choose 2} \frac{n}{4} {4 \choose 2} < \epsilon \frac{n^2}{4}{k \choose 2}.
\end{equation}
Let $h$ be the number of 4-edges $e\in E(H)$ such that  $|e \cap L|= 2$ and such that  there exist two distinct 4-edges
 $f_1, f_2 \in M$ with $|e\cap f_i|=1$ for $i=1,2$. By (\ref{h1}) and (\ref{h2}),
\begin{equation}\label{h}
h \geq  (1- \epsilon) \frac{n^2}{4} {k \choose 2} - \frac{5\epsilon n^2}{4} {k \choose 2} = (1-6\epsilon) \frac{n^2}{4}{k \choose 2}.
\end{equation}
A pair of 4-edges $\{f_1, f_2\} \subset M$ is called {\it switchable} if there exists a matching $\{e_1, e_2, e_3\}$ in the complete bipartite graph $K[V(f_1), V(f_2)]$ such that for $i=1, \dots, 3$,  $|L(e_i) \cap {L \choose 2}| \geq 4k$.
Note that if $\{f_1, f_2\}$ is switchable, then we can find three pairwise disjoint 4-edges  in $H[V(f_1) \cup V(f_2) \cup L]$. Thus, since $M$ is maximum, there are no switchable pairs. In particular for every  $\{f_1, f_2\} \subset M$,
$$\left|E(H) \cap \left(V(f_1)\times V(f_2) \times {L \choose 2}\right)\right| <  8{k \choose 2} + 8 \cdot 4 k$$
as if there are nine edges $e_1, \dots, e_9$ in $K[V(f_1), V(f_2)]$ with $|L(e_i) \cap {L \choose 2}| \geq 4k$ for $i=1, \dots, 9$, then at least three of them are independent.
 A pair of 4-edges $\{f_1, f_2\} \subset M$ is called {\it bounded} if $|E(H) \cap \left( V(f_1) \times V(f_2) \times {L \choose 2}\right)| \leq 7.5 {k \choose 2}$.
If at least $\alpha {m \choose 2}$ pairs in ${M \choose 2}$ are bounded, then
$$h \leq \alpha {m \choose 2} 7.5 {k \choose 2} + (1-\alpha) {m \choose 2} \left(8 {k \choose 2} + 32 k\right) < \left(1 - \frac{\alpha}{16} + \frac{8}{k-1}\right) \frac{n^2}{4} {k \choose 2}.$$
This contradicts $(\ref{h})$ if $k \geq \frac{256}{\alpha} +1$ and $\alpha \geq 192\epsilon$. Consequently, less than $\alpha {m \choose 2}$ pairs in ${M \choose 2}$ are bounded.

Suppose that a pair $\{f_1, f_2\} \subset M$ is neither bounded nor switchable.  We consider the bipartite graph $G[f_1, f_2]$ on $V(f_1) \cup V(f_2)$ by adding $e$ from $E(K[V(f_1), V(f_2)])$ to $E(G[f_1, f_2])$  if  $|L(e) \cap {L \choose 2}| \geq k^2/40$.
As $\{f_1, f_2\} $ is  not switchable, $G[f_1,f_2]$ has a maximum matching of size two and  at most eight edges. Since  $\{f_1, f_2\} $ is unbounded,  $G[f_1,f_2]$ has exactly eight edges. Indeed, if  the number of edges is at most seven, then
$|E(H) \cap \left(V(f_1) \times V(f_2) \times {L \choose 2}\right)| \leq 7 {k \choose 2} + 9  k^2/40 < 7.5 {k \choose 2}$. Therefore $G[f_1, f_2]$ is the graph $G$ in Figure 2.%\ref{graphG-fig}.
\begin{figure}
\label{graphG-fig}
\begin{center}
\epsffile{graphG.eps}
\caption{Graph $G$. We put $e \rightarrow f$.}
\end{center}
\end{figure}
Since at least $(1- \alpha){m \choose 2} > m^2/4$ pairs in ${M \choose 2}$ are neither switchable nor bounded we can find three 4-edges  $f_1,f_2,f_3 \in M$ such that all three graphs $G[f_i,f_j]$ are isomorphic to $G$ from Figure 2.%\ref{graphG-fig}.
 Using the convention from Figure 2 we can assume that $f_1\rightarrow f_2$ and $f_2 \rightarrow f_3$ and it is easy to see that there is a matching of size four in $G[f_1,f_2] \cup G[f_2, f_3]$ (Figure 3). We can switch $f_1,f_2,f_3$ for four 4-edges that contain vertices from $V(f_1) \cup V(f_2) \cup V(f_3) \cup L$.
\begin{figure}\label{graphGmatching}
\begin{center}
\epsffile{graphGmatching.eps}
\caption{Matching of size four in $G[f_1,f_2] \cup G[f_2, f_3]$.}
\end{center}
\end{figure}
\section{Proof of the main theorem}\label{proof-section}
Now we prove Theorem \ref{main}.\\
{\bf Proof of Theorem \ref{main}.}  Let $\beta_0>0$ be the constant in Lemma \ref{extremal-case}, let $\epsilon_0>0$ be the constant from Lemma \ref{large-matching}, and let $n_0$ be sufficiently large. Let $H$ be a 4-graph on
$n > n_0$ vertices with $n \bmod 4 = 0$.  If $H$ is $\beta_0$-extremal, then by Lemma \ref{extremal-case}, $H$ has a perfect matching.  Otherwise
by Lemma \ref{absorbing-lemma}, there is a matching $M_a$ and a constant $\alpha>0$ such that $|M_a| \leq \epsilon_0 n/20$ and $M_a$ can absorb any set of size at most $\alpha n$. Let $H' = H[V(H) \setminus V(M)]$. Then $\delta_2(H') > (1- \epsilon_0) n^2/4$ and so $H'$ contains a matching that contains all but at most $O(1/\epsilon_0)$ vertices which can be absorbed by $M_a$.
\begin{thebibliography}{00}
\bibitem{alon} N. Alon, P. Frankl, H. Huang, V. R\"{o}dl, A. Ruci\'{n}ski, B. Sudakov, Large matchings in uniform hypergraphs and the conjectures of Erd\H{o}os and Samuels, (manuscript).
\bibitem{Schacht}H. H\`{a}n, Y. Person and M. Schacht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM J. Discrete Math., 23(2) (2009), 732--748.
\bibitem{khanmatching}I. Khan, Perfect Matching in 3-uniform hypergraphs with large vertex degree, (manuscript).
\bibitem{khan}I. Khan, Perfect Matchings in 4-uniform hypergraphs, ({manuscript}).
\bibitem{KOT}D. K\"{u}hn, D. Osthus and A. Treglown, Matchings in 3-uniform hypergraphs, (manuscript).
\bibitem{pikhurko} O. Pikhurko, Perfect matchings and K43-tilings in hypergraphs of large codegree, Graphs Combin., 24(4) (2008), 391--404.
\bibitem{RRSS} V. R\"{o}dl, A. Ruci\'{n}ski, M. Schacht and E. Szemer\'{e}di, A note on perfect matchings in uniform hypergraphs with large minimum collective degree, Commentationes Mathematicae Universitatis Carolinae, 49(4) (2008), 633--636.
\bibitem{RRS} V. R\"{o}dl, A. Ruci\'{n}ski, and E. Szemer\'{e}di, Perfect matchings in large uniform hypergraphs with large minimum collective degree, J. Combin. Theory, Ser. A, 116 (2009), 613--636.
\bibitem{simon}M. Simonovits, A method for solving extremal problems in graph theory, stability problems, {\it Theory of Graphs (Proc. Colloq., Tihany, 1966)}, Academic Press, New York, (1968),  279--319.
\bibitem{szem}E. Szemer\'{e}di, Regular Partitions of Graphs, \emph{%
Colloques Internationaux C.N.R.S., Problemes Combinatories et Theorie des
Graphes}, (1978), 399--402.
\bibitem{Zhao}A. Treglown, Y. Zhao, Minimum degree thresholds for perfect matchings in uniform hypergraphs, submitted.
\end{thebibliography}
  \end{document}
