TOPICS
Search

Combinatorial Line


A combinatorial line in {1,...,k}^n is a set of k words obtained by fixing some coordinate positions and placing a common variable letter in all remaining positions, with at least one variable position (Hales and Jewett 1963). Substituting each of the k letters for the variable gives the members of the line. For example, in {1,2,3}^3, the words (1,2,1), (2,2,2), and (3,2,3) form a combinatorial line.

The density Hales-Jewett theorem guarantees a combinatorial line in every subset of {1,...,k}^n of fixed positive density once n is sufficiently large. For k=3, every combinatorial line is a collinear triple in real Euclidean space, although not every collinear triple is a combinatorial line.


See also

Density Hales-Jewett Theorem, Ramsey Theory

Explore with Wolfram|Alpha

References

Hales, A. W. and Jewett, R. I. "Regularity and Positional Games." Trans. Amer. Math. Soc. 106, 222-229, 1963. https://doi.org/10.1090/S0002-9947-1963-0143712-1.

Cite this as:

Weisstein, Eric W. "Combinatorial Line." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CombinatorialLine.html

Subject classifications