Difference between revisions of "Hyper-optimistic conjecture"

From Polymath Wiki
Jump to: navigation, search
(Small values of c^\mu_n)
(add key word "maximum")
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.  
 
[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.  
  
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>.
+
Let <math>c^\mu_n</math> be the maximum [[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>.
  
 
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]].
 
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]].

Revision as of 08:17, 10 March 2009

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

Let [math]c^\mu_n[/math] be the maximum 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].

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.

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

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

Small values of [math]c^\mu_n[/math]

I have now found the extremal solutions for the weighted problem in the hyper-optimistic conjecture, again using integer programming.

The first few values are

  • [math]c^\mu_0=1[/math] (trivial)
  • [math]c^\mu_1=2[/math] (trivial)
  • [math]c^{\mu}_2=4[/math] with 3 solutions
  • [math]c^{\mu}_3=6[/math] with 9 solutions
  • [math]c^{\mu}_4=9[/math] with 1 solution
  • [math]c^{\mu}_5=12[/math] with 1 solution

Comparing this with the known bounds for [math]\overline{c}^\mu_n[/math] we see that the hyper-optimistic conjecture is true for [math]n \leq 5[/math].