Combinatorial subspace: Difference between revisions
mNo edit summary |
mNo edit summary |
||
| Line 1: | Line 1: | ||
An m-dimensional combinatorial subspace is obtained by taking m disjoint subsets <math>W_1,\dots,W_m</math> of <math>[n],</math> fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the <math>W_i</math> and are constant on each <math>W_i.</math> Sometimes one adds the restriction that the maximum of each <math>W_i</math> is less than the minimum of <math>W_{i+1}</math>. (In particular, the Hales-Jewett theorem can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.) In other words, where a [[combinatorial line]] has one set of wildcards, an m-dimensional combinatorial subspace has m sets of wildcards | An m-dimensional combinatorial subspace is obtained by taking m disjoint subsets <math>W_1,\dots,W_m</math> of <math>[n],</math> fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the <math>W_i</math> and are constant on each <math>W_i.</math> Sometimes one adds the restriction that the maximum of each <math>W_i</math> is less than the minimum of <math>W_{i+1}</math>. (In particular, the Hales-Jewett theorem can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.) In other words, where a [[combinatorial line]] has one set of wildcards, an m-dimensional combinatorial subspace has m sets of wildcards | ||
For example, the following strings form a 2-dimensional combinatorial subspace of the strong kind | For example, the following strings form a 2-dimensional combinatorial subspace of the strong kind (with wildcards indicated by full stops and commas) | ||
331.21.311.221,21, 3312131122222 3312131122323 | |||
332.22.312.221,21, 3322231222222 3322231222323 | |||
333.23.313.221,21, 3332331322222 3332331322323 | |||
and the following strings form a 2-dimensional combinatorial subspace of the weaker kind | and the following strings form a 2-dimensional combinatorial subspace of the weaker kind | ||
| Line 12: | Line 12: | ||
113113121311321 113213122311321 113313123311321 | 113113121311321 113213122311321 113313123311321 | ||
113113221312321 113213222312321 113313223312321 | 113113221312321 113213222312321 113313223312321 | ||
113113321313321 113213322313321 113313323313321 | |||
There is also a natural notion of a ''combinatorial embedding'' of <math>[3]^m</math> into <math>[3]^n.</math> Given a string <math>x\in[3]^n</math> and m disjoint subsets <math>W_1,\dots,W_m</math> of <math>[n],</math> send <math>y\in[3]^m</math> to <math>x+\sum_iy_iW_i,</math> where this denotes the sequence that takes the value <math>y_i</math> everywhere in the set <math>W_i</math> and is equal to x everywhere that does not belong to any <math>W_i</math>. An m-dimensional combinatorial subspace is the image of a combinatorial embedding. | There is also a natural notion of a ''combinatorial embedding'' of <math>[3]^m</math> into <math>[3]^n.</math> Given a string <math>x\in[3]^n</math> and m disjoint subsets <math>W_1,\dots,W_m</math> of <math>[n],</math> send <math>y\in[3]^m</math> to <math>x+\sum_iy_iW_i,</math> where this denotes the sequence that takes the value <math>y_i</math> everywhere in the set <math>W_i</math> and is equal to x everywhere that does not belong to any <math>W_i</math>. An m-dimensional combinatorial subspace is the image of a combinatorial embedding. | ||
Revision as of 16:14, 16 February 2009
An m-dimensional combinatorial subspace is obtained by taking m disjoint subsets [math]\displaystyle{ W_1,\dots,W_m }[/math] of [math]\displaystyle{ [n], }[/math] fixing the values of all coordinates outside these subsets, and taking all points that equal the fixed values outside the [math]\displaystyle{ W_i }[/math] and are constant on each [math]\displaystyle{ W_i. }[/math] Sometimes one adds the restriction that the maximum of each [math]\displaystyle{ W_i }[/math] is less than the minimum of [math]\displaystyle{ W_{i+1} }[/math]. (In particular, the Hales-Jewett theorem can be straightforwardly generalized to yield a monochromatic subspace of this more stronger kind.) In other words, where a combinatorial line has one set of wildcards, an m-dimensional combinatorial subspace has m sets of wildcards
For example, the following strings form a 2-dimensional combinatorial subspace of the strong kind (with wildcards indicated by full stops and commas)
331.21.311.221,21, 3312131122222 3312131122323 332.22.312.221,21, 3322231222222 3322231222323 333.23.313.221,21, 3332331322222 3332331322323
and the following strings form a 2-dimensional combinatorial subspace of the weaker kind
113113121311321 113213122311321 113313123311321 113113221312321 113213222312321 113313223312321 113113321313321 113213322313321 113313323313321
There is also a natural notion of a combinatorial embedding of [math]\displaystyle{ [3]^m }[/math] into [math]\displaystyle{ [3]^n. }[/math] Given a string [math]\displaystyle{ x\in[3]^n }[/math] and m disjoint subsets [math]\displaystyle{ W_1,\dots,W_m }[/math] of [math]\displaystyle{ [n], }[/math] send [math]\displaystyle{ y\in[3]^m }[/math] to [math]\displaystyle{ x+\sum_iy_iW_i, }[/math] where this denotes the sequence that takes the value [math]\displaystyle{ y_i }[/math] everywhere in the set [math]\displaystyle{ W_i }[/math] and is equal to x everywhere that does not belong to any [math]\displaystyle{ W_i }[/math]. An m-dimensional combinatorial subspace is the image of a combinatorial embedding.
