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 4m-2 }[/math], assuming [math]\displaystyle{ \mathcal{A} }[/math] is separating; or
• [math]\displaystyle{ 0 \lt \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

• Introductory post
• FUNC1
• FUNC2

General proof strategies

Use a weight function

Find set configurations that imply FUNC

Links

• A good survey article