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

General proof strategies

• Find a strengthened hypothesis that permits an inductive proof
• Find set configurations that imply FUNC

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

By recursively applying FUNC to [math]\displaystyle{ \mathcal{A}_x }[/math] for abundant [math]\displaystyle{ x }[/math], this can be seen to be equivalent to FUNC.

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

Structural theory

There are various ways to investigate the structure of a union-closed family or of a finite lattice.

• Horn clause formulation

Important examples and constructions of examples

Most basic:

• Power sets [math]\displaystyle{ \mathcal{A} = 2^X }[/math]
• Total orders: let [math]\displaystyle{ \mathcal{A} = \{1,12,123,\ldots,1\ldots n\} }[/math]
• Combinations of the previous two, as in the Duffus-Sands example

More sophisticated:

• Renaud-Sarvate example
• Examples based on Steiner systems

General constructions:

• fibre bundle construction

Discussion on Gowers's Weblog

• Introductory post
• FUNC1
• FUNC2
• FUNC3
• FUNC4

Links

• A good survey article