Difference between revisions of "Hyper-optimistic conjecture"

From Polymath Wiki
Jump to: navigation, search
Line 8: Line 8:
  
 
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).
 +
 +
== 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}_2=4</math> with [http://abel.math.umu.se/~klasm/solutions-n=2-k=3-HOC 3 solutions]
 +
* <math>c^{\mu}_3=6</math> with [http://abel.math.umu.se/~klasm/solutions-n=3-k=3-HOC 9 solutions]
 +
* <math>c^{\mu}_4=9</math> with [http://abel.math.umu.se/~klasm/solutions-n=4-k=3-HOC
 +
1 solution]
 +
* <math>c^{\mu}_5=12</math> with [http://abel.math.umu.se/~klasm/solutions-n=5-k=3-HOC
 +
1 solution]

Revision as of 17:27, 4 March 2009

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

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

1 solution]
1 solution]