Strong induction on the maximum size of a set

53 Views Asked by At

I'm currently working on an advancement of the Union-closed sets conjcture, and I have a whole cascading series of implications that follow from one claim, and try as I may, I have not been able to prove this claim (I will provide intuition for why it could be true later on)

Given a union closed family, $F$, on an m-universe, that is, $F$ a collection of subsets of the set: $$ U:= \{1, 2,...,m\} $$ with the property that the union of any two sets in $F$ is also in $F$

Then define the $k^{th}$ layer of of $F$ as

$L_k(F) = \{X \in F: |X| = k \}$

The claim that I am trying to prove is that if every element of $U$ appears in exactly $$ 2^{m-1} - \sum_{i=1}^n \binom{m-1}{i-1}$$ Sets in $F$, for some $n<m$ then the maximum size of $F$ is $$2^{m} - \sum_{i=1}^n \binom{m}{i}$$

Those quantities arise precisely from removing the first $n$ layers of the powerset of $U$, $\mathcal{P}(U)$ and so what the claim is saying is that this is the least amount of sets you can hope to remove so that each element appears exactly that amount of times.

For the powerset itself, i.e when $n=0$ this is indeed true, and every element appears $2^m$ times, and for $n=1$ it seems that not only is it true but this is in fact the only removal which results in every element appearing exactly $2^m -1$ times

I tried attacking this with a strong induction, assuming that for every $n$ up to k, this was the maximum size of $F$, and then showing that it must also be the maximum size for $n=k+1$ the intuition being that if you were to remove some sets from some of the "higher" layers of $\mathcal{P}(U)$, you would necessarily need to remove some sets from all the layers "below" it, to preserve the union-closed property, and indeed, if you remove only one set $X_k$ from $L_k(\mathcal{P}(U))$ then you have to remove at least $k-1$ sets from $L_{k-1}(\mathcal{P}(U))$ to preserve the union-closed property, and the single removal of $X_k$ can be substituted for an equivalent removal of some $X_{k-1}$ from the layer below it, along with the previously removed $k-1 $ sets from this layer (equivalent in terms of the minimum decrease in appearance of all the elements in $X_k$) and so removing only from the layer $L_{k-1}(\mathcal{P}(U))$ is at least as effective as removing from both layers.

This leads one to think that all the ingredients for an inductive step are present, but I haven't been able to complete it, since it gets considerably more complicated to "keep track of things" once you start removing more than simply one set from an otherwise full layer.

Any help would be appreciated, if this were to be proben it would be a significant step forward for the conjecture (sorry,thought it too space consuming to include the description of the original conjecture too), accordingly, any complete answers will get at least an acknowledgment.