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