https://asone.ai/polymath/api.php?action=feedcontributions&user=76.99.55.222&feedformat=atom Polymath Wiki - User contributions [en] 2021-10-23T18:26:18Z User contributions MediaWiki 1.23.5 https://asone.ai/polymath/index.php?title=Hyper-optimistic_conjecture Hyper-optimistic conjecture 2009-03-10T08:17:30Z <p>76.99.55.222: add key word &quot;maximum&quot;</p> <hr /> <div>[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. <br /> <br /> Let &lt;math&gt;c^\mu_n&lt;/math&gt; be the maximum [[equal-slices measure]] of a line-free set. For instance, &lt;math&gt;c^\mu_0 = 1&lt;/math&gt;, &lt;math&gt;c^\mu_1 = 2&lt;/math&gt;, and &lt;math&gt;c^\mu_2 = 4&lt;/math&gt;.<br /> <br /> As in the unweighted case, every time we find a subset &lt;math&gt;B&lt;/math&gt; of the grid &lt;math&gt;\Delta_n := \{ (a,b,c): a+b+c=n\}&lt;/math&gt; without equilateral triangles, it gives a line-free set &lt;math&gt;\Gamma_B := \bigcup_{(a,b,c) \in B} \Gamma_{a,b,c}&lt;/math&gt;. The [[equal-slices measure]] of this set is precisely the cardinality of B. Thus we have the lower bound &lt;math&gt;c^\mu_n \geq \overline{c}^\mu_n&lt;/math&gt;, where &lt;math&gt;\overline{c}^\mu_n&lt;/math&gt; is the largest size of equilateral triangles in &lt;math&gt;\Delta_n&lt;/math&gt;. The computation of the &lt;math&gt;\overline{c}^\mu_n&lt;/math&gt; is [[Fujimura's problem]].<br /> <br /> '''Hyper-optimistic conjecture:''' We in fact have &lt;math&gt;c^\mu_n = \overline{c}^\mu_n&lt;/math&gt;. 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 &lt;math&gt;\Gamma_{a,b,c}&lt;/math&gt;.<br /> <br /> 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 &lt;math&gt;c^\mu_n = \overline{c}^\mu_n = 1&lt;/math&gt; for all n).<br /> <br /> == Small values of &lt;math&gt;c^\mu_n&lt;/math&gt; ==<br /> <br /> I have now found the extremal solutions for the weighted problem in the hyper-optimistic conjecture, again using integer programming.<br /> <br /> The first few values are<br /> <br /> * &lt;math&gt;c^\mu_0=1&lt;/math&gt; (trivial)<br /> * &lt;math&gt;c^\mu_1=2&lt;/math&gt; (trivial)<br /> * &lt;math&gt;c^{\mu}_2=4&lt;/math&gt; with [http://abel.math.umu.se/~klasm/solutions-n=2-k=3-HOC 3 solutions]<br /> * &lt;math&gt;c^{\mu}_3=6&lt;/math&gt; with [http://abel.math.umu.se/~klasm/solutions-n=3-k=3-HOC 9 solutions]<br /> * &lt;math&gt;c^{\mu}_4=9&lt;/math&gt; with [http://abel.math.umu.se/~klasm/solutions-n=4-k=3-HOC 1 solution]<br /> * &lt;math&gt;c^{\mu}_5=12&lt;/math&gt; with [http://abel.math.umu.se/~klasm/solutions-n=5-k=3-HOC 1 solution]<br /> <br /> Comparing this with the [[Fujimura's problem|known bounds]] for &lt;math&gt;\overline{c}^\mu_n&lt;/math&gt; we see that the hyper-optimistic conjecture is true for &lt;math&gt;n \leq 5&lt;/math&gt;.</div> 76.99.55.222