TransWikia.com

Kruskal-Katona type question for union-closed families of sets

MathOverflow Asked by Peter Hegarty on January 30, 2021

Question: Let $n,k$ be two positive integers with $n geq k$. Let $mathcal{F}$ be a family of $C(n,k)$ sets, each of size $k$, and let $langlemathcal{F}rangle$ denote the union-closed family generated by $mathcal{F}$, i.e.: $langlemathcal{F}rangle$ consists of all those sets which can be expressed as a union of members of $mathcal{F}$.

Must it be the case that
begin{equation}
|langlemathcal{F}rangle| geq sum_{j=k}^{n} C(n,j),
end{equation}

with equality if and only if $mathcal{F}$ consists of all $k$-element subsets of an $n$-set ?

Let $w(mathcal G)$ denote the average size of the members of a family $mathcal G$.

It is easy to see that if the inequality holds (whatever about uniqueness), then it implies that, for any union-closed family $mathcal{G}$ and non-negative integer $m$,
$$|mathcal{G}| geq 2^{m}implies w(mathcal{G})ge m/2.$$
This is, in turn, a special case of a result of Reimer [1] that, for any union-closed family $mathcal{G}$ one has
$$w(mathcal{G}) geq frac{1}{2} log_{2} |mathcal{G}|.$$
Indeed I had conjectured the same result and in thinking about it was led to the above question, before I recently became aware of Reimer’s proof, which is a beautiful piece of work !

One can obviously try to generalise my question to an arbitrary number of generating $k$-sets, perhaps along the lines of the Kruskal-Katona theorem for shadows ?

[1] Reimer, David, An average set size theorem, Comb. Probab. Comput. 12, No. 1, 89-93 (2003). ZBL1013.05083.

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP