Combinatorial subspace

From Polymath1Wiki
Jump to: navigation, search

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


3312131122121   3312131122222   3312131122323  
3322231222121   3322231222222   3322231222323
3332331322121   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][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+y_1W_1+\dots+y_mW_m,[/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.