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

The m=13 case

Here is my work on the m=13 case of FUNC

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

Strengthenings involving two families

One can look for strengthening that apply to pairs of set systems [math]\displaystyle{ \mathcal{A},\mathcal{B} }[/math] that satisfy some condition which specializes to union-closure in the case [math]\displaystyle{ \mathcal{A}=\mathcal{B} }[/math]. The idea is that it may be easier to get an induction argument to work.

Abundant pairs

For any union-closed family [math]\displaystyle{ \mathcal{A} }[/math] on a ground set [math]\displaystyle{ X }[/math] with at least two elements there are two distinct elements [math]\displaystyle{ x, y\in X }[/math] such that the number of sets [math]\displaystyle{ A \in \mathcal A }[/math] containing neither [math]\displaystyle{ x }[/math] nor [math]\displaystyle{ y }[/math] is not larger than the number of sets [math]\displaystyle{ A \in \mathcal A }[/math] containing both [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math]. Suggested here.

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
• Lattice approach

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
• Hom-lattices [math]\displaystyle{ \mathrm{Hom}(\mathcal{P},\mathcal{A}) }[/math], for [math]\displaystyle{ \mathcal{P} }[/math] a finite poset and [math]\displaystyle{ \mathcal{A} }[/math] a finite lattice. For example for [math]\displaystyle{ \mathcal{P} = \{0,1\} }[/math], the hom-lattice is the interval lattice of [math]\displaystyle{ \mathcal{A} }[/math].

Discussion on Gowers's Weblog

• Introductory post
• FUNC1
• FUNC2
• FUNC3
• FUNC4

Links

• A good survey article