Hales-Jewett Theorem

#!/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):
  for i in xrange(len(a_list)):
    if a_list[i] == a:
      del a_list[i]
      break
 
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 not any([j == 3 for j in BaseFourList(i)])
 
# Converts a binary list to a list of
# indices which are True.
def TrueIndices(x):
  return [i for i in range(len(x)) if x[i]]
 
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 in range(len(B_nbors)):
      if len(B_nbors[i]) == 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