https://michaelnielsen.org/polymath/index.php?action=history&feed=atom&title=Discretized_Borel_Determinacy_and_P%3DNP 2026-05-27T14:55:52Z Revision history for this page on the wiki MediaWiki 1.42.3 https://michaelnielsen.org/polymath/index.php?title=Discretized_Borel_Determinacy_and_P%3DNP&diff=9755&oldid=prev 2015-11-03T16:37:37Z

<p>Undo revision 9754 by <a href="/polymath/index.php?title=Special:Contributions/Teorth" title="Special:Contributions/Teorth">Teorth</a> (<a href="/polymath/index.php?title=User_talk:Teorth" title="User talk:Teorth">talk</a>)</p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 09:37, 3 November 2015</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">== The problem ==</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Unlike prior Polymath projects</ins>, the <ins style="font-weight: bold; text-decoration: none;">main wiki pages </ins>for <ins style="font-weight: bold; text-decoration: none;">this project will not </ins>be <ins style="font-weight: bold; text-decoration: none;">hosted here</ins>, <ins style="font-weight: bold; text-decoration: none;">but rather at </ins>[<ins style="font-weight: bold; text-decoration: none;">http</ins>://<ins style="font-weight: bold; text-decoration: none;">gowers</ins>.<ins style="font-weight: bold; text-decoration: none;">tiddlyspace</ins>.com <ins style="font-weight: bold; text-decoration: none;">this tiddlywiki</ins>].</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">A &lt;I&gt;sunflower&lt;/I&gt; (a.k.a. &lt;I&gt;Delta-system&lt;/I&gt;) of size &lt;math&gt;r&lt;/math&gt; is a family of sets &lt;math&gt;A_1, A_2, \dots, A_r&lt;/math&gt; such that every element that belongs to more than one of the sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:&lt;B&gt;Erdos-Rado Delta-system theorem&lt;/B&gt;: There is a function &lt;math&gt;f(k,r)&lt;/math&gt; so that every family &lt;math&gt;\cal F&lt;/math&gt; of &lt;math&gt;k&lt;/math&gt;-sets with more than &lt;math&gt;f(k</del>,<del style="font-weight: bold; text-decoration: none;">r)&lt;/math&gt; members contains a sunflower of size &lt;math&gt;r&lt;/math&gt;.</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">(We denote by &lt;math&gt;f(k,r)&lt;/math&gt; </del>the <del style="font-weight: bold; text-decoration: none;">smallest integer that suffices </del>for <del style="font-weight: bold; text-decoration: none;">the assertion of the theorem to </del>be <del style="font-weight: bold; text-decoration: none;">true.) The simple proof giving &lt;math&gt;f(k</del>,<del style="font-weight: bold; text-decoration: none;">r)\le k! (r-1)^k&lt;/math&gt; can be found </del>[<del style="font-weight: bold; text-decoration: none;">https</del>://<del style="font-weight: bold; text-decoration: none;">gilkalai</del>.<del style="font-weight: bold; text-decoration: none;">wordpress</del>.com<del style="font-weight: bold; text-decoration: none;">/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/ here</del>]<del style="font-weight: bold; text-decoration: none;">.</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">The best known general upper bound on &lt;math&gt;f(k,r)&lt;/math&gt; (in the regime where &lt;math&gt;r&lt;/math&gt; is bounded and &lt;math&gt;k&lt;/math&gt; is large) is</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:&lt;math&gt;\displaystyle f(k,r) \leq D(r,\alpha) k! \left( \frac{(\log\log\log k)^2}{\alpha \log\log k} \right)^k&lt;/math&gt;</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">for any &lt;math&gt;\alpha &lt; 1&lt;/math&gt;, and some &lt;math&gt;D(r,\alpha)&lt;/math&gt; depending on &lt;math&gt;r,\alpha&lt;/math&gt;, proven by Kostkocha from 1996.  The objective of this project is to improve this bound, ideally to obtain the Erdos-Rado conjecture</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">:&lt;math&gt;\displaystyle f(k,r) \leq C(r)^k &lt;/math&gt;</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">for some &lt;math&gt;C(r)&lt;/math&gt; depending on &lt;math&gt;k&lt;/math&gt;.  This is known for &lt;math&gt;r=1,2&lt;/math&gt; but remains open for larger r</del>.</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Threads ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Threads ==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [<del style="font-weight: bold; text-decoration: none;">https</del>://<del style="font-weight: bold; text-decoration: none;">gilkalai</del>.wordpress.com/<del style="font-weight: bold; text-decoration: none;">2015</del>/<del style="font-weight: bold; text-decoration: none;">11</del>/<del style="font-weight: bold; text-decoration: none;">03</del>/<del style="font-weight: bold; text-decoration: none;">polymath10</del>-<del style="font-weight: bold; text-decoration: none;">the</del>-<del style="font-weight: bold; text-decoration: none;">erdos</del>-<del style="font-weight: bold; text-decoration: none;">rado</del>-<del style="font-weight: bold; text-decoration: none;">delta</del>-<del style="font-weight: bold; text-decoration: none;">system</del>-<del style="font-weight: bold; text-decoration: none;">conjecture Polymath10: The Erdos Rado Delta System Conjecture</del>], <del style="font-weight: bold; text-decoration: none;">Gil Kalai</del>, <del style="font-weight: bold; text-decoration: none;">Nov 2</del>, <del style="font-weight: bold; text-decoration: none;">2015</del>.  <del style="font-weight: bold; text-decoration: none;">&lt;B&gt;Active&lt;/B&gt;</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [<ins style="font-weight: bold; text-decoration: none;">http</ins>://<ins style="font-weight: bold; text-decoration: none;">gowers</ins>.wordpress.com/<ins style="font-weight: bold; text-decoration: none;">2013</ins>/<ins style="font-weight: bold; text-decoration: none;">10</ins>/<ins style="font-weight: bold; text-decoration: none;">24</ins>/<ins style="font-weight: bold; text-decoration: none;">what</ins>-<ins style="font-weight: bold; text-decoration: none;">i</ins>-<ins style="font-weight: bold; text-decoration: none;">did</ins>-<ins style="font-weight: bold; text-decoration: none;">in</ins>-<ins style="font-weight: bold; text-decoration: none;">my</ins>-<ins style="font-weight: bold; text-decoration: none;">summer</ins>-<ins style="font-weight: bold; text-decoration: none;">holidays/ What I did in my summer holidays</ins>], <ins style="font-weight: bold; text-decoration: none;">Timothy Gowers</ins>, <ins style="font-weight: bold; text-decoration: none;">Oct 24</ins>, <ins style="font-weight: bold; text-decoration: none;">2013</ins>.  <ins style="font-weight: bold; text-decoration: none;">''Inactive''</ins></div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [<ins style="font-weight: bold; text-decoration: none;">http</ins>://<ins style="font-weight: bold; text-decoration: none;">gowers</ins>.<ins style="font-weight: bold; text-decoration: none;">wordpress</ins>.<ins style="font-weight: bold; text-decoration: none;">com</ins>/<ins style="font-weight: bold; text-decoration: none;">2013</ins>/<ins style="font-weight: bold; text-decoration: none;">11</ins>/<ins style="font-weight: bold; text-decoration: none;">03</ins>/<ins style="font-weight: bold; text-decoration: none;">dbd1-initial-post DBD1 </ins>- <ins style="font-weight: bold; text-decoration: none;">initial post</ins>], <ins style="font-weight: bold; text-decoration: none;">Timothy Gowers</ins>, <ins style="font-weight: bold; text-decoration: none;">Nov 3</ins>, <ins style="font-weight: bold; text-decoration: none;">2013</ins>. <ins style="font-weight: bold; text-decoration: none;">''inactive''</ins></div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">== Bibliography ==</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [http://<ins style="font-weight: bold; text-decoration: none;">gowers</ins>.<ins style="font-weight: bold; text-decoration: none;">wordpress.com/2014/01/09</ins>/<ins style="font-weight: bold; text-decoration: none;">dbd2-success-of-a-kind</ins>/ <ins style="font-weight: bold; text-decoration: none;">DBD2 - success </ins>of a <ins style="font-weight: bold; text-decoration: none;">kind</ins>], <ins style="font-weight: bold; text-decoration: none;">Timothy Gowers</ins>, <ins style="font-weight: bold; text-decoration: none;">Jan </ins>9, <ins style="font-weight: bold; text-decoration: none;">2014</ins>. <ins style="font-weight: bold; text-decoration: none;"> </ins>&lt;<ins style="font-weight: bold; text-decoration: none;">B</ins>&gt;<ins style="font-weight: bold; text-decoration: none;">Active</ins>&lt;/<ins style="font-weight: bold; text-decoration: none;">B</ins>&gt;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome!</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div> </div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">* Intersection theorems for systems of sets, H. L. Abbott, D. Hanson, and N. Sauer,  J. Comb. Th. Ser. A 12 (1972), 381–389</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [<del style="font-weight: bold; text-decoration: none;">https</del>://<del style="font-weight: bold; text-decoration: none;">www</del>.<del style="font-weight: bold; text-decoration: none;">math</del>.<del style="font-weight: bold; text-decoration: none;">uni-bielefeld.de</del>/<del style="font-weight: bold; text-decoration: none;">ahlswede</del>/<del style="font-weight: bold; text-decoration: none;">homepage</del>/<del style="font-weight: bold; text-decoration: none;">public</del>/<del style="font-weight: bold; text-decoration: none;">114.pdf The Complete Nontrivial</del>-<del style="font-weight: bold; text-decoration: none;">Intersection Theorem for Systems of Finite Sets</del>], <del style="font-weight: bold; text-decoration: none;">R. Ahlswede</del>, <del style="font-weight: bold; text-decoration: none;">L. Khachatrian</del>, <del style="font-weight: bold; text-decoration: none;">Journal of Combinatorial Theory, Series A 76, 121-�138 (1996)</del>.</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [http://<del style="font-weight: bold; text-decoration: none;">arxiv</del>.<del style="font-weight: bold; text-decoration: none;">org</del>/<del style="font-weight: bold; text-decoration: none;">abs</del>/<del style="font-weight: bold; text-decoration: none;">1205.6847 On the Maximum Number </del>of <del style="font-weight: bold; text-decoration: none;">Edges in </del>a <del style="font-weight: bold; text-decoration: none;">Hypergraph with Given Matching Number</del>], <del style="font-weight: bold; text-decoration: none;">P. Frankl</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">* An intersection theorem for systems of sets, A. V. Kostochka, Random Structures and Algorithms</del>, 9<del style="font-weight: bold; text-decoration: none;">(1996)</del>, <del style="font-weight: bold; text-decoration: none;">213-221</del>.</div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">* [http://www.math.uiuc.edu/~kostochk/docs/2000/survey3.pdf Extremal problems on </del>&lt;<del style="font-weight: bold; text-decoration: none;">math</del>&gt;<del style="font-weight: bold; text-decoration: none;">\Delta</del>&lt;/<del style="font-weight: bold; text-decoration: none;">math</del>&gt;<del style="font-weight: bold; text-decoration: none;">-systems], A. V. Kostochka</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">* [http://arxiv.org/abs/1202.4196 On Erdos' extremal problem on matchings in hypergraphs], T. Luczak, K. Mieczkowska</del></div></td><td colspan="2" class="diff-side-added"></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">* Intersection theorems for systems of sets,  J. H. Spencer, Canad. Math. Bull. 20 (1977), 249-254.</del></div></td><td colspan="2" class="diff-side-added"></td></tr> </table>

Teorth https://michaelnielsen.org/polymath/index.php?title=Discretized_Borel_Determinacy_and_P%3DNP&diff=9754&oldid=prev 2015-11-03T16:37:06Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 09:37, 3 November 2015</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1">Line 1:</td> <td colspan="2" class="diff-lineno">Line 1:</td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div><del style="font-weight: bold; text-decoration: none;">Unlike prior Polymath projects</del>, the <del style="font-weight: bold; text-decoration: none;">main wiki pages </del>for <del style="font-weight: bold; text-decoration: none;">this project will not </del>be <del style="font-weight: bold; text-decoration: none;">hosted here</del>, <del style="font-weight: bold; text-decoration: none;">but rather at </del>[<del style="font-weight: bold; text-decoration: none;">http</del>://<del style="font-weight: bold; text-decoration: none;">gowers</del>.<del style="font-weight: bold; text-decoration: none;">tiddlyspace</del>.com this <del style="font-weight: bold; text-decoration: none;">tiddlywiki]</del>.</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">== The problem ==</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">A &lt;I&gt;sunflower&lt;/I&gt; (a.k.a. &lt;I&gt;Delta-system&lt;/I&gt;) of size &lt;math&gt;r&lt;/math&gt; is a family of sets &lt;math&gt;A_1, A_2, \dots, A_r&lt;/math&gt; such that every element that belongs to more than one of the sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;B&gt;Erdos-Rado Delta-system theorem&lt;/B&gt;: There is a function &lt;math&gt;f(k,r)&lt;/math&gt; so that every family &lt;math&gt;\cal F&lt;/math&gt; of &lt;math&gt;k&lt;/math&gt;-sets with more than &lt;math&gt;f(k</ins>,<ins style="font-weight: bold; text-decoration: none;">r)&lt;/math&gt; members contains a sunflower of size &lt;math&gt;r&lt;/math&gt;.</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">(We denote by &lt;math&gt;f(k,r)&lt;/math&gt; </ins>the <ins style="font-weight: bold; text-decoration: none;">smallest integer that suffices </ins>for <ins style="font-weight: bold; text-decoration: none;">the assertion of the theorem to </ins>be <ins style="font-weight: bold; text-decoration: none;">true.) The simple proof giving &lt;math&gt;f(k</ins>,<ins style="font-weight: bold; text-decoration: none;">r)\le k! (r-1)^k&lt;/math&gt; can be found </ins>[<ins style="font-weight: bold; text-decoration: none;">https</ins>://<ins style="font-weight: bold; text-decoration: none;">gilkalai</ins>.<ins style="font-weight: bold; text-decoration: none;">wordpress</ins>.com<ins style="font-weight: bold; text-decoration: none;">/2008/09/28/extremal-combinatorics-iii-some-basic-theorems/ here].</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">The best known general upper bound on &lt;math&gt;f(k,r)&lt;/math&gt; (in the regime where &lt;math&gt;r&lt;/math&gt; is bounded and &lt;math&gt;k&lt;/math&gt; is large) is</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;math&gt;\displaystyle f(k,r) \leq D(r,\alpha) k! \left( \frac{(\log\log\log k)^2}{\alpha \log\log k} \right)^k&lt;/math&gt;</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">for any &lt;math&gt;\alpha &lt; 1&lt;/math&gt;, and some &lt;math&gt;D(r,\alpha)&lt;/math&gt; depending on &lt;math&gt;r,\alpha&lt;/math&gt;, proven by Kostkocha from 1996.  The objective of </ins>this <ins style="font-weight: bold; text-decoration: none;">project is to improve this bound, ideally to obtain the Erdos-Rado conjecture</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">:&lt;math&gt;\displaystyle f(k,r) \leq C(r)^k &lt;/math&gt;</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">for some &lt;math&gt;C(r)&lt;/math&gt; depending on &lt;math&gt;k&lt;/math&gt;.  This is known for &lt;math&gt;r=1,2&lt;/math&gt; but remains open for larger r</ins>.</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Threads ==</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>== Threads ==</div></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [<del style="font-weight: bold; text-decoration: none;">http</del>://<del style="font-weight: bold; text-decoration: none;">gowers</del>.wordpress.com/<del style="font-weight: bold; text-decoration: none;">2013</del>/<del style="font-weight: bold; text-decoration: none;">10</del>/<del style="font-weight: bold; text-decoration: none;">24</del>/<del style="font-weight: bold; text-decoration: none;">what</del>-<del style="font-weight: bold; text-decoration: none;">i</del>-<del style="font-weight: bold; text-decoration: none;">did</del>-<del style="font-weight: bold; text-decoration: none;">in</del>-<del style="font-weight: bold; text-decoration: none;">my</del>-<del style="font-weight: bold; text-decoration: none;">summer</del>-<del style="font-weight: bold; text-decoration: none;">holidays</del>/ <del style="font-weight: bold; text-decoration: none;">What I did in my summer holidays]</del>, <del style="font-weight: bold; text-decoration: none;">Timothy Gowers</del>, <del style="font-weight: bold; text-decoration: none;">Oct 24</del>, <del style="font-weight: bold; text-decoration: none;">2013</del>.  <del style="font-weight: bold; text-decoration: none;">''Inactive''</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [<ins style="font-weight: bold; text-decoration: none;">https</ins>://<ins style="font-weight: bold; text-decoration: none;">gilkalai</ins>.wordpress.com/<ins style="font-weight: bold; text-decoration: none;">2015</ins>/<ins style="font-weight: bold; text-decoration: none;">11</ins>/<ins style="font-weight: bold; text-decoration: none;">03</ins>/<ins style="font-weight: bold; text-decoration: none;">polymath10</ins>-<ins style="font-weight: bold; text-decoration: none;">the</ins>-<ins style="font-weight: bold; text-decoration: none;">erdos</ins>-<ins style="font-weight: bold; text-decoration: none;">rado</ins>-<ins style="font-weight: bold; text-decoration: none;">delta</ins>-<ins style="font-weight: bold; text-decoration: none;">system</ins>-<ins style="font-weight: bold; text-decoration: none;">conjecture Polymath10: The Erdos Rado Delta System Conjecture], Gil Kalai, Nov 2, 2015.  &lt;B&gt;Active&lt;</ins>/<ins style="font-weight: bold; text-decoration: none;">B&gt;</ins></div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [<del style="font-weight: bold; text-decoration: none;">http</del>://<del style="font-weight: bold; text-decoration: none;">gowers</del>.<del style="font-weight: bold; text-decoration: none;">wordpress</del>.<del style="font-weight: bold; text-decoration: none;">com</del>/<del style="font-weight: bold; text-decoration: none;">2013</del>/<del style="font-weight: bold; text-decoration: none;">11</del>/<del style="font-weight: bold; text-decoration: none;">03</del>/<del style="font-weight: bold; text-decoration: none;">dbd1</del>-<del style="font-weight: bold; text-decoration: none;">initial-post DBD1 - initial post</del>], <del style="font-weight: bold; text-decoration: none;">Timothy Gowers</del>, <del style="font-weight: bold; text-decoration: none;">Nov 3</del>, <del style="font-weight: bold; text-decoration: none;">2013</del>. <del style="font-weight: bold; text-decoration: none;">''inactive''</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [http://<del style="font-weight: bold; text-decoration: none;">gowers</del>.<del style="font-weight: bold; text-decoration: none;">wordpress.com</del>/<del style="font-weight: bold; text-decoration: none;">2014</del>/<del style="font-weight: bold; text-decoration: none;">01/09/dbd2-success-</del>of<del style="font-weight: bold; text-decoration: none;">-</del>a<del style="font-weight: bold; text-decoration: none;">-kind/ DBD2 - success </del>of <del style="font-weight: bold; text-decoration: none;">a kind]</del>, <del style="font-weight: bold; text-decoration: none;">Timothy Gowers</del>, <del style="font-weight: bold; text-decoration: none;">Jan </del>9, <del style="font-weight: bold; text-decoration: none;">2014</del>. <del style="font-weight: bold; text-decoration: none;"> </del>&lt;<del style="font-weight: bold; text-decoration: none;">B</del>&gt;<del style="font-weight: bold; text-decoration: none;">Active</del>&lt;/<del style="font-weight: bold; text-decoration: none;">B</del>&gt;</div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">== Bibliography ==</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">Edits to improve the bibliography (by adding more links, Mathscinet numbers, bibliographic info, etc.) are welcome!</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div> </div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Intersection theorems for systems of sets</ins>, <ins style="font-weight: bold; text-decoration: none;">H. L. Abbott</ins>, <ins style="font-weight: bold; text-decoration: none;">D. Hanson</ins>, <ins style="font-weight: bold; text-decoration: none;">and N</ins>. <ins style="font-weight: bold; text-decoration: none;">Sauer, </ins> <ins style="font-weight: bold; text-decoration: none;">J. Comb. Th. Ser. A 12 (1972), 381–389</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [<ins style="font-weight: bold; text-decoration: none;">https</ins>://<ins style="font-weight: bold; text-decoration: none;">www</ins>.<ins style="font-weight: bold; text-decoration: none;">math.uni-bielefeld</ins>.<ins style="font-weight: bold; text-decoration: none;">de</ins>/<ins style="font-weight: bold; text-decoration: none;">ahlswede</ins>/<ins style="font-weight: bold; text-decoration: none;">homepage</ins>/<ins style="font-weight: bold; text-decoration: none;">public</ins>/<ins style="font-weight: bold; text-decoration: none;">114.pdf The Complete Nontrivial</ins>-<ins style="font-weight: bold; text-decoration: none;">Intersection Theorem for Systems of Finite Sets</ins>], <ins style="font-weight: bold; text-decoration: none;">R. Ahlswede</ins>, <ins style="font-weight: bold; text-decoration: none;">L. Khachatrian, Journal of Combinatorial Theory, Series A 76</ins>, <ins style="font-weight: bold; text-decoration: none;">121-�138 (1996)</ins>.</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [http://<ins style="font-weight: bold; text-decoration: none;">arxiv</ins>.<ins style="font-weight: bold; text-decoration: none;">org</ins>/<ins style="font-weight: bold; text-decoration: none;">abs</ins>/<ins style="font-weight: bold; text-decoration: none;">1205.6847 On the Maximum Number </ins>of <ins style="font-weight: bold; text-decoration: none;">Edges in </ins>a <ins style="font-weight: bold; text-decoration: none;">Hypergraph with Given Matching Number], P. Frankl</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* An intersection theorem for systems </ins>of <ins style="font-weight: bold; text-decoration: none;">sets, A. V. Kostochka</ins>, <ins style="font-weight: bold; text-decoration: none;">Random Structures and Algorithms</ins>, 9<ins style="font-weight: bold; text-decoration: none;">(1996)</ins>, <ins style="font-weight: bold; text-decoration: none;">213-221</ins>.</div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* [http://www.math.uiuc.edu/~kostochk/docs/2000/survey3.pdf Extremal problems on </ins>&lt;<ins style="font-weight: bold; text-decoration: none;">math</ins>&gt;<ins style="font-weight: bold; text-decoration: none;">\Delta</ins>&lt;/<ins style="font-weight: bold; text-decoration: none;">math</ins>&gt;<ins style="font-weight: bold; text-decoration: none;">-systems], A. V. Kostochka</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* [http://arxiv.org/abs/1202.4196 On Erdos' extremal problem on matchings in hypergraphs], T. Luczak, K. Mieczkowska</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* Intersection theorems for systems of sets,  J. H. Spencer, Canad. Math. Bull. 20 (1977), 249-254.</ins></div></td></tr> </table>

Teorth https://michaelnielsen.org/polymath/index.php?title=Discretized_Borel_Determinacy_and_P%3DNP&diff=9348&oldid=prev 2014-01-09T16:32:41Z

<p></p> <table style="background-color: #fff; color: #202122;" data-mw="interface"> <col class="diff-marker" /> <col class="diff-content" /> <col class="diff-marker" /> <col class="diff-content" /> <tr class="diff-title" lang="en"> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td> <td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 09:32, 9 January 2014</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l4">Line 4:</td> <td colspan="2" class="diff-lineno">Line 4:</td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><br></td></tr> <tr><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* [http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summer-holidays/ What I did in my summer holidays], Timothy Gowers, Oct 24, 2013.  &#039;&#039;Inactive&#039;&#039;</div></td><td class="diff-marker"></td><td style="background-color: #f8f9fa; color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #eaecf0; vertical-align: top; white-space: pre-wrap;"><div>* [http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summer-holidays/ What I did in my summer holidays], Timothy Gowers, Oct 24, 2013.  &#039;&#039;Inactive&#039;&#039;</div></td></tr> <tr><td class="diff-marker" data-marker="−"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [http://gowers.wordpress.com/2013/11/03/dbd1-initial-post DBD1 - initial post], Timothy Gowers, Nov 3, 2013. *Active<del style="font-weight: bold; text-decoration: none;">*</del></div></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [http://gowers.wordpress.com/2013/11/03/dbd1-initial-post DBD1 - initial post], Timothy Gowers, Nov 3, 2013. <ins style="font-weight: bold; text-decoration: none;">''inactive''</ins></div></td></tr> <tr><td colspan="2" class="diff-side-deleted"></td><td class="diff-marker" data-marker="+"></td><td style="color: #202122; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* <ins style="font-weight: bold; text-decoration: none;">[http://gowers.wordpress.com/2014/01/09/dbd2-success-of-a-kind/ DBD2 - success of a kind], Timothy Gowers, Jan 9, 2014.  &lt;B&gt;</ins>Active<ins style="font-weight: bold; text-decoration: none;">&lt;/B&gt;</ins></div></td></tr> </table>

Teorth https://michaelnielsen.org/polymath/index.php?title=Discretized_Borel_Determinacy_and_P%3DNP&diff=9151&oldid=prev 2013-11-17T18:41:11Z

<p>New page: Unlike prior Polymath projects, the main wiki pages for this project will not be hosted here, but rather at [http://gowers.tiddlyspace.com this tiddlywiki]. == Threads == * [http://gower...</p> <p><b>New page</b></p><div>Unlike prior Polymath projects, the main wiki pages for this project will not be hosted here, but rather at [http://gowers.tiddlyspace.com this tiddlywiki].<br /> <br /> == Threads ==<br /> <br /> * [http://gowers.wordpress.com/2013/10/24/what-i-did-in-my-summer-holidays/ What I did in my summer holidays], Timothy Gowers, Oct 24, 2013. &#039;&#039;Inactive&#039;&#039;<br /> * [http://gowers.wordpress.com/2013/11/03/dbd1-initial-post DBD1 - initial post], Timothy Gowers, Nov 3, 2013. *Active*</div>

Teorth