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

TobiasFritz (Talk | contribs) (→Strengthenings) |
Tomtom2357 (Talk | contribs) (Added a new section on the m=13 case) |
||

Line 18: | Line 18: | ||

If <math>\mathcal{A}</math> is union-closed then there is an element <math>x</math> such that <math>\lvert \mathcal{A}_x \rvert \geq \frac{n-1}{\log_2 n}</math>. For large <math>n</math> this can be improved slightly to <math>\frac{2.4 n}{\log_2 n}</math>. | If <math>\mathcal{A}</math> is union-closed then there is an element <math>x</math> such that <math>\lvert \mathcal{A}_x \rvert \geq \frac{n-1}{\log_2 n}</math>. For large <math>n</math> this can be improved slightly to <math>\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 == | == General proof strategies == |

## Latest revision as of 01:38, 27 October 2016

A family [math]\mathcal{A}[/math] of sets is called *union closed* if [math]A\cup B\in\mathcal{A}[/math] whenever [math]A\in\mathcal{A}[/math] and [math]B\in\mathcal{A}[/math]. Frankl's conjecture is a disarmingly simple one: if [math]\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.

## Contents

## Definitions

For any [math]x[/math] in the ground set, write [math]\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\}[/math].

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

## Partial results

Let [math]\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]m \leq 12[/math]; or
- [math]n \leq 50[/math]; or
- [math]n \geq \frac23 2^m[/math]; or
- [math]n \leq 4m-2[/math], assuming [math]\mathcal{A}[/math] is separating; or
- [math]0 \lt \lvert A \rvert \leq 2[/math] for some [math]A \in \mathcal{A}[/math].
- [math]\mathcal{A}[/math] contains three sets of three elements that are all subsets of the same five element set.

If [math]\mathcal{A}[/math] is union-closed then there is an element [math]x[/math] such that [math]\lvert \mathcal{A}_x \rvert \geq \frac{n-1}{\log_2 n}[/math]. For large [math]n[/math] this can be improved slightly to [math]\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]x \in X[/math] and some injection [math]\phi : \mathcal{A}_{\bar{x}} \to \mathcal{A}_x[/math] such that [math]A \subset \phi(A)[/math] for all [math]A[/math]? This was answered in the negative.

##### Injection-to-larger

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

##### Weighted FUNC

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

##### Uniform weighted FUNC

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

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

This conjecture is false.

##### FUNC for subsets

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

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

##### Strengthenings involving two families

One can look for strengthening that apply to pairs of set systems [math]\mathcal{A},\mathcal{B}[/math] that satisfy some condition which specializes to union-closure in the case [math]\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]\mathcal{A}[/math] on a ground set [math]X[/math] with at least two elements there are two distinct elements [math]x, y\in X[/math] such that the number of sets [math]A \in \mathcal A[/math] containing neither [math]x[/math] nor [math]y[/math] is not larger than the number of sets [math]A \in \mathcal A[/math] containing both [math]x[/math] and [math]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.

## Important examples and constructions of examples

Most basic:

- Power sets [math]\mathcal{A} = 2^X[/math]
- Total orders: let [math]\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]\mathrm{Hom}(\mathcal{P},\mathcal{A})[/math], for [math]\mathcal{P}[/math] a finite poset and [math]\mathcal{A}[/math] a finite lattice. For example for [math]\mathcal{P} = \{0,1\}[/math], the hom-lattice is the interval lattice of [math]\mathcal{A}[/math].

## Discussion on Gowers's Weblog

## Links

- A good survey article