% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb,amsfonts,latexsym,mathrsfs,cases} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf A generalization of Sperner's theorem on compressed ideals} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Lili Mu \qquad Yi Wang \thanks{Supported by National Natural Science Foundation of China (No. 11371078).}\\ \small School of Mathematical Sciences\\[-0.8ex] \small Dalian University of Technology\\[-0.8ex] \small Dalian, PR China\\ \small\tt lly-mu@hotmail.com \qquad wangyi@dlut.edu.cn\\ %\and %Yi Wang \\ %\small School of Mathematical Sciences\\[-0.8ex] %\small Dalian University of Technology\\[-0.8ex] %\small Dalian, PR China\\ %\small\tt wangyi@dlut.edu.cn } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{December 1, 2015}{July 13, 2016}\\ \small Mathematics Subject Classifications: 05D05, 05A20} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Let $[n]=\{1,2,\ldots,n\}$ and $\mathscr{B}_n=\{A: A\subseteq [n]\}$. A family $\mathscr{A}\subseteq \mathscr{B}_n$ is a Sperner family if $A\nsubseteq B$ and $B\nsubseteq A$ for distinct $A,B\in\mathscr{A}$. Sperner's theorem states that the density of the largest Sperner family in $\mathscr{B}_n$ is $\binom{n}{\left\lceil{n/2}\right\rceil}/2^n$. The objective of this note is to show that the same holds if $\mathscr{B}_n$ is replaced by compressed ideals over $[n]$. % keywords are optional \bigskip\noindent \textbf{Keywords:} Convex family; Sperner family; Ideal; Filter; Compressed ideal \end{abstract} \section{Introduction} Let $\mathscr{B}_n$ be the poset of subsets of $[n]=\{1,2,\ldots,n\}$ ordered by inclusion. A family $\mathscr{A}\subseteq \mathscr{B}_n$ is a {\it Sperner family} if $A\nsubseteq B$ and $B\nsubseteq A$ for distinct $A,B\in\mathscr{A}$. A famous result due to Sperner~\cite{Spe28} states that the density of the largest Sperner family in $\mathscr{B}_n$ is $\binom{n}{\left\lceil n/2\right\rceil}/2^n$. Sperner's theorem is one of the central results in extremal finite set theory and it has many generalizations and extensions (see \cite{And87,Eng97} for instance). For $\mathscr{P}\subseteq \mathscr{B}_n$, we say that $\mathscr{P}$ is a {\it convex} family if $A, B\in\mathscr{P}$ and $A\subseteq C\subseteq B$ imply that $C\in\mathscr{P}$. A family $\mathscr{I}\subseteq \mathscr{B}_n$ is an {\it ideal} if $A\in \mathscr{I}$ and $B\subseteq A$ imply $B\in \mathscr{I}$. Clearly, an ideal is a convex family. In \cite[Conjecture~1.3]{FA87}, Frankl conjectured that the density of the largest Sperner family in any convex subfamily of $\mathscr{B}_n$ is at least $\binom{n}{\left\lceil n/2\right\rceil}/2^n$. \begin{conjecture}\label{FA-conj} For every convex family $\mathscr{P}$ over the set $[n]$, there exists a Sperner family $\mathscr{A}\subseteq \mathscr{P}$ such that $$|\mathscr{A}|/|\mathscr{P}|\geq \binom{n}{\left\lceil{n}/2\right\rceil}/2^n.$$ \end{conjecture} The conjecture seems difficult to prove and no progress was made in more than 30 years. Since no progress for the general case was made, it is quite natural to consider the special case of ideals. Here, we will restrict our research to the compressed ideals of $\mathscr{B}_n$. On $\mathscr{B}_n$ we consider the {\it reverse lexicographic order} $\preceq$, which is defined by $A\preceq A'$ if $\max\{(A\cup A')\backslash(A\cap A')\}\in A'$ or $A=A'$ for $A, A'\in \mathscr{B}_n$. For example, we have $\{3,4\}\preceq\{1,3,5\}$ and $\{3,5\}\preceq\{1,3,5\}$. Let $\mathcal{C}(m,\mathscr{B}_n)$ be the family of the first $m$ minimal elements of $\mathscr{B}_n$ with respect to $\preceq$. The family $\mathcal{C}(m,\mathscr{B}_n)$ is called {\it compressed} and the operation of exchanging an $m$-element family of $\mathscr{B}_n$ by $\mathcal{C}(m,\mathscr{B}_n)$ is called {\it compression}. Denote by $\mathscr{B}^{(k)}_n$ the collection of all $k$-subsets of $\mathscr{B}_n$. Similarly, we define $\mathcal{C}(\mathscr{F})$, where $\mathscr{F}\subseteq \mathscr{B}^{(k)}_n$, to be the first $|\mathscr{F}|$ elements of $\mathscr{B}^{(k)}_n$ with respect to $\preceq$. Here, we use the compress notation from \cite[Ch.~7.5]{And87} and \cite[p.~41]{Eng97}. An ideal $\mathscr{I}$ is called a {\it compressed ideal} if $\mathcal{C}(\mathscr{I}\cap \mathscr{B}^{(k)}_n)=\mathscr{I}\cap \mathscr{B}^{(k)}_n$ for all $0\leq k\leq n$. Clearly, $\mathscr{B}_n$ is a compressed ideal. %under the reverse lexicographic order. In this paper, we will prove the following result. \begin{theorem} \label{thm-ci} Let $\mathscr{I}$ be a compressed ideal in $\mathscr{B}_n$ and $\mathscr{A}$ the largest Sperner family in $\mathscr{I}$. Then \begin{equation} \label{AIineq} |\mathscr{A}|/|\mathscr{I}|\geq\binom{n}{\left\lceil{n/2}\right\rceil}/2^n. \end{equation} \end{theorem} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Proof of Theorem \ref{thm-ci}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $\mathscr{A}\subseteq\mathscr{B}^{(k)}_n$ where $k|\mathscr{F}|$ if $k>\left\lceil n/2\right\rceil$ and $|\nabla\mathscr{F}|>|\mathscr{F}|$ if $k<\left\lfloor n/2 \right\rfloor$. \end{lemma} \begin{lemma}\rm{\cite{Lovasz}} \label{thm-lovasz} Let $\mathscr{F}\subseteq \mathscr{B}_n^{(k)}$. Then there is an $x\geq k$ such that $|\mathscr{F}|=\binom{x}{k}$ and $|\Delta\mathscr{F}|\geq\binom{x}{k-1}$. \end{lemma} \begin{proof} [Proof of Theorem~\ref{thm-ci}] To simplify the notation, let us write $$T(n)=\binom{n}{\left\lceil{n/2}\right\rceil}/2^n.$$ It can be verified that $T(2n-1)=T(2n)$ and $T(2n)/T(2n+1)=(2n+2)/(2n+1)$. Hence we have $$T(1)=T(2)>T(3)=T(4)>\cdots>T(2m-1)=T(2m)>\cdots.$$ We use induction on $n$. The case $n=1$ is trivial. So we proceed to the induction step. Let $\mathscr{I}$ be a compressed ideal in $\mathscr{B}_n$. Then $\mathscr{I}=\mathscr{I}_1\cup \mathscr{I}_2$, where $\mathscr{I}_1=\{A\in \mathscr{I}: n\notin A\}$ and $\mathscr{I}_2=\{A\in \mathscr{I}: n\in \mathscr{I}\}$. Denote by $\mathscr{I}_2(\bar{n})$ the collection of all sets $A\setminus\{n\}$, with $A\in \mathscr{I}_2$. Clearly, $\mathscr{I}_1$ and $\mathscr{I}_2(\bar{n})$ are compressed ideals in $\mathscr{B}_{n-1}$. We therefore use the induction hypothesis for $\mathscr{B}_{n-1}$, assuming that there exists the largest Sperner families $\mathscr{A}_1 \subseteq \mathscr{I}_1$ and $\mathscr{A}_2(\bar{n}) \subseteq \mathscr{I}_2(\bar{n})$ such that \begin{equation}\label{eq1} \frac{\left|\mathscr{A}_1\right|}{\left|\mathscr{I}_1\right|}\geq T(n-1), \quad \frac{\left|\mathscr{A}_2(\bar{n})\right|}{\left|\mathscr{I}_2(\bar{n})\right|}\geq T(n-1). \end{equation} Let $\mathscr{A}_2=\{A\cup\{n\}:A\in \mathscr{A}_2(\bar{n})\}$. Then $\mathscr{A}_2$ is the largest Sperner family in $\mathscr{I}_2$ and \begin{equation}\label{eqa2} \frac{\left|\mathscr{A}_2\right|}{\left|\mathscr{I}_2\right|}= \frac{\left|\mathscr{A}_2(\bar{n})\right|}{\left|\mathscr{I}_2(\bar{n})\right|}\geq T(n-1)\geq T(n). \end{equation} Denote by $\mathscr{I}^{(k)}_i$ the collection of all sets $\mathscr{I}_i$ which occur in $\mathscr{B}^{(k)}_{n}$, and $\mathscr{A}^{(k)}_i$ the collection of all sets $\mathscr{A}_i$ which occur in $\mathscr{I}^{(k)}_i$ for $i=1,2$. Let $s=\min\{k:\mathscr{A}^{(k)}_1\neq\emptyset\}$ and $r=\max\{k:\mathscr{A}^{(k)}_2\neq\emptyset\}$. Then we have $\mathscr{I}^{(r)}_1=\mathscr{B}^{(r)}_{n-1}$ by the definition of compressed ideal. Hence $\mathscr{I}_1$ can be written as \begin{equation}\label{I1} \mathscr{I}_1=\bigcup_{k=0}^{r}\mathscr{B}^{(k)}_{n-1}\cup \bigcup_{k>r} \mathscr{I}^{(k)}_1. \end{equation} We now prove that $r\leq \left\lceil n/2\right\rceil$. Note that $\mathscr{A}^{(r)}_2\subseteq \mathscr{B}^{(r)}_n$ and then $A^{(r)}_2(\bar{n})\subseteq \mathscr{B}^{(r-1)}_{n-1}$. Hence by Lemma \ref{lem-nmp}, if $r-1> \left\lceil (n-1)/2\right\rceil$, then $$\left|\Delta(\mathscr{A}^{(r)}_2(\bar{n}))\right|> \left|\mathscr{A}^{(r)}_2(\bar{n})\right|.$$ Replacing $\mathscr{A}^{(r)}_2(\bar{n})$ by $\Delta(\mathscr{A}^{(r)}_2(\bar{n}))$, we obtain a larger Sperner family than $\mathscr{A}_2(\bar{n})$ in $\mathscr{I}_2(\bar{n})$. Thus $r-1\leq \left\lceil (n-1)/2\right\rceil$, i.e., $r\leq \left\lceil n/2\right\rceil$. In the following, we show that there is the largest Sperner family $\mathscr{A}$ in $\mathscr{I}$ such that (\ref{AIineq}) holds. We distinguish two cases. Case $1$: we consider the case that $n$ is even. Let $n=2m$. Then $r\leq m$. We show that $s\geq r$. Assume that $s< r$. Let $$\bar{\mathscr{A}}_1=\left(\mathscr{A}_1\backslash\{\mathscr{A}_1\cap \mathscr{I}^{(s)}_1\}\right)\cup\left(\nabla^{(r)}(\mathscr{A}_1\cap \mathscr{I}^{(s)}_1)\right),$$ where $$\nabla^{(r)}(\mathscr{A}_1\cap \mathscr{I}^{(s)}_1)= \{A\in \mathscr{B}^{(r)}_{2m-1}: \exists B\in \mathscr{A}_1\cap \mathscr{I}^{(s)}_1, A\supset B \}.$$ By \eqref{I1}, $\nabla^{(r)}(\mathscr{A}_1\cap \mathscr{I}^{(s)}_1) \subset \mathscr{I}_1$ and $\bar{\mathscr{A}}_1$ is still a Sperner family in $\mathscr{I}_1$. By Lemma \ref{lem-nmp}, $$\left|\nabla^{(r)}(\mathscr{A}_1\cap \mathscr{I}^{(s)}_1)\right|> \left|\mathscr{A}_1\cap \mathscr{I}^{(s)}_1 \right|,$$ so that $|\bar{\mathscr{A}}_1|>|\mathscr{A}_1|$ which contradicts the maximality of $\mathscr{A}_1$ in $\mathscr{I}_1$. Hence we have $s\geq r$, which means that $\mathscr{A}_1\cup\mathscr{A}_2$ is still a Sperner family in $\mathscr{I}$. Hence by (\ref{eq1}) and (\ref{eqa2}), we have $$\frac{\left|\mathscr{A}_1\cup \mathscr{A}_2 \right|}{\left|\mathscr{I}\right|}= \frac{\left|\mathscr{A}_1\right|+\left|\mathscr{A}_2\right|}{\left|\mathscr{I}_1\right|+\left|\mathscr{I}_2\right|}\geq T(2m-1)=T(2m),$$ and thus $\mathscr{A}=\mathscr{A}_1\cup \mathscr{A}_2$ is the family as desired. Case $2$: we consider the case that $n$ is odd. Let $n=2m+1$. Then $r\leq m+1$. If $rm+1}\mathscr{I}^{(k)}_1$$ and $\mathscr{A}_1=\mathscr{B}^{(m)}_{2m}$. However $\mathscr{B}^{(m)}_{2m}\cup \mathscr{A}_2$ is no longer a Sperner family. Let $$\bar{\mathscr{A}}_2=\left(\mathscr{A}_2\backslash\{\mathscr{A}^{(m+1)}_2\}\right)\cup\left(\Delta_1(\mathscr{A}^{(m+1)}_2)\right),$$ where $\Delta_1\left(\mathscr{A}^{(m+1)}_2\right)$ is the shadow of $\mathscr{A}^{(m+1)}_2$ in $\mathscr{I}_2$, i.e., $$\Delta_1\left(\mathscr{A}^{(m+1)}_2\right)\triangleq \Delta\left(\mathscr{A}^{(m+1)}_2(\overline{2m+1})\right)\cup\{2m+1\}.$$ Then $\bar{\mathscr{A}}_2$ is still a Sperner family in $\mathscr{I}_2$. Moreover, $\mathscr{B}^{(m)}_{2m}\cup \bar{\mathscr{A}}_2$ is also a Sperner family in $\mathscr{I}$. We then show that \begin{eqnarray} \label{case2} \frac{\left|\mathscr{B}^{(m)}_{2m}\cup\bar{\mathscr{A}}_2\right|}{\left|\mathscr{I}_1\right|+\left|\mathscr{I}_2\right|}\geq T(2m+1). \end{eqnarray} We first claim that \begin{eqnarray} \label{claim1} \binom{2m}{m} \geq (2m+1)|\mathscr{A}_2|-(2m+2)|\bar{\mathscr{A}}_2|. \end{eqnarray} Note that \begin{eqnarray*} %\label{a2} |\mathscr{A}_2|=\left|\mathscr{A}^{(m+1)}_2\right|+\sum_{i