% A LaTex file for an 8 page document
\documentstyle[12pt]{article}
\topmargin -0.25in
\headheight 0.25in
\textwidth 6in
\headsep .25in
\textheight 8.25in

\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{lem}{Lemma}
\newtheorem{clm}{Claim}

\begin{document}

\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 2 (1995)
 \#R16\hfill}
\thispagestyle{empty}

\begin{center}
\Large
{\bf On the shadow of squashed families of $k$-sets }
\end{center}

\bigskip

\begin{center}
\normalsize

Fr\'ed\'eric Maire\\
{\small {\tt maire@fit.qut.edu.au} \\
 Neurocomputing Research Center\\
 Queensland University of Technology\\
 Box 2434 Brisbane Qld 4001, Australia}
\end{center}

\bigskip


\noindent
{\bf Abstract:} 
The {\em shadow} of a collection   ${\cal A}$ of $k$-sets 
is defined as the collection
of the $(k-1)$-sets which are contained in at least one $k$-set of 
 ${\cal A}$. Given $|{\cal A}|$, the size of the shadow is minimum 
when ${\cal A}$ is the family of the first $k$-sets in 
{\em squashed order} 
(by definition, a $k$-set $A$ is smaller than a $k$-set
$B$ in the squashed order if the largest element of the symmetric
difference of $A$ and $B$ is in $B$).
We give a tight upper bound and an asymptotic formula  for the size of
the shadow of squashed families of $k$-sets.

\bigskip


\noindent
{\em Submitted:} January 15, 1995; {\em Accepted:} August 25, 1995.
\bigskip

\noindent
{\bf AMS Subject Classification.}  04A20,03E05,05A20.



\section{Introduction}

A hypergraph  is a collection of subsets (called {\em edges})
 of a finite set $S$. If a hypergraph  ${\cal A}$ is such that
  $A_i,A_j \in {\cal A}$ implies $ A_i \not\subseteq A_j$,
then  ${\cal A}$ is called an {\em antichain}.
In other words  ${\cal A}$ is a collection of incomparable sets.
Antichains are also
known under the  names {\em simple hypergraph } or {\em clutter}.

 The {\em shadow} of a collection   ${\cal A}$ of $k$-sets (set of size $k$)
is defined as the collection
of the $(k-1)$-sets which are contained in at least one $k$-set of  ${\cal A}$.
 The  shadow of  ${\cal A}$ is denoted by  $\Delta({\cal A})$.

In the following we assume that $S$ is a  set of integers.
The {\em squashed order} is defined on the the set of $k$-sets.
Given two $k$-sets $A$ and $B$, we say that $A$ is smaller than
$B$ in the squashed order if the largest element of the symmetric
difference of $A$ and $B$ is in $B$. The first $3$-sets in the squashed
order are \[\{1,2,3\},\{1,2,4\},\{1,3,4\},\{2,3,4\},\{1,2,5\},\{1,3,5\},
\cdots\]

Let $F_k(x)$ denote the family of the first  $x$ $k$-sets in the 
squashed order.
 We will  prove the following.

\begin{thm}
If $x \leq { n \choose k}$ then
$$
|\Delta ( F_k(x) )| \leq k x  - x (x-1) \times q_{n,k}
\mbox{    where    }
q_{n,k} = \frac{k}{{ n \choose k}-1 }\times \frac{n-k}{n-k+1}
$$
Equality holds when $x=0$ or  $x= { n \choose k}$.
\end{thm}


\begin{thm}
 When $x \rightarrow \infty$, 
$
|\Delta ( F_k(x) )| \sim \frac{k}{\sqrt[k]{k !}} \; x^{1-\frac{1}{k}}
$
\end{thm}
\vspace*{0.5 cm}

The squashed order is very useful when dealing with the size of the
shadow of a collection of $k$-sets. The main result is that if you want
to minimize the shadow then you have to take the first sets in the
squashed order. This is a consequence of  the Kruskal-Katona 
theorem~\cite{kr,ka}. Before stating their theorem,  recall 
the definition of the $l$-binomial representation of a number.
\begin{thm}
Given positive integers $x$ and $l$, there exists a unique representation 
of $x$ (called the $l$-binomial representation) in the form
$$
x={ x_{l} \choose l}+ { x_{l-1} \choose l-1}+ \cdots+{ x_{t} \choose t}
$$
where $ x_{l} > x_{l-1} > \cdots >  x_{t} \geq t$.
\end{thm}
 See \cite{anderson} or \cite{ber2} for more details.
\begin{thm}[Kruskal-Katona]
Let  ${\cal A}$ be a collection of $l$-sets, and suppose that the
 $l$-binomial representation of  $|{\cal A}|$ is
$$
 |{\cal A}|={ x_{l} \choose l}+ { x_{l-1} \choose l-1}+ 
\cdots+{ x_{t} \choose t}
$$
where $ x_{l} > x_{l-1} > \cdots >  x_{t} \geq t$.  Then
$$
 |\Delta({\cal A})| \geq { x_{l} \choose l-1}+ { x_{l-1} \choose l-2}+ 
\cdots+{ x_{t} \choose t-1}
$$
There is equality when  ${\cal A}$ is the collection
of the first  $|{\cal A}|$ $l$-sets in the squashed order.
\end{thm}

Though the above theorem gives the exact values of the shadow
when the antichain is squashed, it is awkward to manipulate.
Because  of this, 
   theorem~1  may  be more useful
for some problems such as those of construction of completely separating systems
(see \cite{colin}, for example).


\section{Proofs}
\subsection{Proof of theorem~1}
We need a few lemmas before proving  theorem~1.
\begin{lem}
The inequality of theorem~1 holds when $n \leq 6$.
\end{lem}
\noindent{\bf Proof of  lemma~1:}
Done by computer check. Can be done
by hand too.  $\Box$\\

\begin{lem}
The inequality of theorem~1 holds when $k=1$.
\end{lem}
\noindent{\bf Proof of  lemma~2:}
We have $q_{n,1}=  1/n$. So the inequality to prove is;

$$
|\Delta ( F_1(x) )| \leq  x  - x (x-1) \times \frac{ 1}{n} 
$$
The right hand side of the inequality can be rewritten as

$$ 
\frac{x}{n} (n - x + 1)
$$
As $|\Delta ( F_1(x) )|$ is equal to $1$
 (because $\Delta ( F_1(x) )=\{\emptyset\}$), all we have to prove is that
$$ 
\frac{n}{x} \leq n - x + 1
$$
i.e.
$$
x^2 - (n+1) x + n \leq 0
$$
The zeroes of this polynomial are $1$ and $n$. This implies that for
$x$ in the interval $[1,{ n \choose 1}]$, the inequality holds.$\Box$\\

\begin{lem}
The 
inequality of 
theorem~1 holds when $k=n-1$.
\end{lem}
\noindent{\bf Proof of  lemma~3:}
We  have $ q_{n,n-1} = \frac{1}{2}$. So the inequality to prove is;
$$
|\Delta ( F_{n-1}(x) )| \leq  x [n-1  -  \frac{x- 1}{2}]
$$
The value of $x$ is in the range $[1 , n]$.
If $x=n$ then both sides of the inequality are equal to ${ n \choose 2}$.
Now, assume that $x$ is in the range  $[1 , n-1]$. The $(n-1)$-binomial
representation of $x$ is:
$$
x={ x_{n-1} \choose n-1}+ { x_{n-2} \choose n-2}+ \cdots+{ x_{t} \choose t}
$$
where $ x_{n-1} > x_{n-2} > \cdots >  x_{t} \geq t$.
As $x \leq n-1$, we have  $ x_{n-1} = n-1$. And, therefore
$x_{n-i}=n-i$ for all $i \in [1,n-t]$.
Hence $x=n-t$.
Because of the  $(n-1)$-binomial representation of $x$, the size of the
shadow of  $F_{n-1}(x)$ is given by the  formula:
$$
| \Delta ( F_{n-1}(x) )|=
 { n-1 \choose n-2}+ { n-2 \choose n-3}+ 
\cdots+{ t \choose t-1}
$$
i.e.
$$
|\Delta ( F_{n-1}(x) )| =
 { n-1 \choose 1}+ { n-2 \choose 1}+ \cdots+{ t \choose 1}
$$
Finally, we have 
$$
|\Delta ( F_{n-1}(x) )| =
\frac{n(n-1)}{2} - \frac{t(t-1)}{2} =
\frac{1}{2} (n-t)(n+t-1)
$$
As  $x=n-t$. By substituting  $n-x$ to $t$ in the right hand side, we
find that 

$$
|\Delta ( F_{n-1}(x) )| =x [n-1  -  \frac{x- 1}{2}]
$$
Which is what we wanted to prove. $\Box$\\

\begin{lem}
The inequality of theorem~1 holds when $k=n$.
\end{lem}
\noindent{\bf Proof of  lemma~4:} obvious.  $\Box$\\



\begin{lem}
 The function $n \longmapsto q_{n,k}$ is decreasing
on $[k+1,\infty]$.
\end{lem}
\noindent{\bf Proof of  lemma~5:}
$$
 q_{n+1,k}- q_{n,k} = \frac{k}{ {n+1 \choose k} -1} \times \frac{n+1-k}{n+2-k}
 - \frac{k}{ {n \choose k} -1} \times \frac{n-k}{n+1-k}
$$
which has the same sign as
$$
k (n+1-k)^2 \times ({n \choose k} -1)-
k (n-k) (n+2-k) \times ({n +1\choose k} -1)
$$
which has the same sign as
$$
(n+1-k)^2 \times ({n \choose k} -1)-
 (n-k) (n+2-k) \times ({n \choose k} +{n \choose k-1} -1)
$$
$$
={n \choose k} -1 -(n-k) (n-k+2) \times {n \choose k-1}
$$
$$
={n \choose k} -1 -{n \choose k} \frac{k (n-k) (n-k+2)}{n-k+1} < 0
$$
 $\Box$\\
\vspace*{0.5 cm}

To prove  theorem~1, we use a double induction on $k$ then $n$. 
The case $k=1$ has been considered
in lemma~2.
If $x \leq  {n-1 \choose k}$ then as the function 
$n \longmapsto q_{n,k}$ is decreasing, using  the induction
hypothesis we are done. Thus, we can assume that
$x={n-1 \choose k}  + j$ with $j \leq  {n-1 \choose k-1}$.
It is a classical result (see~\cite{ber2} or \cite{anderson})  that

$$
|\Delta ( F_k( x ))| =
{n-1 \choose k-1}+|\Delta ( F_{k-1}( j) )|
$$
By induction hypothesis
$$
|\Delta ( F_{k-1}(j) )| \leq j (k-1) - j(j-1) \times q_{n-1,k-1}
$$
Combining these inequalities we get:
\begin{clm}
$$
|\Delta ( F_k( x) )|  \leq
{n-1 \choose k-1}+j(k-1)-j (j-1) q_{n-1,k-1} 
$$
\end{clm}
\vspace*{0.5cm}

If theorem~1 is true then
$
|\Delta ( F_k( x) )|  \leq
k x  - x (x-1) \times q_{n,k}
$
  with equality when $j= {n-1 \choose k-1}$.
Hence, to prove theorem~1 it is sufficient to prove that  
we have:
$$
{n-1 \choose k-1}+j(k-1)-j (j-1) q_{n-1,k-1} 
 \leq   
k x  - x (x-1) \times q_{n,k}
\eqno{(\star)}
$$
As
$ k {n-1 \choose k}= (n-k)  {n-1 \choose k-1}$
and  $x={n-1 \choose k}  + j$,
$(\star)$ is equivalent to
$$
x(x-1) q_{n,k}
 \leq  
(n-k-1){n-1 \choose k-1} + j+ j(j-1) 
q_{n-1,k-1}
$$
To simplify the expressions we introduce some new variables.
Let $q_0=q_{n,k}$ and  $q_1=q_{n-1,k-1}$.
Let $y= {n-1 \choose k-1}$.
We will use later the facts that ${n \choose k} =\frac{n}{k} y$, and that
$ {n-1 \choose k} = \frac{n-k}{k} y$.
With  this notation $(\star)$ is equivalent to
$$
x (x-1) q_0 \leq (n-k-1) y + j  (j-1) q_1 +j
$$
As
$ x = \frac{n-k}{k} y+j $, we have
$$
x (x-1) q_0= q_0 j^2 + q_0(2 \frac{n-k}{k} y-1)j + q_0 (\frac{n-k}{k} y)^2
- \frac{n-k}{k} y q_0
$$
Therefore, $(\star)$ is equivalent to
$$
0 \leq
j^2 (q_1-q_0)- j(-1+q_1-q_0+ 2  \frac{n-k}{k} y q_0) +
(n-k-1) y -  q_0 (\frac{n-k}{k} y)^2
+ \frac{n-k}{k} y q_0
$$
Finally we have,
\begin{clm}
 $(\star)$ is equivalent to
$$
0 \leq
j^2 (q_1-q_0)- j(-1+q_1-q_0+ 2  \frac{n-k}{k} y q_0 ) +
(n-k-1) y +  q_0 \frac{n-k}{k} y (1-\frac{n-k}{k} y)
$$
\end{clm}
\vspace*{0.2 cm}

Let $\Phi(j)=j^2 (q_1-q_0)- j(-1+q_1-q_0+ 2  \frac{n-k}{k} y q_0 ) +
(n-k-1) y +  q_0 \frac{n-k}{k} y (1-\frac{n-k}{k} y)$.
We will prove that this polynomial in $j$ is positive on the
interval  $[0,{ n-1 \choose k-1}]$,  by proving that $\Phi'' \geq 0$,
 $\Phi'(y) \leq 0$ and $\Phi(y) = 0$.
Let's prove that $\Phi''=q_1-q_0$ is positive.
$$
q_0-q_1 = [ \frac{k}{{ n \choose k}-1 }  -  \frac{k-1}{{ n-1 \choose k-1}-1 }]
 \frac{n-k}{n-k+1}
$$
i.e.
$$
q_0-q_1 = [ \frac{k}{ \frac{n}{k} y-1 }  -  \frac{k-1}{y-1 }]
 \frac{n-k}{n-k+1}
$$
 The sign of  $q_0-q_1$  is the same as the sign of
$$
k (y-1)-(k-1)(\frac{n}{k} y-1)
= ky -k- n y + k + \frac{n}{k} y -1 = y (k  - n + \frac{n}{k}) -1
$$
Notice that $k-n+ \frac{n}{k}$ is negative because   $k \in [2,n-2]$.
Indeed, the sign of  $k-n+ \frac{n}{k}$ is the same as the sign of
 $k^2-nk+ n$. It's easy to check that this polynomial in $k$ is negative
 on  $[2,n-1]$ as soon as $n \geq 5$. Hence,  $q_0-q_1$ is negative.

%\vspace*{0.5cm}

Let's check  that $(\star)$ becomes an equality  when $j$ takes the value of
  $y={ n-1 \choose k-1}$. By substituting
 ${ n \choose k}$ to $x$ in the right hand side of the inequality
of theorem~1, we get $ { n \choose k-1}$ as expected.
By  substituting $y={ n-1 \choose k-1}$ to $j$ in the  inequality of 
claim~1, we obtain  also $ { n \choose k-1}$  (use the induction
hypothesis that $|\Delta ( F_{k-1}(y) )|={ n-1 \choose k-2}$).
This implies that  ${ n-1 \choose k-1}$ is a root of the polynomial
 $\Phi(j)$. 

To finish the proof of theorem~1
we will prove that $y={ n-1 \choose k-1}$ is the smaller root of
$\Phi(j)$, by showing that at that point the derivative
of  $\Phi(j)$ is negative. This will sufficient as we already
know that the second derivative is positive.
We have 
$$
\Phi'(y)=2 y (q_1-q_0) - (-1+q_1-q_0+ 2  \frac{n-k}{k} y q_0 )
$$
$ \Phi'(y) \leq 0$ is equivalent to 
$$2 y (q_1-q_0) \leq -1+ q_1-q_0+ 2  \frac{n-k}{k} y q_0$$
which is equivalent to
$$
2 y (\frac{k-1}{y-1} - \frac{k}{\frac{n}{k}y-1}) \frac{n-k}{n-k+1}
\leq -1+q_1-q_0 +2 \frac{n-k}{k} y \frac{k}{\frac{n}{k}y-1} \frac{n-k}{n-k+1}
$$
which is equivalent to
$$
2 y (\frac{k-1}{y-1} - \frac{k^2}{n y-k})+ \frac{n-k+1}{n-k}
\leq (q_1-q_0) \frac{n-k+1}{n-k} + \frac{2 (n-k) k y}{n y -k}
$$
i.e.
$$
\frac{2 y (k-1)}{y-1} + \frac{n-k+1}{n-k}
\leq (q_1-q_0) \frac{n-k+1}{n-k} + \frac{2 n k y}{n y -k}
$$
It is sufficient to prove that
$$
\frac{2 y (k-1)}{y-1} +  \frac{3}{2}\leq  \frac{2 n k y}{n y -k}
$$
The left hand side is equal to $2 k - \frac{1}{2}+\frac{2 (k-1)}{y-1}$.
The right hand side is equal to $2 k  +\frac{2 k^2}{n y - k}$.
The function $t \mapsto  \frac{-1}{2} +\frac{2 (k-1)}{t-1}$ is negative as
soon as $t \geq 4(k-1) +1$. As $n \geq 7$ and $ k \in [2,n-2]$, we
have $y={n-1  \choose k-1}  \geq 4(k-1) +1$. Therefore,
$$
\frac{2 y (k-1)}{y-1} + 3/2 \leq  \frac{2 n k y}{n y -k}
$$
This finishes the proof of theorem~1. $\Box$\\
\subsection{Proof of theorem 2 }


Consider the $k$-binomial representation of $x$ :
$$
x={ x_{k} \choose k}+ { x_{k-1} \choose k-1}+ \cdots+{ x_{t} \choose t}
\mbox{  where  }  x_{k} > x_{k-1} > \cdots >  x_{t} \geq t
$$
It is easy to prove that
$$ 
\mbox{ when }  x \rightarrow \infty,  
\quad x \sim  { x_{k} \choose k}
\mbox{ and similarly },\quad |\Delta ( F_k(x) )| \sim  { x_{k} \choose k-1}
$$
As $x \sim  { x_{k} \choose k}$, 
 we have 
 $x \sim  \frac{ {x_{k}}^{k}}{k!} $. This implies that
$x_{k} \sim (x (k!))^{\frac{1}{k}}$.
Therefore
$$
\frac{|\Delta ( F_k(x) )|}{x} \sim 
\frac{  { x_{k} \choose k-1}}
{  { x_{k} \choose k}} \sim \frac{k}{x_k-k+1}
$$
Hence
$
\quad\frac{|\Delta ( F_k(x) )|}{x} \sim  \frac{k}{ (x (k!))^{\frac{1}{k}}}
$
 $\Box$

\bigskip

\begin{thebibliography}{9}
\bibitem {anderson}
Anderson I. : Combinatorics of finite sets, Oxford science publication, 1987.
\bibitem {ber2}
Berge C. : Graphs and Hypergraphs, North-Holland, 1985.
\bibitem {ka}
Katona, G. O. H. (1966) :  A theorem on finite sets. In 'Theory of Graphs'.
Proc. Colloq. Tihany, 1966, pp. 187-207. Akademia Kiado. Academic Press,
New York.
\bibitem{kr}
Kruskal, J. B. (1963) : The number of simplices in a complex.
In 'Mathematical optimization techniques' (ed. R. Bellman), pp. 251-78.
University of California Press, Berkeley.
\bibitem{colin}
Ramsey, C., Roberts I. (1994) : Minimal completely separating systems
of $k$-sets. To appear in 'Proc. Colloq. of the 20th Australasian Conference on
 Combinatorial Mathematics', Auckland 1994.

\end{thebibliography}

\end{document}

.