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].

Strengthenings

Various strengthenings of FUNC have been proposed. Some have been disproved, and some implications between them have been shown.

Conjectures that imply FUNC

Injection-to-superset

Is there always some [math]\displaystyle{ x \in X }[/math] and some injection [math]\displaystyle{ \phi : \mathcal{A}_{\bar{x}} \to \mathcal{A}_x }[/math] such that [math]\displaystyle{ A \subset \phi(A) }[/math] for all [math]\displaystyle{ A }[/math]? This was answered in the negative.

Injection-to-larger

Is there always some [math]\displaystyle{ x \in X }[/math] and some injection [math]\displaystyle{ \phi : \mathcal{A}_{\bar{x}} \to \mathcal{A}_x }[/math] such that [math]\displaystyle{ \lvert A \rvert \lt \lvert \phi(A) \rvert }[/math] for all [math]\displaystyle{ A }[/math]?

Weighted FUNC

Let [math]\displaystyle{ f : \mathcal{A} \to \mathbb{R} }[/math] be such that [math]\displaystyle{ f(A) \geq 0 }[/math] for all [math]\displaystyle{ A }[/math] and [math]\displaystyle{ f(A) \leq f(B) }[/math] whenever [math]\displaystyle{ A \subseteq B }[/math]. Is there always an [math]\displaystyle{ x \in X }[/math] such that [math]\displaystyle{ \sum_{A : x \in A} f(A) \geq \sum_{A : x \notin A} f(A) }[/math]?

Uniform weighted FUNC

Is there always an [math]\displaystyle{ x \in X }[/math] such that [math]\displaystyle{ \sum_{A : x \in A} f(A) \geq \sum_{A : x \notin A} f(A) }[/math] for every [math]\displaystyle{ f : \mathcal{A} \to \mathbb{R} }[/math] such that [math]\displaystyle{ f(A) \geq 0 }[/math] for all [math]\displaystyle{ A }[/math] and [math]\displaystyle{ f(A) \leq f(B) }[/math] whenever [math]\displaystyle{ A \subseteq B }[/math]?

This is equivalent to the conjecture that there is some [math]\displaystyle{ x }[/math] that is abundant in every upper set in [math]\displaystyle{ \mathcal{A} }[/math].

This conjecture is false.

FUNC for subsets

Is there for every [math]\displaystyle{ r }[/math] a subset [math]\displaystyle{ S \subseteq X }[/math] of size [math]\displaystyle{ r }[/math] such that [math]\displaystyle{ \lvert \{A \in \mathcal{A} : S \subseteq A\} \rvert \geq 2^{-r} \lvert \mathcal{A} \rvert }[/math]?

Disjoint intervals

Igor Balla points out that the following conjecture implies FUNC: suppose we have a collection of disjoint intervals [math]\displaystyle{ [A_i, B_i] = \{S : A_i \subseteq S \subseteq B_i\} }[/math] where [math]\displaystyle{ A_i \subseteq B_i }[/math], and the [math]\displaystyle{ B_i }[/math] form an upward-closed family in a ground set [math]\displaystyle{ X }[/math]. Then there is some [math]\displaystyle{ x \in X }[/math] belonging to at least half of the [math]\displaystyle{ A_i }[/math].

Relationships between them

Various implications between these conjectures have been shown. We have:

• injection-to-superset implies uniform weighted FUNC;
• uniform weighted FUNC implies weighted FUNC;
• uniform weighted FUNC implies injection-to-larger.

(These implications are only relevant in so far as they restrict the search space for counterexamples to the weaker conjectures.)

Discussion on Gowers's Weblog

• Introductory post
• FUNC1
• FUNC2
• FUNC3

General proof strategies

Use a weight function

Find set configurations that imply FUNC

Links

• A good survey article