Polymath Wiki - User contributions [en]

"New Proof" grant acknowledgments

2015-12-10T23:13:51Z

Jozsef: Grant acknowledgement added (Jozsef)

Ryan O'Donnell was supported in part by NSF CAREER grant CCF-0747250, a Sloan Foundation research fellowship, and an Okawa Foundation research fellowship.

"This material is based upon work supported by the National Science Foundation under Grant No. CCF-0747250. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF)."

Terence Tao is supported by a grant from the MacArthur Foundation, by NSF grant DMS-0649473, and by the NSF Waterman award.

Jozsef Solymosi is supported by grants form NSERC and OTKA.

DHJ(k) implies multidimensional DHJ(k)

2009-03-15T16:36:08Z

Jozsef:

==Introduction==

This is a result that will be needed if the [[A_second_outline_of_a_density-increment_argument|proof of DHJ(3)]] is correct and we want to push it through for DHJ(k).

==The proof==

Let <math>\mathcal{A}</math> be a [[density]]-<math>\delta</math> subset of <math>[k]^n</math> and let M be large enough so that every subset of <math>[k]^M</math> of density at least <math>\theta</math> contains a [[combinatorial line]]. Now split <math>[k]^n</math> up into <math>[k]^M\times[k]^{n-M}.</math> For a proportion at least <math>\delta/2</math> of the points y in <math>[k]^{n-M}</math> the set of <math>x\in[k]^M</math> such that <math>(x,y)\in\mathcal{A}</math> has density at least <math>\delta/2.</math> Therefore, by DHJ(k) (with <math>\theta=\delta/2</math>) we have a combinatorial line. Since there are fewer than <math>(k+1)^M</math> combinatorial lines to choose from, by the pigeonhole principle we can find a combinatorial line <math>L\subset[k]^M</math> and a set <math>\mathcal{A}_1</math> of density <math>\delta/2(k+1)^M</math> in <math>[k]^{n-M}</math> such that <math>(x,y)\in\mathcal{A}</math> whenever <math>x\in L</math> and <math>y\in\mathcal{A}_1.</math> And now by induction we can find an (m-1)-dimensional subspace in <math>\mathcal{A}_1</math> and we're done.

==A weak multidimensional DHJ(k) implies DHJ(k)==

It is also true that a weak multidimensional DHJ(k) implies DHJ(k). We will show that the following statement is equivalent to DHJ(k):

“There is a constant, c < 1 that for every d there is an n that any c-dense subset of <math> [k]^n</math> contains a d-dimensional subspace.”

We should show that the statement above implies DHJ(k). As before, write <math> [k]^n</math> as <math> [k]^r\times[k]^s </math> , where s is much bigger than r. For each <math> y\in [k]^s</math> , define <math> \mathcal{A}_y</math> to be <math> \{x\in[k]^r:(x,y)\in\mathcal{A}\}</math> . Let Y denote the set of <math> y\in [k]^s</math> , that \mathcal{A}_y</math> is empty. Suppose that <math> \mathcal{A} </math> is large, line-free, and its density is <math> \delta =\Delta-\epsilon</math> where <math> \Delta</math> is the limit of density of line-free sets and <math> \epsilon < (1-c)\Delta</math> . We can also suppose that no <math> \mathcal{A}_y</math> has density much larger than <math> \Delta</math> as that would guarantee a combinatorial line. But then the density of Y is at most 1-c, so there is a c-dense set, <math> Z=[k]^s-Y</math>, such that any element is a tail of some elements of <math> \mathcal{A}</math> . For every <math> y \in Z</math> choose an <math> x\in [k]^r:(x,y)\in\mathcal{A}</math> . This x will be the colour of y. It gives a <math> [k]^r</math> colouring on Z. By the initial condition Z contains arbitrary large subspaces, so by HJ(k) we get a line in <math> \mathcal{A}</math> .

Main Page

2009-03-09T16:44:19Z

Jozsef: Undo revision 734 by 213.163.65.73 (Talk)

== Threads and further problems==

* (1-199) [http://gowers.wordpress.com/2009/02/01/a-combinatorial-approach-to-density-hales-jewett/ A combinatorial approach to density Hales-Jewett] (inactive)
* (200-299) [http://terrytao.wordpress.com/2009/02/05/upper-and-lower-bounds-for-the-density-hales-jewett-problem/ Upper and lower bounds for the density Hales-Jewett problem] (inactive)
* (300-399) [http://gowers.wordpress.com/2009/02/06/dhj-the-triangle-removal-approach/ The triangle-removal approach] (inactive)
* (400-499) [http://gowers.wordpress.com/2009/02/08/dhj-quasirandomness-and-obstructions-to-uniformity Quasirandomness and obstructions to uniformity] (inactive)
* (500-599) [http://gowers.wordpress.com/2009/02/13/dhj-possible-proof-strategies/#more-441/ Possible proof strategies] (inactive)
* (600-699) [http://terrytao.wordpress.com/2009/02/11/a-reading-seminar-on-density-hales-jewett/ A reading seminar on density Hales-Jewett] (inactive)
* (700-799) [http://terrytao.wordpress.com/2009/02/13/bounds-for-the-first-few-density-hales-jewett-numbers-and-related-quantities/ Bounds for the first few density Hales-Jewett numbers, and related quantities] (inactive)
* (800-849) [http://gowers.wordpress.com/2009/02/23/brief-review-of-polymath1/ Brief review of polymath1] (inactive)
* (850-899) [http://gowers.wordpress.com/2009/03/02/dhj3-851-899/ DHJ(3): 851-899] (active)
* (900-999) [http://terrytao.wordpress.com/2009/03/04/dhj3-900-999-density-hales-jewett-type-numbers/ DHJ(3): 900-999 (Density Hales-Jewett type numbers)] (active)

[http://blogsearch.google.com/blogsearch?hl=en&ie=UTF-8&q=polymath1&btnG=Search+Blogs Here is a further list of blog posts related to the Polymath1 project]. [http://en.wordpress.com/tag/polymath1/ Here is wordpress's list]. Here is a [[timeline]] of progress so far.

A spreadsheet containing the latest upper and lower bounds for <math>c_n</math> can be found [http://spreadsheets.google.com/ccc?key=p5T0SktZY9DsU-uZ1tK7VEg here]. Here are the proofs of our [[upper and lower bounds]] for these constants.

We are also collecting bounds for [[Fujimura's problem]], motivated by a [[hyper-optimistic conjecture]].

There is also a chance that we will be able to improve the known bounds on [[Moser's cube problem]].

Here are some [[unsolved problems]] arising from the above threads.

Here is a [[tidy problem page]].

== Proof strategies ==

It is natural to look for strategies based on one of the following:

* [[Szemerédi's original proof of Szemerédi's theorem]].
* [[Szemerédi's combinatorial proof of Roth's theorem]].
* [[Ajtai-Szemerédi's proof of the corners theorem]].
* The [[density increment method]].
* The [[triangle removal lemma]].
* [[Ergodic-inspired methods]].
* The [[Furstenberg-Katznelson argument]].
* Use of [[equal-slices measure]].

== Related theorems ==

* [[Carlson's theorem]].
* The [[Carlson-Simpson theorem]].
* [[Folkman's theorem]].
* The [[Graham-Rothschild theorem]].
* The colouring [[Hales-Jewett theorem]].
* The [[Kruskal-Katona theorem]].
* [[Roth's theorem]].
* The [[IP-Szemerédi theorem]].
* [[Sperner's theorem]].
* [[Szemerédi's regularity lemma]].
* [[Szemerédi's theorem]].
* The [[triangle removal lemma]].

All these theorems are worth knowing. The most immediately relevant are Roth's theorem, Sperner's theorem, Szemerédi's regularity lemma and the triangle removal lemma, but some of the others could well come into play as well.

==Important concepts related to possible proofs==

* [[Complexity of a set]]
* [[Concentration of measure]]
* [[Influence of variables]]
* [[Obstructions to uniformity]]
* [[Quasirandomness]]

==Complete proofs or detailed sketches of potentially useful results==

*[[Sperner's theorem|The multidimensional Sperner theorem]]
*[[Line-free sets correlate locally with complexity-1 sets]]
*[[Correlation with a 1-set implies correlation with a subspace]] (Not finished)
*[[Fourier-analytic_proof_of_Sperner|A Fourier-analytic proof of Sperner's theorem]]
*[[A second Fourier decomposition related to Sperner's theorem]]
*[[A Hilbert space lemma]]
*A [[Modification of the Ajtai-Szemerédi argument]]
*[[DHJ(k) implies multidimensional DHJ(k)]]

==Attempts at proofs of DHJ(3)==

*[[An outline of a density-increment argument]] (ultimately didn't work)
*[[A second outline of a density-increment argument]] (seems to be OK but more checking needed)

== Bibliography ==

[[Density Hales-Jewett]]

# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/hj43.pdf A density version of the Hales-Jewett theorem for k=3]“, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–241.
# H. Furstenberg, Y. Katznelson, “[http://math.stanford.edu/~katznel/dhj12.pdf A density version of the Hales-Jewett theorem]“, J. Anal. Math. 57 (1991), 64–119.
# R. McCutcheon, “[http://www.msci.memphis.edu/~randall/preprints/HJk3.pdf The conclusion of the proof of the density Hales-Jewett theorem for k=3]“, unpublished.

[[Coloring Hales-Jewett theorem]]

# A. Hales, R. Jewett, [http://www.jstor.org/stable/1993764 Regularity and positional games], Trans. Amer. Math. Soc. 106 1963 222--229. [http://www.ams.org/mathscinet-getitem?mr=143712 MR143712]
# N. Hindman, E. Tressler, "[http://www.math.ucsd.edu/~etressle/hj32.pdf The first non-trivial Hales-Jewett number is four]", preprint.
# P. Matet, "[http://dx.doi.org/10.1016/j.ejc.2006.06.021 Shelah's proof of the Hales-Jewett theorem revisited]", European J. Combin. 28 (2007), no. 6, 1742--1745. [http://www.ams.org/mathscinet-getitem?mr=2339499 MR2339499]
# S. Shelah, "[http://www.jstor.org/stable/1990952 Primitive recursive bounds for van der Waerden numbers]", J. Amer. Math. Soc. 1 (1988), no. 3, 683--697. [http://www.ams.org/mathscinet-getitem?mr=929498 MR 929498]

[[Roth's theorem]]

# E. Croot, "[http://www.math.gatech.edu/~ecroot/szemeredi.pdf Szemeredi's theorem on three-term progressions, at a glance], preprint.

Behrend-type constructions

# M. Elkin, "[http://arxiv.org/abs/0801.4310 An Improved Construction of Progression-Free Sets ]", preprint.
# B. Green, J. Wolf, "[http://arxiv.org/abs/0810.0732 A note on Elkin's improvement of Behrend's construction]", preprint.
# K. O'Bryant, "[http://arxiv.org/abs/0811.3057 Sets of integers that do not contain long arithmetic progressions]", preprint.

Triangles and corners

# M. Ajtai, E. Szemerédi, Sets of lattice points that form no squares, Stud. Sci. Math. Hungar. 9 (1974), 9--11 (1975). [http://www.ams.org/mathscinet-getitem?mr=369299 MR369299]
# I. Ruzsa, E. Szemerédi, Triple systems with no six points carrying three triangles. Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, pp. 939--945, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, 1978. [http://www.ams.org/mathscinet-getitem?mr=519318 MR519318]
# J. Solymosi, [http://journals.cambridge.org/action/displayAbstract?fromPage=online&aid=206943 A note on a question of Erdős and Graham], Combin. Probab. Comput. 13 (2004), no. 2, 263--267. [http://www.ams.org/mathscinet-getitem?mr=2047239 MR 2047239]

[[Kruskal-Katona theorem]]

# P. Keevash, "[http://arxiv.org/abs/0806.2023 Shadows and intersections: stability and new proofs]", preprint.

Main Page

2009-03-09T16:38:02Z

Jozsef: Undo revision 732 by 213.163.65.73 (Talk)

Sperner's theorem

2009-03-09T02:26:59Z

Jozsef: /* Strong version */

==Statement of the theorem==

Sperner's theorem as originally stated is a result about set systems. Suppose that you want to find the largest collection of sets <math>\mathcal{A}</math> such that no set in <math>\mathcal{A}</math> is a proper subset of any other. Then the best you can do is choose all the sets of some fixed size---and of course the best size to pick is <math>\lfloor n/2\rfloor</math>, since the binomial coefficient <math>\binom nm</math> is maximized when <math>m=\lfloor n/2\rfloor.</math>

Sperner's theorem is closely related to the density Hales-Jewett theorem: in fact, it is nothing other than DHJ(2) with the best possible bound. To see this, we associate each set <math>A\subset[n]</math> with its characteristic function (that is, the sequence that is 0 outside A and 1 in A). If we have a pair of sets <math>A\subset B,</math> then the two sequences form a [[combinatorial line]] in <math>[2]^n.</math> For example, if n=6 and A and B are the sets <math>\{2,3\}</math> and <math>\{2,3,4,6\}</math>, then we get the combinatorial line that consists of the two points 011000 and 011101, which we can denote by 011*0* (so the wildcard set is <math>\{4,6\}</math>).

==Proof of the theorem==

There are several proofs, but perhaps the most enlightening is a very simple averaging argument that proves a stronger result. Let <math>\mathcal{A}</math> be a collection of subsets of [n]. For each k, let <math>\delta_k</math> denote the density of <math>\mathcal{A}</math> in the kth [[slice|layer]] of the cube: that is, it is the number of sets in <math>\mathcal{A}</math> of size k, divided by <math>\binom nk.</math> The [[equal-slices measure]] of <math>\mathcal{A}</math> is defined to be <math>\delta_0+\dots+\delta_n.</math>

Now the equal-slices measure of <math>\mathcal{A}</math> is easily seen to be equal to the following quantity. Let <math>\pi</math> be a random permutation of [n], let <math>U_0,U_1,U_2\dots,U_n</math> be the sets <math>\emptyset, \{\pi(1)\},\{\pi(1),\pi(2)\},\dots,[n],</math> and let <math>\mu(\mathcal{A})</math> be the expected number of the sets <math>U_i</math> that belong to <math>\mathcal{A}.</math> This is the same by linearity of expectation and the fact that the probability that <math>U_k</math> belongs to <math>\mathcal{A}</math> is <math>\delta_k.</math>

Therefore, if the equal-slices measure of <math>\mathcal{A}</math> is greater than 1, then the expected number of sets <math>U_k</math> in <math>\mathcal{A}</math> is greater than 1, so there must exist a permutation for which it is at least 2, and that gives us a pair of sets with one contained in the other.

To see that this implies Sperner's theorem, one just has to make the simple observation that a set with equal-slices measure at most 1 must have cardinality at most <math>\binom n{\lfloor n/2\rfloor}.</math> (If n is odd, so that there are two middle layers, then it is not quite so obvious that to have an extremal set you must pick one or other of the layers, but this is the case.) This stronger version of the statement is called the LYM inequality

==Multidimensional version==

The following proof is a variant of the [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-45GMWMS-9&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d2d74495dece42adf2ad10297bcb49ee Gunderson-Rodl-Sidorenko] result. Its parameters are a little worse, but the proof is a little simpler.

'''Proposition 1:''' Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta</math>. Let <math>Y_1, \dots, Y_d</math> be a partition of <math>[n]</math> with <math>|Y_i| \geq r</math> for each <math>i</math>. If

<math>\delta^{2^d} - \frac{d}{\sqrt{\pi r}} > 0, </math> (1)

then <math>A</math> contains a nondegenerate combinatorial subspace of dimension <math>d</math>, with its <math>i</math>th wildcard set a subset of <math>Y_i</math>.

'''Proof:''' Let <math>C_i</math> denote a random chain from <math>0^{|Y_i|}</math> up to <math>1^{|Y_i|}</math>, thought of as residing in the coordinates <math>Y_i</math>, with the <math>d</math> chains chosen independently. Also, let <math>s_i, t_i</math> denote independent Binomial</math>(|Y_i|, 1/2)</math> random variables, <math>i \in [d]</math>. Note that <math>C_i(s_i)</math> and <math>C_i(t_i)</math> are (dependent) uniform random strings in <math>\{0,1\}^{Y_i}</math>. We write, say,

<math>(C_1(s_1), C_2(t_2), C_3(t_3), \dots, C_d(s_d)) </math> (2)

for the string in <math>\{0,1\}^n</math> formed by putting <math>C_1(s_1)</math> into the <math>Y_1</math> coordinates, <math>C_2(t_2)</math> into the <math>Y_2</math> coordinates, etc. Note that each string of this form is also uniformly random, since the chains are independent.

If all <math>2^d</math> strings of the form in (2) are simultaneously in <math>A</math> then we have a <math>d</math>-dimensional subspace inside <math>A</math> with wildcard sets that are \emph{subsets} of <math>Y_1, \dots, Y_d</math>. All <math>d</math> dimensions are nondegenerate iff <math>s_i \neq t_i</math> for all <math>i</math>. Since <math>s_i</math> and <math>t_i</math> are independent Binomial<math>(|Y_i|, 1/2)</math>'s with <math>|Y_i| \geq r</math>, we have

<math>\Pr[s_i = t_i] \leq \frac{1}{\sqrt{\pi r}}.</math>

Thus to complete the proof, it suffices to show that with probability at least <math>\delta^{2^d}</math>, all <math>2^d</math> strings of the form in (2) are in <math>A</math>.

This is easy: writing <math>f</math> for the indicator of <math>A</math>, the probability is

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, t_d}[f(C_1(s_1), \dots, C_d(s_d)) \cdots f(C_1(t_1), \dots, C_d(t_d))]\right].</math>

Since <math>s_1, \dots, t_d</math> are independent, the inside expectation-of-a-product can be changed to a product of expectations. But for fixed <math>C_1, \dots, C_d</math>, each string of the form in (2) has the same distribution. Hence the above equals

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]^{2^d}\right].</math>

By Jensen (or repeated Cauchy-Schwarz), this is at least

<math>\left(\mathbf{E}_{C_1, \dots, C_d} \mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]\right)^{2^d}.</math>

But this is just <math>\delta^{2^d}</math>, since <math>(C_1(s_1), \dots, C_d(s_d))</math> is uniformly distributed. []

As an aside:
'''Corollary 2:''' If <math>A \subseteq [n]</math> has density <math>\Omega(1)</math>, then <math>A</math> contains a nondegenerate combinatorial subspace of dimension at least <math>\log_2 \log n - O(1)</math>.

If we are willing to sacrifice significantly more probability, we can find a <math>d</math>-dimensional subspace randomly.

'''Corollary 3:''' In the setting of Proposition 1, assume <math>\delta < 2/3</math> and

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math> (3)

Suppose we choose a random nondegenerate <math>d</math>-dimensional subspace of <math>[n]</math> with wildcard sets <math>Z_i \subseteq Y_i</math>. By this we mean choosing, independently for each <math>i</math>, a random combinatorial line within <math>\{0,1\}^{Y_i}</math>, uniformly from the <math>3^r - 1</math> possibilities. Then this subspace is entirely contained within <math>A</math> with probability at least <math>3^{-dr}</math>.

This follows immediately from Proposition~\ref{prop:1}: having <math>r</math> as in (3) achieves (1), hence the desired nondengenerate combinatorial subspace exists and we pick it with probability <math>1/(3^r-1)^d</math>.

We can further conclude:
'''Corollary 4''': Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta < 2/3</math> and let <math>Y_1, \dots, Y_d</math> be disjoint subsets of <math>[n]</math> with each <math>|Y_i| \geq r</math>,

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math>

Choose a nondegenerate combinatorial subspace at random by picking uniformly nondegenerate combinatorial lines in each of <math>Y_1, \dots, Y_d</math>, and filling in the remaining coordinates outside of the <math>Y_i</math>'s uniformly at random. Then with probability at least <math>\exp(-r^{O(1)})</math>, this combinatorial subspace is entirely contained within <math>A</math>.

This follows because for a random choice of the coordinates outside the <math>Y_i</math>'s, there is a <math>\delta/2</math> chance that <math>A</math> has density at least <math>\delta/2</math> over the <math>Y</math> coordinates. We then apply the previous corollary, noting that <math>\exp(-r^{O(1)}) \ll (\delta/2)3^{-dr}</math>, even with <math>\delta</math> replaced by <math>\delta/2</math> in the lower bound demanded of <math>r</math>.

===Strong version===

An alternative argument deduces the multidimensional Sperner theorem from the density Hales-Jewett theorem. We can think of <math>[2]^n</math> as <math>[2^k]^{n/k}.</math> If we do so and apply DHJ(2^k) and translate back to <math>[2]^n,</math> then we find that we have produced a k-dimensional combinatorial subspace. This is obviously a much more sophisticated proof, since DHJ(2^k) is a very hard result, but it gives more information, since the wildcard sets turn out to have the same size. A sign that this strong version is genuinely strong is that it implies Szemerédi's theorem. For instance, suppose you take as your set <math>\mathcal{A}</math> the set of all sequences such that the number of 0s plus the number of 1s in even places plus twice the number of 1s in odd places belongs to some dense set in <math>[3n].</math> Then if you have a 2D subspace with both wildcard sets of size d, one wildcard set consisting of odd numbers and the other of even numbers (which this proof gives), then this implies that in your dense set of integers you can find four integers of the form a, a+d, a+2d, a+d+2d, which is an arithmetic progression of length 4.

One can also prove the above strong form of Sperner theorem by using the multidimensional Szemerédi theorem which has combinatorial proofs. (reference!) It states that large dense high dimensional grids contain [[corners]]. Given a dense subset of <math>[2]^n,</math> denoted by <math>\mathcal{A}</math>. We can suppose that the elements of <math>\mathcal{A}</math> are of size about <math>\frac{n}{2}\pm C\sqrt{n}.</math> Take a random permutation of [n]. An element of <math>\mathcal{A}</math> is “<math>d-</math>nice” after the permutation if it consists of <math>d</math> intervals, each of length between <math>\frac{n}{2d}\pm C\sqrt{n}/2,</math> and each interval begins at position <math>id</math> for some <math>0\leq i< \frac{n}{d}.</math> (Suppose that <math>d</math> divides <math>n</math>) Any <math>d-</math>nice set can be represented as a point in a <math>d-</math>dimensional <math>[C\sqrt{n}]^d</math> cube. The sets represented by the vertices of an axis-parallel <math>d-</math>dimensional cube in <math>[C\sqrt{n}]^d</math> form a subspace with equal sized wildcard sets. Finding a cube is clearly more difficult than finding a corner, but it's existence in dense sets also follows from the multidimensional Szemerédi theorem. All what we need is to show that the expected number of the <math>d-</math>nice elements is <math>c\sqrt{n}^d</math> where c only depends on the density of <math>\mathcal{A}</math>. For a typical <math>m-</math>element subset of <math>\mathcal{A}</math> the probability that it is <math>d-</math>nice after the permutation is about <math>\binom{n}{m}^{-1}\sqrt{n}^{d-1}.</math> The sum for elements of <math>\mathcal{A}</math> with size between <math>\frac{n}{2}\pm C\sqrt{n},</math> gives that the expected number of the <math>d-</math>nice elements is <math>c\sqrt{n}^d,</math> so there is a cube if n is large enough.

==Further remarks==

The k=3 generalisation of the LYM inequality is the [[hyper-optimistic conjecture]].

Sperner's theorem is also related to the [[Kruskal-Katona theorem]].

* [http://en.wikipedia.org/wiki/Sperner%27s_theorem The Wikipedia entry for Sperner's theorem]
* [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality The Wikipedia entry for the LYM inequality]

Sperner's theorem

2009-03-09T02:13:52Z

Jozsef: /* Strong version */

==Statement of the theorem==

Sperner's theorem as originally stated is a result about set systems. Suppose that you want to find the largest collection of sets <math>\mathcal{A}</math> such that no set in <math>\mathcal{A}</math> is a proper subset of any other. Then the best you can do is choose all the sets of some fixed size---and of course the best size to pick is <math>\lfloor n/2\rfloor</math>, since the binomial coefficient <math>\binom nm</math> is maximized when <math>m=\lfloor n/2\rfloor.</math>

Sperner's theorem is closely related to the density Hales-Jewett theorem: in fact, it is nothing other than DHJ(2) with the best possible bound. To see this, we associate each set <math>A\subset[n]</math> with its characteristic function (that is, the sequence that is 0 outside A and 1 in A). If we have a pair of sets <math>A\subset B,</math> then the two sequences form a [[combinatorial line]] in <math>[2]^n.</math> For example, if n=6 and A and B are the sets <math>\{2,3\}</math> and <math>\{2,3,4,6\}</math>, then we get the combinatorial line that consists of the two points 011000 and 011101, which we can denote by 011*0* (so the wildcard set is <math>\{4,6\}</math>).

==Proof of the theorem==

There are several proofs, but perhaps the most enlightening is a very simple averaging argument that proves a stronger result. Let <math>\mathcal{A}</math> be a collection of subsets of [n]. For each k, let <math>\delta_k</math> denote the density of <math>\mathcal{A}</math> in the kth [[slice|layer]] of the cube: that is, it is the number of sets in <math>\mathcal{A}</math> of size k, divided by <math>\binom nk.</math> The [[equal-slices measure]] of <math>\mathcal{A}</math> is defined to be <math>\delta_0+\dots+\delta_n.</math>

Now the equal-slices measure of <math>\mathcal{A}</math> is easily seen to be equal to the following quantity. Let <math>\pi</math> be a random permutation of [n], let <math>U_0,U_1,U_2\dots,U_n</math> be the sets <math>\emptyset, \{\pi(1)\},\{\pi(1),\pi(2)\},\dots,[n],</math> and let <math>\mu(\mathcal{A})</math> be the expected number of the sets <math>U_i</math> that belong to <math>\mathcal{A}.</math> This is the same by linearity of expectation and the fact that the probability that <math>U_k</math> belongs to <math>\mathcal{A}</math> is <math>\delta_k.</math>

Therefore, if the equal-slices measure of <math>\mathcal{A}</math> is greater than 1, then the expected number of sets <math>U_k</math> in <math>\mathcal{A}</math> is greater than 1, so there must exist a permutation for which it is at least 2, and that gives us a pair of sets with one contained in the other.

To see that this implies Sperner's theorem, one just has to make the simple observation that a set with equal-slices measure at most 1 must have cardinality at most <math>\binom n{\lfloor n/2\rfloor}.</math> (If n is odd, so that there are two middle layers, then it is not quite so obvious that to have an extremal set you must pick one or other of the layers, but this is the case.) This stronger version of the statement is called the LYM inequality

==Multidimensional version==

The following proof is a variant of the [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-45GMWMS-9&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d2d74495dece42adf2ad10297bcb49ee Gunderson-Rodl-Sidorenko] result. Its parameters are a little worse, but the proof is a little simpler.

'''Proposition 1:''' Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta</math>. Let <math>Y_1, \dots, Y_d</math> be a partition of <math>[n]</math> with <math>|Y_i| \geq r</math> for each <math>i</math>. If

<math>\delta^{2^d} - \frac{d}{\sqrt{\pi r}} > 0, </math> (1)

then <math>A</math> contains a nondegenerate combinatorial subspace of dimension <math>d</math>, with its <math>i</math>th wildcard set a subset of <math>Y_i</math>.

'''Proof:''' Let <math>C_i</math> denote a random chain from <math>0^{|Y_i|}</math> up to <math>1^{|Y_i|}</math>, thought of as residing in the coordinates <math>Y_i</math>, with the <math>d</math> chains chosen independently. Also, let <math>s_i, t_i</math> denote independent Binomial</math>(|Y_i|, 1/2)</math> random variables, <math>i \in [d]</math>. Note that <math>C_i(s_i)</math> and <math>C_i(t_i)</math> are (dependent) uniform random strings in <math>\{0,1\}^{Y_i}</math>. We write, say,

<math>(C_1(s_1), C_2(t_2), C_3(t_3), \dots, C_d(s_d)) </math> (2)

for the string in <math>\{0,1\}^n</math> formed by putting <math>C_1(s_1)</math> into the <math>Y_1</math> coordinates, <math>C_2(t_2)</math> into the <math>Y_2</math> coordinates, etc. Note that each string of this form is also uniformly random, since the chains are independent.

If all <math>2^d</math> strings of the form in (2) are simultaneously in <math>A</math> then we have a <math>d</math>-dimensional subspace inside <math>A</math> with wildcard sets that are \emph{subsets} of <math>Y_1, \dots, Y_d</math>. All <math>d</math> dimensions are nondegenerate iff <math>s_i \neq t_i</math> for all <math>i</math>. Since <math>s_i</math> and <math>t_i</math> are independent Binomial<math>(|Y_i|, 1/2)</math>'s with <math>|Y_i| \geq r</math>, we have

<math>\Pr[s_i = t_i] \leq \frac{1}{\sqrt{\pi r}}.</math>

Thus to complete the proof, it suffices to show that with probability at least <math>\delta^{2^d}</math>, all <math>2^d</math> strings of the form in (2) are in <math>A</math>.

This is easy: writing <math>f</math> for the indicator of <math>A</math>, the probability is

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, t_d}[f(C_1(s_1), \dots, C_d(s_d)) \cdots f(C_1(t_1), \dots, C_d(t_d))]\right].</math>

Since <math>s_1, \dots, t_d</math> are independent, the inside expectation-of-a-product can be changed to a product of expectations. But for fixed <math>C_1, \dots, C_d</math>, each string of the form in (2) has the same distribution. Hence the above equals

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]^{2^d}\right].</math>

By Jensen (or repeated Cauchy-Schwarz), this is at least

<math>\left(\mathbf{E}_{C_1, \dots, C_d} \mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]\right)^{2^d}.</math>

But this is just <math>\delta^{2^d}</math>, since <math>(C_1(s_1), \dots, C_d(s_d))</math> is uniformly distributed. []

As an aside:
'''Corollary 2:''' If <math>A \subseteq [n]</math> has density <math>\Omega(1)</math>, then <math>A</math> contains a nondegenerate combinatorial subspace of dimension at least <math>\log_2 \log n - O(1)</math>.

If we are willing to sacrifice significantly more probability, we can find a <math>d</math>-dimensional subspace randomly.

'''Corollary 3:''' In the setting of Proposition 1, assume <math>\delta < 2/3</math> and

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math> (3)

Suppose we choose a random nondegenerate <math>d</math>-dimensional subspace of <math>[n]</math> with wildcard sets <math>Z_i \subseteq Y_i</math>. By this we mean choosing, independently for each <math>i</math>, a random combinatorial line within <math>\{0,1\}^{Y_i}</math>, uniformly from the <math>3^r - 1</math> possibilities. Then this subspace is entirely contained within <math>A</math> with probability at least <math>3^{-dr}</math>.

This follows immediately from Proposition~\ref{prop:1}: having <math>r</math> as in (3) achieves (1), hence the desired nondengenerate combinatorial subspace exists and we pick it with probability <math>1/(3^r-1)^d</math>.

We can further conclude:
'''Corollary 4''': Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta < 2/3</math> and let <math>Y_1, \dots, Y_d</math> be disjoint subsets of <math>[n]</math> with each <math>|Y_i| \geq r</math>,

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math>

Choose a nondegenerate combinatorial subspace at random by picking uniformly nondegenerate combinatorial lines in each of <math>Y_1, \dots, Y_d</math>, and filling in the remaining coordinates outside of the <math>Y_i</math>'s uniformly at random. Then with probability at least <math>\exp(-r^{O(1)})</math>, this combinatorial subspace is entirely contained within <math>A</math>.

This follows because for a random choice of the coordinates outside the <math>Y_i</math>'s, there is a <math>\delta/2</math> chance that <math>A</math> has density at least <math>\delta/2</math> over the <math>Y</math> coordinates. We then apply the previous corollary, noting that <math>\exp(-r^{O(1)}) \ll (\delta/2)3^{-dr}</math>, even with <math>\delta</math> replaced by <math>\delta/2</math> in the lower bound demanded of <math>r</math>.

===Strong version===

An alternative argument deduces the multidimensional Sperner theorem from the density Hales-Jewett theorem. We can think of <math>[2]^n</math> as <math>[2^k]^{n/k}.</math> If we do so and apply DHJ(2^k) and translate back to <math>[2]^n,</math> then we find that we have produced a k-dimensional combinatorial subspace. This is obviously a much more sophisticated proof, since DHJ(2^k) is a very hard result, but it gives more information, since the wildcard sets turn out to have the same size. A sign that this strong version is genuinely strong is that it implies Szemerédi's theorem. For instance, suppose you take as your set <math>\mathcal{A}</math> the set of all sequences such that the number of 0s plus the number of 1s in even places plus twice the number of 1s in odd places belongs to some dense set in <math>[3n].</math> Then if you have a 2D subspace with both wildcard sets of size d, one wildcard set consisting of odd numbers and the other of even numbers (which this proof gives), then this implies that in your dense set of integers you can find four integers of the form a, a+d, a+2d, a+d+2d, which is an arithmetic progression of length 4.

One can also prove the above strong form of Sperner theorem by using the multidimensional Szemerédi theorem which has combinatorial proofs. (reference!) It states that large dense high dimensional grids contain [[corners]]. Given a dense subset of <math>[2]^n,</math> denoted by <math>\mathcal{A}</math>. Take a random permutation of [n]. An element of <math>\mathcal{A}</math> is “<math>d-</math>nice” after the permutation if it consists of <math>d</math> intervals, each of length between <math>\frac{n}{2d}\pm \sqrt{n},</math> and each interval begins at position <math>id</math> for some <math>0\leq i< \frac{n}{d}.</math> (Suppose that <math>d</math> divides <math>n</math>) Any <math>d-</math>nice set can be represented as a point in a <math>d-</math>dimensional <math>[\sqrt{n}]^d</math> cube. The sets represented by the vertices of an axis-parallel <math>d-</math>dimensional cube in <math>[\sqrt{n}]^d</math> form a subspace with equal sized wildcard sets. Finding a cube is clearly more difficult than finding a corner, but it's existence in dense sets also follows from the multidimensional Szemerédi theorem. All what is left to show is that the expected number of the <math>d-</math>nice elements is <math>c\sqrt{n}^d</math> where c only depends on the density of <math>\mathcal{A}</math>. For a typical <math>m-</math>element subset of <math>\mathcal{A}</math> the probability that it is <math>d-</math>nice after the permutation is about <math>\binom{n}{m}^{-1}\sqrt{n}^{d-1}.</math> The sum for elements of <math>\mathcal{A}</math> with size between <math>\frac{n}{2}\pm C\sqrt{n},</math> gives that the expected number of the <math>d-</math>nice elements is <math>c\sqrt{n}^d,</math> so there is a cube if n is large enough.

==Further remarks==

The k=3 generalisation of the LYM inequality is the [[hyper-optimistic conjecture]].

Sperner's theorem is also related to the [[Kruskal-Katona theorem]].

* [http://en.wikipedia.org/wiki/Sperner%27s_theorem The Wikipedia entry for Sperner's theorem]
* [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality The Wikipedia entry for the LYM inequality]

Sperner's theorem

2009-03-09T01:53:18Z

Jozsef: /* Strong version */

==Statement of the theorem==

Sperner's theorem as originally stated is a result about set systems. Suppose that you want to find the largest collection of sets <math>\mathcal{A}</math> such that no set in <math>\mathcal{A}</math> is a proper subset of any other. Then the best you can do is choose all the sets of some fixed size---and of course the best size to pick is <math>\lfloor n/2\rfloor</math>, since the binomial coefficient <math>\binom nm</math> is maximized when <math>m=\lfloor n/2\rfloor.</math>

Sperner's theorem is closely related to the density Hales-Jewett theorem: in fact, it is nothing other than DHJ(2) with the best possible bound. To see this, we associate each set <math>A\subset[n]</math> with its characteristic function (that is, the sequence that is 0 outside A and 1 in A). If we have a pair of sets <math>A\subset B,</math> then the two sequences form a [[combinatorial line]] in <math>[2]^n.</math> For example, if n=6 and A and B are the sets <math>\{2,3\}</math> and <math>\{2,3,4,6\}</math>, then we get the combinatorial line that consists of the two points 011000 and 011101, which we can denote by 011*0* (so the wildcard set is <math>\{4,6\}</math>).

==Proof of the theorem==

There are several proofs, but perhaps the most enlightening is a very simple averaging argument that proves a stronger result. Let <math>\mathcal{A}</math> be a collection of subsets of [n]. For each k, let <math>\delta_k</math> denote the density of <math>\mathcal{A}</math> in the kth [[slice|layer]] of the cube: that is, it is the number of sets in <math>\mathcal{A}</math> of size k, divided by <math>\binom nk.</math> The [[equal-slices measure]] of <math>\mathcal{A}</math> is defined to be <math>\delta_0+\dots+\delta_n.</math>

Now the equal-slices measure of <math>\mathcal{A}</math> is easily seen to be equal to the following quantity. Let <math>\pi</math> be a random permutation of [n], let <math>U_0,U_1,U_2\dots,U_n</math> be the sets <math>\emptyset, \{\pi(1)\},\{\pi(1),\pi(2)\},\dots,[n],</math> and let <math>\mu(\mathcal{A})</math> be the expected number of the sets <math>U_i</math> that belong to <math>\mathcal{A}.</math> This is the same by linearity of expectation and the fact that the probability that <math>U_k</math> belongs to <math>\mathcal{A}</math> is <math>\delta_k.</math>

Therefore, if the equal-slices measure of <math>\mathcal{A}</math> is greater than 1, then the expected number of sets <math>U_k</math> in <math>\mathcal{A}</math> is greater than 1, so there must exist a permutation for which it is at least 2, and that gives us a pair of sets with one contained in the other.

To see that this implies Sperner's theorem, one just has to make the simple observation that a set with equal-slices measure at most 1 must have cardinality at most <math>\binom n{\lfloor n/2\rfloor}.</math> (If n is odd, so that there are two middle layers, then it is not quite so obvious that to have an extremal set you must pick one or other of the layers, but this is the case.) This stronger version of the statement is called the LYM inequality

==Multidimensional version==

The following proof is a variant of the [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-45GMWMS-9&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d2d74495dece42adf2ad10297bcb49ee Gunderson-Rodl-Sidorenko] result. Its parameters are a little worse, but the proof is a little simpler.

'''Proposition 1:''' Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta</math>. Let <math>Y_1, \dots, Y_d</math> be a partition of <math>[n]</math> with <math>|Y_i| \geq r</math> for each <math>i</math>. If

<math>\delta^{2^d} - \frac{d}{\sqrt{\pi r}} > 0, </math> (1)

then <math>A</math> contains a nondegenerate combinatorial subspace of dimension <math>d</math>, with its <math>i</math>th wildcard set a subset of <math>Y_i</math>.

'''Proof:''' Let <math>C_i</math> denote a random chain from <math>0^{|Y_i|}</math> up to <math>1^{|Y_i|}</math>, thought of as residing in the coordinates <math>Y_i</math>, with the <math>d</math> chains chosen independently. Also, let <math>s_i, t_i</math> denote independent Binomial</math>(|Y_i|, 1/2)</math> random variables, <math>i \in [d]</math>. Note that <math>C_i(s_i)</math> and <math>C_i(t_i)</math> are (dependent) uniform random strings in <math>\{0,1\}^{Y_i}</math>. We write, say,

<math>(C_1(s_1), C_2(t_2), C_3(t_3), \dots, C_d(s_d)) </math> (2)

for the string in <math>\{0,1\}^n</math> formed by putting <math>C_1(s_1)</math> into the <math>Y_1</math> coordinates, <math>C_2(t_2)</math> into the <math>Y_2</math> coordinates, etc. Note that each string of this form is also uniformly random, since the chains are independent.

If all <math>2^d</math> strings of the form in (2) are simultaneously in <math>A</math> then we have a <math>d</math>-dimensional subspace inside <math>A</math> with wildcard sets that are \emph{subsets} of <math>Y_1, \dots, Y_d</math>. All <math>d</math> dimensions are nondegenerate iff <math>s_i \neq t_i</math> for all <math>i</math>. Since <math>s_i</math> and <math>t_i</math> are independent Binomial<math>(|Y_i|, 1/2)</math>'s with <math>|Y_i| \geq r</math>, we have

<math>\Pr[s_i = t_i] \leq \frac{1}{\sqrt{\pi r}}.</math>

Thus to complete the proof, it suffices to show that with probability at least <math>\delta^{2^d}</math>, all <math>2^d</math> strings of the form in (2) are in <math>A</math>.

This is easy: writing <math>f</math> for the indicator of <math>A</math>, the probability is

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, t_d}[f(C_1(s_1), \dots, C_d(s_d)) \cdots f(C_1(t_1), \dots, C_d(t_d))]\right].</math>

Since <math>s_1, \dots, t_d</math> are independent, the inside expectation-of-a-product can be changed to a product of expectations. But for fixed <math>C_1, \dots, C_d</math>, each string of the form in (2) has the same distribution. Hence the above equals

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]^{2^d}\right].</math>

By Jensen (or repeated Cauchy-Schwarz), this is at least

<math>\left(\mathbf{E}_{C_1, \dots, C_d} \mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]\right)^{2^d}.</math>

But this is just <math>\delta^{2^d}</math>, since <math>(C_1(s_1), \dots, C_d(s_d))</math> is uniformly distributed. []

As an aside:
'''Corollary 2:''' If <math>A \subseteq [n]</math> has density <math>\Omega(1)</math>, then <math>A</math> contains a nondegenerate combinatorial subspace of dimension at least <math>\log_2 \log n - O(1)</math>.

If we are willing to sacrifice significantly more probability, we can find a <math>d</math>-dimensional subspace randomly.

'''Corollary 3:''' In the setting of Proposition 1, assume <math>\delta < 2/3</math> and

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math> (3)

Suppose we choose a random nondegenerate <math>d</math>-dimensional subspace of <math>[n]</math> with wildcard sets <math>Z_i \subseteq Y_i</math>. By this we mean choosing, independently for each <math>i</math>, a random combinatorial line within <math>\{0,1\}^{Y_i}</math>, uniformly from the <math>3^r - 1</math> possibilities. Then this subspace is entirely contained within <math>A</math> with probability at least <math>3^{-dr}</math>.

This follows immediately from Proposition~\ref{prop:1}: having <math>r</math> as in (3) achieves (1), hence the desired nondengenerate combinatorial subspace exists and we pick it with probability <math>1/(3^r-1)^d</math>.

We can further conclude:
'''Corollary 4''': Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta < 2/3</math> and let <math>Y_1, \dots, Y_d</math> be disjoint subsets of <math>[n]</math> with each <math>|Y_i| \geq r</math>,

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math>

Choose a nondegenerate combinatorial subspace at random by picking uniformly nondegenerate combinatorial lines in each of <math>Y_1, \dots, Y_d</math>, and filling in the remaining coordinates outside of the <math>Y_i</math>'s uniformly at random. Then with probability at least <math>\exp(-r^{O(1)})</math>, this combinatorial subspace is entirely contained within <math>A</math>.

This follows because for a random choice of the coordinates outside the <math>Y_i</math>'s, there is a <math>\delta/2</math> chance that <math>A</math> has density at least <math>\delta/2</math> over the <math>Y</math> coordinates. We then apply the previous corollary, noting that <math>\exp(-r^{O(1)}) \ll (\delta/2)3^{-dr}</math>, even with <math>\delta</math> replaced by <math>\delta/2</math> in the lower bound demanded of <math>r</math>.

===Strong version===

An alternative argument deduces the multidimensional Sperner theorem from the density Hales-Jewett theorem. We can think of <math>[2]^n</math> as <math>[2^k]^{n/k}.</math> If we do so and apply DHJ(2^k) and translate back to <math>[2]^n,</math> then we find that we have produced a k-dimensional combinatorial subspace. This is obviously a much more sophisticated proof, since DHJ(2^k) is a very hard result, but it gives more information, since the wildcard sets turn out to have the same size. A sign that this strong version is genuinely strong is that it implies Szemerédi's theorem. For instance, suppose you take as your set <math>\mathcal{A}</math> the set of all sequences such that the number of 0s plus the number of 1s in even places plus twice the number of 1s in odd places belongs to some dense set in <math>[3n].</math> Then if you have a 2D subspace with both wildcard sets of size d, one wildcard set consisting of odd numbers and the other of even numbers (which this proof gives), then this implies that in your dense set of integers you can find four integers of the form a, a+d, a+2d, a+d+2d, which is an arithmetic progression of length 4.

One can also prove the above strong form of Sperner theorem by using the multidimensional Szemerédi theorem which has combinatorial proofs. (reference!) It states that large dense high dimensional grids contain [[corners]]. Given a dense subset of <math>[2]^n,</math> denoted by <math>\mathcal{A}</math>. Take a random permutation of [n]. An element of <math>\mathcal{A}</math> is “<math>d-</math>nice” after the permutation if it consists of <math>d</math> intervals, each of length between <math>\frac{n}{2d}\pm \sqrt{n},</math> and each interval begins at position <math>id</math> for some <math>0\leq i< \frac{n}{d}.</math> (Suppose that <math>d</math> divides <math>n</math>) Any <math>d-</math>nice set can be represented as a point in a <math>d-</math>dimensional <math>[\sqrt{n}]^d</math> cube. The sets represented by the vertices of an axis-parallel <math>d-</math>dimensional cube in <math>[\sqrt{n}]^d</math> form a subspace with equal sized wildcard sets. Finding a cube is clearly more difficult than finding a corner, but it's existence in dense sets also follows from the multidimensional Szemerédi theorem.(cont.)

==Further remarks==

The k=3 generalisation of the LYM inequality is the [[hyper-optimistic conjecture]].

Sperner's theorem is also related to the [[Kruskal-Katona theorem]].

* [http://en.wikipedia.org/wiki/Sperner%27s_theorem The Wikipedia entry for Sperner's theorem]
* [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality The Wikipedia entry for the LYM inequality]

Sperner's theorem

2009-03-09T01:36:14Z

Jozsef: /* Strong version */

==Statement of the theorem==

Sperner's theorem as originally stated is a result about set systems. Suppose that you want to find the largest collection of sets <math>\mathcal{A}</math> such that no set in <math>\mathcal{A}</math> is a proper subset of any other. Then the best you can do is choose all the sets of some fixed size---and of course the best size to pick is <math>\lfloor n/2\rfloor</math>, since the binomial coefficient <math>\binom nm</math> is maximized when <math>m=\lfloor n/2\rfloor.</math>

Sperner's theorem is closely related to the density Hales-Jewett theorem: in fact, it is nothing other than DHJ(2) with the best possible bound. To see this, we associate each set <math>A\subset[n]</math> with its characteristic function (that is, the sequence that is 0 outside A and 1 in A). If we have a pair of sets <math>A\subset B,</math> then the two sequences form a [[combinatorial line]] in <math>[2]^n.</math> For example, if n=6 and A and B are the sets <math>\{2,3\}</math> and <math>\{2,3,4,6\}</math>, then we get the combinatorial line that consists of the two points 011000 and 011101, which we can denote by 011*0* (so the wildcard set is <math>\{4,6\}</math>).

==Proof of the theorem==

There are several proofs, but perhaps the most enlightening is a very simple averaging argument that proves a stronger result. Let <math>\mathcal{A}</math> be a collection of subsets of [n]. For each k, let <math>\delta_k</math> denote the density of <math>\mathcal{A}</math> in the kth [[slice|layer]] of the cube: that is, it is the number of sets in <math>\mathcal{A}</math> of size k, divided by <math>\binom nk.</math> The [[equal-slices measure]] of <math>\mathcal{A}</math> is defined to be <math>\delta_0+\dots+\delta_n.</math>

Now the equal-slices measure of <math>\mathcal{A}</math> is easily seen to be equal to the following quantity. Let <math>\pi</math> be a random permutation of [n], let <math>U_0,U_1,U_2\dots,U_n</math> be the sets <math>\emptyset, \{\pi(1)\},\{\pi(1),\pi(2)\},\dots,[n],</math> and let <math>\mu(\mathcal{A})</math> be the expected number of the sets <math>U_i</math> that belong to <math>\mathcal{A}.</math> This is the same by linearity of expectation and the fact that the probability that <math>U_k</math> belongs to <math>\mathcal{A}</math> is <math>\delta_k.</math>

Therefore, if the equal-slices measure of <math>\mathcal{A}</math> is greater than 1, then the expected number of sets <math>U_k</math> in <math>\mathcal{A}</math> is greater than 1, so there must exist a permutation for which it is at least 2, and that gives us a pair of sets with one contained in the other.

To see that this implies Sperner's theorem, one just has to make the simple observation that a set with equal-slices measure at most 1 must have cardinality at most <math>\binom n{\lfloor n/2\rfloor}.</math> (If n is odd, so that there are two middle layers, then it is not quite so obvious that to have an extremal set you must pick one or other of the layers, but this is the case.) This stronger version of the statement is called the LYM inequality

==Multidimensional version==

The following proof is a variant of the [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6WHS-45GMWMS-9&_user=10&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=d2d74495dece42adf2ad10297bcb49ee Gunderson-Rodl-Sidorenko] result. Its parameters are a little worse, but the proof is a little simpler.

'''Proposition 1:''' Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta</math>. Let <math>Y_1, \dots, Y_d</math> be a partition of <math>[n]</math> with <math>|Y_i| \geq r</math> for each <math>i</math>. If

<math>\delta^{2^d} - \frac{d}{\sqrt{\pi r}} > 0, </math> (1)

then <math>A</math> contains a nondegenerate combinatorial subspace of dimension <math>d</math>, with its <math>i</math>th wildcard set a subset of <math>Y_i</math>.

'''Proof:''' Let <math>C_i</math> denote a random chain from <math>0^{|Y_i|}</math> up to <math>1^{|Y_i|}</math>, thought of as residing in the coordinates <math>Y_i</math>, with the <math>d</math> chains chosen independently. Also, let <math>s_i, t_i</math> denote independent Binomial</math>(|Y_i|, 1/2)</math> random variables, <math>i \in [d]</math>. Note that <math>C_i(s_i)</math> and <math>C_i(t_i)</math> are (dependent) uniform random strings in <math>\{0,1\}^{Y_i}</math>. We write, say,

<math>(C_1(s_1), C_2(t_2), C_3(t_3), \dots, C_d(s_d)) </math> (2)

for the string in <math>\{0,1\}^n</math> formed by putting <math>C_1(s_1)</math> into the <math>Y_1</math> coordinates, <math>C_2(t_2)</math> into the <math>Y_2</math> coordinates, etc. Note that each string of this form is also uniformly random, since the chains are independent.

If all <math>2^d</math> strings of the form in (2) are simultaneously in <math>A</math> then we have a <math>d</math>-dimensional subspace inside <math>A</math> with wildcard sets that are \emph{subsets} of <math>Y_1, \dots, Y_d</math>. All <math>d</math> dimensions are nondegenerate iff <math>s_i \neq t_i</math> for all <math>i</math>. Since <math>s_i</math> and <math>t_i</math> are independent Binomial<math>(|Y_i|, 1/2)</math>'s with <math>|Y_i| \geq r</math>, we have

<math>\Pr[s_i = t_i] \leq \frac{1}{\sqrt{\pi r}}.</math>

Thus to complete the proof, it suffices to show that with probability at least <math>\delta^{2^d}</math>, all <math>2^d</math> strings of the form in (2) are in <math>A</math>.

This is easy: writing <math>f</math> for the indicator of <math>A</math>, the probability is

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, t_d}[f(C_1(s_1), \dots, C_d(s_d)) \cdots f(C_1(t_1), \dots, C_d(t_d))]\right].</math>

Since <math>s_1, \dots, t_d</math> are independent, the inside expectation-of-a-product can be changed to a product of expectations. But for fixed <math>C_1, \dots, C_d</math>, each string of the form in (2) has the same distribution. Hence the above equals

<math>\mathbf{E}_{C_1, \dots, C_d} \left[\mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]^{2^d}\right].</math>

By Jensen (or repeated Cauchy-Schwarz), this is at least

<math>\left(\mathbf{E}_{C_1, \dots, C_d} \mathbf{E}_{s_1, \dots, s_d}[f(C_1(s_1), \dots, C_d(s_d))]\right)^{2^d}.</math>

But this is just <math>\delta^{2^d}</math>, since <math>(C_1(s_1), \dots, C_d(s_d))</math> is uniformly distributed. []

As an aside:
'''Corollary 2:''' If <math>A \subseteq [n]</math> has density <math>\Omega(1)</math>, then <math>A</math> contains a nondegenerate combinatorial subspace of dimension at least <math>\log_2 \log n - O(1)</math>.

If we are willing to sacrifice significantly more probability, we can find a <math>d</math>-dimensional subspace randomly.

'''Corollary 3:''' In the setting of Proposition 1, assume <math>\delta < 2/3</math> and

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math> (3)

Suppose we choose a random nondegenerate <math>d</math>-dimensional subspace of <math>[n]</math> with wildcard sets <math>Z_i \subseteq Y_i</math>. By this we mean choosing, independently for each <math>i</math>, a random combinatorial line within <math>\{0,1\}^{Y_i}</math>, uniformly from the <math>3^r - 1</math> possibilities. Then this subspace is entirely contained within <math>A</math> with probability at least <math>3^{-dr}</math>.

This follows immediately from Proposition~\ref{prop:1}: having <math>r</math> as in (3) achieves (1), hence the desired nondengenerate combinatorial subspace exists and we pick it with probability <math>1/(3^r-1)^d</math>.

We can further conclude:
'''Corollary 4''': Let <math>A \subseteq \{0,1\}^n</math> have density <math>\delta < 2/3</math> and let <math>Y_1, \dots, Y_d</math> be disjoint subsets of <math>[n]</math> with each <math>|Y_i| \geq r</math>,

<math> r \geq \exp(4 \ln(1/\delta) 2^d). </math>

Choose a nondegenerate combinatorial subspace at random by picking uniformly nondegenerate combinatorial lines in each of <math>Y_1, \dots, Y_d</math>, and filling in the remaining coordinates outside of the <math>Y_i</math>'s uniformly at random. Then with probability at least <math>\exp(-r^{O(1)})</math>, this combinatorial subspace is entirely contained within <math>A</math>.

This follows because for a random choice of the coordinates outside the <math>Y_i</math>'s, there is a <math>\delta/2</math> chance that <math>A</math> has density at least <math>\delta/2</math> over the <math>Y</math> coordinates. We then apply the previous corollary, noting that <math>\exp(-r^{O(1)}) \ll (\delta/2)3^{-dr}</math>, even with <math>\delta</math> replaced by <math>\delta/2</math> in the lower bound demanded of <math>r</math>.

===Strong version===

An alternative argument deduces the multidimensional Sperner theorem from the density Hales-Jewett theorem. We can think of <math>[2]^n</math> as <math>[2^k]^{n/k}.</math> If we do so and apply DHJ(2^k) and translate back to <math>[2]^n,</math> then we find that we have produced a k-dimensional combinatorial subspace. This is obviously a much more sophisticated proof, since DHJ(2^k) is a very hard result, but it gives more information, since the wildcard sets turn out to have the same size. A sign that this strong version is genuinely strong is that it implies Szemerédi's theorem. For instance, suppose you take as your set <math>\mathcal{A}</math> the set of all sequences such that the number of 0s plus the number of 1s in even places plus twice the number of 1s in odd places belongs to some dense set in <math>[3n].</math> Then if you have a 2D subspace with both wildcard sets of size d, one wildcard set consisting of odd numbers and the other of even numbers (which this proof gives), then this implies that in your dense set of integers you can find four integers of the form a, a+d, a+2d, a+d+2d, which is an arithmetic progression of length 4.

One can also prove the above strong form of Sperner theorem by using the multidimensional Szemerédi theorem which has combinatorial proofs. (reference!) It states that large dense high dimensional grids contain [[corners]]. Given a dense subset of <math>[2]^n,</math> denoted by <math>\mathcal{A}</math>. Take a random permutation of [n]. An element of <math>\mathcal{A}</math> is “<math>d-</math>nice” after the permutation if it consists of <math>d</math> intervals, each of length between <math>\frac{n}{2d}\pm \sqrt{n},</math> and each interval begins at position <math>id</math> for some <math>0\leq i< \frac{n}{d}.</math> (Suppose that <math>d</math> divides <math>n</math>) Any interval like this can be represented as a point in a <math>d-</math>dimensional <math>[\sqrt{n}]^d</math> cube. If it’s dense then multidimensional Szemerédi gives us the strong version of Sperner.(cont.)

==Further remarks==

The k=3 generalisation of the LYM inequality is the [[hyper-optimistic conjecture]].

Sperner's theorem is also related to the [[Kruskal-Katona theorem]].

* [http://en.wikipedia.org/wiki/Sperner%27s_theorem The Wikipedia entry for Sperner's theorem]
* [http://en.wikipedia.org/wiki/Lubell-Yamamoto-Meshalkin_inequality The Wikipedia entry for the LYM inequality]

Corners

2009-03-09T01:17:29Z

Jozsef:

A ''corner'' is a subset of <math>[n]^2</math> of the form <math>\{(x,y),(x+d,y),(x,y+d)\}</math> with <math>d\ne 0.</math> One often insists also that d should be positive.

The [[corners theorem]] asserts that for every <math>\delta>0</math> there exists n such that every subset A of <math>[n]^2</math> of density at least <math>\delta</math> contains a corner.

In general, a corner is a subset of <math>[n]^m</math> of the form <math>\{(x_1,x_2,\ldots , x_m),(x_1+d,x_2,\ldots , x_m),(x_1,x_2+d,\ldots , x_m),\ldots ,(x_1,x_2,\ldots , x_m+d)\}</math> with <math>d\ne 0.</math>

The Multidimensional Szemeredi's theorem (proved by Furstenberg and Katznelson) asserts that for every real <math>\delta>0</math> and integer <math>m>1</math> there exists n such that every subset A of <math>[n]^m</math> of density at least <math>\delta</math> contains a corner.