3
$\begingroup$

I'm reading a research article lately, and got confused about a question. So, the fundamental theorem of Kruskal and Katona states that if each set in a given set system $\mathcal{A}$ has $k$ elements and $|\mathcal{A}|=m$, then the lower shadow of $\mathcal{A}$ is at least as large as the lower shadow of the initial segment of length $m$ of $N^{(k)}$ in the colex order. Here, $N^{(k)}$ is the family of all $k$-element sets of all the natural numbers. Then, the article mentioned that, as an easy consequence of this Kruskal-Katona theorem, we have the following lemma:

If $\mathcal{F}$ is a down-set, $||\mathcal{F}|| \leq || \mathcal{I}(|\mathcal{F}|) ||$. Here, $\mathcal{I}(m)$ is the initial segment of length $m$ of $N^{(<\inf)}$ in the colex order. Here, $N^{(<\inf)}$ is the family of all the finite subsets of all natural numbers. I did not see the reasoning behind this. Could anyone give me a hint of this? Many thanks for your time and attention.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Not every question involving sets is a set theory question. You didn't tag this as number theory, despite the fact that were numbers involved (k, m, etc.)... $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 15, 2017 at 22:52
  • 1
    $\begingroup$ I'd say it should be tagged number theory and combinatorics $\endgroup$
    – kodlu
    Commented Sep 15, 2017 at 23:50
  • $\begingroup$ based on the article, it is simply an easy consequence of Kruskal and Katona's result. $\endgroup$
    – Joseph Stone
    Commented Sep 16, 2017 at 1:06
  • 2
    $\begingroup$ why not give a precise reference to the article? $\endgroup$
    – j.c.
    Commented Sep 16, 2017 at 4:03
  • 2
    $\begingroup$ @j.c.: This is Tom Eccles's "A stability result for the union-closed size problem", Lemma 2.2. (arxiv.org/pdf/1311.2298.pdf) $\endgroup$
    – Seva
    Commented Sep 16, 2017 at 9:37

1 Answer 1

Reset to default
1
$\begingroup$

The inequality the OP is asking for seems to be

  • little else than the inequality one gets by summing all the finitely-many inequalities in the relevant instance of the usual Kruskal-Katona theoreom.

Just take any usual statement of the Kruskal-Katona theorem, adapt the statement you took to your context, and then sum all the inequalities between f-vector-components.

I did not quite work out the details, yet it seems that there is essentially nothing more in the "Lemma 2.2" you cite. The difficulty of deriving the inequality asked for by the OP seems comparable to the difficulty of deriving $a+c\leq b+d$ from ($a\leq b$ $\wedge$ $c\leq d$) .

Is that enough to help you get on with it?

Remarks.

  • A reference you could use is Samuel Kolins: Notes For Algebraic Methods in Combinatorics 2008. Theorem 1.45. Sum the inequalities therein and see whether this answers your question for you.

  • The Kruskal-Katona theorem is a characterization of the second-order predicate '$\exists$ at least one abstract simplicial complex whose f-vector is the given vector'$\colon$ $\omega^{d+1}\to\{$true,false$\}$ by a, in a sense, first-order predicate, using another signature though, which says 'for each index the relevant inequality between the components holds'. I would bet that the inequality you are asking about is only necessary, i.e., $\mathcal{F}$ need not be a 'down-set' if it happens to hold. (I haven't stopped to think about this, however. Yet it seems trivial to find examples that this inequality from Lemma 2.2 is not equivalent to the Kruskal-Katona theorem; basically, any random example should work as a counterexample; I know you didn't claim it to be equivalent anywhere, it just seems good to mention this.

  • Worth pointing out: a usual synonym for 'down-set' is 'abstract simplicial complex'.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Could you explain more clearly from a combinatorial sense? @Peter Heinig $\endgroup$
    – Joseph Stone
    Commented Sep 18, 2017 at 0:18
  • $\begingroup$ @JosephStone: re "could you explain": probably yes, unfortunately, no time today. Hope to get round to in the next few days. Again: from what I saw, there does not seem to be much of a problem here. Just sum the inequalities. The inequality you stated seems to be the sum of the component-wise inequalities. $\endgroup$
    – Peter Heinig
    Commented Sep 18, 2017 at 6:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .