Difficult examples for Frankl's union-closed conjecture - MathOverflow

Difficult examples for Frankl's union-closed conjecture

2010-11-26T11:04:10Z

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there must be an element that belongs to at least half the sets.

I know that pretty well any naive approach one takes to this conjecture is known to fail. By "naive approach" I suppose I mean something like an observation that it would follow from such-and-such a stronger conjecture -- it seems that all sensible stronger conjectures one thinks of are false. A very simple example of a stronger conjecture would be that if you pick a random element then on average it will belong to at least half the sets. That is completely false: take the family that consists of the empty set, {1}, and {1,2,3,4,5,6,7,8,9,10}, for example. One can try to "correct" this strengthening by devices such as insisting that for any two elements there is a set that contains one and not the other (which WLOG is the case), but such corrections don't get one very far.

What I am asking for is examples, either small ones or ones that are constructed theoretically, of union-closed families that defeat more sophisticated strengthenings of the original conjecture. I'm fairly sure they are out there but I am not an expert on this problem so I don't know them myself.

Apologies in advance if this resembles an existing question (which it feels as thought it easily might). But I've looked and not found anything.

Answer by Victor Falgas--Ravry for Difficult examples for Frankl's union-closed conjecture

2011-01-05T09:53:56Z

I am not sure whether this is the type of things you are looking for, but here is a strengthening of the original conjecture for which I would like to have a counterexample.

Let $\mathcal{S}$ be a union-closed family and let $V$ be the maximal set in $\mathcal{S}$. Given $x \in V$, write $\mathcal{S}_x $ for the family $\{A\setminus\{x\}: \ A \in \mathcal{S}, x \in A\}$ and $d_{\mathcal{S}}(x)= |\mathcal{S}_x|$ for the degree of $x$ in $\mathcal{S}$.

Claim: Suppose $x$ is an element of $\mathcal{V}$ of minimal degree in $\mathcal{S}$. Then for every $y \neq x$, we have \[ \frac{d_{\mathcal{S}_x}(y)}{d(x)}\geq \min \left(\frac{1}{2}, \frac{d(y)}{|\mathcal{S}|}\right).\]

(In other words if an element has lowest degree in $\mathcal{S}$ than the other elements must correlate well with it.)

Answer by Jérôme JEAN-CHARLES for Difficult examples for Frankl's union-closed conjecture

2013-03-01T16:23:08Z

i) Definitions:
Let $F$ be a union closed family (U.C. family for short)
Let $S$ := $\cup_{ \Omega \in F} \Omega $ (the support of the family).
Let $F_{x} $ denote the members of $F$ containing $x$.

A) Union Closed Average variation : ( with $S$ being $T_0$-separated by $F$)

$ \sum_{x \in S}{ |F_{x}| } is \ge |F|.|S|/2 $.
( That is average $F_x$ size (on $S$) is greater than $|F|/2$)

Note: I cannot find any counter-example.
The $T_0$ separation of $ S $ by $ F $ means that for any two different points ${x,y} $ there exist a member of $F$ containing one point and not the other(you can choose which!) .

Another avenue of generalization that I cannot dismiss is a the multiset variation.

B) Mutltiset variation :
F is a family of $(\Omega,\eta_{\Omega})$ where:
- the $\Omega$ forms an U.C family say $F_0$
- $\eta : F_0 \rightarrow \mathbb {N}^{\gt 0}$ ( or $\mathbb {R^{\gt 0}}$ or $ [1,2,..,p]$ ordered naturally )
- for any $ \Omega_1 , \Omega_2$ of $F_0$ : $ \eta_{\Omega_1 \cup \Omega_2} \ge Sup ( \eta_{\Omega_1} ,\eta_{\Omega_2} )$

Now the conjecture is: The best measured $F_x$ is at least half that of $F$, where measure means the sum of members measure : the standard U.C. conjecture appears when $\eta$ is the constant one function.

C) The general point of view: (not strictly a generalization as asked by M.O.),
The U.C. problem is I believe of a fundamental nature, it pertains to very weak structures in the following sense: in algebra the weak (or basic or atomic) structures are the ideals, in the case of an order (or lattice) it is an upset (a family stable by overclusion , otherwise said an over-set of any member is a member), whereas we have in this problem something even weaker or more basic: stable by max only. All this comes of observing first that U.C. conjecture is easy for upsets family and still unsolved otherwise and second that algebraic techniques are not very helpful.