# Hales-Jewett Theorem

Below is a piece of code designed to help empirically determine some lower bounds for cn, defined as the size of the largest subset $A\subset [3]^n$ containing no combinatorial line. A combinatorial line in [3]n is a triple (w1,w2,w3) given by mapping a word $w\in \{1,2,3,\ast\}^n$ to wi, where $\ast$ is replaced by i; for example, the word $w = 12\ast 2\ast 3$ denotes the triple of points (121213,122223,123233).

The code found the following lower bounds for cn:

n lower bound for cn
3 18
4 50
5 140
6 420
7 1155
8 3346
9 11340
10 32676

It is interesting to note that c4 = 52, so that the lower bound provided here is not tight. This means that the straightforward greedy algorithm won't always produce an optimal answer.

#!/usr/bin/python

# The main functions of interest here are GenerateGraph, which
# builds a bipartite graph representing [3]^n and all combinatorial
# lines therein; and the function FindSmallExclusionSet, which
# takes in such a graph and greedily finds a small set whose
# complement in [3]^n contains no such lines.
#
# So, to empirically find a lower bound for c_n, you could run
#   3**n - len(FindSmallExclusionSet(GenerateGraph(n)))
#
# What is our graph format?
# Note that it's a bipartite graph.
# G = [A_nbors, B_nbors]
# We index sets A and B starting at 0.
# {A,B}_nbors = [[nbor_1_of_{a,b}0, nbor_2_of_{a,b}0, ...],
#                nbors_of_{a,b}1, nbors_of_{a,b}2, ...]
#
# lower_bds.py - Tyler Neylon, 2009

# Assumes there's only one copy of a in the list.
def RemoveFromList(a, a_list):
try:
a_list.remove(a)
except: pass

def BaseFourList(i):
base_four = []
while i > 0:
base_four.append(i % 4)
i /= 4
return base_four

def IntFromBaseBList(base_list, B):
i = 0
mult = 1
for j in base_list:
i += j * mult
mult *= B
return i

def IsInThreeToTheN(i):
return 3 not in BaseFourList(i)

# Converts a binary list to a list of
# indices which are True.
def TrueIndices(x):
return [i for i, v in enumerate(x) if v]

def PointsInLine(i):
i_base_four = BaseFourList(i)
stars = TrueIndices(j == 3 for j in i_base_four)
points_in_line = []
p = list(i_base_four)
for k in range(3):
for n in stars:
p[n] = k
points_in_line.append(IntFromBaseBList(p,3))
return points_in_line

def GenerateGraph(n):
# Iterate through all strings in [4]^n.
# If it's in [3]^n, add to B_list.  Else,
# add this line to the graph.
A_nbors = [[] for i in xrange(4**n)]
B_nbors = [[] for i in xrange(3**n)]
for i in range(4**n):
if not IsInThreeToTheN(i):
points = PointsInLine(i)
A_nbors[i] = list(points)
for p in points:
B_nbors[p].append(i)
return [A_nbors, B_nbors]

# Tries to find a small subset of B which hits
# all edges.  Removes all edges of structure G in the process.
def FindSmallExclusionSet(G):
[A_nbors, B_nbors] = G
excluded_B = []
while any(B_nbors):
print "Excluded %d points so far" % len(excluded_B)
degrees = [len(i) for i in B_nbors]
max_deg = max(degrees)
for i, x in enumerate(B_nbors):
if len(x) == max_deg:
excluded = i
break
excluded_B.append(excluded)

# Remove all associated edges.
for a in B_nbors[excluded]:
for b in A_nbors[a]:
if b != excluded:
RemoveFromList(a, B_nbors[b])
A_nbors[a] = []
B_nbors[excluded] = []
return excluded_B