Polymath Wiki - User contributions [en]

Linear norm grant acknowledgments

2017-12-29T21:36:48Z

TobiasFritz:

Participants should be arranged in alphabetical order of surname.

== Participants and contact information ==

Caution: this list may be incomplete. Participants who have made significant contributions to the project (on par with a co-author on a traditional mathematical research paper) should add themselves to this list, or email tao@math.ucla.edu if they are unable to do so directly. Participants who have made auxiliary contributions to the project (on par with those mentioned in an Acknowledgments section in a traditional paper) should add themselves instead to the list at the bottom of the page.

* Tobias Fritz, MPI MIS, [http://personal-homepages.mis.mpg.de/fritz/]
* Siddhartha Gadgil, Indian Institute of Science, Bangalore [http://math.iisc.ac.in/~gadgil/]
* Apoorva Khare, Indian Institute of Science, Bangalore, and the Analysis and Probability Research Group, Bangalore [http://www.math.iisc.ac.in/~khare/]
* Pace Nielsen, BYU, [https://math.byu.edu/~pace/]
* Lior Silberman, UBC, [https://www.math.ubc.ca/~lior/]
* Terence Tao, UCLA, [http://www.math.ucla.edu/~tao]

=== Grant information ===

* Apoorva Khare was supported by a Young Investigator Award from the Infosys Foundation.
* Pace Nielsen was supported by NSA grant H98230-16-1-0048.
* Lior Silberman was supported by an NSERC Discovery grant.
* Terence Tao was supported by a Simons Investigator grant, the James and Carol Collins Chair, the Mathematical Analysis & Application Research Fund Endowment, and by NSF grant DMS-1266164.

=== Other acknowledgments ===

Other contributors to the project include Sean Eberhard, Tobias Hartnick, Chris Jerdonek, Antonio Machiavelo, Andy Putman, Will Sawin, Alexander Shamov, and David Speyer.

Thanks to Michael Nielsen for hosting the polymath wiki for this project.

User:TobiasFritz

2017-12-23T10:56:32Z

TobiasFritz: Created page with "I have been active at * FUNC * Linear norm"

I have been active at

* [[Frankl's_union-closed_conjecture|FUNC]]
* [[Linear_norm|Linear norm]]

Linear norm grant acknowledgments

2017-12-23T10:01:16Z

TobiasFritz:

Participants should be arranged in alphabetical order of surname.

== Participants and contact information ==

Caution: this list may be incomplete. Participants who have made significant contributions to the project (on par with a co-author on a traditional mathematical research paper) should add themselves to this list, or email tao@math.ucla.edu if they are unable to do so directly. Participants who have made auxiliary contributions to the project (on par with those mentioned in an Acknowledgments section in a traditional paper) should add themselves instead to the list at the bottom of the page.

* Tobias Fritz, MPI MIS, [http://personal-homepages.mis.mpg.de/fritz/]
* Pace Nielsen, BYU, [https://math.byu.edu/~pace/]
* Lior Silberman, UBC, [https://www.math.ubc.ca/~lior/]
* Terence Tao, UCLA, [http://www.math.ucla.edu/~tao]

=== Grant information ===

* Pace Nielsen was supported by NSA grant H98230-16-1-0048.
* Lior Silberman was supported by an NSERC Discovery grant.
* Terence Tao was supported by a Simons Investigator grant, the James and Carol Collins Chair, the Mathematical Analysis & Application Research Fund Endowment, and by NSF grant DMS-1266164.

=== Other acknowledgments ===

Other contributors to the project include ....

Thanks to Michael Nielsen for hosting the polymath wiki for this project.

Linear norm

2017-12-21T21:28:25Z

TobiasFritz: /* Corollaries */

This is the wiki page for understanding ''seminorms of linear growth'' on a group <math>G</math> (such as the free group on two generators). These are functions <math>\| \|: G \to [0,+\infty)</math> that obey the triangle inequality

:<math>\|xy\| \leq \|x\| + \|y\| \quad (1)</math>

and the linear growth condition

:<math> \|x^n \| = |n| \|x\| \quad (2) </math>

for all <math>x,y \in G</math> and <math>n \in {\bf Z}</math>.

We use the usual group theory notations <math>x^y := yxy^{-1}</math> and <math>[x,y] := xyx^{-1}y^{-1}</math>.

== Threads ==

* [https://terrytao.wordpress.com/2017/12/16/bi-invariant-metrics-of-linear-growth-on-the-free-group/ https://terrytao.wordpress.com/2017/12/16/bi-invariant-metrics-of-linear-growth-on-the-free-group/], Dec 16 2017.
* [https://terrytao.wordpress.com/2017/12/19/bi-invariant-metrics-of-linear-growth-on-the-free-group-ii/ Bi-invariant metrics of linear growth on the free group, II], Dec 19 2017.

== Key lemmas ==

Henceforth we assume we have a seminorm <math>\| \|</math> of linear growth. The letters <math>s,t,x,y,z,w</math> are always understood to be in <math>G</math>, and <math>i,j,n,m</math> are always understood to be integers.

From (2) we of course have
:<math> \|x^{-1} \| = \| x\| \quad (3)</math>

'''Lemma 1'''. If <math>x</math> is conjugate to <math>y</math>, then <math>\|x\| = \|y\|</math>.

'''Proof'''. By hypothesis, <math>x = zyz^{-1}</math> for some <math>z</math>, thus <math>x^n = z y^n z^{-1}</math>, hence by the triangle inequality

:<math> n \|x\| = \|x^n \| \leq \|z\| + n \|y\| + \|z^{-1} \|</math>

for any <math>n \geq 1</math>. Dividing by <math>n</math> and taking limits we conclude that <math>\|x\| \leq \|y\|</math>. Similarly <math>\|y\| \leq \|x\|</math>, giving the claim. <math>\Box</math>

An equivalent form of the lemma is that

:<math> \|xy\| = \|yx\| \quad (4).</math>

We can generalise Lemma 1:

'''Lemma 2'''. If <math>x^i</math> is conjugate to <math>wy</math> and <math>x^j</math> is conjugate to <math>zw^{-1}</math>, then <math> \|x\| \leq \frac{1}{|i+j|} ( \|w\| + \|z\| )</math>.

'''Proof'''. By hypothesis, <math>x^i = s wy s^{-1}</math> and <math>x^j = t zw^{-1} t^{-1}</math> for some <math>s,t</math>. For any natural number <math>n</math>, we then have

:<math> x^{in} x^{jn} = s wy \dots wy s^{-1} t zw^{-1} \dots zw^{-1} t^{-1}</math>

where the terms <math>wy, zw</math> are each repeated <math>n</math> times. By Lemma 1, conjugation by <math>w</math> does not change the norm. From many applications of this and the triangle inequality, we conclude that

:<math> |i+j| n \|x\| = \| x^{in} x^{jn} \| \leq \|s\| + n \|y\| + \|s^{-1} t\| + n \|z\| + \|t^{-1}\|.</math>

Dividing by <math>n</math> and sending <math>n \to \infty</math>, we obtain the claim. <math>\Box</math>

== Corollaries ==

'''Corollary 0'''. The eight commutators <math>[x^{\pm 1}, y^{\pm 1}], [y^{\pm 1}, x^{\pm 1}]</math> all have the same norm.

'''Proof'''. Each of these commutators is conjugate to either <math>[x,y]</math> or its inverse. <math>\Box</math>

'''Corollary 1'''. The function <math>n \mapsto \|x^n y\|</math> is convex in <math>n</math>.

'''Proof'''. <math>x^n y</math> is conjugate to <math>x (x^{n-1} y)</math> and to <math>(x^{n+1} y) x^{-1}</math>, hence by Lemma 2
:<math>\| x^n y \| \leq \frac{1}{2} (\| x^{n-1} y \| + \| x^{n+1} y \|),</math>
giving the claim. <math>\Box</math>

'''Corollary 2'''. For any <math>k \geq 1</math>, one has
:<math>\| [x,y] \| \leq \frac{1}{2k+2} (\| [x^{-1},y^{-1}]^k x^{-1} \| + \| [x,y]^k x \|).</math>
Thus for instance
:<math>\| [x,y] \| \leq \frac{1}{4} (\| [x^{-1},y^{-1}] x^{-1} \| + \| [x,y] x \|).</math>

'''Proof'''. <math>[x,y]^{k+1}</math> is conjugate both to <math>x(y[x^{-1},y^{-1}]^k x^{-1}y^{-1})</math> and to <math>(y^{-1} [x,y]^k xy)x^{-1}</math>, hence by Lemma 2
:<math> \| [x,y] \| \leq \frac{1}{2k+2} ( \| y[x^{-1},y^{-1}]^k x^{-1} \| + \| (y^{-1} [x,y]^k xy)x^{-1}\|)</math>
giving the claim by Lemma 1. <math>\Box</math>

'''Corollary 3'''. One has
:<math> \|[x,y]^2 x\| \leq \frac{1}{2} ( \| x y^{-1} [x,y] \| + \| xy [x,y] \| ).</math>

'''Proof'''. <math>[x,y]^2 x</math> is conjugate both to <math>y (x^{-1} y^{-1} [x,y] x^2)</math> and to <math>(x[x,y]xyx^{-1}) y^{-1}</math>, hence by Lemma 2
:<math> \displaystyle \|[x,y]^2 x\| \leq \frac{1}{2} ( \|x^{-1} y^{-1} [x,y] x^2\| + \|x[x,y]xyx^{-1}\|)</math>
giving the claim by Lemma 1. <math>\Box</math>

'''Corollary 4'''. One has
:<math>\| [x,y] x\| \leq \frac{1}{4} ( \| x^2 y [x,y] \| + \| xy^{-1} x [x,y] \| ).</math>

'''Proof'''. <math>([x,y] x)^2</math> is conjugate both to <math>y^{-1} (x [x,y] x^2 y x^{-1})</math> and to <math>(x^{-1} y^{-1} x [x,y] x^2) y</math>, hence Lemma 2
:<math>\| [x,y] x\| \leq \frac{1}{4} ( \| x [x,y] x^2 y x^{-1} \| + \| x^{-1} y^{-1} x [x,y] x^2 \| ),</math>
giving the claim by Lemma 1. <math>\Box</math>

'''Corollary 5'''. One has
:<math> \|[x,y] x\| \leq \|x\| + \frac{1}{2} \| [x^2, y] \|</math>.

'''Proof'''. <math>[x,y]x</math> is conjugate to both <math>x [x^{-2},y^{-1}]</math> and to <math>(y^{-1} x^2 y) x^{-1}</math>, hence by Lemma 2
:<math>\| [x,y] x\| \leq \frac{1}{2} ( \| [x^{-2}, y^{-1}] \| + \| y^{-1} x^2 y \| ),</math>
giving the claim by Lemma 1 and Corollary 0. <math>\Box</math>

'''Corollary 6'''. One has
:<math> \| [x,y]\| \leq \frac{1}{4} ( \| x\| + \| [x^2,y] \| + \| [x,y] x\| ) </math>.

'''Proof'''. From Lemma 2 we have
:<math> \| [x,y] \| \leq \frac{1}{4} ( \| x^{-1} [x,y]^2 \| + \| [x,y] x \| ).</math>
Since <math>x^{-1} [x,y]^2</math> is conjugate to <math>(yx^{-1} y^{-1}) (xyx^{-2} y^{-1} x)</math>, we have
:<math> \| x^{-1} [x,y]^2 \| \leq \| yx^{-1} y^{-1} \| fis + \|xyx^{-2} y^{-1} x\|</math>
and the claim follows from Lemma 1 and (3). <math>\Box</math>

'''Corollary 7'''. For any <math>m,k \geq 1</math>, one has
:<math> \| x^m [x,y]^k \| \leq \frac{1}{2} ( \| x^{m-1} [x,y]^k \| + \|x^{m+1} [x,y]^{k-1} \| )</math>.

'''Proof'''. <math>x^m[x,y]^k</math> is trivially conjugate to <math>x(x^{m-1}[x,y]^k)</math> and conjugate to <math>(y^{-1}x^m[x,y]^{k-1}xy)x^{-1}</math>. Hence by Lemma 2,
:<math>\| x^m[x,y]^k \| \leq \frac{1}{2} ( \| x^{m-1}[x,y]^k \| + \| y^{-1}x^m[x,y]^{k-1}xy \| ) = \frac{1}{2} ( \| x^{m-1}[x,y]^k \| + \| x^{m+1}[x,y]^{k-1} \|),</math>
where the final equation is by conjugation invariance.

'''Corollary 8'''. One has <math>\|x\| \leq \| [x,y] x \|</math>.

'''Proof'''. <math>x</math> is equal to both <math> (x^2 y x y^{-1} x^{-2}) (x^2 y x^{-1} y^{-1} x^{-1})</math> and to <math>(x^2 y x^{-1} y^{-1} x^{-1})^{-1} (x^2 y x^{-1} y^{-1})</math>, hence by Lemma 2
:<math> \|x\| \leq \frac{1}{2} ( \| x^2 y x y^{-1} x^{-2} \| + \|x^2 y x^{-1} y^{-1}\| ).</math>
By Lemma 1, the RHS is <math>\frac{1}{2} \|x\| + \frac{1}{2} \| [x,y] x \|</math>, and the claim follows. <math>\Box</math>

== Iterations ==

Call a pair of real numbers <math>(\alpha,\beta)</math> '''admissible''' if one has the inequality

:<math> \| [x,y] \| \leq \alpha \|x\| + \beta \|y \|</math>

for all <math>x,y</math>. Clearly the set of admissible pairs is closed and convex, and if <math>(\alpha,\beta)</math> is admissible then so is <math>(\alpha',\beta')</math> for any <math>\alpha' \geq \alpha, \beta' \geq \beta</math>. From Corollary 0 we also see that the set is symmetric: <math>(\alpha,\beta)</math> is admissible if and only if <math>(\beta,\alpha)</math> is.

Writing <math>[x,y] = y^x y^{-1}</math> we see that <math>(0,2)</math> is admissible, and similarly so is <math>(0,2)</math>.

'''Proposition 1'''. If <math>(\alpha,\beta)</math> is admissible, then so is <math>(\frac{\alpha+1}{2}, \frac{\beta}{4})</math>.

'''Proof'''. From Corollary 5 and hypothesis one has
:<math>\| [x,y] x\| \leq \|x\| + \frac{1}{2} ( \alpha \|x^2\| + \beta \|y\| ) = (\alpha+1) \|x\| + \frac{\beta}{2} \|y\|</math>
and hence also
:<math>\| [x^{-1},y^{-1}] x^{-1}\| \leq (\alpha+1) \|x\| + \frac{\beta}{2} \|y\|.</math>
From Corollary 2 we thus have
:<math>\| [x,y]\| \leq \frac{\alpha+1}{2} \|x\| + \frac{\beta}{4} \|y\|.</math>

The map <math>(\alpha,\beta) \mapsto (\frac{\alpha+1}{2}, \frac{\beta}{4})</math> is a contraction with fixed point <math>(1,0)</math>. Thus

:<math> \|[x,y]\| \leq \|x\| \quad (4)</math>.

From symmetry we also see that if <math>(\alpha,\beta)</math> is admissible, then so is (\frac{\beta+1}{2}, \frac{\alpha}{4})</math>. The map <math>(\alpha,\beta) \mapsto (\frac{\beta+1}{2}, \frac{\alpha}{4})</math> is a contraction with fixed point (4/7,1/7), thus

:<math> \|[x,y]\| \leq \frac{4}{7} \|x\| + \frac{1}{7} \|y\| </math>.

Lattice approach

2016-03-21T09:03:10Z

TobiasFritz:

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices and/or finding suitably large subsemilattices over which one has good control. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's estimates ==

The following 'relative' Knill-type inequalities are abstract versions of the techniques of [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik].

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result. An alternative point of view on this estimate is that it lower bounds the size of the interval <math>[A,B]</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Wójcik's fibre bundle decomposition ==

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice <math>\mathcal{A}'\subseteq\mathcal{A}</math> that decomposes into a fibre bundle. His construction is an instance of the following.

'''Lemma:''' Let <math>\mathcal{B}\subseteq\mathcal{A}</math> be a subsemilattice and <math>X\in\mathcal{A}</math> such that <math>-\vee X:\mathcal{B}\to\mathcal{A}</math> is injective. Then the intervals <math>[B,B\vee X]</math> are disjoint, and <math>\mathcal{A}':= \bigcup_B [B,B\vee X]</math> decomposes into a fibre bundle over <math>\mathcal{B}</math>.

'''Proof:''' The intervals are disjoint since if <math>A\in [B,B\vee X]\cap [C,C\vee X]</math>, then <math>B\vee X = A\vee X = C\vee X</math>, and therefore <math>B = C</math> by assumption. So concerning the bundle, the fibre over <math>C\in\mathcal{B}</math> is precisely the interval <math>\mathcal{B}_C := [C,C\vee X]</math>, and the transition map <math>\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]</math> for <math>B\leq C</math> in <math>\mathcal{B}</math> is given by <math>\phi_{B,C}(A) := A\vee C</math>. This is join-preserving and satisfies the required cocycle condition <math>\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}</math> for <math>B\leq C\leq D</math>. It is straightforward to check that the inclusion map of the bundle <math>\mathcal{A}':=\int\mathcal{B}</math> into <math>\mathcal{A}</math> is a semilattice homomorphism. QED.

When applying this, it is likely relevant to have a lower bound on the size of this subsemilattice in order to guarantee that it is not too small relative to <math>\mathcal{A}</math>. The estimate
<math>\sum_{B\in\mathcal{B}} |[B,B\vee X]| \geq \sum_B 2^{\frac{|\uparrow B| - |\uparrow(B\vee X)|}{m}} \geq 2^{-\frac{|\uparrow X|}{m}} \sum_B 2^{\frac{|\uparrow B|}{m}}</math>
seems to be part of what Wójcik uses. So the challenge is to make <math>\mathcal{B}</math> and the <math>\uparrow B</math>'s large, while keeping <math>\uparrow X</math> small.

The way that Wójcik achieves this is to first fix <math>X</math> in a clever way. He then considers the join-irreducibles <math>\mathcal{J}_X</math> in the upset <math>\uparrow X</math>, and then chooses for every <math>J\in\mathcal{J}_X</math> some join-irreducible <math>G(J)</math> in <math>\mathcal{A}</math> with <math>J = G(J)\vee X</math>. Then <math>\mathcal{B}</math> is taken to be the semilattice generated by the <math>G(J)</math>'s. Using a [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal-Katona] type bound (Theorem 3.1) completes his arguments. But more on this some other time.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

The meaning of "join-irreducible" here is that <math>A</math> is join-irreducible if <math>A = B\vee C</math> implies <math>A=B</math> or <math>A=C</math>. This condition seems a bit artificial, since the more natural notion of join-irreducibility would be to require that if <math>A</math> is a join of an arbitrary collection of elements, then <math>A</math> itself must be a member of this collection. While this definition essentially coincides with the earlier one in case of a lattice, in non-lattice posets there are in general fewer join-irreducible elements with the latter definition. This results in simple counterexamples to Poset FUNC with the latter definition, such as taking the power set of a 5-set and removing all the 2-sets.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-21T03:36:26Z

TobiasFritz: clarified what join-irreducible means here

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's estimates ==

The following 'relative' Knill-type inequalities are abstract versions of the techniques of [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik].

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result. An alternative point of view on this estimate is that it lower bounds the size of the interval <math>[A,B]</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Wójcik's fibre bundle decomposition ==

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice <math>\mathcal{A}'\subseteq\mathcal{A}</math> that decomposes into a fibre bundle. His construction is an instance of the following.

'''Lemma:''' Let <math>\mathcal{B}\subseteq\mathcal{A}</math> be a subsemilattice and <math>X\in\mathcal{A}</math> such that <math>-\vee X:\mathcal{B}\to\mathcal{A}</math> is injective. Then the intervals <math>[B,B\vee X]</math> are disjoint, and <math>\mathcal{A}':= \bigcup_B [B,B\vee X]</math> decomposes into a fibre bundle over <math>\mathcal{B}</math>.

'''Proof:''' The intervals are disjoint since if <math>A\in [B,B\vee X]\cap [C,C\vee X]</math>, then <math>B\vee X = A\vee X = C\vee X</math>, and therefore <math>B = C</math> by assumption. So concerning the bundle, the fibre over <math>C\in\mathcal{B}</math> is precisely the interval <math>\mathcal{B}_C := [C,C\vee X]</math>, and the transition map <math>\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]</math> for <math>B\leq C</math> in <math>\mathcal{B}</math> is given by <math>\phi_{B,C}(A) := A\vee C</math>. This is join-preserving and satisfies the required cocycle condition <math>\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}</math> for <math>B\leq C\leq D</math>. It is straightforward to check that the inclusion map of the bundle <math>\mathcal{A}':=\int\mathcal{B}</math> into <math>\mathcal{A}</math> is a semilattice homomorphism. QED.

When applying this, it is likely relevant to have a lower bound on the size of this subsemilattice in order to guarantee that it is not too small relative to <math>\mathcal{A}</math>. The estimate
<math>\sum_{B\in\mathcal{B}} |[B,B\vee X]| \geq \sum_B 2^{\frac{|\uparrow B| - |\uparrow(B\vee X)|}{m}} \geq 2^{-\frac{|\uparrow X|}{m}} \sum_B 2^{\frac{|\uparrow B|}{m}}</math>
seems to be part of what Wójcik uses. So the challenge is to make <math>\mathcal{B}</math> and the <math>\uparrow B</math>'s large, while keeping <math>\uparrow X</math> small.

The way that Wójcik achieves this is to first fix <math>X</math> in a clever way. He then considers the join-irreducibles <math>\mathcal{J}_X</math> in the upset <math>\uparrow X</math>, and then chooses for every <math>J\in\mathcal{J}_X</math> some join-irreducible <math>G(J)</math> in <math>\mathcal{A}</math> with <math>J = G(J)\vee X</math>. Then <math>\mathcal{B}</math> is taken to be the semilattice generated by the <math>G(J)</math>'s. Using a [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal-Katona] type bound (Theorem 3.1) completes his arguments. But more on this some other time.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

The meaning of "join-irreducible" here is that <math>A</math> is join-irreducible if <math>A = B\vee C</math> implies <math>A=B</math> or <math>A=C</math>. This condition seems a bit artificial, since the more natural notion of join-irreducibility would be to require that if <math>A</math> is a join of an arbitrary collection of elements, then <math>A</math> itself must be a member of this collection. While this definition essentially coincides with the earlier one in case of a lattice, in non-lattice posets there are in general fewer join-irreducible elements with the latter definition. This results in simple counterexamples to Poset FUNC with the latter definition, such as taking the power set of a 5-set and removing all the 2-sets.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-19T19:43:26Z

TobiasFritz: /* Wójcik's fibre bundle decomposition */

Lattice approach

2016-03-19T18:16:45Z

TobiasFritz: /* Wójcik's fibre bundle decomposition */

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's estimates ==

The following 'relative' Knill-type inequalities are abstract versions of the techniques of [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik].

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result. An alternative point of view on this estimate is that it lower bounds the size of the interval <math>[A,B]</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Wójcik's fibre bundle decomposition ==

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice <math>\mathcal{A}'\subseteq\mathcal{A}</math> that decomposes into a fibre bundle. His construction is an instance of the following.

'''Lemma:''' Let <math>\mathcal{B}\subseteq\mathcal{A}</math> be a subsemilattice and <math>X\in\mathcal{A}</math> such that <math>-\vee X:\mathcal{B}\to\mathcal{A}</math> is injective. Then the intervals <math>[B,B\vee X]</math> are disjoint, and <math>\mathcal{A}':= \bigcup_B [B,B\vee X]</math> decomposes into a fibre bundle over <math>\mathcal{B}</math>.

'''Proof:''' The intervals are disjoint since if <math>A\in [B,B\vee X]\cap [C,C\vee X]</math>, then <math>B\vee X = A\vee X = C\vee X</math>, and therefore <math>B = C</math> by assumption. So concerning the bundle, the fibre over <math>C\in\mathcal{B}</math> is precisely the interval <math>\mathcal{B}_C := [C,C\vee X]</math>, and the transition map <math>\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]</math> for <math>B\leq C</math> in <math>\mathcal{B}</math> is given by <math>\phi_{B,C}(A) := A\vee C</math>. This is join-preserving and satisfies the required cocycle condition <math>\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}</math> for <math>B\leq C\leq D</math>. It is straightforward to check that the inclusion map of the bundle <math>\mathcal{A}':=\int\mathcal{B}</math> into <math>\mathcal{A}</math> is a semilattice homomorphism. QED.

When applying this, it is likely relevant to have a lower bound on the size of this subsemilattice in order to guarantee that it is not too small relative to <math>\mathcal{A}</math>. The estimate
<math>\sum_{B\in\mathcal{B}} |[B,B\vee X]| \geq \sum_B 2^{\frac{|\uparrow B| - |\uparrow(B\vee X)|}{m}} \geq 2^{\frac{-|\uparrow X|}{m}} \sum_B 2^{\frac{|\uparrow B|}{m}}</math>
seems to be part of what Wójcik uses. So the challenge is to make <math>\mathcal{B}</math> and the <math>\uparrow B</math>'s large, while keeping <math>\uparrow X</math> small.

The way that Wójcik achieves this is to first fix <math>X</math> in a clever way. He then considers the join-irreducibles <math>\mathcal{J}_X</math> in the upset <math>\uparrow X</math>, and then chooses for every <math>J\in\mathcal{J}_X</math> some join-irreducible <math>G(J)</math> in <math>\mathcal{A}</math> with <math>J = G(J)\vee X</math>. Then <math>\mathcal{B}</math> is taken to be the semilattice generated by the <math>G(J)</math>'s. Using a [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal-Katona] type bound (Theorem 3.1) completes his arguments. But more on this some other time.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-19T18:13:49Z

TobiasFritz: /* Wójcik's estimates */

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's estimates ==

The following 'relative' Knill-type inequalities are abstract versions of the techniques of [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik].

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result. An alternative point of view on this estimate is that it lower bounds the size of the interval <math>[A,B]</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Wójcik's fibre bundle decomposition ==

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice <math>\mathcal{A}'\subseteq\mathcal{A}</math> that decomposes into a fibre bundle. His construction is an instance of the following.

'''Lemma:''' Let <math>\mathcal{B}\subseteq\mathcal{A}</math> be a subsemilattice and <math>X\in\mathcal{A}</math> such that <math>-\vee X:\mathcal{B}\to\mathcal{A}</math> is injective. Then the intervals <math>[B,B\vee X]</math> are disjoint, and <math>\mathcal{A}':= \bigcup_B [B,B\vee X]</math> decomposes into a fibre bundle over <math>\mathcal{B}</math>.

'''Proof:''' The intervals are disjoint since if <math>A\in [B,B\vee X]\cap [C,C\vee X]</math>, then <math>B\vee X = A\vee X = C\vee X</math>, and therefore <math>B = C</math> by assumption. So concerning the bundle, the fibre over <math>C\in\mathcal{B}</math> is precisely the interval <math>\mathcal{B}_C := [C,C\vee X]</math>, and the transition map <math>\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]</math> for <math>B\leq C</math> in <math>\mathcal{B}</math> is given by <math>\phi_{B,C}(A) := A\vee C</math>. This is join-preserving and satisfies the required cocycle condition <math>\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}</math> for <math>B\leq C\leq D</math>. It is straightforward to check that the inclusion map of the bundle <math>\mathcal{A}':=\int\mathcal{B}</math> into <math>\mathcal{A}</math> is a semilattice homomorphism. QED.

When applying this, it is likely relevant to have a lower bound on the size of this subsemilattice in order to guarantee that it is not too small relative to <math>\mathcal{A}</math>. The estimate
<math>\sum_{B\in\mathcal{B}} |[B,B\vee X]| \geq \sum_B 2^{c(B,B\vee X)}\geq \sum_B 2^{\frac{|\uparrow B| - |\uparrow(B\vee X)|}{m}} \geq 2^{\frac{-|\uparrow X|}{m}} \sum_B 2^{\frac{|\uparrow B|}{m}}</math>
seems to be part of what Wójcik uses. So the challenge is to make <math>\mathcal{B}</math> and the <math>\uparrow B</math>'s large, while keeping <math>\uparrow X</math> small.

The way that Wójcik achieves this is to first fix <math>X</math>, consider the join-irreducibles <math>\mathcal{J}_X</math> in the upset <math>\uparrow X</math>, and then choose for every <math>J\in\mathcal{J}_X</math> some join-irreducible <math>G(J)</math> in <math>\mathcal{A}</math> with <math>J = G(J)\vee X</math>. He then takes <math>\mathcal{B}</math> to be the semilattice generated by the <math>G(J)</math>'s. Choosing <math>X</math> in a clever way and using a [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal-Katona] type bound (Theorem 3.1) completes his arguments. But more on this some other time.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-19T18:10:39Z

TobiasFritz: /* Wójcik's fibre bundle decomposition */

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's estimates ==

The following 'relative' Knill-type inequalities are abstract versions of the techniques of [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik].

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Wójcik's fibre bundle decomposition ==

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice <math>\mathcal{A}'\subseteq\mathcal{A}</math> that decomposes into a fibre bundle. His construction is an instance of the following.

'''Lemma:''' Let <math>\mathcal{B}\subseteq\mathcal{A}</math> be a subsemilattice and <math>X\in\mathcal{A}</math> such that <math>-\vee X:\mathcal{B}\to\mathcal{A}</math> is injective. Then the intervals <math>[B,B\vee X]</math> are disjoint, and <math>\mathcal{A}':= \bigcup_B [B,B\vee X]</math> decomposes into a fibre bundle over <math>\mathcal{B}</math>.

'''Proof:''' The intervals are disjoint since if <math>A\in [B,B\vee X]\cap [C,C\vee X]</math>, then <math>B\vee X = A\vee X = C\vee X</math>, and therefore <math>B = C</math> by assumption. So concerning the bundle, the fibre over <math>C\in\mathcal{B}</math> is precisely the interval <math>\mathcal{B}_C := [C,C\vee X]</math>, and the transition map <math>\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]</math> for <math>B\leq C</math> in <math>\mathcal{B}</math> is given by <math>\phi_{B,C}(A) := A\vee C</math>. This is join-preserving and satisfies the required cocycle condition <math>\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}</math> for <math>B\leq C\leq D</math>. It is straightforward to check that the inclusion map of the bundle <math>\mathcal{A}':=\int\mathcal{B}</math> into <math>\mathcal{A}</math> is a semilattice homomorphism. QED.

When applying this, it is likely relevant to have a lower bound on the size of this subsemilattice in order to guarantee that it is not too small relative to <math>\mathcal{A}</math>. The estimate
<math>\sum_{B\in\mathcal{B}} |[B,B\vee X]| \geq \sum_B 2^{c(B,B\vee X)}\geq \sum_B 2^{\frac{|\uparrow B| - |\uparrow(B\vee X)|}{m}} \geq 2^{\frac{-|\uparrow X|}{m}} \sum_B 2^{\frac{|\uparrow B|}{m}}</math>
seems to be part of what Wójcik uses. So the challenge is to make <math>\mathcal{B}</math> and the <math>\uparrow B</math>'s large, while keeping <math>\uparrow X</math> small.

The way that Wójcik achieves this is to first fix <math>X</math>, consider the join-irreducibles <math>\mathcal{J}_X</math> in the upset <math>\uparrow X</math>, and then choose for every <math>J\in\mathcal{J}_X</math> some join-irreducible <math>G(J)</math> in <math>\mathcal{A}</math> with <math>J = G(J)\vee X</math>. He then takes <math>\mathcal{B}</math> to be the semilattice generated by the <math>G(J)</math>'s. Choosing <math>X</math> in a clever way and using a [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal-Katona] type bound (Theorem 3.1) completes his arguments. But more on this some other time.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-19T18:05:52Z

TobiasFritz: /* Wójcik's fibre bundle decomposition */

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's estimates ==

The following 'relative' Knill-type inequalities are abstract versions of the techniques of [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik].

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Wójcik's fibre bundle decomposition ==

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice <math>\mathcal{A}'\subseteq\mathcal{A}</math> that decomposes into a fibre bundle. His construction is an instance of the following.

'''Lemma:''' Let <math>\mathcal{B}\subseteq\mathcal{A}</math> be a subsemilattice and <math>X\in\mathcal{A}</math> such that <math>-\vee X:\mathcal{B}\to\mathcal{A}</math> is injective. Then the intervals <math>[B,B\vee X]</math> are disjoint, and <math>\mathcal{A}':= \bigcup_B [B,B\vee X]</math> decomposes into a fibre bundle over <math>\mathcal{B}</math>.

'''Proof:''' The intervals are disjoint since if <math>A\in [B,B\vee X]\cap [C,C\vee X]</math>, then <math>B\vee X = A\vee X = C\vee X</math>, and therefore <math>B = C</math> by assumption. So concerning the bundle, the fibre over <math>C\in\mathcal{B}</math> is precisely the interval <math>\mathcal{B}_C := [C,C\vee X]</math>, and the transition map <math>\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]</math> for <math>B\leq C</math> in <math>\mathcal{B}</math> is given by <math>\phi_{B,C}(A) := A\vee C</math>. This is join-preserving and satisfies the required cocycle condition <math>\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}</math> for <math>B\leq C\leq D</math>. It is straightforward to check that the inclusion map of the bundle <math>\mathcal{A}':=\int\mathcal{B}</math> into <math>\mathcal{A}</math> is a semilattice homomorphism. QED.

When applying this, it is likely relevant to have a lower bound on the size of this subsemilattice in order to guarantee that it is not too small relative to <math>\mathcal{A}</math>. The relevant estimate seems to be
<math>\sum_{B\in\mathcal{B}} |[B,B\vee X]| \geq \sum_B 2^{c(B,B\vee X)}\geq \sum_B 2^{\frac{|\uparrow B| - |\uparrow(B\vee X)|}{m}} \geq \frac{1}{m} \sum_B 2^{\frac{|\uparrow B| - |\uparrow X|}{m}}.</math>

The way that Wójcik employs this is to first fix <math>X</math>, consider the join-irreducibles <math>\mathcal{J}_X</math> in the upset <math>\uparrow X</math>, and then choose for every <math>J\in\mathcal{J}_X</math> some join-irreducible <math>G(J)</math> in <math>\mathcal{A}</math> with <math>J = G(J)\vee X</math>. He then takes <math>\mathcal{B}</math> to be the semilattice generated by the <math>G(J)</math>'s. Choosing <math>X</math> in a clever way and using estimates as in the previous section together with a [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal-Katona] type bound (Theorem 3.1) completes his arguments. But more on this some other time.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-19T12:29:49Z

TobiasFritz: /* Wójcik's arguments */

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's estimates ==

The following 'relative' Knill-type inequalities are abstract versions of the techniques of [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik].

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Wójcik's fibre bundle decomposition ==

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice <math>\mathcal{A}'\subseteq\mathcal{A}</math> that decomposes into a fibre bundle. His construction is an instance of the following.

'''Lemma:''' Let <math>\mathcal{B}\subseteq\mathcal{A}</math> be a subsemilattice and <math>X\in\mathcal{A}</math> such that <math>-\vee X:\mathcal{B}\to\mathcal{A}</math> is injective. Then the intervals <math>[B,B\vee X]</math> are disjoint, and <math>\mathcal{A}':= \bigcup_B [B,B\vee X]</math> decomposes into a fibre bundle over <math>\mathcal{B}</math>.

'''Proof:''' The intervals are disjoint since if <math>A\in [B,B\vee X]\cap [C,C\vee X]</math>, then <math>B\vee X = A\vee X = C\vee X</math>, and therefore <math>B = C</math> by assumption. So concerning the bundle, the fibre over <math>C\in\mathcal{B}</math> is precisely the interval <math>\mathcal{B}_C := [C,C\vee X]</math>, and the transition map <math>\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]</math> for <math>B\leq C</math> in <math>\mathcal{B}</math> is given by <math>\phi_{B,C}(A) := A\vee C</math>. This is join-preserving and satisfies the required cocycle condition <math>\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}</math> for <math>B\leq C\leq D</math>. It is straightforward to check that the inclusion map of the bundle <math>\mathcal{A}':=\int\mathcal{B}</math> into <math>\mathcal{A}</math> is a semilattice homomorphism. QED.

The way that Wójcik employs this is to first fix <math>X</math>, consider the join-irreducibles <math>\mathcal{J}_X</math> in the upset <math>\uparrow X</math>, and then choose for every <math>J\in\mathcal{J}_X</math> some join-irreducible <math>G(J)</math> in <math>\mathcal{A}</math> with <math>J = G(J)\vee X</math>. He then takes <math>\mathcal{B}</math> to be the semilattice generated by the <math>G(J)</math>'s. Choosing <math>X</math> in a clever way and using estimates as in the previous section together with a [https://en.wikipedia.org/wiki/Kruskal%E2%80%93Katona_theorem Kruskal-Katona] type bound (Theorem 3.1) completes his arguments. But more on this some other time.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-19T08:57:23Z

TobiasFritz: corrected

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's arguments ==

The following observations are not exactly what [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik] uses, but are closely related.

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' Let <math>\mathcal{P}</math> be a finite poset with a least element and <math>|\mathcal{P}|\geq 2</math>. Then there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-18T10:05:57Z

TobiasFritz: /* Reduction to atomistic lattices */

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A}| + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's arguments ==

The following observations are not exactly what [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik] uses, but are closely related.

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' In every finite poset <math>\mathcal{P}</math>, there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

[[Category:Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-18T09:39:13Z

TobiasFritz: added more results

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice with set of join-irreducibles <math>\mathcal{J}</math> of cardinality <math>|\mathcal{J}|=j</math>, and write <math>n=|\mathcal{A}|</math>. Write <math>m</math> for the maximum of <math>n - \uparrow\{J\}</math> over all join-irreducibles <math>J</math>; the goal is to lower bound <math>m</math> in terms of <math>n</math>, and FUNC claims that <math>m\geq n/2</math>.

== General observations ==

'''Lemma:''' If there is a constant <math>C>0</math> such that (weak) FUNC holds for all lattices with <math>|\mathcal{J}| \leq C|\mathcal{A}|</math>, then it holds in general.

'''Proof:''' For given <math>\mathcal{A}</math>, consider the <math>k</math>-th cartesian powers <math>\mathcal{A}^k</math>. (Weak) FUNC holds for any one of these if and only if it holds for <math>\mathcal{A}</math> itself. Since the number of join-irreducibles of <math>\mathcal{A}^k</math> is <math>k|\mathcal{J}|</math>, which grows much slower than <math>|\mathcal{A}|^k</math>, the claim follows by choosing <math>k</math> large enough. QED.

== Reduction to atomistic lattices ==

'''Lemma:''' (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

'''Proof:''' Let <math>\mathcal{J}</math> be the set of join-irreducibles of <math>\mathcal{A}</math>. Define <math>\hat{\mathcal{A}}</math> as being equal to <math>\mathcal{A}</math> together with two additional elements <math>A_J,A'_J</math> for every <math>J\in\mathcal{J}</math>, ordered such that <math>0\leq A_J,A'_J\leq J</math>, and incomparable to all other elements. Then <math>\hat{\mathcal{A}}</math> is again a lattice: the join of any two 'old' elements is as before; the join of <math>A_J</math> with some <math>K\in\mathcal{A}</math> is <math>J\vee K</math>, and similarly the join of <math>A_J</math> with <math>A_K</math> is <math>J\vee K</math>; and crucially, <math>A_J\vee A'_J = J</math>. So by virtue of being a finite join-semilattice, <math>\hat{\mathcal{A}}</math> is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have <math>|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|</math>, and assume the existence of an atom <math>A_J</math> such that <math>|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|</math>. This implies <math>|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 < c(|\mathcal{A} + 2|\mathcal{J}|)</math>. The conclusion follows since the previous lemma allows us to assume the ratio <math>|\mathcal{J}|/|\mathcal{A}|</math> to be arbitrarily small. QED.

Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic <math>\mathcal{A}</math> has a prime element, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' Let <math>P</math> be the prime element. The claim follows if the map <math>\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}</math> given by <math>A\mapsto A\vee P</math> is surjective. Write any given <math>B\in\uparrow\{P\}</math> as a join of join-irreducibles. Since <math>P</math> is prime, <math>P</math> must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to <math>P</math>. Again by atomicity, the remaining factors are not in <math>\uparrow\{P\}</math>, and hence neither is their join. This join is the desired preimage of <math>B</math> under <math>A\mapsto A\vee P</math>. QED.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every downset <math>\downarrow\{A\}</math> is complemented, then <math>\mathcal{A}</math> satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible <math>J</math> is rare, since the map <math>\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}</math> given by <math>A\mapsto A\vee J</math> is surjective: the complement of <math>J</math> in <math>\downarrow\{B\}</math> is a preimage of <math>B\in\uparrow\{J\}</math>. QED.

By a [http://www.sciencedirect.com/science/article/pii/S0012365X81800271 result of Björner], we can therefore also assume that <math>\mathcal{A}</math> contains a 3-element interval.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}'\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J}' = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}'</math> has abundance at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, resulting in <math>m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}</math>.

Note that at the two extreme values <math>|\mathcal{J}'|=2</math> or <math>|\mathcal{J}'|=\log_2(n)</math>, this establishes <math>m \geq n/2</math>. However, unless <math>|\mathcal{J}'|</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>m\geq \frac{n-1}{|\mathcal{J}'|}</math>.

'''Proof:''' Let <math>\mathcal{B}_{\mathcal{J}'}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}'</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}</math> given by <math>\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}'</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}'</math> would not be minimal with <math>\bigvee \mathcal{J}' = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}') = 1</math> by the assumption on <math>\mathcal{J}'</math>. Since the abundance of each <math>J\in\mathcal{J}'</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_{\mathcal{J}'}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|\mathcal{J}'|}</math>. For the remaining weight of <math>n-2^{|\mathcal{J}'|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_{\mathcal{J}'}</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}'</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>. This means that its total abundance is at most <math>2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}</math>, as was to be shown. QED.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then <math>m \geq \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property. QED.

== Wójcik's arguments ==

The following observations are not exactly what [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik] uses, but are closely related.

'''Lemma:''' Let <math>A\leq B</math> in <math>\mathcal{A}</math>. Then <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}</math>.

For <math>A=0</math> and <math>B=1</math>, this specializes to Knill's result.

'''Proof:''' Let <math>\mathcal{J}'</math> be a minimal set of join-irreducibles with <math>A \vee \bigvee \mathcal{J}' = B</math>. Since all the <math>A\vee\bigvee \mathcal{K}</math> must be distinct as <math>\mathcal{K}\subseteq\mathcal{J}'</math> varies by the minimality of <math>\mathcal{J}'</math>, we have <math>|\mathcal{J}'|\leq \log_2 |[A,B]|</math>. On the other hand, <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. Combining these two inequalities results in the claim. QED.

'''Proposition:''' Let <math>[A_i,B_i]</math> be a collection of disjoint intervals that cover <math>\mathcal{A}</math>. Then <math>\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n</math>.

For a single interval <math>[A,B]</math>, this specializes to the lemma; while for covering <math>\mathcal{A}</math> by all the singleton intervals, one obtains the tight but tautological inequality <math>n\leq n</math>.

'''Proof:''' Let the <math>\mathcal{J}'_i</math> be as in the previous proof. The arguments there show that <math>\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n</math>. QED.

Wójcik's actual reasoning generalizes along the following lines. Let <math>c(A,B)</math> be the smallest cardinality of any set of join-irreducibles <math>\mathcal{J'}</math> with <math>A\vee\bigvee\mathcal{J}' = B</math>; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For <math>A\not\leq B</math>, we set <math>c(A,B)=\infty</math>. This behaves like a quasimetric on <math>\mathcal{A}</math>, in the sense that the triangle inequality holds and <math>c(A,B)=0</math> is equivalent to <math>A=B</math>.

'''Lemma:''' For <math>A\lt B</math>, we have <math>m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}</math>.

'''Proof:''' Let <math>\mathcal{J}'</math> be a set of join-irreducibles of cardinality <math>c(A,B)</math> with <math>A \vee \bigvee \mathcal{J}' = B</math>. Then <math>|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|</math> by the union bound, since taking <math>-\vee J</math> for a join-irreducible <math>J</math> decreases the size of the upset by at most <math>m</math>. QED.

== Equal maximal chains ==

Another extreme situation is when all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=j+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and therefore we can assume <math>h\leq j</math>.

=== Case b: large width ===

In this case, one can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

== From strong FUNC to weighted FUNC ==

'''Strong FUNC ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' Every finite lattice <math>A</math> has a join-irreducible element of abundance at most <math>1/2</math>, with equality if and only if <math>A</math> is a Boolean algebra.

'''[https://gowers.wordpress.com/2016/02/22/func4-further-variants/ Weighted FUNC]:''' If <math>w:\mathcal{A}\to\mathbb{R}_{\geq 0}</math> is monotone in the sense that <math>w(A)\geq w(B)</math> for <math>A\leq B</math>, then there exists a join-irreducible element <math>A</math> of <math>w</math>-abundance at most <math>\frac{1}{2}\sum_B w(B)</math>.

'''Proposition:''' Strong FUNC implies weighted FUNC in the special case where every weight is a power of <math>2</math>.

'''Proof sketch:''' Use the fibre bundle construction with base <math>\mathcal{A}</math>. For the fibre <math>\mathcal{A}_B</math>, take a Boolean algebra of size <math>w(B)</math>, which is possible since <math>w(B)</math> is a power of <math>2</math>. The transition maps <math>\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C</math> are specified by using the fact that the Boolean algebra of size <math>w(B)</math> is the free join-semilattice on <math>\log_2 w(B)</math> many generators, and so we take <math>\phi_{B,C}</math> to be the unique join-preserving extension of a suitable surjective map from a set of size <math>\log_2 w(B)</math> to a set of size <math>\log_2 w(C)</math>. In order to guarantee the cocyle condition <math>\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}</math>, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle <math>\int\mathcal{A}</math> is a finite lattice of size <math>\sum_B w(B)</math>. There are two kinds of join-irreducibles: first, those in the fibre <math>\mathcal{A}_0</math>, which all have an abundance of exactly <math>1/2</math>; second, the bottom elements of the fibres <math>\mathcal{A}_J</math> for <math>J</math> join-irreducible in <math>\mathcal{A}</math>, with abundance <math>\sum_{B\in\uparrow J} w(B)</math>. Hence by strong FUNC, there is <math>J</math> with <math>\sum_{B\in\uparrow J} w(B) < \frac{1}{2}\sum_B w(B)</math> if and only if <math>\int\mathcal{A}</math> is not a Boolean algebra. The latter is guaranteed if <math>\mathcal{A}</math> itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that <math>\mathcal{A}</math> is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

== Poset FUNC ==

'''Conjecture:''' In every finite poset <math>\mathcal{P}</math>, there is a join-irreducible element <math>A\in\mathcal{P}</math> with <math>|\uparrow A|\leq |\mathcal{P}|/2</math>.

[[Category:Frankl's union-closed sets conjecture]]

Frankl's union-closed conjecture

2016-03-17T09:27:38Z

TobiasFritz: /* Strengthenings */

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.

== 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 <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).

== 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 < \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>.

== 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154652 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154685 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 [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911 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 [https://gowers.wordpress.com/2016/02/22/func4-further-variants/#comment-154820 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 [https://gowers.wordpress.com/2016/02/22/func4-further-variants/#comment-154825 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 [https://gowers.wordpress.com/2016/02/22/func4-further-variants/#comment-154873 here].

=== Relationships between them ===

Various implications between these conjectures [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154651 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>\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:

* [http://mathoverflow.net/a/228124/27013 Renaud-Sarvate example]
* Examples based on [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154069 Steiner systems]

General constructions:

* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ 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 ==

* [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/ Introductory post]
* [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/ FUNC1]
* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ FUNC2]
* [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/ FUNC3]
* [https://gowers.wordpress.com/2016/02/22/func4-further-variants/ FUNC4]

== Links ==

* A good [http://www.zaik.uni-koeln.de/~schaudt/UCSurvey.pdf survey article]

[[Category: Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-15T14:03:18Z

TobiasFritz: /* Wójcik's arguments */

Lattice approach

2016-03-15T13:44:28Z

TobiasFritz: corrected and expanded

Lattice approach

2016-03-14T15:22:02Z

TobiasFritz: /* Knill's argument in lattice terms */

Lattice approach

2016-03-14T15:20:58Z

TobiasFritz: update with new notation

Lattice approach

2016-03-14T10:19:17Z

TobiasFritz:

Lattice approach

2016-03-14T10:18:29Z

TobiasFritz: added minor consequence

Lattice approach

2016-03-14T10:11:31Z

TobiasFritz: /* Wójcik's argument */

Lattice approach

2016-03-14T10:10:48Z

TobiasFritz: added some key parts of Wójcik's argument

Frankl's union-closed conjecture

2016-03-14T09:15:01Z

TobiasFritz:

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.

== 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 <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).

== 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 < \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>.

== 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154652 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154685 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 [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911 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 [https://gowers.wordpress.com/2016/02/22/func4-further-variants/#comment-154820 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 [https://gowers.wordpress.com/2016/02/22/func4-further-variants/#comment-154825 get an induction argument to work].

=== Relationships between them ===

Various implications between these conjectures [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154651 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>\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:

* [http://mathoverflow.net/a/228124/27013 Renaud-Sarvate example]
* Examples based on [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154069 Steiner systems]

General constructions:

* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ 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 ==

* [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/ Introductory post]
* [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/ FUNC1]
* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ FUNC2]
* [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/ FUNC3]
* [https://gowers.wordpress.com/2016/02/22/func4-further-variants/ FUNC4]

== Links ==

* A good [http://www.zaik.uni-koeln.de/~schaudt/UCSurvey.pdf survey article]

[[Category: Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-14T08:28:41Z

TobiasFritz: clarified

Lattice approach

2016-03-13T18:07:49Z

TobiasFritz: expanded on the 'atomistic wlog' remark

Frankl's union-closed conjecture

2016-03-13T17:38:47Z

TobiasFritz: new idea for examples (based on functor categories)

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.

== 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 <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).

== 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 < \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>.

== 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154652 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154685 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 [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911 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>.

=== Relationships between them ===

Various implications between these conjectures [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154651 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]]

== 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:

* [http://mathoverflow.net/a/228124/27013 Renaud-Sarvate example]
* Examples based on [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154069 Steiner systems]

General constructions:

* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ 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

== Discussion on Gowers's Weblog ==

* [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/ Introductory post]
* [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/ FUNC1]
* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ FUNC2]
* [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/ FUNC3]
* [https://gowers.wordpress.com/2016/02/22/func4-further-variants/ FUNC4]

== Links ==

* A good [http://www.zaik.uni-koeln.de/~schaudt/UCSurvey.pdf survey article]

[[Category: Frankl's union-closed sets conjecture]]

Lattice approach

2016-03-13T17:07:44Z

TobiasFritz: adding more basic material

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice containing <math>m</math> join-irreducibles, and write <math>n=|\mathcal{A}|</math>.

== Reduction to atomistic lattices ==

'''Lemma:'''' weak FUNC holds for all lattices if and only if it holds for atomistic lattices.

'''Proof:'''

Hence we assume wlog that $\mathcal{A}$ is atomistic.

== Easy lattice classes ==

'''Proposition:''' If atomistic $\mathcal{A}$ has a prime element, then $\mathcal{A}$ satisfies FUNC.

'''Proof:''' Let $P$ be the prime element. The claim follows if the map $\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}$ given by $A\mapsto A\vee P$ is surjective. Write any given $B\in\uparrow\{P\}$ as a join of join-irreducibles. Since $P$ is prime, $P$ must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to $P$. Again by atomicity, the remaining factors are not in $\uparrow\{P\}$, and hence neither is their join. This join is the desired preimage of $B$ under $A\mapsto A\vee P$.

'''Proposition ([http://www.sciencedirect.com/science/article/pii/0097316592900686 Poonen]):''' If every interval $\downarrow\{A\}$ is complemented, then $\mathcal{A}$ satisfies FUNC.

'''Proof:''' In this case, ''any'' join-irreducible $J$ is rare, since the map $\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}$ given by $A\mapsto A\vee J$ is surjective: the complement of $J$ in $\downarrow\{A\}$ is a preimage of $A\in\uparrow\{J\}$.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J} = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}</math> has abundance at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>.

Note that at the two extreme values <math>|J|=2</math> or <math>|J|=\log_2(n)</math>, this establishes an element of abundance at most <math>1/2</math>. Unless <math>J</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>n - \frac{n-1}{|J|}</math>.

'''Proof:''' Let <math>\mathcal{B}_\mathcal{J}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_\mathcal{J}</math> given by <math>\phi(A):=\{J\in \mathcal{J}\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}</math> would not be minimal with <math>\bigvee \mathcal{J} = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_\mathcal{J}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}) = 1</math> by the assumption on <math>\mathcal{J}</math>. Since the abundance of each <math>J\in\mathcal{J}</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_\mathcal{J}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|J|}</math>. For the remaining weight of <math>n-2^{|J|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_J</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|J|-1)(n-2^{|J|})}{|J|}</math>. This means that its total abundance is at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>, as was to be shown.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then there is a join-irreducible element of abundance at most <math>n - \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property.

== Case 2: Equal maximal chains ==

The opposite extreme is that all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. We distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case 2a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=m+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and we are done since every prime element is rare.

=== Case 2b: large width ===

In this case, can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

[[Category:Frankl's union-closed sets conjecture]]

Category:Frankl's union-closed sets conjecture

2016-03-11T09:53:25Z

TobiasFritz: Created page with "This is a list of pages created during the Polymath11 project tackling Frankl's union-closed conjecture."

This is a list of pages created during the Polymath11 project tackling [[Frankl's union-closed conjecture]].

Lattice approach

2016-03-11T09:51:54Z

TobiasFritz:

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice containing <math>m</math> join-irreducibles, and write <math>n=|\mathcal{A}|</math>.

Throwing in a new atom below every join-irreducible creates a new lattice in which abundances differ by less than a factor of 2. So for the purposes of weak FUNC, it should be possible to assume wlog that <math>\mathcal{A}</math> is atomistic.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J} = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}</math> has abundance at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>.

Note that at the two extreme values <math>|J|=2</math> or <math>|J|=\log_2(n)</math>, this establishes an element of abundance at most <math>1/2</math>. Unless <math>J</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>n - \frac{n-1}{|J|}</math>.

'''Proof:''' Let <math>\mathcal{B}_\mathcal{J}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_\mathcal{J}</math> given by <math>\phi(A):=\{J\in \mathcal{J}\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}</math> would not be minimal with <math>\bigvee \mathcal{J} = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_\mathcal{J}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}) = 1</math> by the assumption on <math>\mathcal{J}</math>. Since the abundance of each <math>J\in\mathcal{J}</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_\mathcal{J}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|J|}</math>. For the remaining weight of <math>n-2^{|J|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_J</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|J|-1)(n-2^{|J|})}{|J|}</math>. This means that its total abundance is at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>, as was to be shown.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then there is a join-irreducible element of abundance at most <math>n - \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property.

== Case 2: Equal maximal chains ==

The opposite extreme is that all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. We distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case 2a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=m+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and we are done since every prime element is rare.

=== Case 2b: large width ===

In this case, can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

[[Category:Frankl's union-closed sets conjecture]]

Find set configurations that imply FUNC

2016-03-11T09:51:20Z

TobiasFritz:

== Introduction ==

One of the first observations on the conjecture is that if a union closed family contains a singleton set {x}, then the set <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\}</math>, contains at least as many sets as <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \notin A\}</math>. A slightly more clever argument shows that if a two element set {x, y} is in <math>\mathcal{A}</math>, then FUNC holds for <math>\mathcal{A}</math>:

Let <math>\mathcal{A}_{xy} = \{A \in \mathcal{A} : x, y \in A\}</math>, <math>\mathcal{A}_x = \{A \in \mathcal{A} : x \in A\ , y\notin A\}</math>, <math>\mathcal{A}_y = \{A \in \mathcal{A} : y \in A\ , x\notin A\}</math>, <math>\mathcal{A}_\emptyset = \{A \in \mathcal{A} : x, y\notin A\}</math>. Because {x, y} is in <math>\mathcal{A}</math>, the set <math>\mathcal{A}_{xy}</math> has at least as many sets as <math>\mathcal{A}_\emptyset</math>. Therefore, depending on which of <math>\mathcal{A}_x</math> and <math>\mathcal{A}_y</math> is larger, x or y are in at least half of the sets.

One might assume that a similar argument would work for three element sets, but unfortunately the argument fails. In fact, there is a family <math>\mathcal{A}</math> with only 9 elements in the ground set, and one set with three elements, such that none of those three elements is in at least half of the sets. However, one can show that if <math>\mathcal{A}</math> contains certain configurations of sets of size 3, then FUNC holds for <math>\mathcal{A}</math>. For example, in [http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r88/pdf this] article, it is shown that if <math>\mathcal{A}</math> contains 3 sets of size three that are subsets of the same set of size 5, then FUNC holds for <math>\mathcal{A}</math>. This article attempts to extend the results given in that paper.

== Lemma 1 ==
If <math>\mathcal{A}</math> contains 4 sets of size 3 in the configuration {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6}, then FUNC holds for <math>\mathcal{A}</math>.

Proof: Let K be any set disjoint from {1, 2, 3, 4, 5, 6}, and let C be the set of all subsets s of {1, 2, 3, 4, 5, 6} such that KUs is in <math>\mathcal{A}</math>. We need to show that for all K, the average size of the sets in C is at least 3 (then you can use the weight function that assigns 1 to all of 1, 2, 3, 4, 5, 6). The empty set {} may or may not be in C, but if C is nonempty (and there is no point in considering a K for which C is empty), then the full set {1, 2, 3, 4, 5, 6} is in C. We say that a set has deficit n if the set has n less elements than the target average (in this case 3), and surplus n if it has n elements more than the average. If for every K the total surplus is at least the total deficit, then FUNC holds for <math>\mathcal{A}</math>.

Assume that FUNC does not hold for A, then for some K the total deficit of C is more than the total surplus of C.

Case 1: {} is in C: The surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of the empty set. Since {} is in C, then {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, along with all their unions, which together make up all the sets of size 5. The total surplus of these sets is 12 (there are 6 sets of size 5, and each has surplus 2, and we’re ignoring the full set), therefore the total deficit must be at least 13. However, for every set of size 1 in C, there are two sets of size 4 in C, as follows:
1: {1, 2, 4, 6}, {1, 3, 5, 6}
2: {1, 2, 4, 5}, {2, 3, 5, 6}
3: {1, 3, 4, 5}. {2, 3, 4, 6}
4: {1, 2, 3, 4}, {3, 4, 5, 6}
5: {1, 2, 3, 5}, {2, 4, 5, 6}
6: {1, 2, 3, 6}, {1, 4, 5, 6}
Therefore, the total deficit of the size two sets must make up the 13. But then there must be at least 13 sets of size 2 in C (since they only have deficit 1), and together, these 13 sets generate all of the sets of size 4 (since each set of size 4 can be generated in 3 ways, you need to remove 3 sets before you can’t generate a set of size 4). Therefore, the total surplus is 27, which is the maximum that the total deficit can be.

Case 2: {} is not in C. In this case, since {} is not in C, we consider the set {1, 2, 3, 4, 5, 6} as counting towards the total surplus (as the empty set isn’t there to cancel it out). Now, each set of size 1 in C means that two of {1, 2, 3}, {1, 4, 5}, {2, 4, 6}, {3, 5, 6} are in C, and the union of those is a size 5 set, so each size one set cancels out with a size 5 set. Now, every set of size 2 in C forces a set of size 4 to be in C, except {1, 6}, {2, 5}, {3, 4}. We just need a bijection from the sets of size 2 (excluding the above) to the sets of size 4 (excluding {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}), such that if a set of size 2 is in C, then the associated set of size 4 is in C. One such bijection is:
{1, 2}->{1, 2, 4, 5},
{1, 3}->{1, 3, 5, 6},
{1, 4}->{1, 2, 4, 6},
{1, 5}->{1, 2, 3, 5},
{2, 3}->{2, 3, 4, 6},
{2, 4}->{1, 2, 3, 4},
{2, 6}->{2, 3, 5, 6},
{3, 5}->{1, 3, 4, 5},
{3, 6}->{1, 2, 3, 6},
{4, 5}->{3, 4, 5, 6},
{4, 6}->{1, 4, 5, 6},
{5, 6}->{2, 4, 5, 6}

So, the surplus of {1, 2, 3, 4, 5, 6} cancels out the deficit of {1, 6}, {2, 5}, {3, 4}, and every other set of size 2 has an associated set of size 4. Therefore, the surplus is at least the deficit.

== Finding the implied abundance given a configuration ==

Even if a configuration does not directly imply Frankl's conjecture holds for <math>\mathcal{A}</math>, it can give some interesting results about the minimal abundance, and the weight function. Having one set of size 3, the only way to weight the set is to give equal weight to each element, and the lowest possible abundance on elements of that set is 4/9. If two sets of size 3 having an intersection of size 2 ({1, 2, 3}, {1, 2, 4}), then the lowest possible abundance of an element is 27/55, which is the best possible, and it is given by the weight function w(1)=w(2)=31, w(3)=w(4)=24. This was found by equating the abundance at the two extreme cases of this case: {1}, {2}, {3} in C (and same replacing 3 with 4), and {3}, {4} in C. Hopefully I will be able to find the optimal weight distribution for larger configurations.

[[Category:Frankl's union-closed sets conjecture]]

Horn clause formulation

2016-03-11T09:50:50Z

TobiasFritz:

The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form

<math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in A</math>

To keep the notation concise, we use the shorthand notation <math>(x,S)</math> for such a Horn clause. The following page provides various details of this formulation. Throughout, <math>\mathcal{A}\subseteq 2^X</math> is union-closed with <math>\emptyset\in\mathcal{A}</math>.

== Canonical systems ==

There are at least three canonical systems of Horn clauses that describe a given union-closed family.

=== Maximal one ===

Considering all <math>(x,S)</math> that are satisfied by <math>\mathcal{A}</math> characterizes <math>\mathcal{A}</math>. To see this, we need to show that every set not in <math>\mathcal{A}</math> violates some <math>(x,S)</math>. Indeed for <math>A\not\in\mathcal{A}</math>, take some <math>x\in A</math> that is not an element of any <math>\mathcal{A}</math>-member contained in <math>A</math>; this is possible due to the union-closure assumption. Then put <math>S:=X\setminus A</math>.

In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. The following is taken from [http://www.sciencedirect.com/science/article/pii/S0304397510000034 this paper], which investigates the dual notions for intersection-closed families.

=== Using minimal transversals ===

It is sufficient to consider those <math>(x,S)</math> for which <math>S</math> is not contained in any other <math>S'</math> for which <math>(x,S')</math>. In other words, <math>S</math> can be assumed to be a [https://en.wikipedia.org/wiki/Hypergraph#Transversals minimal transversal] of <math>\mathcal{A}_x</math>.

Various reformulations of this can be found in the paper above.

=== Using free sets ===

A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (At least this is the terminology used in the dual case of intersection-closed families, where it seems to be motivated by the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>.

== Literature ==

For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].

[[Category:Frankl's union-closed sets conjecture]]

Frankl's union-closed conjecture

2016-03-11T09:50:16Z

TobiasFritz:

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.

== 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 <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).

== 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 < \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>.

== 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154652 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154685 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 [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911 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>.

=== Relationships between them ===

Various implications between these conjectures [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154651 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]]

== 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:

* [http://mathoverflow.net/a/228124/27013 Renaud-Sarvate example]
* Examples based on [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154069 Steiner systems]

General constructions:

* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ fibre bundle construction]

== Discussion on Gowers's Weblog ==

* [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/ Introductory post]
* [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/ FUNC1]
* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ FUNC2]
* [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/ FUNC3]
* [https://gowers.wordpress.com/2016/02/22/func4-further-variants/ FUNC4]

== Links ==

* A good [http://www.zaik.uni-koeln.de/~schaudt/UCSurvey.pdf survey article]

[[Category: Frankl's union-closed sets conjecture]]

Horn clause formulation

2016-03-11T09:44:06Z

TobiasFritz: correction

Lattice approach

2016-03-11T08:10:39Z

TobiasFritz:

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice containing <math>m</math> join-irreducibles, and write <math>n=|\mathcal{A}|</math>.

Throwing in a new atom below every join-irreducible creates a new lattice in which abundances differ by less than a factor of 2. So for the purposes of weak FUNC, it should be possible to assume wlog that <math>\mathcal{A}</math> is atomistic.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J} = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}</math> has abundance at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>.

Note that at the two extreme values <math>|J|=2</math> or <math>|J|=\log_2(n)</math>, this establishes an element of abundance at most <math>1/2</math>. Unless <math>J</math> is very close to the maximal value <math>\log_2(n)</math>, the bound is only marginally better than Knill's original one, which is <math>n - \frac{n-1}{|J|}</math>.

'''Proof:''' Let <math>\mathcal{B}_\mathcal{J}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_\mathcal{J}</math> given by <math>\phi(A):=\{J\in \mathcal{J}\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}</math> would not be minimal with <math>\bigvee \mathcal{J} = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_\mathcal{J}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}) = 1</math> by the assumption on <math>\mathcal{J}</math>. Since the abundance of each <math>J\in\mathcal{J}</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_\mathcal{J}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|J|}</math>. For the remaining weight of <math>n-2^{|J|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_J</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|J|-1)(n-2^{|J|})}{|J|}</math>. This means that its total abundance is at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>, as was to be shown.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length <math>c</math>. Then there is a join-irreducible element of abundance at most <math>n - \frac{n-1}{c-1}</math>.

'''Proof:''' If the maximal chain is <math>0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1</math>, then write <math>A_{k+1} = A_k\lor J_k</math> for join-irreducible <math>J_k</math>. Then <math>\bigvee_k J_k = 1</math>, and choose a minimal subset of the <math>J_k</math>'s with this property.

== Case 2: Equal maximal chains ==

The opposite extreme is that all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. We distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case 2a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=m+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and we are done since every prime element is rare.

=== Case 2b: large width ===

In this case, can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

Lattice approach

2016-03-11T04:04:09Z

TobiasFritz: added Knill's argument

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice containing <math>m</math> join-irreducibles, and write <math>n=|\mathcal{A}|</math>.

Throwing in a new atom below every join-irreducible creates a new lattice in which abundances differ by less than a factor of 2. So for the purposes of weak FUNC, it should be possible to assume wlog that <math>\mathcal{A}</math> is atomistic.

== Knill's argument in lattice terms ==

The following is a lattice-theoretic formulation of a [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154383 small tightening] of Knill's argument.

'''Proposition:''' Let <math>\mathcal{J}\subseteq\mathcal{A}</math> be a set of join-irreducibles with <math>\bigvee \mathcal{J} = 1</math> and minimal with this property. Then some member of <math>\mathcal{J}</math> has abundance at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>.

Note that at the two extreme values <math>|J|=2</math> or <math>|J|=\log_2(n)</math>, this establishes an element of abundance at most <math>1/2</math>.

'''Proof:''' Let <math>\mathcal{B}_\mathcal{J}</math> be the Boolean algebra of subsets of the set <math>\mathcal{J}</math>. Consider the map <math>\phi:\mathcal{A}\to\mathcal{B}_\mathcal{J}</math> given by <math>\phi(A):=\{J\in \mathcal{J}\:|\: J\leq A\}</math>. We claim that <math>\phi</math> is surjective. Indeed, for every <math>\mathcal{I}\subseteq\mathcal{J}</math> we have <math>\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}</math>; for if <math>\phi\left(\bigvee \mathcal{I} \right)</math> was larger, then <math>\mathcal{J}</math> would not be minimal with <math>\bigvee \mathcal{J} = 1</math>.

Now consider the weight function <math>w:\mathcal{B}_\mathcal{J}\to\mathbb{N}</math> given by <math>w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|</math>. We know <math>w(\mathcal{I})\geq 1</math> by surjectivity, and moreover <math>w(\mathcal{J}) = 1</math> by the assumption on <math>\mathcal{J}</math>. Since the abundance of each <math>J\in\mathcal{J}</math> in <math>\mathcal{A}</math> coincides with its <math>w</math>-abundance in <math>\mathcal{B}_\mathcal{J}</math>, it is enough to derive a suitable bound on the <math>w</math>-abundance.

<math>w\geq 1</math> already fixes the distribution of a total weight of <math>2^{|J|}</math>. For the remaining weight of <math>n-2^{|J|}</math>, the worst-case scenario is that it is completely concentrated on the coatoms of <math>\mathcal{B}_J</math>. (And this [https://gowers.wordpress.com/2016/02/08/func2-more-examples/#comment-154419 can indeed happen].) Since every <math>J\in\mathcal{J}</math> is contained in all but one coatoms, the pigeonhole principle guarantees that there is <math>J</math> whose abundance with respect to the remaining weight is at most <math>\frac{(|J|-1)(n-2^{|J|})}{|J|}</math>. This means that its total abundance is at most <math>2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|}</math>, as was to be shown.

'''Corollary:''' Suppose that <math>\mathcal{A}</math> contains a maximal chain of length $c$. Then...

'''Proof:'''

== Case 1: Short maximal chains ==

If <math>\mathcal{A}</math> has a maximal chain of sufficiently small length <math>l</math>, then a Knill-type argument establishes the existence of a join-irreducible element with relative abundance of at most <math>1-\frac{1}{l-1}</math>.

== Case 2: Equal maximal chains ==

The opposite extreme is that all maximal chains have equal length, i.e. that <math>\mathcal{A}</math> satisfies the Jordan-Dedekind chain condition. In this case, <math>\mathcal{A}</math> is graded. We distinguish two subcases depending on the height <math>h</math> and the width <math>w</math>; [https://en.wikipedia.org/wiki/Mirsky%27s_theorem#Relation_to_the_Erd.C5.91s.E2.80.93Szekeres_theorem since] <math>(h-1)(w-1)\geq n-1</math>, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

=== Case 2a: large height ===

The height of <math>\mathcal{A}</math> can be at most <math>h=m+1</math>. If this value is reached, then <math>\mathcal{A}</math> has a prime element by the dual of Theorem 15 in [http://link.springer.com/article/10.1007%2FBF00383950 this paper], and we are done since every prime element is rare.

=== Case 2b: large width ===

In this case, can try to choose a large maximal antichain and a join-irreducible element <math>x</math> such that <math>\mathcal{A}_x</math> contains as few elements of the antichain as possible.

Lattice approach

2016-03-10T16:18:11Z

TobiasFritz:

Lattice approach

2016-03-10T16:15:10Z

TobiasFritz: Created page with "This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices. Let <math>\mathcal{A}</math> be a finite lattice containin..."

Horn clause formulation

2016-03-10T14:49:02Z

TobiasFritz:

The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form

<math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in\mathcal{A}</math>

To keep the notation concise, we use the shorthand notation <math>(x,S)</math> for such a Horn clause. The following page provides various details of this formulation. Throughout, <math>\mathcal{A}\subseteq 2^X</math> is union-closed with <math>\emptyset\in\mathcal{A}</math>.

== Canonical systems ==

There are at least three canonical systems of Horn clauses that describe a given union-closed family.

=== Maximal one ===

Considering all <math>(x,S)</math> that are satisfied by <math>\mathcal{A}</math> characterizes <math>\mathcal{A}</math>. To see this, we need to show that every set not in <math>\mathcal{A}</math> violates some <math>(x,S)</math>. Indeed for <math>A\not\in\mathcal{A}</math>, take some <math>x\in A</math> that is not an element of any <math>\mathcal{A}</math>-member contained in <math>A</math>; this is possible due to the union-closure assumption. Then put <math>S:=X\setminus A</math>.

In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. The following is taken from [http://www.sciencedirect.com/science/article/pii/S0304397510000034 this paper], which investigates the dual notions for intersection-closed families.

=== Using minimal transversals ===

It is sufficient to consider those <math>(x,S)</math> for which <math>S</math> is not contained in any other <math>S'</math> for which <math>(x,S')</math>. In other words, <math>S</math> can be assumed to be a [https://en.wikipedia.org/wiki/Hypergraph#Transversals minimal transversal] of <math>\mathcal{A}_x</math>.

Various reformulations of this can be found in the paper above.

=== Using free sets ===

A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (At least this is the terminology used in the dual case of intersection-closed families, where it seems to be motivated by the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>.

== Literature ==

For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].

Horn clause formulation

2016-03-10T14:46:50Z

TobiasFritz:

The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form

<math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in\mathcal{A}</math>

To keep the notation concise, we use the shorthand notation <math>(x,S)</math> for such a Horn clause. The following page provides various details of this formulation. Throughout, <math>\mathcal{A}\subseteq 2^X</math> is union-closed with <math>\emptyset\in\mathcal{A}</math>.

== Canonical systems ==

There are at least three canonical systems of Horn clauses that describe a given union-closed family.

=== Maximal one ===

Considering all <math>(x,S)</math> that are satisfied by <math>\mathcal{A}</math> characterizes <math>\mathcal{A}</math>. To see this, we need to show that every set not in <math>\mathcal{A}</math> violates some <math>(x,S)</math>. Indeed for <math>A\not\in\mathcal{A}</math>, take some <math>x\in A</math> that is not an element of any <math>\mathcal{A}</math>-member contained in <math>A</math>; this is possible due to the union-closure assumption. Then put <math>S:=X\setminus A</math>.

In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. The following is taken from [http://www.sciencedirect.com/science/article/pii/S0304397510000034 this paper], which investigates the dual notions for intersection-closed families.

=== Using minimal transversals ===

It is sufficient to consider those <math>(x,S)</math> for which <math>S</math> is not contained in any other <math>S'</math> for which <math>(x,S')</math>. In other words, <math>S</math> can be assumed to be a [https://en.wikipedia.org/wiki/Hypergraph#Transversals minimal transversal] of <math>\mathcal{A}_x</math>.

Various reformulations of this can be found in the paper above.

=== Using free sets ===

A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (This terminology seems motivated by the dual notion for intersection-closed families, applied to the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>.

== Literature ==

For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis. There is [http://arxiv.org/abs/1411.6432 a survey].

Horn clause formulation

2016-03-10T12:35:49Z

TobiasFritz:

The members of a union-closed family that contains the empty set can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses. These are implications of the form

<math>x\in A \:\Longrightarrow\: \bigvee_{y\in S} y\in\mathcal{A}</math>

To keep the notation concise, we use the shorthand notation <math>(x,S)</math> for such a Horn clause. The following page provides various details of this formulation. Throughout, <math>\mathcal{A}\subseteq 2^X</math> is union-closed with <math>\emptyset\in\mathcal{A}</math>.

== Canonical systems ==

There are at least three canonical systems of Horn clauses that describe a given union-closed family.

=== Maximal one ===

Considering all <math>(x,S)</math> that are satisfied by <math>\mathcal{A}</math> characterizes <math>\mathcal{A}</math>. To see this, we need to show that every set not in <math>\mathcal{A}</math> violates some <math>(x,S)</math>. Indeed for <math>A\not\in\mathcal{A}</math>, take some <math>x\in A</math> that is not an element of any <math>\mathcal{A}</math>-member contained in <math>A</math>; this is possible due to the union-closure assumption. Then put <math>S:=X\setminus A</math>.

In most cases, there are smaller systems of Horn clauses that still characterize <math>\mathcal{A}</math>. The following is taken from [http://www.sciencedirect.com/science/article/pii/S0304397510000034 this paper], which investigates the dual notions for intersection-closed families.

=== Using minimal transversals ===

It is sufficient to consider those <math>(x,S)</math> for which <math>S</math> is not contained in any other <math>S'</math> for which <math>(x,S')</math>. In other words, <math>S</math> can be assumed to be a [https://en.wikipedia.org/wiki/Hypergraph#Transversals minimal transversal] of <math>\mathcal{A}_x</math>.

Various reformulations of this can be found in the paper above.

=== Using free sets ===

A set <math>S</math> is ''free'' if for every <math>y\in S</math> there is <math>A\in\mathcal{A}_y</math> with <math>A\cap S = \{y\}</math>. (This terminology seems motivated by the dual notion for intersection-closed families, applied to the special case of the flats of a matroid: in this case, the free sets are the independent sets.) Then take all Horn clauses <math>(x,S)</math> with <math>S</math> free and <math>x</math> such that <math>A\cap S=\emptyset</math> implies <math>x\not\in A</math>.

== Literature ==

For intersection-closed families, there are plenty of relevant papers in certain areas of artificial intelligence research, including data analysis, relational databases, expert systems and formal concept analysis.

Frankl's union-closed conjecture

2016-03-10T11:20:29Z

TobiasFritz: /* Conjectures that imply FUNC */

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.

== 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 <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).

== 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 < \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>.

== 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154652 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154685 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 [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911 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>.

=== Relationships between them ===

Various implications between these conjectures [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154651 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]]

== 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:

* [http://mathoverflow.net/a/228124/27013 Renaud-Sarvate example]
* Examples based on [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154069 Steiner systems]

General constructions:

* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ fibre bundle construction]

== Discussion on Gowers's Weblog ==

* [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/ Introductory post]
* [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/ FUNC1]
* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ FUNC2]
* [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/ FUNC3]
* [https://gowers.wordpress.com/2016/02/22/func4-further-variants/ FUNC4]

== Links ==

* A good [http://www.zaik.uni-koeln.de/~schaudt/UCSurvey.pdf survey article]

Horn clause formulation

2016-03-09T10:37:36Z

TobiasFritz: begin adding content

Frankl's union-closed conjecture

2016-03-09T10:06:32Z

TobiasFritz: reordered content and added a bit

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.

== 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 <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).

== 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 < \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>.

== 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154652 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154685 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>?

===== Disjoint intervals =====

Igor Balla [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911 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>.

=== Relationships between them ===

Various implications between these conjectures [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154651 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]]

== 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:

* [http://mathoverflow.net/a/228124/27013 Renaud-Sarvate example]
* Examples based on [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/#comment-154069 Steiner systems]

General constructions:

* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ fibre bundle construction]

== Discussion on Gowers's Weblog ==

* [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/ Introductory post]
* [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/ FUNC1]
* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ FUNC2]
* [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/ FUNC3]
* [https://gowers.wordpress.com/2016/02/22/func4-further-variants/ FUNC4]

== Links ==

* A good [http://www.zaik.uni-koeln.de/~schaudt/UCSurvey.pdf survey article]

Horn clause formulation

2016-03-09T09:21:52Z

TobiasFritz: created with essentially no content yet

The members of a union-closed family can be characterized as consisting of precisely those sets which satisfy a bunch of Horn clauses.

Frankl's union-closed conjecture

2016-02-24T08:51:23Z

TobiasFritz:

<h1>Polymath11 -- Frankl's union-closed conjecture</h1>

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 4m-2</math>, assuming <math>\mathcal{A}</math> is separating; or
* <math>0 < \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>.

<h2>Strengthenings</h2>

Various strengthenings of FUNC have been proposed. Some have been disproved, and some implications between them have been shown.

<h3>Conjectures that imply FUNC</h3>

<h4>Injection-to-superset</h4>

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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154441 answered in the negative].

<h4>Injection-to-larger</h4>

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>?

<h4>Weighted FUNC</h4>

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>?

<h4>Uniform weighted FUNC</h4>

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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154652 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 [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154685 is false].

<h4>FUNC for subsets</h4>

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>?

<h4>Disjoint intervals</h4>

Igor Balla [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/#comment-153911 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>.

<h3>Relationships between them</h3>

Various implications between these conjectures [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/#comment-154651 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.)

<h2>Discussion on Gowers's Weblog</h2>

* [https://gowers.wordpress.com/2016/01/21/frankls-union-closed-conjecture-a-possible-polymath-project/ Introductory post]
* [https://gowers.wordpress.com/2016/01/29/func1-strengthenings-variants-potential-counterexamples/ FUNC1]
* [https://gowers.wordpress.com/2016/02/08/func2-more-examples/ FUNC2]
* [https://gowers.wordpress.com/2016/02/13/func3-further-strengthenings-and-variants/ FUNC3]
* [https://gowers.wordpress.com/2016/02/22/func4-further-variants/ FUNC4]

== General proof strategies ==

[[Use a weight function]]

[[Find set configurations that imply FUNC]]

<h2>Links</h2>

* A good [http://www.zaik.uni-koeln.de/~schaudt/UCSurvey.pdf survey article]