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.

MathOverflow Asked by Peter Hegarty on January 30, 2021

0 Answers1 Asked on February 17, 2021

at algebraic topology cohomology fundamental group homological algebra homotopy theory

1 Asked on February 16, 2021 by castor

co combinatorics gr group theory graph theory reference request sandpile

1 Asked on February 16, 2021 by bernard_karkanidis

0 Asked on February 15, 2021

expander graphs extremal graph theory graph theory spanning tree trees

0 Asked on February 15, 2021 by proof-by-wine

1 Asked on February 14, 2021 by sina

2 Asked on February 12, 2021 by federico-fallucca

ag algebraic geometry covering spaces field extensions ramification

1 Asked on February 12, 2021 by gmra

1 Asked on February 12, 2021 by patrick-nicodemus

at algebraic topology ct category theory homological algebra

1 Asked on February 12, 2021 by christian-gaetz

co combinatorics discrete geometry hyperplane arrangements mg metric geometry

1 Asked on February 8, 2021 by harharkh

2 Asked on February 7, 2021 by mustafa-said

1 Asked on February 7, 2021 by fozz

ap analysis of pdes fa functional analysis harmonic functions

1 Asked on February 6, 2021 by sylvain-julien

analytic number theory goldbach type problems nt number theory prime constellations prime numbers

4 Asked on February 5, 2021 by john-r-ramsden

1 Asked on February 5, 2021

complex geometry dg differential geometry differential operators vector bundles

28 Asked on February 3, 2021 by psihodelia

2 Asked on February 2, 2021 by serge

computer algebra hochschild cohomology quivers ra rings and algebras

0 Asked on February 2, 2021

Get help from others!

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

Recent Answers

- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- kjetil b halvorsen on How to test consistency of responses?
- Philipp on How do i draw a ray in unity
- eric_kernfeld on How to test consistency of responses?
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed

© 2022 AnswerBun.com. All rights reserved.