# Difference between revisions of "Frankl's union-closed conjecture"

A family $\mathcal{A}$ of sets is called union closed if $A\cup B\in\mathcal{A}$ whenever $A\in\mathcal{A}$ and $B\in\mathcal{A}$. Frankl's conjecture is a disarmingly simple one: if $\mathcal{A}$ 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 $x$ in the ground set, write $\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\}$.

We say that $\mathcal{A}$ 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 $\mathcal{A}_x$ are all distinct).

## Partial results

Let $\mathcal{A}$ 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:

• $m \leq 12$; or
• $n \leq 50$; or
• $n \geq \frac23 2^m$; or
• $n \leq 4m-2$, assuming $\mathcal{A}$ is separating; or
• $0 \lt \lvert A \rvert \leq 2$ for some $A \in \mathcal{A}$.
• $\mathcal{A}$ contains three sets of three elements that are all subsets of the same five element set.

If $\mathcal{A}$ is union-closed then there is an element $x$ such that $\lvert \mathcal{A}_x \rvert \geq \frac{n-1}{\log_2 n}$. For large $n$ this can be improved slightly to $\frac{2.4 n}{\log_2 n}$.

## The m=13 case

Here is my work on the m=13 case of 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 $x \in X$ and some injection $\phi : \mathcal{A}_{\bar{x}} \to \mathcal{A}_x$ such that $A \subset \phi(A)$ for all $A$? This was answered in the negative.

##### Injection-to-larger

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

##### Weighted FUNC

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

##### Uniform weighted FUNC

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

This is equivalent to the conjecture that there is some $x$ that is abundant in every upper set in $\mathcal{A}$.

This conjecture is false.

##### FUNC for subsets

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

By recursively applying FUNC to $\mathcal{A}_x$ for abundant $x$, 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 $[A_i, B_i] = \{S : A_i \subseteq S \subseteq B_i\}$ where $A_i \subseteq B_i$, and the $B_i$ form an upward-closed family in a ground set $X$. Then there is some $x \in X$ belonging to at least half of the $A_i$.

##### Strengthenings involving two families

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

##### Abundant pairs

For any union-closed family $\mathcal{A}$ on a ground set $X$ with at least two elements there are two distinct elements $x, y\in X$ such that the number of sets $A \in \mathcal A$ containing neither $x$ nor $y$ is not larger than the number of sets $A \in \mathcal A$ containing both $x$ and $y$. 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.

## Important examples and constructions of examples

Most basic:

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

More sophisticated:

General constructions:

• fibre bundle construction
• Hom-lattices $\mathrm{Hom}(\mathcal{P},\mathcal{A})$, for $\mathcal{P}$ a finite poset and $\mathcal{A}$ a finite lattice. For example for $\mathcal{P} = \{0,1\}$, the hom-lattice is the interval lattice of $\mathcal{A}$.