Frankl's union-closed conjecture
Polymath11 -- Frankl's union-closed conjecture
A family [math]\displaystyle{ \mathcal{A} }[/math] of sets is called union closed if [math]\displaystyle{ A\cup B\in\mathcal{A} }[/math] whenever [math]\displaystyle{ A\in\mathcal{A} }[/math] and [math]\displaystyle{ B\in\mathcal{A} }[/math]. Frankl's conjecture is a disarmingly simple one: if [math]\displaystyle{ \mathcal{A} }[/math] is a union-closed family of n sets, then must there be an element that belongs to at least n/2 of the sets? The problem has been open for decades, despite the attention of several people.
Definitions
For any [math]\displaystyle{ x }[/math] in the ground set, write [math]\displaystyle{ \mathcal{A}_x = \{A \in \mathcal{A} : x \in A\} }[/math].
We say that [math]\displaystyle{ \mathcal{A} }[/math] is separating if for any two elements of the ground set there is a set in the family containing exactly one of them (in other words, if the [math]\displaystyle{ \mathcal{A}_x }[/math] are all distinct).
Partial results
Let [math]\displaystyle{ \mathcal{A} }[/math] be a union-closed family of n sets, with a ground set of size m. It is known that Frankl's conjecture is true for the cases:
- [math]\displaystyle{ m \leq 12 }[/math]; or
- [math]\displaystyle{ n \leq 50 }[/math]; or
- [math]\displaystyle{ n \geq \frac23 2^m }[/math]; or
- [math]\displaystyle{ n \leq 2m }[/math], assuming [math]\displaystyle{ \mathcal{A} }[/math] is separating; or
- [math]\displaystyle{ \lvert A \rvert \leq 2 }[/math] for some [math]\displaystyle{ A \in \mathcal{A} }[/math].
- [math]\displaystyle{ \mathcal{A} }[/math] contains three sets of three elements that are all subsets of the same five element set.
If [math]\displaystyle{ \mathcal{A} }[/math] is union-closed then there is an element [math]\displaystyle{ x }[/math] such that [math]\displaystyle{ \lvert \mathcal{A}_x \rvert \geq \frac{n-1}{\log_2 n} }[/math]. For large [math]\displaystyle{ n }[/math] this can be improved slightly to [math]\displaystyle{ \frac{2.4 n}{\log_2 n} }[/math].
Discussion on Gowers's Weblog
Links
- A good survey article
