Hyper-optimistic conjecture

2009-03-10T08:17:30Z

76.99.55.222: add key word "maximum"

[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 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 [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_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}_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]

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

Polymath Wiki - User contributions [en]

Hyper-optimistic conjecture