Difference between revisions of "Hyper-optimistic conjecture"

From Polymath Wiki
Jump to: navigation, search
(New page: [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-obst...)
 
Line 3: Line 3:
 
:<math>\mu(A) := \sum_{a+b+c=n} |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}|</math>
 
:<math>\mu(A) := \sum_{a+b+c=n} |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}|</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>.
+
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>.
  
 
'''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.
 
'''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.

Revision as of 01:20, 14 February 2009

Gil Kalai and 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

[math]\mu(A) := \sum_{a+b+c=n} |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}|[/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].

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.

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 LYM inequality (in fact, for k=2 we have [math]c^\mu_n = \overline{c}^\mu_n = 1[/math] for all n).