%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                                                              %
%            On matchings in hypergraphs                       %
%                                                              %
%                         by                                   %
%                                                              %
%             Peter Frankl, Tomasz {\L}uczak                   %
%               and Katarzyna Mieczkowska                      %
%                                                              %
%                                                              %
%          March 19, 2012, rev. May 31, 2012                   %
%                                                              %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P42}{19(2)}{2012}
%\usepackage{latexsym,amsmath}
\usepackage{amsthm, amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
%
%
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%
\newcommand\eps{\varepsilon}
\newcommand\pl{{\textrm{pl}}}
\newcommand\hV{\hat V}
\newcommand\hM{{\hat M}}
\newcommand\bV{\bar V}
\newcommand\bv{\bar v}
\newcommand\bM{{\bar M}}
\newcommand\bG{\bar G}
\newcommand\tG{\tilde G}
\newcommand\bH{\bar H}
\newcommand\Gn{\mathcal{G}_n}
\newcommand\Ge{\mathcal{G}_n(\eps)}
\newcommand\cH{\mathcal{H}}
\newcommand\cA{\mathcal{A}}
\newcommand\cM{\mathcal{M}}
\newcommand\Cl{\textrm{Cl}}
\newcommand\Cov{\textrm{Cov}}
\newcommand{\sh}{\textbf{sh}}
\newcommand{\Sh}{\textbf{Sh}}
%\newcommand{\bad}{bad}
%\newcommand\qedc{\hfill $\Diamond$ \smallskip}
%\renewcommand{\labelenumi}{(\roman{enumi})}
%
\title%[On matchings in hypergraphs]
{\bf On matchings in hypergraphs}
\author{Peter Frankl\\
\small Tokyo, Japan\\
\small{\tt peter.frankl@gmail.com}\\[-14pt]
\phantom{very long line so that it doesn't put something beside}\\
\and 
Tomasz \L{u}czak\thanks{Partially supported by 
the Foundation for Polish Science and NSF grant DMS-1102086.}\\
\small Adam Mickiewicz University\\[-0.8ex]
\small Faculty of Mathematics and CS\\[-0.8ex]
\small Pozna\'n, Poland\\
\small and\\
\small Emory University\\[-0.8ex]
\small Department of Mathematics and CS\\[-0.8ex]
\small Atlanta, USA\\
\small\tt tomasz@amu.edu.pl
\and
Katarzyna Mieczkowska\\
\small Adam Mickiewicz University\\[-0.8ex]
\small Faculty of Mathematics and CS\\[-0.8ex]
\small  Pozna\'n, Poland\\
\small\tt kaska@amu.edu.pl\\
\phantom{spacer}}
%\keywords {extremal graph theory, matching, %hypergraphs} 
%homomorphism
%\subjclass{%
%05C35,  %extremal 
%05C65, %Hypergraphs  
%05C70.} % Factorization, matching, partitioning, covering and packing

\date{\dateline{Mar 30, 2012}{Jun 3, 2012}{Jun 13, 2012}\\
\small Mathematics Subject Classifications:
05C35,  %extremal 
05C65, %Hypergraphs  
05C70.}

\begin{document}

\maketitle


\begin{abstract}
We show that if the largest matching in a  $k$-uniform hypergraph
$G$ on $n$ vertices has precisely $s$ edges, and $n>3k^2s/2\log k$,
then $H$ has at most $\binom n k - \binom {n-s} k $ edges
and this upper bound is achieved only for  hypergraphs in which
the set of edges consists of all $k$-subsets 
which intersect a given set of $s$ vertices. 
\end{abstract}

\maketitle

%\section{Introduction}

A {\em $k$-uniform hypergraph}  $G=(V,E)$ 
is a set of vertices $V\subseteq \mathbb{N}$ 
together with a family $E$ of 
$k$-element subsets of $V$, which are called edges.
In this note by $v(G)=|V|$ and $e(G)=|E|$ we denote the number of vertices 
and edges of $G=(V,E)$, respectively. 
By a {\em matching} we mean any family
of disjoint edges of $G$, and we denote by $\mu(G)$ the size 
of the largest matching contained in $E$. 
Moreover, by $\nu_k(n,s)$ we mean the largest possible 
number of edges in a $k$-uniform hypergraph $G$ with $v(G)=n$ 
and $\mu(G)=s$, and by $\cM_k(n,s)$ we denote the family 
of the extremal hypergraphs for this problems, i.e.
$H\in \cM_k(n,s)$ if $v(H)=n$, $\mu(H)=s$, and $e(H)=\nu_k(n,s)$.   
In 1965 Erd\H{o}s~\cite{E} conjectured that, unless $n=2k$ and $s=1$, 
all graphs from $\cM_k(n,s)$ are either cliques, or belong to 
the family $\Cov_k(n,s)$ of hypergraphs on $n$ vertices in which 
the set of edges consists of all $k$-subsets which intersect
a given subset $S\subseteq V$, with $|S|=s$. This conjecture, 
which is a natural generalization of Erd\H{o}s-Gallai result~\cite{EG} for 
graphs, has been verified only for $k=3$ (see~\cite{Fr} and~\cite{LM}). 
For general $k$ there have been series of results which state that
\begin{equation}\label{eq0}
\cM_k(n,s)=\Cov_k(n,s)\quad \textrm{for} \quad  n\ge g(k)s,
\end{equation}
where $g(k)$ is some function of $k$. The existence of such $g(k)$ 
was shown by Erd\H{o}s~\cite{E}, then 
Bollob\'as, Daykin and Erd\H{o}s~\cite{BDE} proved that~(\ref{eq0}) 
holds whenever $g(k)\ge 2k^3$; Frankl and F\"uredi~\cite{FF} showed 
that (\ref{eq0}) is true for $g(k)\ge 100k^2 $ and  recently,   Huang, Loh, and~Sudakov~\cite{HLS}
verified~(\ref{eq0}) for $g(k)\ge 3 k^2$. The main result of 
 this note  slightly improves these bounds 
 and confirms~(\ref{eq0}) for $g(k)\ge {2k^2}/{\log k}$.

\begin{theorem}\label{thm:main}
If $k\ge 3$ and 
\begin{equation}\label{eq1}
n> \frac{2k^2s}{\log k},
\end{equation} 
then $\cM_k(n,s)=\Cov_k(n,s)$.
\end{theorem}

In the proof we use the technique of shifting (for details see \cite{F}).
Let $G=(V,E)$ be a hypergraph with vertex set $V=\{1,2,\dots, n\}$, and let 
$1\le i<j\le n$. The hypergraph $\sh_{i,j}(G)$ is 
obtained from $G$ by replacing each edge $e\in E$ 
such that $j\in e$, $i\notin e$ and $e_{ij}=e\setminus \{j\}\cup \{i\}\notin E$, 
by $e_{ij}$. Let $\Sh(G)$ denote the hypergraph obtained from $G$ by 
the maximum sequence of shifts, such that for all possible $i,j$ we have $\sh_{ij}(\Sh(G))=\Sh(G)$.
It is well known and not hard to prove that the following holds
(e.g. see \cite{F} or \cite{LM}).


\begin{lemma}\label{l1a}
$G\in \cM_k(n,s)$ if and only if $\Sh(G)\in \cM_k(n,s)$.
\end{lemma}

\begin{lemma}\label{l1b}
Let $G\in \cM_k(n,s)$ and $n\ge 2k+1$. Then 
$G\in \Cov_k(n,s)$ if and only if $\Sh(G)\in \Cov_k(n,s)$.
\end{lemma}

Thus, it is enough to show Theorem~\ref{thm:main} for hypergraphs $G$ for which $\Sh(G)=G$.
Let us start with the following observation.


\begin{lemma}\label{l2a}
If $G$ is a hypergraph on vertex set $[n]$ such that  $\Sh(G)=G$
and $\mu(G)=s$, 
then $$G\subseteq \cA_1\cup \cA_2\cup\dots\cup A_k\,,$$
where 
$$\cA_i=\{A\subseteq [n]: |A|=k,\ |A\cap \{1,2,\dots,i(s+1)-1)\}|\ge i\},$$
 for $i=1,2,\dots, k$.
\end{lemma}

\begin{proof}
Note that  the set $e_0=\{s+1, 2s+2,\dots, ks+k\}$ is not an edge of 
$G$. Indeed, in such a case  each of the edges $\{i,i+s+1,\dots, i+(k-1)(s+1)\}$, 
$i=1,2,\dots, s+1$,  belongs to $G$
due to the fact that $G=\Sh(G)$ and, clearly, they form a matching of size $s+1$.
Now it is enough to observe that all sets which do not dominate $e_0$ must belong to 
$\bigcup_{i=1}^k \cA_i$.
\end{proof}

The following numerical consequence of the above result is crucial for our argument.

\begin{lemma}\label{l3}
Let $G$ be a hypergraph with vertex set $\{1,2,\dots, n\}$ such that $\Sh(G)=G$
and $\mu(G)=s$, where $n\ge k(s+1)-1$. Then all except at most $ \frac{s(s+1)}{2}\binom {n-1}{k-2}$ edges 
of $G$ intersect $\{1,2,\dots,s\}$. 
\end{lemma}
 
 
\begin{proof}
Let $\cA=\bigcup_{i=1}^k \cA_i$. 
Observe first that $|\cA|=s\binom {n}{k-1}$, for $n\ge k(s+1)-1$. Indeed, it 
follows from an easy induction on $k$, and then on $n$. For $k=1$ it is obvious. 
For $k\geq 1$ and $n=k(s+1)-1$ we have clearly $|\cA|=\binom {n}{k}=s\binom {n}{k-1}$. 
Now let $k\geq 2$, $n\geq k(s+1)$ and split all the sets of $\cA$ into those 
which contain $n$ and those which do not.
Then, the inductional hypothesis gives 
$$|\cA|= s\binom {n-1}{k-2}+s\binom {n-1}{k-1}=s\binom {n}{k-1}\,.$$

Observe also that $\binom{n} {k}=\sum_{i=1}^s \binom{n-i}{k-1}+\binom{n-s}{k}$,
which is a direct consequence of the identity 
$\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$.
Thus, using Lemma~\ref{l2a} and the above observation, 
the number of edges of $G$ which do not intersect $\{1,2,\dots, s\}$ 
can be bounded in the following way.
\begin{align*}
|G|-|G\cap \cA_1|%&=(|G|+ |\cA_1\setminus G|)-(|\cA_1\setminus G|+|G\cap \cA_1| )\\
&\leq|\cA|-|\cA_1|= s\binom {n}{k-1}-\bigg[\binom{n}{k}-\binom{n-s}{k}\bigg]\\
&= s\left[\sum_{i=1}^s\binom{n-i}{k-2}+\binom{n-s}{k-1}\right]-
\sum_{i=1}^s\binom{n-i}{k-1}\\
&= s\sum_{i=1}^s\binom{n-i}{k-2} -\sum_{i=1}^s\sum_{j=1}^{s-i} \binom{n-i-j}{k-2}\\
&= s\sum_{i=1}^s\binom{n-i}{k-2} -\sum_{i=2}^s(i-1)\binom{n-i}{k-2}\\
&= \sum_{i=1}^s (s-i+1)\binom{n-i}{k-2}\leq \sum_{i=1}^s i\binom{n-1}{k-2}\\
&= \frac{s(s+1)}{2}\binom {n-1}{k-2}.
\end{align*}
\end{proof}

\begin{proof}[Proof of Theorem~\ref{thm:main}]
Let us assume that (\ref{eq1}) holds for $G\in \cM_k(n,s)$.  
Then, by Lemma~\ref{l1a},  the hypergraph $H=\Sh(G)$
belongs to $\cM_k(n,s)$. We shall show that $H\in \Cov_k(n,s)$ 
which, due to Lemma~\ref{l1b}, would imply that $G\in \Cov_k(n,s)$.
Our argument is based on the following two observations.
Here and below by the degree $\deg(i)$ of a vertex $i$ we mean 
 the number of edges containing $i$, and by $V$ and $E$ we denote
 the sets of vertices and edges of $H$ respectively.
 
\begin{claim}\label{cl1}
If $s\ge 2$, then $\{1,ks+2,ks+3,\ldots,ks+k\}\in E$.
\end{claim} 
 
\begin{proof}  
Let us assume that the assertion does not hold.
We shall show that then $H$ has fewer edges than the graph $H'=(V,E')$ whose edge
set consists of all $k$-subsets intersecting $\{1,2,\dots,s\}$. 
Let $E_i=\{\{i\}\cup e':e'\subset\{ks+2,\ldots,n\}, |e'|=k-1\}$, $i\in[s]$
and observe that the sets $E_i$ are pairwise disjoint and 
$|E_i|=\binom{n-ks-1}{k-1}$ for every $i\in[s]$.
Moreover, since $H=\Sh(H)$ and $\{1,ks+2,ks+3,\ldots,ks+k\}\notin E$, 
$E_1\cap E=\emptyset$, and so $E_i\cap E=\emptyset$ for every $i\in[s]$.
Thus,
\begin{equation}\label{eq3}
\begin{aligned}
|E'\setminus E|&\ge s\binom{n-ks-1}{k-1}\\
&\ge \frac{s (n-1)_{k-1}}{(k-1)!}\Big(1-\frac{ks}{n-k+1}\Big)^{k-1},   
\end{aligned}
\end{equation}
while from Lemma~\ref{l3} we get
\begin{equation}\label{eq4}
\begin{aligned}
|E\setminus E'|&\le \frac{s(s+1)}{2}\binom{n-1}{k-2}= \frac{s (n-1)_{k-1}}{(k-1)!}\frac{(s+1)(k-1)}{2(n-k+1)}\\
& \leq \frac{s (n-1)_{k-1}}{(k-1)!}\frac{ks}{n-k+1}.   
\end{aligned}
\end{equation}
Thus, 
$$e(H')-e(H)\ge \frac{s (n-1)_{k-1}}{(k-1)!}
\bigg(\Big(1-\frac{ks}{n-k+1}\Big)^{k-1}-\frac{ks}{n-k+1}\bigg).$$
Let $x=ks/(n-k+1)$. It is easy to check that for all $k\ge 3$ and $x\in (0, 0.7 \log k/k)$ 
we have 
$$(1-x)^{k-1}> x\,.$$
Thus, $e(H')-e(H)>0$ provided $k^2 s<0.7 \log k(n-k+1) $, which holds whenever
$n\ge 2sk^2/\log k$.  
Thus, since clearly $\mu(H')=s$,  we arrive at  contradiction with the assumption that 
$H\in \cM_k(n,s)$.
\end{proof} 
 
\begin{claim}\label{cl2}
If $s\ge 2$ then $\deg(1)=\binom {n-1}{k-1}$. In particular, the 
hypergraph~$H^-$, obtained from $H$ by deleting the vertex $1$ 
together with all edges it is contained in, belongs to $\cM_k(n-1,s-1)$. 
\end{claim} 

\begin{proof} 
Let us assume that there is a $k$-subset of $V$, which contains $1$ and is not an edge in $H$.
%$e\subset V$ such that $1\in e$ and $e\notin E$. 
Then, in particular, $e=\{1,n-k+2,\ldots,n\}\notin E$.
Let us consider hypergraph $\bar H$ obtained  
from $H$ by adding $e$ to its edge set. Since $H\in \cM_k(n,s)$, there is a 
matching of size $s+1$ in $\bar H$ containing $e$. 
Hence, as $H=\Sh(H)$, there exists a matching $M$ in $H$ such that 
$M\subset\{2,\ldots,ks+1\}$.
Note however that, by Claim~\ref{cl1}, $f=\{1,ks+2,ks+3,\ldots,ks+k\}\in E$.
But then $M'=M\cup \{f\}$ is a matching of size $s+1$ in $H$, contradicting 
the fact that $H\in \cM_k(n,s)$. Hence, we must have $\deg(1)=\binom {n-1}{k-1}$.
Since $n\ge ks$, the second part of the assertion is obvious.
\end{proof}

 
Now Theorem~\ref{thm:main} follows easily from Claim~\ref{cl2} and the observation 
that, since $\frac{s-1}{n-1}\le \frac{s}{n}$,  if (\ref{eq1}) holds then 
it holds also when $n$ is replaced by $n-1$ and $s$ is replaced by $s-1$.
Thus, we can reduce the problem to the case when $s=1$ and use 
Erd\H{o}s-Ko-Rado theorem (note that then $n> 2k^2/\log k>2k+1$). 
\end{proof} 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibliographystyle{plain}

%\bibliography{bibliography}
\begin{thebibliography}{99}
%\small


\bibitem{BDE} {B.~Bollob{\'a}s, E.~Daykin, and P.~Erd\H{o}s},
\newblock{Sets of independent edges of a hypergraph}, 
\newblock{\em Quart. J. Math. Oxford Ser. (2)}, 27:25--32, 1976. 

\bibitem{E} {P.~Erd\H{o}s},
\newblock{A problem on independent $r$-tuples}, 
\newblock{\em Ann. Univ. Sci. Budapest. E\"otv\"os Sect. Math.}, {8}:93--95, 1965. 

\bibitem{EG} {P.~Erd\H{o}s and T.~Gallai},
\newblock{On maximal paths and circuits of graphs}, 
\newblock{\em Acta Math. Acad. Sci. Hungar.} 
{10}:337--356, 1959.

%\bibitem{EKR} {P.~Erd\H{o}s, C.~Ko, and R.~Rado},
%{\em Intersection theorems for systems of finite sets}, {Quart. J. Math. Oxford Set. 2} {\bf 12} (1961), 313--320.

\bibitem{F} {P.~Frankl},
\newblock{The shifting technique in extremal set theory}. 
\newblock In {\em Surveys in Combinatorics},
volume 123 of  {\em Lond. Math. Soc. Lect. Note Ser.}, pages 81--110. Cambridge, 1987.


\bibitem{Fr} {P.~Frankl}, 
\newblock{On the maximum number of edges in a hypergraph with given matching number},
\newblock{\tt arXiv:1205.6847}.

\bibitem{FF} {P.~Frankl and Z.~F\"{u}redi}, \newblock unpublished.


\bibitem{HLS} {H.~Huang, P.~Loh, and B.~Sudakov}, 
\newblock{The size of a hypergraph and its matching 
number}, 
\newblock{\em Combinatorics, Probability\ \&\ Computing}, 21:442-450, 2012.

\bibitem{LM} 
{T.~{\L}uczak, K.~Mieczkowska},
\newblock{On Erd\H{o}s' extremal problem on matchings in hypergraphs}, 
\newblock{\tt arXiv:1202.4196}.

\end{thebibliography}

\end{document}