\documentclass[12pt]{article}
\usepackage{e-jc,amsfonts,amssymb,amsthm,amsbsy,amscd,amsmath,bbm,bm,calc,color,euscript,enumerate,e-jc,graphicx,latexsym,manfnt, marvosym,mathrsfs,marvosym,setspace,tensor,textcomp,tikz,upgreek,verbatim,xcolor}
\specs{P3.28}{23(3)}{2016}

\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}

\theoremstyle{definition}
\newtheorem*{construction}{Construction}
\newtheorem*{conjecture}{Conjecture}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}

\newcommand{\M}[2][]{\ensuremath{{\textnormal{M}}_{#1}(#2)}}

\makeatletter
\def\imod#1{\allowbreak\mkern10mu({\operator@font mod}\,\,#1)}
\def\@textbottom{\vskip\z@\@plus 18pt}
\let\@texttop\relax
\makeatother

\title{\bf A new construction of non-extendable\\ intersecting families of sets}
%Counterexamples to a conjecture of Lov\'{a}sz\\ on uniform maximal intersecting families}
\author{Kaushik Majumder\\
\small R C Bose Centre for Cryptology and Security\\[-0.8ex]
\small Indian Statistical Institute\\[-0.8ex] 
\small $202$ Barrackpore Trunk Road, Kolkata - $700108$, India.\\
\small\tt kaushikbnmajumder@gmail.com}

\date{\dateline{Mar 1, 2016}{Aug 1, 2016}{Aug 19, 2016}\\
\small Mathematics Subject Classifications: 05D05, 05A16.}



\begin{document}
\maketitle
\begin{abstract}
In 1975, Lov\'{a}sz conjectured that any maximal intersecting family of $k$-sets has at most $\lfloor(e-1)k!\rfloor$ blocks, where $e$ is the base of the natural logarithm. This conjecture was disproved in 1996 by Frankl and his co-authors. In this short note, we reprove the result of Frankl et al.~using a vastly simplified construction of maximal intersecting families with many blocks. This construction yields a maximal intersecting family $\mathbb{G}_{k}$ of $k$-sets whose number of blocks is asymptotic to $e^{2}(\frac{k}{2})^{k-1}$ as~$k\rightarrow\infty$.

\bigskip\noindent \textbf{Keywords:} Intersecting family of $k$-sets, Maximal $k$-cliques.
\end{abstract}


\section{Introduction}
For positive integers $k$, by a $k$-set we mean a set of size $k$. The members of a family $\mathcal{F}$ of $k$-sets are usually called the  blocks of $\mathcal{F}$. Such a family is said to be an intersecting family if any two of its blocks have a non-empty intersection. A family $\mathcal{F}$ of $k$-sets is called a \emph{maximal intersecting family of $k$-sets} if (a) $\mathcal{F}$ is an intersecting family of $k$-sets, and (b) there is no intersecting family $\mathcal{G}$ of $k$-sets such that $\mathcal{G}\supsetneqq\mathcal{F}$. Maximal intersecting families of $k$-sets are also known as \emph{$k$-uniform maximal cliques}.

This notion was introduced by Erd\H{o}s and Lov\'{a}sz in \cite{MR0382050}. In this paper they proved the amazing result that any maximal intersecting family of $k$-sets has at most $k^{k}$ blocks, and hence for any given $k$, there are only finitely many maximal intersecting families of $k$-sets. (This result may be viewed as a special case of \cite[Theorem~2.3]{aX14111480}.) Therefore, Erd\H{o}s and Lov\'{a}sz initiated the problem of finding or estimating the function $\M{k}$ defined by
\begin{equation*}
\M{k}:=\max\left\{|\mathcal{F}|: \mathcal{F} \textup{ is a maximal intersecting family of }k-\textup{sets}\right\}.
\end{equation*}

In \cite{MR0382050}, Erd\H{o}s and Lov\'{a}sz also proved:
\begin{lemma}\label{inductive_relation}
 For $k\geq 2$, $\M{k}\geq 1+k\cdot\M{k-1}$.
\end{lemma}
\begin{proof}
Let $\mathcal{F}$ be a maximal intersecting family of $(k-1)$-sets with $\M{k-1}$ blocks. Choose a $k$-set $B$ disjoint from all the blocks of $\mathcal{F}$, and consider the family
\begin{equation*}
\widehat{\mathcal{F}}:=\{B\}\cup\{A\sqcup\{x\}: A\in\mathcal{F},\  x\in B\}
\end{equation*}
Then it is easy to verify that $\widehat{\mathcal{F}}$ is a maximal intersecting family of $k$-sets with $1+k\cdot\M{k-1}$ blocks.
\end{proof}

Since $\M{1}=1$, using Lemma~\ref{inductive_relation} and an easy induction on $k$, one deduces that 
\begin{equation*}
\M{k}\geq k!\left(\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{k!}\right)=\lfloor(e-1)k!\rfloor.
\end{equation*}

Thus Erd\H{o}s and Lov\'{a}sz showed 
\begin{equation}\label{Lovasz_relation}
\lfloor(e-1)k!\rfloor\leq\M{k}\leq k^{k}.
\end{equation}

In  \cite{MR510823}, Lov\'{a}sz conjectured that the lower bound in \eqref{Lovasz_relation} is sharp, i.e. $\M{k}=\lfloor(e-1)k!\rfloor$ for all $k$. In \cite{MR1383503}, Frankl et al. disproved this conjecture (for all $k\geq 4$) by an extremely elegant but complicated family of counterexamples. Indeed, it is hard to verify that their construction actually yields a maximal intersecting family of $k$-sets. (We addressed this question in a recent paper \cite{aX1502178} with Mukherjee.) There appears to be a gap in the proof sketched in \cite{MR1383503}. Specifically, the Claim~2 in \cite{MR1383503} seems to be incorrect. Therefore, it seems desirable to present a simpler construction (with short and complete proof) reproving this result. 

In this note we prove:
\begin{theorem}\label{main_theorem}
\[%begin{align*}
\M{k}\geq\begin{cases}
(\frac{k}{2}+1)^{k-1}+(k-1)(\frac{k}{2}+1)^{\frac{k}{2}-1} & \textnormal{for even } k,\\[0.75ex]
1+k(\frac{k+1}{2})^{k-2}+k(k-2)(\frac{k+1}{2})^{\frac{k-3}{2}} & \textnormal{for odd } k.
\end{cases}
\]%end{align*}
\end{theorem}
Note that this lower bound is asymptotic to $e^{2}(\frac{k}{2})^{k-1}$ through even $k$ and $2e(\frac{k}{2})^{k-1}$ through odd $k$. Since $k!$ grows roughly like $(\frac{k}{e})^{k}$, the bound in Theorem~\ref{main_theorem} beats the lower bound of \eqref{Lovasz_relation} by the exponential factor $(\frac{e}{2})^{k}$ (roughly). This bound is comparable to the explicit bound of \cite{MR1383503}, but the latter is somewhat better. Our bound beats the lower bound of \eqref{Lovasz_relation} for $k\geq8$, while the bound in \cite{MR1383503} is better than \eqref{Lovasz_relation} for $k\geq4$. In a final remark in section~2, we indicate how the lower bound of Theorem~\ref{main_theorem} may be sharpened.
 
\section{The construction}

In this section, $k$ is an even number. We construct a family $\mathbb{G}_{k}$ as follows. 

\begin{construction}
Let $X_{n}$, $0\leq n\leq k-2$ be pairwise disjoint sets, where each $X_{n}$ is of size $1+\frac{k}{2}$. Let $\alpha$ be a new symbol which does not belong to any of the $X_{n}$'s. The blocks of $\mathbb{G}_{k}$ are of two types. The blocks of type~1 are the sets $X_{n}\sqcup\{x_{i}:1\leq i\leq\frac{k}{2}-1\}$, where $0\leq n\leq k-2$, and $x_{i}\in X_{n+i}$ for $1\leq i\leq\frac{k}{2}-1$. Here the addition in the suffix is modulo $k-1$. The blocks of type~2 are the sets $\{\alpha\}\sqcup\{x_{i}: 0\leq i\leq k-2\}$, where $x_{i}\in X_{i}$ for $0\leq i\leq k-2$. 
\end{construction}

To appreciate the following proof, it may be helpful to visualize the sets $X_{n}$ as $k-1$ equally spaced blobs arranged on a circle.

\begin{theorem}\label{MIF}
For each even number $k$, $\mathbb{G}_{k}$ is a maximal intersecting family of $k$-sets.
\end{theorem}
\begin{proof}
Clearly $\mathbb{G}_{k}$ is a family of $k$-sets. For indices $m$, $n$ in the range $0\leq m,n\leq k-2$, let us write $m\rightarrow n$ to denote that $n\equiv m+i\pmod{k-1}$, for some $i$ in the range $1\leq i\leq\frac{k}{2}-1$. Notice that, for $m\neq n$, exactly one of the relations $m\rightarrow n$ and $n\rightarrow m$ holds true.

Clearly any block of type~2 intersects all the blocks of $\mathbb{G}_{k}$. Let $B_{1}$ and $B_{2}$ be two blocks of type~1. Then there are two indices $m$, $n$ such that $B_{1}\supseteq X_{m}$ and $B_{2}\supseteq X_{n}$. If $m=n$, then $B_{1}$ and $B_{2}$ intersect at least in $X_{m}$. Otherwise, we may assume without loss of generality that $m\rightarrow n$. Then every block containing $X_{m}$ intersects $X_{n}$. Therefore $B_{1}$ and $B_{2}$ intersect in this case also. Thus, $\mathbb{G}_{k}$ is an intersecting family of $k$-sets. 

Let $C$ be a set of size $k$ which intersects all the blocks of $\mathbb{G}_{k}$. To prove that $\mathbb{G}_{k}$ is maximal, it suffices to show that $C$ must be a block.

\noindent Case~A : $\alpha\notin C$. Since $C$ intersects all the blocks of type~2, it follows that there is an index $m$ such that $C\supseteq X_{m}$. Since $C$ is a $k$-set and the $X$'s are pairwise disjoint sets of size $\frac{k}{2}+1$, this index $m$ is unique. Suppose, if possible, that there is an index $n$ such that $C\cap X_{n}=\emptyset$ and $m\rightarrow n$. Since $C$ intersects all the blocks containing $X_{n}$, it follows there must exist an index $l$ such that $X_{l}\subset C$ and $n\rightarrow l$. By the uniqueness of the index $m$, we get $l=m$. Therefore, $m\rightarrow n$ and $n\rightarrow m$, a contradiction. Thus, $C$ intersects all the $(\frac{k}{2}-1)$ sets $X_{n}$ such that $m\rightarrow n$. Since, also, $C\supseteq X_{m}$ it follows that there is a block $B\supseteq X_{m}$ such that $C\supseteq B$. Since $|C|=k=|B|$, we get that $C=B$ is a block of type~1 in this case.  

\noindent Case~B : $\alpha\in C$. Let $T=C\smallsetminus\{\alpha\}$. Thus $T$ is a set of size $k-1$ which intersects all the type~1 blocks. Suppose, if possible, that there is an index $n$ such that $T\cap X_{n}=\emptyset$. Then arguing as in the previous case, we see that there is a unique index $m$ such that $T\supseteq X_{m}$. Also, $n\rightarrow m$ for all indices $n$ for which $T\cap X_{n}=\emptyset$. Contrapositively, $X_{n}\cap T\neq\emptyset$ for all the $\frac{k}{2}-1$ indices $n$ such that $m\rightarrow n$. Since $T\supseteq X_{m}$ and $|X_{m}|=\frac{k}{2}+1$, it follows that $|T|\geq\frac{k}{2}+1+\frac{k}{2}-1=k$, and hence $|C|>k$, a contradiction. Thus, $T\cap X_{n}\neq\emptyset$ for all $n$. Since there are $k-1=|T|$ pairwise disjoint sets $X_{n}$, it follows that $|T\cap X_{n}|=1$ for all $n$. Hence $C$ is a block of type~2 in this case.      
\end{proof}

\begin{proof}[Proof of Theorem~\ref{main_theorem}]
First let $k$ be an even positive integer. Note that $\mathbb{G}_{k}$ has $(\frac{k}{2}+1)^{k-1}$ blocks of type~2 and $(k-1)(\frac{k}{2}+1)^{\frac{k}{2}-1}$ blocks of type~1. Therefore the total number of blocks in $\mathbb{G}_{k}$ is  $(\frac{k}{2}+1)^{k-1}+(k-1)(\frac{k}{2}+1)^{\frac{k}{2}-1}$. Since by Theorem~\ref{MIF}, $\mathbb{G}_{k}$ is a maximal intersecting family of $k$-sets, this number is a lower bound on $\M{k}$.

Next let $k>1$ be an odd integer. (The result is trivial for $k=1$.) Using Lemma~\ref{inductive_relation} and the above bound (with $k-1$ in place of $k$) we get $\M{k}\geq1+k\cdot\M{k-1}\geq1+k(\frac{k+1}{2})^{k-2}+k(k-2)(\frac{k+1}{2})^{\frac{k-3}{2}}$.
\end{proof}

\begin{remark}
When $k$ is an odd positive integer, we may modify the above construction by putting
\[%begin{align*}
|X_{n}|=
\begin{cases}
\frac{k+1}{2} & \textnormal{ if } 0\leq n\leq\frac{k-1}{2}-1\\[0.75ex]
\frac{k+1}{2}+1 & \textnormal{ if } \frac{k-1}{2}\leq n\leq k-2
\end{cases}
\]%end{align*}
and taking the type~1 blocks of $\mathbb{G}_{k}$ to be the sets $X_{m}\sqcup\{x_{i}:1\leq i\leq k-|X_{m}|\}$, where $0\leq m\leq k-2$ and $x_{i}\in X_{m+i}$ for all $i$. Here addition in the suffix is modulo $k-1$. The type~2 blocks are as before. Then it can be shown that the resulting family $\mathbb{G}_{k}$ is again a maximal intersecting family of $k$-sets. The proof is similar, but a little more complicated. Using this construction (together with the preceding construction for even positive integer $k$) we can prove the following estimate, which improves upon Theorem~\ref{main_theorem}.
\end{remark}

\begin{theorem}
\[%begin{align*}
\M{k}\geq|\mathbb{G}_{k}|=\begin{cases}
(k-1)(\frac{k}{2}+1)^{\frac{k}{2}-1}+(\frac{k}{2}+1)^{k-1} & \textnormal{if } 
k \textup{ is an even integer}\\[0.75ex]
\frac{k+5}{2}\left\{(\frac{k+3}{2})^{\frac{k-1}{2}}-(\frac{k+1}{2})^{\frac{k-1}{2}}\right\}+(\frac{k+1}{2})^{\frac{k-1}{2}}(\frac{k+3}{2})^{\frac{k-1}{2}} & \textnormal{if }  k \textup{ is an odd integer}.
\end{cases}
\]%end{align*}
\end{theorem}

This lower bound is asymptotic to $e^{2}(\frac{k}{2})^{k-1}$ as $k\rightarrow\infty$. It seems safe to propose:
\begin{conjecture}
$\M{k}$ is asymptotic to $e^2(\frac{k}{2})^{k-1}$ as $k\rightarrow\infty$.
\end{conjecture}

\subsection*{Acknowledgement}
The author's sincere thanks go to Professor Bhaskar Bagchi for his constant help in preparing this note.

\SquashBibFurther
\begin{thebibliography}{99}
\bibitem{MR0382050}
{\sc Paul Erd\H{o}s} and {\sc L\'{a}szl\'{o} Lov\'{a}sz},\newblock Problems and results on $3$-chromatic hypergraphs and some related questions, \emph{Infinite and finite sets} %(Proceedings of a Colloquium held at Keszthely from June $25$ to July $1, 1973$), 
\newblock Vol.-II, North-Holland, Amsterdam, 1975, pp.~609--627. Colloquia Mathematica Societatis J\'{a}nos Bolyai {\bf10}.

\bibitem{MR1383503}
{\sc P\'{e}ter Frankl}, {\sc Katsuhiro Ota} and {\sc Norihide Tokushige}, \newblock Covers in uniform intersecting families and a counterexample to a conjecture of Lov\'{a}sz, \newblock \emph{J. Combin. Theory Ser. A} \textbf{74} (1996), No.~1, 33--42. 

\bibitem{MR510823}
{\sc L\'{a}szl\'{o} Lov\'{a}sz}, \newblock On minimax theorems of combinatorics, \newblock \emph{Matematikai Lapok} \textbf{26} (1975), No.~3-4, 209--264.

\bibitem{aX14111480}
{\sc Kaushik Majumder}, \newblock On the maximum number of points in a maximal intersecting family of finite sets, \newblock \emph{Combinatorica}, to appear. \url{http://dx.doi.org/10.1007/s00493-015-3275-8} %(Online published on June~24, 2015.)

\bibitem{aX1502178}
{\sc Kaushik Majumder} and {\sc Satyaki Mukherjee}, \newblock A note on the transversal size of a series of families constructed over cycle graph, \arxiv{1501.02178} (2015).
\end{thebibliography}
\end{document}