Hyper-optimistic conjecture: Difference between revisions
No edit summary |
|||
| Line 15: | Line 15: | ||
The first few values are | 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 [http://abel.math.umu.se/~klasm/solutions-n=2-k=3-HOC 3 solutions] | * <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}_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 | * <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] | |||
* <math>c^{\mu}_5=12</math> with [http://abel.math.umu.se/~klasm/solutions-n=5-k=3-HOC | |||
Comparing this with the [[Fujimura's problem|known bounds]] for <math>\overline{c}^\mu_n</math> we see that the hyper-optimistic conjecture is true for <math>n \leq 5</math>. | |||
Revision as of 09:30, 4 March 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).
Small values of [math]\displaystyle{ 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]\displaystyle{ c^\mu_0=1 }[/math] (trivial)
- [math]\displaystyle{ c^\mu_1=2 }[/math] (trivial)
- [math]\displaystyle{ c^{\mu}_2=4 }[/math] with 3 solutions
- [math]\displaystyle{ c^{\mu}_3=6 }[/math] with 9 solutions
- [math]\displaystyle{ c^{\mu}_4=9 }[/math] with 1 solution
- [math]\displaystyle{ c^{\mu}_5=12 }[/math] with 1 solution
Comparing this with the known bounds for [math]\displaystyle{ \overline{c}^\mu_n }[/math] we see that the hyper-optimistic conjecture is true for [math]\displaystyle{ n \leq 5 }[/math].
