Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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$, if $|\mathcal{G}| \geq 2^{m}$ then the average size, let's denote it $w(\mathcal{G})$, of a member of $\mathcal{G}$ is at least $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] D. Reimer, An average set size theorem, Combin. Probab. Computing 12 (2003), 89-93.

share|improve this question
    
You might make it clear that union F is potentially greater than n. Gerhard "Ask Me About System Design" Paseman, 2011.09.16 –  Gerhard Paseman Sep 16 '11 at 16:07
    
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 –  Gerhard Paseman Sep 16 '11 at 16:11
    
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 –  Gerhard Paseman Sep 16 '11 at 17:52
    
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 :) –  Peter Hegarty Sep 17 '11 at 15:04
    
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 –  Gerhard Paseman Sep 17 '11 at 19:05
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.