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

Slice densities

Given any [math]\displaystyle{ (a,b,c) \in \Delta_n }[/math] and a line-free set A, define the slice density [math]\displaystyle{ \alpha_{a,b,c} }[/math] to be the quantity [math]\displaystyle{ \alpha_{a,b,c} := |A \cap \Gamma_{a,b,c}|/|\Gamma_{a,b,c}| }[/math]. The equal-slices measure of A is thus the sum of all the slice densities.

Clearly [math]\displaystyle{ 0 \leq \alpha_{a,b,c} \leq 1 }[/math]. We also have that [math]\displaystyle{ \alpha_{a+r,b,c}+\alpha_{a,b+r,c}+\alpha_{a,b,c+r} \leq 2 }[/math] for all upward-pointing triangles (a+r,b,c), (a,b+r,c), (a,b,c+r).

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} }[/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 one point say 111 is removed then we must cover all lines of the form xx2 xx3 and x22 and x33

Look at the pairs of lines such as xx2 and 33x one with moving coordinates in two positions and a fixed coordinate equal to 2 or 3 say 2 the other with fixed coordinates equal to the other value which in this case is 3 so if the fixed coordinate(s) in one point of the pair is 2 in the other

they or it will be three

Then we must have one of the points 222 112 332 removed to block the first line of the pair and for the second line we can use 333 332 331. However we do not have the points 222 or 333 removed in this case so we must have either 332 or the pair 112 or 331. For every one of the six point 332 or 223 we will have a similar choice forcing either the removal of the point itself or the associated pair. After these choices have been made more points of the form aab can be added but there must be a subset corresponding to one set of the above six choices since in each case there are only two ways to cover the lines noted. If we start with the configuration 111 removed all six points with two 2’s and one three and two 3’s and one two removed and all points of the form abc removed then this configuration has weight 6 then we can perform a series of steps which will reach all combinatorial line free configurations.

These steps are as follows:

1 Making choices as above and allowing the addition Of all possible abcs

2.Removal of points of the form aab and addition of all possible abc’s

3.Removal of abc

It will be shown that with each step the weight decreases or remains the same so the weight is 6 or less This will give all line free configurations as we must have sub configuration corresponding to one of the six choices and all we can do is add points of the form aab and take the resulting set with the most possible Abc’s and them remove any arbitrary abcs that we wish to remove.

Are the making of the six choices noted above and the addition of any points of the form abc where possible without forming a combinatorial line. At the start each point of the form abc cannot be added because it has two lines which are some permutations of x12 and x13 now look at the points possibly blocking x12 they are 112 212 and 312 initially point 312 which is removed could not be added because the two points 112 and 212 are not removed as each choice is moved then each of the removed lines of type 113 covers two lines of the form permutations of x13 similarly lines of type 133 covers two lines of the form permutations of x13 now each choice to replace a line of the form 332 increase the number of points removed with two coordinates the same by one thus lowers the weight by one third and blocks four lines of the form x13 or x12 thus after n such choices we have reduced the weight by n/3 and covered 4n such lines since every point of the of the form permutations of 123 starts out with 2 such lines which it is blocking and can only be added when they are filled we can only add at most 2n such points which since they have weight 1/6 at the end of n such steps the weight is unchanged now afterwards if we remove more points of the form aab they cover at most two lines of the form xab and thus allow at most two points of the form abc to be added thus the change in weight is at most -1/3 +1/6 +1/6=0 finally afterwards we can remove points of the form abc but that will only lower the weight.

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