1
$\begingroup$

Let $\mathcal{F} \subseteq \binom{[n]}{4}$ be a collection of size-4 subsets of $\{1,\ldots,n\}$, i.e., a 4-uniform set family.

Let $\mathcal{F'}$ be the collection of size-3 sets for which a superset is contained in $\mathcal{F}$, i.e., $$\mathcal{F'} := \{ S \subseteq [n] \colon |S|=3 \wedge \exists T \in \mathcal{F}: S \subseteq T \}.$$

Can we give an asymptotic lower bound on $|\mathcal{F'}|$ in terms of $|\mathcal{F}|$?

If $\mathcal{F}$ contains all size-$4$ subsets of $[n]$, then $\mathcal{F'}$ contains all size-$3$ subsets of $[n]$, so that $|\mathcal{F}| = \binom{n}{4}$ and $|\mathcal{F'}| = \binom{n}{3}$, giving $|\mathcal{F'}| \in \mathcal{\Omega}(|\mathcal{F}|^{3/4})$. I would expect this to hold generally. Can anyone point me in the right direction?

$\endgroup$
5
  • $\begingroup$ Your notations are incorrect, e.g. $\mathcal{F} \subseteq {[n]\choose 4}$. $\endgroup$
    – user64494
    Feb 14, 2018 at 11:33
  • 2
    $\begingroup$ @user64494: How is '$\mathcal{F}\subseteq\binom{[n]}{4}$' incorrect? I think it is incorrect to say that that is incorrect. What the OP writes means ' a subset of the set of all 4-element subsets of $[n]$', and to call this a 'collection of size-4 subsets' is correct. Would someone please tell me what I am missing, or second what I am saying? $\endgroup$ Feb 14, 2018 at 11:36
  • $\begingroup$ @Peter Heinig: The LHS is a set whereas the LHS is a number. $\endgroup$
    – user64494
    Feb 14, 2018 at 12:33
  • $\begingroup$ @user64494: "The LHS is a set whereas the LHS is a number." is wrong, or beside the point, in at least three respects: (0) in the usual formalization of most of combinatorics, namely: ZF set theory, every number is a set; (1) you write 'LHS' twice, while presumably you mean 'RHS' in the second occurrence, (2), the notation $\binom{[n]}{k}$ is very usual in the combinatorical literature for the set of $k$-element subsets. If that was your reason to object, then the objection was without merit. $\endgroup$ Feb 14, 2018 at 12:50
  • $\begingroup$ @Peter Heinig: One more discordance: "asymptotic lower bound on$|\mathcal{F}'|$ in terms of $|\mathcal{F}|$ and "If $|\mathcal{F}|$ contains all size-4 subsets.." $\endgroup$
    – user64494
    Feb 14, 2018 at 14:24

1 Answer 1

2
$\begingroup$

The usual technical term within hypergraph theory for the set $\mathcal{F}'$ in the OP is (lower) shadow of $\mathcal{F}$. Cf. e.g. [Béla Bollobás: Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability. Cambridge University Press, 1986 ISBN 9780521337038; page 23].

In the following, to facilitate discussion of (lb0), the notation $\mathcal{F}'$ will not be used, rather, I will use the longer but more explanatory notation

$\mathcal{F}' = \mathrm{Shad}_3(\mathcal{F})$

where the right-hand side is just what is defined in the OP (and is also defined below). As the lower index '3' indicates, this notion can of course be defined more generally, in the anologous way.(notation)

I also take the liberty to use $n=\{0,1,\dotsc,n-1\}$ instead of the OP's $[n]=\{1,\dotsc,n\}$ as ground-set. In particular,

I write $\binom{n}{k}$ for the set of $k$-element subsets of $n$.

An answer to your question can be obtained from a theorem of Kruskal and Katona. For any $0\leq k\leq n$ let $\prec$ denote the linear order on $\binom{n}{k}$ defined by(alternative) (colex)

$ A\prec B $ if and only if $\max( A\setminus B) < \max( B\setminus A)$.

(Here, $\max$ denotes the usual maximum w.r.t. the natural linear order on $\omega$.)

For any $k,l\in\omega$, let $\mathrm{Init}_\prec(k,l)$ denote the initial segment of the linear order $(\binom{n}{k},\prec)$ consisting of the first $l$ elements of the linear order.(length)

For any hypergraph $\mathcal{H}\subseteq 2^{n}$ let(term)

$\mathrm{Shad}_3(\mathcal{H}):=\{ S\subseteq n\colon \lvert S\rvert=3,\quad \exists e\in\mathcal{H},\ \ S\subseteq e\}$.

Gyula O. H. Katona and Joseph Kruskal independently proved more general statements which in particular imply that

$\lvert \mathrm{Shad}_3(\mathcal{F}) \rvert\geq\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,\lvert\mathcal{F}\rvert))\rvert\qquad$ for all $n\in\omega$ and all $\mathcal{F}\subseteq\binom{n}{4}$ ${}\hspace{22pt}$ (lb0)

This is a lower bound for $\lvert\mathcal{F}'\rvert=\lvert \mathrm{Shad}_3(\mathcal{F}) \rvert$, a proof of which was requested in the OP, in terms of $\lvert\mathcal{F}\rvert$, while the bound is difficult to use because of the difficult function $m\mapsto \lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))\rvert$.

In particular, the lower bound does not depend on the structure of the hypergraph $\mathcal{F}$, only on its size $\lvert\mathcal{F}\rvert$. In a sense, this is better than the 'asymptotic' bound requested, for it holds for all $n$, not only for sufficiently large ones; in another sense, it is worse than what was requested (because it lacks the transparent informativeness of a statement like the OP's expectation $\Omega(\lvert\mathcal{F}\rvert^{\frac34})$; but see below, where that, too, is provided).

While it might seem unsatisfactory that the lower bound for $\lvert\mathrm{Shad}_3(\cdot)\rvert$ in (lb0) is again in terms of that very same function; however, the argument of that function in the lower bound is one specific explicit hypergraph, namely: $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,\lvert\mathcal{F}\rvert))$, into which $\mathcal{F}$ enters only by way of its size, not its structure.

The hypergraph $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))$ can efficiently be computed for every $m\in\omega$, and, notably, the ground set used is irrelevant, as long as it has at least $4m$ elements. In tabulating these specific hypergraphs, it is important to note(absolute) that essentially there isn't any dependency on $n$, in the sense that the initial segments of the colexicographic order do not change with increasing $n$, so that to tabulate the hypergraphs $\mathrm{Init}_\prec(4,m)$, $m\in\omega$, one can assume that the ground-set is $\omega$, and hence the hypergraphs $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))$ are 'one-dimensional data', i.e., a countable sequence of 4-uniform hypergraphs.

The first thirty-five terms of the linear order $\prec$, on ground-set $\omega$, are

$0, 1, 2, 3$

$\prec$

$0, 1, 2, 4$

$\prec$

$0, 1, 3, 4$

$\prec$

$0, 2, 3, 4$

$\prec$

$1, 2, 3, 4$

$\prec$

$0, 1, 2, 5$

$\prec$

$0, 1, 3, 5$

$\prec$

$0, 2, 3, 5$

$\prec$

$1, 2, 3, 5$

$\prec$

$0, 1, 4, 5$

$\prec$

$0, 2, 4, 5$

$\prec$

$1, 2, 4, 5$

$\prec$

$0, 3, 4, 5$

$\prec$

$1, 3, 4, 5$

$\prec$

$2, 3, 4, 5$

$\prec$

$0, 1, 2, 6$

$\prec$

$0, 1, 3, 6$

$\prec$

$0, 2, 3, 6$

$\prec$

$1, 2, 3, 6$

$\prec$

$0, 1, 4, 6$

$\prec$

$0, 2, 4, 6$

$\prec$

$1, 2, 4, 6$

$\prec$

$0, 3, 4, 6$

$\prec$

$1, 3, 4, 6$

$\prec$

$2, 3, 4, 6$

$\prec$

$0, 1, 5, 6$

$\prec$

$0, 2, 5, 6$

$\prec$

$1, 2, 5, 6$

$\prec$

$0, 3, 5, 6$

$\prec$

$1, 3, 5, 6$

$\prec$

$2, 3, 5, 6$

$\prec$

$0, 4, 5, 6$

$\prec$

$1, 4, 5, 6$

$\prec$

$2, 4, 5, 6$

$\prec$

$3, 4, 5, 6$

and for all $1\leq m\leq 35$, the hypergraph $\mathrm{Init}_\prec(4,m)$ is obtained by collecting precisely the first $m$ terms in the above sequence. The hypergraphs $\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))$ for $1\leq m\leq 35$ can be computed from this list.

One way to phrase (lb0) is: the specific hypergraph $\mathcal{F}:=\mathrm{Init}_\prec(4,m)$ is a hypergraph of least size $\lvert F'\rvert$ of the $3$-shadow among all 4-uniform hypergraphs with $m$ on ground set $n$. (It is usually not the unique minimizer, though.)

The function $\lambda\colon m\mapsto\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))\rvert$ is known as the Kruskal--Macaulay function, and is tabulated at OEIS A123573, plotted there as

enter image description here Caption. This is your "lower bound" function as a function of increasing $\lvert\mathcal{F}\rvert$. The resemblance to the a part of the blancmange curve can be mathematically explained (cf. [FMRT1995]).

There is a similar result attributed to László Lovász, which implies that

$\lvert \mathrm{Shad}_3(\mathcal{F}) \rvert \geq \binom{h(\lvert \mathcal{F} \rvert)}{3}$

where $h\colon\omega\to\mathbb{R}$ is the function defined by $h(x) := \max\{ \xi\in\mathbb{R}\colon\quad \xi>0, \quad x\geq \binom{\xi}{4} = \frac{\Gamma(\xi+1)}{\Gamma(4+1)\cdot\Gamma(\xi-4+1)} \}$ ${}\hspace{50pt}$ (lb1)

A proof of (lb1) can be found in (the proof of) Theorem 10.15 of(index)

Stasys Jukna, Extremal Combinatorics. Second Edition. Springer 2011. xxiv+412 pages. ISBN 978-3-642-17363-9

or in

Boriks Bukh, Multidimensional Kruskal-Katona Theorem, SIAM J. Discrete Math., vol. 26(2), pp. 548–554, 2012. errata

Working with these bounds is not easy. There is a curious connection to Takagi's construction of a continuous nowhere-differentiable function. You can find more detail in (the references in):

[FMRT1995] Peter Frankl, Makoto Matsumoto, Imre Z. Ruzsa, Norihide Tokushige: Minimum shadows in Uniform Hypergraphs and a Generalization of the Takagi Function. Journal of Combinatorial Theory, Series A 69, 125-148 (1995)

However, your conjecture/expectation that

$\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,\lvert\mathcal{F}\rvert))\rvert \in \Omega(\lvert\mathcal{F}\rvert^{\frac34})$

can easily be confirmed with the help of Lovász's bound (lb1). To see this, for brevity let $x=h(\lvert\mathcal{F}\rvert)$ and (m)$m=\lvert\mathcal{F}\rvert$. The definition of $h$ in (lb1) implies that $x$ is the unique positive real with

$x^4-6x^3+11x^2-6x-24m=0$ $\hspace{125pt}$ (quartic)

This quartic equation has negative discriminant for all the nontrivial cases $m\in\omega\setminus\{0\}$, hence has exactly two real roots, the larger of which is positve and equal to

$x = x(m) = \frac12\left(3 + \sqrt{ 5 + 4 \sqrt{1 + 24m} } \right)$.

The lower bound in (lb1) therefore is

$\frac{1}{12}\cdot\biggl( 3 + 3\sqrt{1+24m} + \sqrt{5+4\sqrt{1+24m}} + \sqrt{ 5 + 120m + 4(1+24m)^{\frac32} } \biggr)$$\hspace{125pt}$ (lb.explicit)

It is evident from (lb.explicit) that, as you expected,

$\lvert\mathrm{Shad}_3(\mathrm{Init}_\prec(4,m))\rvert \in \Omega(m^{\frac34})$

The Puiseux expansion of $\frac{1}{3!}\cdot x(m)\cdot (x(m)-1) \cdot (x(m)-2)$ at infinity is

$2(\frac23)^{1/4}\quad m^{\frac34} + (\frac32)^{1/2}\quad m^{\frac12} + \frac{13}{8\cdot 2^{1/4}\cdot 3^{3/4}}\quad m^{\frac14} + \frac14 + \frac{151}{768\cdot 24^{1/4}}\cdot m^{-\frac14} + \frac{1}{16\cdot 6^{1/2}}\cdot m^{-\frac12} + \frac{341}{24576\cdot 54^{1/4}}\cdot m^{-\frac34} + O(m^{-1})$

(I did not calculate this manually, which in principle would be routine, though I did do one successful numerical check with a random value of $m$.)

Finally, here is a plot of both the exact Kruskal-Macaulay function, and of (lb.explicit):

Kruskal-Macaulay function from m=0 to m=70; and best-possible lower bound

By the way, it seems that no one so far has proved general estimates of how well the lower bound in (lb.explicit) approximates the Kruskal-Macaulay function (of course, it is sharp for infinitely-many values of $m$; my point is that there is no estimate for how bad it can get in between these points).

${}$__________________________

(absolute) This property is easy to prove (a 4-set from a larger ground-set using one of the larger ground-set elements cannot precede any of the already known sets because its 'large' element will differ from all elements of any set compared with it, and that single element by itself be sufficient reason to rank that 4-set higher than any of these sets). It is also widely known and sometimes explicitly mentioned in the literature; e.g., in [Gordon Royle: Combinatorial Enumeration: Theory and Practice. Course CITS7209 at University of Western Australia 2004; Lecture 2, p. 19] one reads

enter image description here

In particular, given any $4$-element subset of $\omega$, one can efficiently compute its absolute rank in the colexicographic order $\prec$, and that rank is the same no matter what set $X$ with $4\subseteq X\subseteq\omega$ the ground set is.

(alternative) Alternative definitions are

and

  • $A\prec B$ $\Leftrightarrow$ if both $A$ and $B$ are each represented as tuples $\mathrm{rep}(A)$ and $\mathrm{rep}(B)$ in decreasing natural order, then $\mathrm{rep}(A) <^{\mathrm{lexicographic}} \mathrm{rep}(B)$

(colex) This linear order is often called colexicographic order. This is not the order obtained by reversing the lexicographic order.

(index) Curiously, the important Kruskal-Katona theorem, while carefully treated in the book, is missing from the book's index, which should be remedied in the third edition.

(length) Here, $l$ is for 'length', which here means 'number of elements in the segment, not the graph-theoretic length of the segment as a digraph.

(m) The notation $m$ honors the long tradition in graph theory of denoting the number of edges by $m$.

(notation) Reference [FMRT1995] writes $\Delta_3(\cdot)$ instead of $\mathrm{Shadow}_3(\cdot)$, which I avoid because '$\Delta$' is used for the maximum vertex-degree of a hypergraph, and moreover carried connotations of 'difference operators', neither of which is a helpful association here.

(term) Needless to say, these 'shadows' do not have any meaningful relation to the notion of 'shadow' in nonstandard analysis. Another usual term, though somewhat less relevant, is skeleton (of an abstract simplicial complex). Very strictly speaking, one would first have to take the down-closure of the given hypergraph $\mathcal{F}$ before one is allowed to speak of its $d$-dimensional skeleton. Your $\mathcal{F}'$ is the $4$-dimensional skeleton of the $5$-dimensional abstract simplicial complex $\lfloor\mathcal{F}\rfloor$, where $\lfloor\cdot\rfloor$ denotes down-closure.

$\endgroup$
1
  • 1
    $\begingroup$ The terms 'shadow' and 'Kruskal-Katona theorem' were exactly what I needed - thanks so much for those, and the explanation here. (In lb0, you probably mean $F \subseteq \binom{[n]}{4}$ rather than $\mathcal{F} \in \ldots$ as it currently says.) $\endgroup$ Feb 14, 2018 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.