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]?
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 weighted FUNC (relevant because it restricts the search space for counterexamples to weighted FUNC);
- weighted FUNC implies uniform weighted FUNC;
- weighted FUNC implies injection-to-larger.
Discussion on Gowers's Weblog
General proof strategies
Find set configurations that imply FUNC
Links
- A good survey article
