Hyper-optimistic conjecture: Difference between revisions

From Polymath Wiki
Jump to navigationJump to search
← Older editNewer edit →
No edit summary
No edit summary
Line 1: Line 1:
[http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity/#comment-2114 Gil Kalai] and [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity/#comment-2119 Tim Gowers] have proposed a “hyper-optimistic” conjecture. Given a set <math>A \subset {}[3]^n</math>, define the ''weighted size'' <math>\mu(A)</math> of <math>A</math> by the formula
[http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity/#comment-2114 Gil Kalai] and [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity/#comment-2119 Tim Gowers] have proposed a “hyper-optimistic” conjecture.  


:<math>\mu(A) := \sum_{a+b+c=n} |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}|</math>
Let <math>c^\mu_n</math> be the [[equal-slices measure]] of a line-free set. For instance, <math>c^\mu_0 = 1</math>, <math>c^\mu_1 = 2</math>, and <math>c^\mu_2 = 4</math>.


thus each slice <math>\Gamma_{a,b,c}</math> has weighted size 1 (and we have been referring to \mu as “slices-equal measure” for this reason), and the whole cube <math>{}[3]^n</math> has weighted size equal to the <math>(n+1)^{th}</math> triangular number, <math>\frac{(n+1)(n+2)}{2}</math>.
As in the unweighted case, every time we find a subset <math>B</math> of the grid <math>\Delta_n := \{ (a,b,c): a+b+c=n\}</math> without equilateral triangles, it gives a line-free set <math>\Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c}</math>. The [[equal-slices measure]] of this set is precisely the cardinality of B. Thus we have the lower bound <math>c^\mu_n \geq \overline{c}^\mu_n</math>, where <math>\overline{c}^\mu_n</math> is the largest size of equilateral triangles in <math>\Delta_n</math>.  The computation of the <math>\overline{c}^\mu_n</math> is [[Fujimura's problem]].


'''Example:''' in <math>{}[3]^2</math>, the diagonal points 11, 22, 33 each have weighted size 1, whereas the other six off-diagonal points have weighted size 1/2. The total weighted size of <math>{}[3]^2</math> is 6.
'''Hyper-optimistic conjecture:''' We in fact have <math>c^\mu_n = \overline{c}^\mu_n</math>. In other words, to get the optimal [[equal-slices measure]] for a line-free set, one should take a set which is a union of slices <math>\Gamma_{a,b,c}</math>.
 
Let <math>c^\mu_n</math> be the largest weighted size of a line-free set. For instance, <math>c^\mu_0 = 1</math>, <math>c^\mu_1 = 2</math>, and <math>c^\mu_2 = 4</math>.
 
As in the unweighted case, every time we find a subset <math>B</math> of the grid <math>\Delta_n := \{ (a,b,c): a+b+c=n\}</math> without equilateral triangles, it gives a line-free set <math>\Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c}</math>. The weighted size of this set is precisely the cardinality of B. Thus we have the lower bound <math>c^\mu_n \geq \overline{c}^\mu_n</math>, where <math>\overline{c}^\mu_n</math> is the largest size of equilateral triangles in <math>\Delta_n</math>.  The computation of the <math>\overline{c}^\mu_n</math> is [[Fujimura's problem]].
 
'''Hyper-optimistic conjecture:''' We in fact have <math>c^\mu_n = \overline{c}^\mu_n</math>. In other words, to get the optimal weighted size for a line-free set, one should take a set which is a union of slices <math>\Gamma_{a,b,c}</math>.


This conjecture, if true, will imply the DHJ theorem. Note also that all our best lower bounds for the unweighted problem to date have been unions of slices. Also, the k=2 analogue of the conjecture is true, and is known as the [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality LYM inequality] (in fact, for k=2 we have <math>c^\mu_n = \overline{c}^\mu_n = 1</math> for all n).
This conjecture, if true, will imply the DHJ theorem. Note also that all our best lower bounds for the unweighted problem to date have been unions of slices. Also, the k=2 analogue of the conjecture is true, and is known as the [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality LYM inequality] (in fact, for k=2 we have <math>c^\mu_n = \overline{c}^\mu_n = 1</math> for all n).

Revision as of 10:33, 15 February 2009

Gil Kalai and Tim Gowers have proposed a “hyper-optimistic” conjecture.

Let [math]\displaystyle{ c^\mu_n }[/math] be the equal-slices measure of a line-free set. For instance, [math]\displaystyle{ c^\mu_0 = 1 }[/math], [math]\displaystyle{ c^\mu_1 = 2 }[/math], and [math]\displaystyle{ c^\mu_2 = 4 }[/math].

As in the unweighted case, every time we find a subset [math]\displaystyle{ B }[/math] of the grid [math]\displaystyle{ \Delta_n := \{ (a,b,c): a+b+c=n\} }[/math] without equilateral triangles, it gives a line-free set [math]\displaystyle{ \Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c} }[/math]. The equal-slices measure of this set is precisely the cardinality of B. Thus we have the lower bound [math]\displaystyle{ c^\mu_n \geq \overline{c}^\mu_n }[/math], where [math]\displaystyle{ \overline{c}^\mu_n }[/math] is the largest size of equilateral triangles in [math]\displaystyle{ \Delta_n }[/math]. The computation of the [math]\displaystyle{ \overline{c}^\mu_n }[/math] is Fujimura's problem.

Hyper-optimistic conjecture: We in fact have [math]\displaystyle{ c^\mu_n = \overline{c}^\mu_n }[/math]. In other words, to get the optimal equal-slices measure for a line-free set, one should take a set which is a union of slices [math]\displaystyle{ \Gamma_{a,b,c} }[/math].

This conjecture, if true, will imply the DHJ theorem. Note also that all our best lower bounds for the unweighted problem to date have been unions of slices. Also, the k=2 analogue of the conjecture is true, and is known as the LYM inequality (in fact, for k=2 we have [math]\displaystyle{ c^\mu_n = \overline{c}^\mu_n = 1 }[/math] for all n).

Retrieved from "https://michaelnielsen.org/polymath/index.php?title=Hyper-optimistic_conjecture&oldid=175"