Frankl's union-closed conjecture: Difference between revisions
No edit summary |
List a few partial results. |
||
| Line 2: | Line 2: | ||
A family <math>\mathcal{A}</math> of sets is called <em>union closed</em> 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. | A family <math>\mathcal{A}</math> of sets is called <em>union closed</em> 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. | ||
<h2>Definitions</h2> | |||
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 <em>separating</em> 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). | |||
<h2>Partial results</h2> | |||
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 2m</math>, assuming <math>\mathcal{A}</math> is separating; or | |||
* <math>\lvert A \rvert \leq 2</math> for some <math>A \in \mathcal{A}</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>. | |||
<h2>Discussion on Gowers's Weblog</h2> | <h2>Discussion on Gowers's Weblog</h2> | ||
Revision as of 12:49, 30 January 2016
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 2m }[/math], assuming [math]\displaystyle{ \mathcal{A} }[/math] is separating; or
- [math]\displaystyle{ \lvert A \rvert \leq 2 }[/math] for some [math]\displaystyle{ A \in \mathcal{A} }[/math].
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].
Discussion on Gowers's Weblog
Links
- A good survey article
