Skip to main content

Section 5.1 Combinatorial Lines

Last year I went fishing with Salvador Dali. He was using a dotted line. He caught every other fish. — Steven Alexander Wright, American comedian, actor and writer, 1955–

Alphabet. For \(m\in \mathbb{N}\text{,}\) any set \(A\) such that \(|A|=m\) is called an alphabet on \(m\) symbols.

Example 5.1.1.

Let \(A=\{a,1,\triangle\}\text{.}\) Then \(A\) is an alphabet on \(|A|=3\) symbols.

Words. Let \(A\) be an alphabet on \(m\) symbols. For \(n\in\mathbb{N}\text{,}\) any function \(w:[1,n]\to A\) is called a word of length \(n\) on the alphabet \(A\text{.}\) If \(w(i)=a_i\text{,}\) \(i\in[1,n]\) then we write

\begin{equation*} w=a_1a_2\cdots a_n\text{.} \end{equation*}

The set of all words of length \(n\) on the alphabet \(A\) is denoted by \(A^n\text{.}\) We say that \(A^n\) is the \(n\)-dimensional cube on alphabet \(A\).

Example 5.1.2.

Let \(A=\{a,1,\triangle\}\) be an alphabet on three symbols. Then \(w=a1a1a1\) is a word of length 6 on the alphabet \(A\text{.}\) Here \(w:[1,6]\to A\) is defined as \(w(1)=w(3)=w(5)=a\) and \(w(2)=w(4)=w(6)=1\text{.}\)

Also, \(A^2=\{w:w:[1,2]\to A\}=\{aa,a1,a\triangle, 1a,11,1\triangle,\triangle a,\triangle 1, \triangle\triangle\}\text{.}\)

Roots. Let \(A\) be an alphabet (on \(m\) symbols) and let \(\ast\) be a symbol such that \(\ast\not\in A\text{.}\) We consider the alphabet \(A_\ast=A\cup\{ \ast\}\text{.}\) Any word on the alphabet \(A_\ast\text{,}\) i.e, any element of \((A_\ast)^n=A_\ast^n\text{,}\) for some \(n\in \mathbb{N}\text{,}\) that contains the symbol \(\ast\) is called a root.

Example 5.1.3.

Let \(A=\{a,1,\triangle\}\) be an alphabet on three symbols. Then \(A_\ast=A\cup\{\ast\}=\{a,1,\triangle\,\ast\}\text{.}\) By definition, \(1\ast\triangle\) and \(a\ast a \ast\) are two roots.

Words From Roots. For a root \(\tau \in A_\ast^n\) and a symbol \(a\in A\) we define the word \(\tau_a\in A^n\) in the following way. For \(i\in [1,n]\)

\begin{equation*} \tau_a(i)= \left\{ \begin{array}{rcl} \tau(i)\amp \mbox{ if } \amp \tau(i)\not= \ast ,\\ a\amp \mbox{ if } \amp \tau(i)= \ast . \end{array} \right. \end{equation*}
Example 5.1.4.

Let \(A=\{ a,b,c\}\) and let \(\tau = \ast \ b \ c \ b \in A_\ast ^4\) be a root. Then

\begin{align*} \tau_a\amp =\amp \Box \ b \ c \ b\\ \tau_b\amp =\amp \Box \ b \ c \ b\\ \tau_c\amp =\amp \Box \ b \ c \ b \text{.} \end{align*}
Example 5.1.5.

Example: Let \(A=[1,4]\) and let \(\tau = \ast \ 1 \ 3 \ \ast \ 4 \ \ast \in A_\ast ^6\) be a root. Then

\begin{equation*} \tau_2=\Box \ 1 \ 3 \ \Box \ 4 \ \Box\text{.} \end{equation*}

Combinatorial Line: Let \(A\) be an alphabet, let \(n\in \mathbb{N}\text{,}\) and let \(\tau \in A_\ast^n\) be a root. A combinatorial line in \(A^n\) rooted in \(\tau\) is the set of words

\begin{equation*} L_\tau=\{ \tau _a:a\in A\}\text{.} \end{equation*}
Observation 5.1.6.

\(L\tau \subseteq A^n\text{.}\)

Example 5.1.7.

Let \(A=\{1,2,3\}\) and \(n=2\text{.}\) Find all combinatorial lines in \(A^2\text{.}\)

  1. All roots in \(A_\ast^2\text{:}\)

    \begin{align*} \tau \amp =\amp \ast \ 1\\ \sigma \amp =\amp \ast \ 2\\ \theta \amp =\amp \ast \ 3\\ \rho \amp =\amp 1\ \ast\\ \chi \amp =\amp 2 \ \ast\\ \phi \amp =\amp 3 \ \ast\\ \mu \amp =\amp \ast \ \ast\text{.} \end{align*}

  2. All combinatorial lines:

    \begin{align*} L_\tau \amp =\amp \{ 1 \ 1, 2 \ 1, 3 \ 1\}\\ L_\sigma \amp =\amp \{ 1 \ 2, 2 \ 2, 3 \ 2\}\\ L_\theta \amp =\amp \{ 1 \ 3, 2 \ 3, 3 \ 3\}\\ L_\rho \amp =\amp \{ 1 \ 1, 1 \ 2, 1 \ 3\}\\ L_\chi \amp =\amp \{ 2 \ 1, 2 \ 2, 2 \ 3\}\\ L_\phi \amp =\amp \{ 3\ 1, 3 \ 2, 3 \ 3\}\\ L_\mu \amp =\amp \{ 1 \ 1, 2 \ 2, 3 \ 3\}\text{.} \end{align*}

All combinatorial lines - Another view:

\begin{equation*} \begin{array}{|c|c|c|c|c|c|c|c|} \hline L_\tau \amp L_\sigma \amp L_\theta \amp L_\rho \amp L_\chi \amp L_\phi \amp L_\mu\\ \hline \color{red}{1}\ 1\amp \color{red}{1}\ 2\amp \color{red}{1} \ 3\amp 1\ \color{red}{1}\amp 2\ \color{red}{1}\amp 3\ \color{red}{1}\amp \color{red}{1}\ \color{red}{1}\\ \color{red}{2}\ 1\amp \color{red}{2}\ 2\amp \color{red}{2} \ 3\amp 1\ \color{red}{2}\amp 2\ \color{red}{2}\amp 3\ \color{red}{2}\amp \color{red}{2}\ \color{red}{2}\\ \color{red}{3}\ 1\amp \color{red}{3}\ 2\amp \color{red}{3} \ 3\amp 1\ \color{red}{3}\amp 2\ \color{red}{3}\amp 3\ \color{red}{3}\amp \color{red}{3}\ \color{red}{3}\\ \hline \end{array} \end{equation*}

All combinatorial lines - Another view (see Figure 5.1.8):

Figure 5.1.8. All combinatorial lines in \([1,3]^2\text{.}\)

It looks like… (See Figure 5.1.9.)

Figure 5.1.9. Tic-Tac-Toe: it's a win!
Example 5.1.10.

What About Combinatorial Lines in \([1,3]^3\text{?}\)

Consider roots:

\begin{equation*} \tau= \ast \ 2\ 3, \ \ \sigma = \ast \ \ast \ 3, \ \theta =\ast \ \ast \ \ast\text{.} \end{equation*}

Then (also see Figure 5.1.11):

\begin{equation*} \begin{array}{|c|c|c|} \hline L_\tau\amp L_\sigma\amp L_\theta\\ \hline {\color{red}{1} }23\amp {\color{red}{11}} 3\amp \color{red}{111}\\ {\color{red}{2}}23\amp {\color{red}{22} } 3\amp \color{red}{222}\\ {\color{red}{3}}23\amp {\color{red}{33}} 3\amp \color{red}{333}\\ \hline \end{array} \end{equation*}
Figure 5.1.11. Three combinatorial lines in \([1,3]^3\text{.}\)

\(4\times 4\times 4\) Tic-Tac-Toe

This is just a 2-player Tic-Tac-Toe game on a 4 x 4 x 4 cube. The player wins who first gets four in a row of his own pieces - either horizontal, vertical, or diagonal. See Figure 5.1.12. (Source BoardGameGeek.)

Figure 5.1.12. The first edition of Qubic by any company was produced by Duplicon in 1946 or 1947.

Rules of the Game. Create a monochromatic combinatorial line in \([1,4]^3\text{.}\)

Question 5.1.13.

Let \(A\) be an alphabet on \(m\) symbols and let \(A^n\) be the \(n\)-dimensional cube on alphabet \(A\text{:}\)

\begin{equation*} A^n=\{a_1a_2\cdots a_n: a_i\in A, i\in [1,n]\}\text{.} \end{equation*}

If \(A^n\) is \(k\)-coloured, can we be sure that \(A^n\) contains a monochromatic combinatorial line?

More precisely … Let \(m,k\in \mathbb{N}\) and let \(A\) be an alphabet on \(m\) symbols. Does there exist an \(n\in \mathbb{N}\) such that whenever \(A^n\) is \(k\)-coloured there exists a monochromatic line? See Figure 5.1.14.

Figure 5.1.14. Is it true that whenever \(A^n\) is \(k\)-coloured there exists a monochromatic line?