10
$\begingroup$

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 $\langle\mathcal{F}\rangle$ denote the union-closed family generated by $\mathcal{F}$, i.e.: $\langle\mathcal{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} |\langle\mathcal{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.

$\endgroup$
8
  • $\begingroup$ You might make it clear that union F is potentially greater than n. Gerhard "Ask Me About System Design" Paseman, 2011.09.16 $\endgroup$ Sep 16, 2011 at 16:07
  • $\begingroup$ What about the underlying set being of size C(n,k), and each member of F is that set minus a singleton? I then get < F > having one set more than F. Or is there something I am missing? Gerhard "Ask Me About System Design" Paseman, 2011.09.16 $\endgroup$ Sep 16, 2011 at 16:11
  • $\begingroup$ I apologize for not meeting all of the problem requirements, especially the condition of each set being of size k. Nevertheless, I have a feeling that some example similar to the above is possible, and that one can find F which do not satisfy the inequality because of getting several pairs of elements to have the same union. Gerhard "Back To The Drawing Board" Paseman, 2011.09.16 $\endgroup$ Sep 16, 2011 at 17:52
  • $\begingroup$ But, intuiutively, it seems to me that the best way to get most overlap in the unions is to start off by "packing" the sets as close as you can, i.e: as k-subsets of an n-set. Not that this proves anything :) $\endgroup$ Sep 17, 2011 at 15:04
  • $\begingroup$ I sympathize with the intuition. So instead let's consider k-sets of N >> n. Perhaps it can be shown that there is a partition of [k,N] into intervals [k_i, k_{i+1}) such that C(N,k+i) is less than the sets of < F > whose sizes fall into the ith interval, and that the inequality can be established that way. It would be interesting to know this even in the case N=n+1. Gerhard "Ask Me About System Design" Paseman, 2011.09.17 $\endgroup$ Sep 17, 2011 at 19:05

0

Your Answer

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

Browse other questions tagged or ask your own question.