Hyper-optimistic conjecture

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

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

n=2 by hand

One should in fact be able to get the Pareto-optimal and extremal statistics for the slice densities [math]\displaystyle{ \alpha_{a,b,c} := |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}| }[/math] in this case.

n=3 by hand

[math]\displaystyle{ c^{\mu}_3=6 }[/math]:

If we have all Three points of the form xxx removed Then the remaining points have value 7 and We have covered all lines any set of moving coordinates And all constant points equal to one value this leaves The lines xab a,b not equal. Each point of the set abc covers three of these lines the entire set covers each of these lines there is no duplication the only alternative is to remove a point abc and cover the lines with points of the form aab which have a higher weight and only cover one line each this would lower the weight so the maximum weight occurs when all of abc is omitted along with the three points xxx and the weight is 6

If we have only two points removed of the form xxx then The weight is at most 8 say the point not removed is 222 Then we must cover the lines xx2 and x22 we have three six such Lines and all the xx2 must be covered one at a time by either 112 Or 332 the x22 must be covered one at a time by 322 or 122 These points must be removed and the that lowers the weight To 8 - 3*(2/6) – 3*(2/6) = 6 again we have c^{\mu} must be less than 6

If we have one point removed say 111 then we must cover all lines of The form xx2 xx3 and x22 and x33 the best we can do is to cover these lines Two of at once as no point can cover x22 and x33 or xx2 and xx3 And we have all points of the form aab when a = 2 and b =3 Or b=2 and a=3 Only points of the form xxy can cover these lines and as we have 12 lines Cover 2 at a times we must have 6 such lines which will have weight 2/6 So we will have removed one point with weight one and six more With weight 1/3 giving remaining weight 7 and we will have Lines of the form x11 and xx1 to cover as well as x12 and x13 The lines of the form x11 will have to be covered by 3 lines with Weight 1/3 however we are not done as we can split a point of the Form 223 into 113 and 221 then we will cover the lines 22x and xx3 With two lines instead of one but we will cover one line of the Form 11x however we due this we will either have to split 3 pairs and we will have weight 6 since 7-1=6 or split two and use one point of the form 11x for the remaining line of the form 11x or again the total is 6 or split one and use 2 and again the remaining points total 6.

Finally we have no points of the form xxx removed but then we will have a line of the form xxx.