Lattice approach - Revision history

TobiasFritz at 09:03, 21 March 2016

2016-03-21T09:03:10Z

← Older revision		Revision as of 02:03, 21 March 2016
Line 1:		Line 1:
	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>.		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 ==		== General observations ==

TobiasFritz: clarified what join-irreducible means here

2016-03-21T03:36:26Z

clarified what join-irreducible means here

← Older revision		Revision as of 20:36, 20 March 2016
Line 114:		Line 114:

	Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.		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]]		[[Category:Frankl's union-closed sets conjecture]]

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

2016-03-19T19:43:26Z

Wójcik's fibre bundle decomposition

← Older revision		Revision as of 12:43, 19 March 2016
Line 78:		Line 78:

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

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

2016-03-19T18:16:45Z

Wójcik's fibre bundle decomposition

← Older revision		Revision as of 11:16, 19 March 2016
Line 78:		Line 78:

	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		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>		<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.		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.		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 ==		== Equal maximal chains ==

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

2016-03-19T18:13:49Z

Wójcik's estimates

← Older revision		Revision as of 11:13, 19 March 2016
Line 53:		Line 53:
	'''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>.		'''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.		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.		'''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.

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

2016-03-19T18:10:39Z

Wójcik's fibre bundle decomposition

← Older revision		Revision as of 11:10, 19 March 2016
Line 77:		Line 77:
	'''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.		'''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~~		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 \frac{1}{m} \sum_B 2^{\frac{\|\uparrow B~~\| - \|\uparrow X~~\|}{m}}.</math>		<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 ~~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.		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 ==		== Equal maximal chains ==

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

2016-03-19T18:05:52Z

Wójcik's fibre bundle decomposition

← Older revision		Revision as of 11:05, 19 March 2016
Line 76:		Line 76:

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

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

2016-03-19T12:29:49Z

Wójcik's arguments

← Older revision		Revision as of 05:29, 19 March 2016
Line 47:		Line 47:
	'''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.		'''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~~ ==		== Wójcik's estimates ==

	The following ~~observations~~ are ~~not exactly what~~ [http://www.sciencedirect.com/science/article/pii/S0012365X98002088 Wójcik] ~~uses, but are closely related~~.		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>.		'''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>.
Line 68:		Line 68:

	'''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.		'''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 ==		== Equal maximal chains ==

TobiasFritz: corrected

2016-03-19T08:57:23Z

corrected

← Older revision		Revision as of 01:57, 19 March 2016
Line 97:		Line 97:
	== Poset FUNC ==		== 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>.		'''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]]		[[Category:Frankl's union-closed sets conjecture]]

TobiasFritz: /* Reduction to atomistic lattices */

2016-03-18T10:05:57Z

Reduction to atomistic lattices

← Older revision		Revision as of 03:05, 18 March 2016
Line 13:		Line 13:
	'''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.		'''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.		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.		Hence we assume wlog that <math>\mathcal{A}</math> is atomistic.