Rota's conjecture - Revision history

Chowt: /* Discussion */

2017-10-23T00:26:12Z

Discussion

← Older revision		Revision as of 17:26, 22 October 2017
Line 86:		Line 86:
	* [https://polymathprojects.org/2017/02/23/rotas-basis-conjecture-polymath-12/ Rota’s Basis Conjecture: Polymath 12?] (Feb 23, 2017)		* [https://polymathprojects.org/2017/02/23/rotas-basis-conjecture-polymath-12/ Rota’s Basis Conjecture: Polymath 12?] (Feb 23, 2017)
	* [https://polymathprojects.org/2017/03/06/rotas-basis-conjecture-polymath-12-2/ Rota's Basis Conjecture: Polymath 12] (March 6, 2017)		* [https://polymathprojects.org/2017/03/06/rotas-basis-conjecture-polymath-12-2/ Rota's Basis Conjecture: Polymath 12] (March 6, 2017)
			* [https://polymathprojects.org/2017/05/05/rotas-basis-conjecture-polymath-12-post-3/ Rota's Basis Conjecture: Polymath 12, post 3] (May 5, 2017)

	== References ==		== References ==

Chowt: /* Definitions */

2017-10-23T00:15:55Z

Definitions

← Older revision		Revision as of 17:15, 22 October 2017
Line 14:		Line 14:

	A maximal independent set of a matroid is called a <b>basis</b> and it is a theorem that bases all have the same cardinality; this cardinality is the <b>rank</b> of the matroid.		A maximal independent set of a matroid is called a <b>basis</b> and it is a theorem that bases all have the same cardinality; this cardinality is the <b>rank</b> of the matroid.

			The acyclic subsets of edges of an undirected graph form the independents sets of a matroid. Matroids arising in this way are called <b>graphic</b>.

	A matroid is <b>strongly base-orderable</b> if, for any two bases <math>B</math><sub>1</sub> and <math>B</math><sub>2</sub>, there exists a bijection <math>f : B</math><sub>1</sub> → <math>B</math><sub>2</sub> such that for every subset <math>S &sube; B</math><sub>1</sub>, both <math>B</math><sub>1</sub> \ <math>S ∪ f(S)</math> and <math>B</math><sub>2</sub> \ <math>f(S) ∪ S</math> are bases. The definition of a <b>base-orderable</b> matroid is the same except that the condition is required to hold only for <i>singleton</i> sets <math>S</math> (so in particular, a strongly base-orderable matroid is base-orderable).		A matroid is <b>strongly base-orderable</b> if, for any two bases <math>B</math><sub>1</sub> and <math>B</math><sub>2</sub>, there exists a bijection <math>f : B</math><sub>1</sub> → <math>B</math><sub>2</sub> such that for every subset <math>S &sube; B</math><sub>1</sub>, both <math>B</math><sub>1</sub> \ <math>S ∪ f(S)</math> and <math>B</math><sub>2</sub> \ <math>f(S) ∪ S</math> are bases. The definition of a <b>base-orderable</b> matroid is the same except that the condition is required to hold only for <i>singleton</i> sets <math>S</math> (so in particular, a strongly base-orderable matroid is base-orderable).

Chowt: /* Variants of the problem */

2017-10-23T00:09:47Z

Variants of the problem

← Older revision		Revision as of 17:09, 22 October 2017
Line 77:		Line 77:
	[KL2015] give several equivalent formulations of the Alon–Tarsi Conjecture in terms of certain integrals over the special unitary group. [G2016] gives an equivalent formulation of the Alon–Tarsi Conjecture in terms of spherical functions.		[KL2015] give several equivalent formulations of the Alon–Tarsi Conjecture in terms of certain integrals over the special unitary group. [G2016] gives an equivalent formulation of the Alon–Tarsi Conjecture in terms of spherical functions.

	Various attempts have been made to formulate an Alon–Tarsi Conjecture for odd <math>n</math>. For example, it is conjectured by [SW2012] that the number of <i>reduced</i> even Latin squares is not equal to the number of <i>reduced</i> odd Latin squares; [AL2015] prove that this is equivalent to the original Alon–Tarsi conjecture. [Z1997] has a related conjecture where "reduced" is replaced by "the first row is the identity permutation and the diagonal is all 1's."		Various attempts have been made to formulate an Alon–Tarsi Conjecture for odd <math>n</math>. For example, it is conjectured by [SW2012] that the number of <i>reduced</i> even Latin squares is not equal to the number of <i>reduced</i> odd Latin squares; [AL2015] prove that this is equivalent to the original Alon–Tarsi conjecture. [Z1997] has a related conjecture where "reduced" is replaced by "the first row is the identity permutation and the diagonal is all 1's." Yet another (unpublished) conjecture along these lines has been [http://mathoverflow.net/q/259195 posted to MathOverflow].

	== Discussion ==		== Discussion ==

Chowt: /* Variants of the problem */

2017-10-23T00:07:18Z

Variants of the problem

← Older revision		Revision as of 17:07, 22 October 2017
Line 68:		Line 68:
	A generalization due to Jeff Kahn postulates <math>n</math><sup>2</sup> bases <math>B</math><sub><math>ij</math></sub> of a vector space of dimension <math>n</math>, and asks if there exists a choice of <math>n</math><sup>2</sup> elements <math>v</math><sub><math>ij</math></sub>, one from each <math>B</math><sub><math>ij</math></sub>, such that the rows and columns are all bases (i.e., that {<math>v</math><sub><math>ij</math></sub>} is a basis for any fixed <math>i</math> and for any fixed <math>j</math>).		A generalization due to Jeff Kahn postulates <math>n</math><sup>2</sup> bases <math>B</math><sub><math>ij</math></sub> of a vector space of dimension <math>n</math>, and asks if there exists a choice of <math>n</math><sup>2</sup> elements <math>v</math><sub><math>ij</math></sub>, one from each <math>B</math><sub><math>ij</math></sub>, such that the rows and columns are all bases (i.e., that {<math>v</math><sub><math>ij</math></sub>} is a basis for any fixed <math>i</math> and for any fixed <math>j</math>).

	The <i>online</i> version of RBC posits that the bases are revealed one at a time, and the ordering of the elements of each basis must be chosen without knowing what the future bases are. [BD2015] prove that if the characteristic if the field does not divide AT(<math>n</math>), then the online version is true for that value of <math>n</math>. On the other hand, if <math>n</math> is odd and the field contains an <math>m</math>th root of unity for all odd <math>m < n</math>, then the online version of RBC is false. One positive outcome of Polymath12 was to ~~improve~~ our understanding of the online version of RBC.		The <i>online</i> version of RBC posits that the bases are revealed one at a time, and the ordering of the elements of each basis must be chosen without knowing what the future bases are. [BD2015] prove that if the characteristic if the field does not divide AT(<math>n</math>), then the online version is true for that value of <math>n</math>. On the other hand, if <math>n</math> is odd and the field contains an <math>m</math>th root of unity for all odd <math>m < n</math>, then the online version of RBC is false. One positive outcome of Polymath12 was to sharpen our understanding of the online version of RBC.

	[C2009] proposes the following conjecture. For <math>k ≤ n</math>, let <math>M</math> be a matroid of rank <math>k</math> on <math>kn</math> elements that is a disjoint union of <math>k</math> bases. Let <math>I</math><sub>1</sub>, <math>I</math><sub>2</sub>, …, <math>I</math><sub><math>n</math></sub> be disjoint independent sets of <math>M</math>, with 0 ≤ \|<math>I</math><sub><math>i</math></sub>\| ≤ <math>k</math> for all <math>i</math>. Then there exists an <math>n</math> × <math>k</math> grid <math>G</math> containing each element of <math>M</math> exactly		[C2009] proposes the following conjecture. For <math>k ≤ n</math>, let <math>M</math> be a matroid of rank <math>k</math> on <math>kn</math> elements that is a disjoint union of <math>k</math> bases. Let <math>I</math><sub>1</sub>, <math>I</math><sub>2</sub>, …, <math>I</math><sub><math>n</math></sub> be disjoint independent sets of <math>M</math>, with 0 ≤ \|<math>I</math><sub><math>i</math></sub>\| ≤ <math>k</math> for all <math>i</math>. Then there exists an <math>n</math> × <math>k</math> grid <math>G</math> containing each element of <math>M</math> exactly

Chowt: /* Variants of the problem */

2017-10-23T00:06:43Z

Variants of the problem

← Older revision		Revision as of 17:06, 22 October 2017
Line 67:		Line 67:

	A generalization due to Jeff Kahn postulates <math>n</math><sup>2</sup> bases <math>B</math><sub><math>ij</math></sub> of a vector space of dimension <math>n</math>, and asks if there exists a choice of <math>n</math><sup>2</sup> elements <math>v</math><sub><math>ij</math></sub>, one from each <math>B</math><sub><math>ij</math></sub>, such that the rows and columns are all bases (i.e., that {<math>v</math><sub><math>ij</math></sub>} is a basis for any fixed <math>i</math> and for any fixed <math>j</math>).		A generalization due to Jeff Kahn postulates <math>n</math><sup>2</sup> bases <math>B</math><sub><math>ij</math></sub> of a vector space of dimension <math>n</math>, and asks if there exists a choice of <math>n</math><sup>2</sup> elements <math>v</math><sub><math>ij</math></sub>, one from each <math>B</math><sub><math>ij</math></sub>, such that the rows and columns are all bases (i.e., that {<math>v</math><sub><math>ij</math></sub>} is a basis for any fixed <math>i</math> and for any fixed <math>j</math>).

			The <i>online</i> version of RBC posits that the bases are revealed one at a time, and the ordering of the elements of each basis must be chosen without knowing what the future bases are. [BD2015] prove that if the characteristic if the field does not divide AT(<math>n</math>), then the online version is true for that value of <math>n</math>. On the other hand, if <math>n</math> is odd and the field contains an <math>m</math>th root of unity for all odd <math>m < n</math>, then the online version of RBC is false. One positive outcome of Polymath12 was to improve our understanding of the online version of RBC.

			[C2009] proposes the following conjecture. For <math>k ≤ n</math>, let <math>M</math> be a matroid of rank <math>k</math> on <math>kn</math> elements that is a disjoint union of <math>k</math> bases. Let <math>I</math><sub>1</sub>, <math>I</math><sub>2</sub>, …, <math>I</math><sub><math>n</math></sub> be disjoint independent sets of <math>M</math>, with 0 ≤ \|<math>I</math><sub><math>i</math></sub>\| ≤ <math>k</math> for all <math>i</math>. Then there exists an <math>n</math> × <math>k</math> grid <math>G</math> containing each element of <math>M</math> exactly
			once, such that for every <math>i</math>, the elements of <math>I</math><sub><math>i</math></sub> appear in the <math>i</math>th row of <math>G</math> and such that every column of <math>G</math> is a basis of <math>M</math>. It is shown that for any fixed <math>k</math>, this conjecture would imply RBC, but unfortunately [HKL2010] show that it is false for <math>k ≤ n/3</math>. These counterexamples are useful for disproving various other overly strong generalizations of RBC.

	RBC may be thought of as a conjecture about square shapes. [CFGV2003] extend RBC to shapes of what that they call <i>wide partitions</i>. A partition <math>λ</math> is <i>wide</i> if <math>μ ≥ μ'</math> for every partition <math>μ</math> whose parts are a submultiset of the multiset of parts of <math>λ</math>. Here <math>≥</math> denotes dominance (a.k.a. majorization) order and <math>μ'</math> denotes the conjugate of <math>μ</math>.		RBC may be thought of as a conjecture about square shapes. [CFGV2003] extend RBC to shapes of what that they call <i>wide partitions</i>. A partition <math>λ</math> is <i>wide</i> if <math>μ ≥ μ'</math> for every partition <math>μ</math> whose parts are a submultiset of the multiset of parts of <math>λ</math>. Here <math>≥</math> denotes dominance (a.k.a. majorization) order and <math>μ'</math> denotes the conjugate of <math>μ</math>.

	The <i>online</i> version of RBC posits that the bases are revealed one at a time, and the ordering of the elements of each basis must be chosen without knowing what the future bases are. [BD2015] prove that if the characteristic if the field does not divide AT(<math>n</math>), then the online version is true for that value of <math>n</math>. On the other hand, if <math>n</math> is odd and the field contains an <math>m</math>th root of unity for all odd <math>m < n</math>, then the online version of RBC is false. One positive outcome of Polymath12 was to improve our understanding of the online version of RBC.

	[KL2015] give several equivalent formulations of the Alon–Tarsi Conjecture in terms of certain integrals over the special unitary group. [G2016] gives an equivalent formulation of the Alon–Tarsi Conjecture in terms of spherical functions.		[KL2015] give several equivalent formulations of the Alon–Tarsi Conjecture in terms of certain integrals over the special unitary group. [G2016] gives an equivalent formulation of the Alon–Tarsi Conjecture in terms of spherical functions.

	Various attempts have been made to formulate an Alon–Tarsi Conjecture for odd <math>n</math>. For example, it is conjectured by [SW2012] that the number of <i>reduced</i> even Latin squares is not equal to the number of <i>reduced</i> odd Latin squares; [AL2015] prove that this is equivalent to the original Alon–Tarsi conjecture. [Z1997] has a related conjecture where "reduced" is replaced by "the first row is the identity permutation and the diagonal is all 1's."		Various attempts have been made to formulate an Alon–Tarsi Conjecture for odd <math>n</math>. For example, it is conjectured by [SW2012] that the number of <i>reduced</i> even Latin squares is not equal to the number of <i>reduced</i> odd Latin squares; [AL2015] prove that this is equivalent to the original Alon–Tarsi conjecture. [Z1997] has a related conjecture where "reduced" is replaced by "the first row is the identity permutation and the diagonal is all 1's."

	[C2009] proposes the following conjecture. For <math>k ≤ n</math>, let <math>M</math> be a matroid of rank <math>k</math> on <math>kn</math> elements that is a disjoint union of <math>k</math> bases. Let <math>I</math><sub>1</sub>, <math>I</math><sub>2</sub>, …, <math>I</math><sub><math>n</math></sub> be disjoint independent sets of <math>M</math>, with 0 ≤ \|<math>I</math><sub><math>i</math></sub>\| ≤ <math>k</math> for all <math>i</math>. Then there exists an <math>n</math> × <math>k</math> grid <math>G</math> containing each element of <math>M</math> exactly
	once, such that for every <math>i</math>, the elements of <math>I</math><sub><math>i</math></sub> appear in the <math>i</math>th row of <math>G</math> and such that every column of <math>G</math> is a basis of <math>M</math>. It is shown that for any fixed <math>k</math>, this conjecture would imply RBC, but unfortunately [HKL2010] show that it is false for <math>k ≤ n/3</math>. These counterexamples are useful for disproving various other overly strong generalizations of RBC.

	== Discussion ==		== Discussion ==

Chowt: /* Variants of the problem */

2017-10-23T00:05:36Z

Variants of the problem

← Older revision		Revision as of 17:05, 22 October 2017
Line 61:		Line 61:

	== Variants of the problem ==		== Variants of the problem ==

			Again this list is not meant to be an exhaustive list of variants.

	RBC generalizes immediately to arbitrary matroids and no matroid counterexample is known.		RBC generalizes immediately to arbitrary matroids and no matroid counterexample is known.

Chowt: /* Partial results */

2017-10-23T00:04:26Z

Partial results

← Older revision		Revision as of 17:04, 22 October 2017
Line 22:		Line 22:

	== Partial results ==		== Partial results ==

			What follows is not a complete list of partial results, but some attempt has been made to list all major partial results that can be succinctly stated.

	For a positive integer <math>n</math>, let AT(<math>n</math>) (the <b>Alon–Tarsi constant</b>) denote the number of even <math>n × n</math> Latin squares minus the number of odd <math>n × n</math> Latin squares. Then the <b>Alon–Tarsi Conjecture</b> [AT1992] states that AT(<math>n</math>) ≠ 0 for all even <math>n</math>. (It is easy to show that AT(<math>n</math>) = 0 for odd <math>n</math>.) We can simultaneously replace "even" with "row-even" and "odd" with "row-odd"; the resulting conjecture has been proved by Huang and Rota to be equivalent to the Alon–Tarsi Conjecture. There is a close relationship between the Alon–Tarsi Conjecture and RBC.		For a positive integer <math>n</math>, let AT(<math>n</math>) (the <b>Alon–Tarsi constant</b>) denote the number of even <math>n × n</math> Latin squares minus the number of odd <math>n × n</math> Latin squares. Then the <b>Alon–Tarsi Conjecture</b> [AT1992] states that AT(<math>n</math>) ≠ 0 for all even <math>n</math>. (It is easy to show that AT(<math>n</math>) = 0 for odd <math>n</math>.) We can simultaneously replace "even" with "row-even" and "odd" with "row-odd"; the resulting conjecture has been proved by Huang and Rota to be equivalent to the Alon–Tarsi Conjecture. There is a close relationship between the Alon–Tarsi Conjecture and RBC.

Chowt: /* Partial results */

2017-10-23T00:01:42Z

Partial results

← Older revision		Revision as of 17:01, 22 October 2017
Line 49:		Line 49:

	<b>Theorem 7</b> [GW2007, DG2017]. Under the hypotheses of RBC, there exist at least &lfloor; <math>n</math>/(6&lceil;log <math>n</math>&rceil;)&rfloor; disjoint transversals that are all bases. (Note: GW2007 established a lower bound of <math>O(√n)</math> which was later improved by DG2017, but DG2017 is unpublished as of this writing.)		<b>Theorem 7</b> [GW2007, DG2017]. Under the hypotheses of RBC, there exist at least &lfloor; <math>n</math>/(6&lceil;log <math>n</math>&rceil;)&rfloor; disjoint transversals that are all bases. (Note: GW2007 established a lower bound of <math>O(√n)</math> which was later improved by DG2017, but DG2017 is unpublished as of this writing.)

			<b>Theorem 8</b> [W1994]. For a graphic matroid coming from a graph with maximum degree <math>d < n/3</math>, it is possible to construct <math>&lceil; (n+3d)/2d&rceil; - 1</math> disjoint transversals that are all bases.

	We can form another matroid <math>N</math> on <math>E</math> by letting the independent sets of <math>N</math> be the partial transversals of <math>M</math>. Then RBC can be restated as saying that the minimum number <math>β</math> of disjoint common independent sets (i.e., independent in both <math>M</math> and <math>N</math>) into which <math>E</math> may be partitioned is <math>n</math>.		We can form another matroid <math>N</math> on <math>E</math> by letting the independent sets of <math>N</math> be the partial transversals of <math>M</math>. Then RBC can be restated as saying that the minimum number <math>β</math> of disjoint common independent sets (i.e., independent in both <math>M</math> and <math>N</math>) into which <math>E</math> may be partitioned is <math>n</math>.

	<b>Theorem 8</b> [AB2006, Polymath12]. <math>β ≤ 2n-2</math>. (Note: AB2006 proved that <math>β ≤ 2n</math> and this was improved to <math>β ≤ 2n-2</math> by Polymath12.)		<b>Theorem 9</b> [AB2006, Polymath12]. <math>β ≤ 2n-2</math>. (Note: AB2006 proved that <math>β ≤ 2n</math> and this was improved to <math>β ≤ 2n-2</math> by Polymath12.)

	<b>Theorem 9</b> [P2004]. There is a grid of vectors such that for all <math>i</math>, the first <math>i</math> columns of the grid comprise a disjoint union of <math>i</math> bases.		<b>Theorem 10</b> [P2004]. There is a grid of vectors such that for all <math>i</math>, the first <math>i</math> columns of the grid comprise a disjoint union of <math>i</math> bases.

	== Variants of the problem ==		== Variants of the problem ==

Chowt: /* Variants of the problem */

2017-10-22T23:53:23Z

Variants of the problem

← Older revision		Revision as of 16:53, 22 October 2017
Line 64:		Line 64:
	RBC may be thought of as a conjecture about square shapes. [CFGV2003] extend RBC to shapes of what that they call <i>wide partitions</i>. A partition <math>λ</math> is <i>wide</i> if <math>μ ≥ μ'</math> for every partition <math>μ</math> whose parts are a submultiset of the multiset of parts of <math>λ</math>. Here <math>≥</math> denotes dominance (a.k.a. majorization) order and <math>μ'</math> denotes the conjugate of <math>μ</math>.		RBC may be thought of as a conjecture about square shapes. [CFGV2003] extend RBC to shapes of what that they call <i>wide partitions</i>. A partition <math>λ</math> is <i>wide</i> if <math>μ ≥ μ'</math> for every partition <math>μ</math> whose parts are a submultiset of the multiset of parts of <math>λ</math>. Here <math>≥</math> denotes dominance (a.k.a. majorization) order and <math>μ'</math> denotes the conjugate of <math>μ</math>.

	The <i>online</i> version of RBC posits that the bases are revealed one at a time, and the ordering of the elements of each basis must be chosen without knowing what the future bases are. [BD2015] prove that if the characteristic if the field does not divide AT(<math>n</math>), then the online version is true for that value of <math>n</math>. On the other hand, if <math>n</math> is odd and the field contains an <math>m</math>th root of unity for all odd <math>m < n</math>, then the online version of RBC is false.		The <i>online</i> version of RBC posits that the bases are revealed one at a time, and the ordering of the elements of each basis must be chosen without knowing what the future bases are. [BD2015] prove that if the characteristic if the field does not divide AT(<math>n</math>), then the online version is true for that value of <math>n</math>. On the other hand, if <math>n</math> is odd and the field contains an <math>m</math>th root of unity for all odd <math>m < n</math>, then the online version of RBC is false. One positive outcome of Polymath12 was to improve our understanding of the online version of RBC.

	[KL2015] give several equivalent formulations of the Alon–Tarsi Conjecture in terms of certain integrals over the special unitary group. [G2016] gives an equivalent formulation of the Alon–Tarsi Conjecture in terms of spherical functions.		[KL2015] give several equivalent formulations of the Alon–Tarsi Conjecture in terms of certain integrals over the special unitary group. [G2016] gives an equivalent formulation of the Alon–Tarsi Conjecture in terms of spherical functions.

Chowt: /* Variants of the problem */

2017-10-22T23:51:30Z

Variants of the problem

← Older revision		Revision as of 16:51, 22 October 2017
Line 70:		Line 70:
	Various attempts have been made to formulate an Alon–Tarsi Conjecture for odd <math>n</math>. For example, it is conjectured by [SW2012] that the number of <i>reduced</i> even Latin squares is not equal to the number of <i>reduced</i> odd Latin squares; [AL2015] prove that this is equivalent to the original Alon–Tarsi conjecture. [Z1997] has a related conjecture where "reduced" is replaced by "the first row is the identity permutation and the diagonal is all 1's."		Various attempts have been made to formulate an Alon–Tarsi Conjecture for odd <math>n</math>. For example, it is conjectured by [SW2012] that the number of <i>reduced</i> even Latin squares is not equal to the number of <i>reduced</i> odd Latin squares; [AL2015] prove that this is equivalent to the original Alon–Tarsi conjecture. [Z1997] has a related conjecture where "reduced" is replaced by "the first row is the identity permutation and the diagonal is all 1's."

	[C2009] proposes the following conjecture. For <math>k ≤ n</math>, let <math>M</math> be a matroid of rank <math>k</math> on <math>kn</math> elements that is a disjoint union of <math>k</math> bases. Let <math>I</math><sub>1</sub>, <math>I</math><sub>1</sub>, … <math>I</math><sub><math>n</math></sub> be disjoint independent sets of <math>M</math>, with 0 ≤ \|<math>I</math><sub><math>i</math></sub>\| ≤ <math>k</math> for all <math>i</math>. Then there exists an <math>n</math> × <math>k</math> grid <math>G</math> containing each element of <math>M</math> exactly		[C2009] proposes the following conjecture. For <math>k ≤ n</math>, let <math>M</math> be a matroid of rank <math>k</math> on <math>kn</math> elements that is a disjoint union of <math>k</math> bases. Let <math>I</math><sub>1</sub>, <math>I</math><sub>2</sub>, …, <math>I</math><sub><math>n</math></sub> be disjoint independent sets of <math>M</math>, with 0 ≤ \|<math>I</math><sub><math>i</math></sub>\| ≤ <math>k</math> for all <math>i</math>. Then there exists an <math>n</math> × <math>k</math> grid <math>G</math> containing each element of <math>M</math> exactly
	once, such that for every <math>i</math>, the elements of <math>I</math><sub><math>i</math></sub> appear in the <math>i</math>th row of <math>G</math> and such that every column of <math>G</math> is a basis of <math>M</math>. It is shown that this conjecture ~~implies~~ RBC, but unfortunately [HKL2010] show that it is false for <math>k ≤ n/3</math>.		once, such that for every <math>i</math>, the elements of <math>I</math><sub><math>i</math></sub> appear in the <math>i</math>th row of <math>G</math> and such that every column of <math>G</math> is a basis of <math>M</math>. It is shown that for any fixed <math>k</math>, this conjecture would imply RBC, but unfortunately [HKL2010] show that it is false for <math>k ≤ n/3</math>. These counterexamples are useful for disproving various other overly strong generalizations of RBC.

	== Discussion ==		== Discussion ==