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