#Copyright 1999 by Aaron Robertson

#input k and l
#Definition:  Difference Graph is a 2 coloring of K_n such that the edges of
#each
#difference (j-i where i and j are labelled verticies) are all the same color.
#This program will first search for a maximal difference graph on n verticies
#where n is determined by the first procedure, such that there is no
#red K_k and no blue K_l.
#Then the program will write its OWN program to double check that there are no
#red K_k or blue K_l.  Hence it will conclude that R(k,l) > n.
#Note n may not be the maximal number such that R(k,l) > n, but
#it will be the maximal number among all difference graphs.

#completely automated and routine for all k and l
#contingent only upon speed and size of computer
lprint(``):
print(`This is AUTORAMSEY, a Maple package written by`):
print(`Aaron Robertson.`):
print(`Available for download at www.math.temple.edu/~aaron.`):
lprint(``):
print(`Please report any bugs to aaron@math.temple.edu.`):
print(`These will be acknowledge in later versions.`):
lprint(``):
print(`IMPORTANT:  This package requires Maple version 4 if you want`):
print(`the computer written program and/or paper (see below).`):
lprint(``):
print(`The main procedure is R(k,l,ProgramName,PaperName).`):
print(`The other procedures are`):
print(`diffgraph, mset, edgegraph, checkprogram, and autopaper.`):
print(`For help with a specific procedure type ezra(procedure name).`):
print(`For general help type ezra().`):
lprint(``):



ezra:=proc()
if args=NULL then
print(`AUTORAMSEY`):
print(`A Maple package for finding lower bounds for )`):
print(`classical Ramsey numbers.`):
print(`For help with a specific procedure, type "ezra(procedure_name);"`):
print(`Contains procedures: `):
print(`R, diffgraph, mset, edgecheck, checkprogram, and autopaper. `):
fi:
 
 
if nops([args])=1 and op(1,[args])=`R` then
print(`The call is R(k,l,ProgramName,PaperName), where we are searching for the`):
print(`Ramsey number R(k,l).  ProgramName is the name of the file`):
print(`where the computer will store the program it creates.`):
print(`PaperName is the name of the file where the computer`):
print(`written paper will be stored.  NOTE: the .tex extention will not work.`):
print(`eg Ramsey33.tex will be stored in Ramsey33tex (no dot).`):
print(`The arguments ProgramName and PaperName are OPTIONAL.`):
print(`If you do not want either or both, then simply type "no" (without quotes),`):
print(`for example, R(3,3,no,Ramsey33Paper) will find the maximal`):
print(`difference graph that avoids a monochromatic K_3, does not write`):
print(`a verification program, but does write a paper stored under`):
print(`filename Ramsey33Paper.`):
fi:


if nops([args])=1 and op(1,[args])=`mset` then
print(`The call is mset(k,Dk,addDiff) where we are trying to avoid`):
print(`a red K_k, Dk is the list of red differences, and addDiff is`):
print(`the vertex we are trying to add to the graph in search of`):
print(`a maximal difference graph.`):
print(`The output is an ordered "multiset" of differences from Dk.`):
print(`The multiset has size k-1.`):
print(`These correspond to k-1 edges of a subgraph.`):
fi:


if nops([args])=1 and op(1,[args])=`edgecheck` then
print(`The call is edgecheck(k,l,S,T,addDiff) where we are trying to avoid`):
print(`a red K_k and a blue K_l, S is a pair of lists: `):
print(`S=[[mset(k,Dk,addDiff)],[mset(l,Dl,addDiff)]],`):
print(`T is the pre-addDiff pair of differences [[Dk],[Dl]], and`):
print(`addDiff is the vertex we are trying to add.`):
print(`This procedure checks to see which difference graphs still`):
print(`avoid a red K_k and a blue K_l after adding a new vertex (addDiff).`):
print(`The output is a list of survivors, if any, or 0 if no survivors.`):
fi:

if nops([args])=1 and op(1,[args])=`diffgraph` then
print(`The call is diffgraph(k,l) where we are searching for a lower`):
print(`bound of the Ramsey number R(k,l).  This procedure finds the`):
print(`set of all maximal difference graphs that avoid a red K_k and`):
print(`a blue K_l.`):
fi:

if nops([args])=1 and op(1,[args])=`checkprogram` then
print(`The call is checkprogram(filename,k,l,Dk,Dl) with k and l`):
print(`from R(k,l), filename is the name of the file where the`):
print(`program will be stored, Dk is the list of red differences, and`):
print(`Dl is the list of blue difference.`):
print(`This procedure will write a verification program that can`):
print(`be run in Maple to check that indeed there is no red`):
print(`K_k and no blue K_l in our colored graph.`):
print(`The program is straightforward and can easily be seen`):
print(`to check the coloring correctly (rather than relying`):
print(`solely on the procedure which generates the graph).`):
fi:


if nops([args])=1 and op(1,[args])=`autopaper` then
print(`The call is autopaper(filename,k,l,n,critset), with k and l as`):
print(`before, filename is the name of the file where the paper will be`):
print(`stored (DO use the .tex extension if you want it),`):
print(`n is the size of one of the maximal difference graphs`):
print(`(which is in the output of diffgraph), and critset is`):
print(`the set of differences colored red (also from diffgraph).`):
print(`This writes a one page paper on the lower bound.`):
fi:

end:




R:=proc(a,b,ProgramName,PaperName)
local k,l,n,W,Dk,Dl,numbcritical,critexample,critset,RamseyTempPaper,RamseyTemp:
k:=a:
l:=b:

RamseyTemp:=ProgramName:
RamseyTempPaper:=PaperName:

W:=diffgraph(k,l):
n:=W[1]:
numbcritical:=nops(W[2]):
#color the below differences red for no red K_k, others blue for no blue K_l
critexample:=op(1,op(1,W[2])):
if k=l then numbcritical:=numbcritical/2:fi:
if numbcritical >1 then
printf(`There are %d distinct difference graphs on %d verticies for which \n`,numbcritical,n):
printf(`there is no red K_%d and no blue K_%d. \n`,k,l):
printf(`Further, these are the maximal such difference graphs.\n`):
printf(`So we have established that R(%d,%d) > %d.\n`,k,l,n):
else
printf(`There is 1 distinct difference graph on %d verticies for which \n`,n):
printf(`there is no red K_%d and no blue K_%d. \n`,k,l):
printf(`Further, this is the maximal such difference graph.\n`):
printf(`So we have established that R(%d,%d) > %d.\n`,k,l,n):
fi:

#Dk:=all differences that are red:
#Dl:=all blue differences ({1,2,...,n} minus Dk)

Dk:=critexample:
Dl:=op(2,op(1,W[2])):

if RamseyTemp<>`no` then
checkprogram(RamseyTemp,k,l,n,Dk,Dl):
printf(`Program written. \n`):
fi:

if RamseyTempPaper<>`no` then
critset:={op(critexample)}:
autopaper(RamseyTempPaper,k,l,n,critset):
printf(`Paper written. \n`):
fi:

end:



#this computes all maximal difference graphs

diffgraph:=proc(k,l)
local z,a,b,i,j,s,Dk,Dl,flag,EdgeConfigk,EdgeConfigl,addDiff,m,n ,listk,listl,birth,preBirth,afterBirth,saveBirth,tempDk,tempDl,nogoodk,nogoodl:
with(combinat,numbcomb,choose):
m:=min(k,l):

#we now look at differences on m-1 vertices, since then cannot possibly
#have a red K_k or blue K_l, regardless of coloring.  Hence these are
#the starting difference lists.

#the starting list is a list of lists of sets, where the sets are of the form Dk and Dl
#the sets are the differences and each entry of startlist is a
#partition of the verticies 1 through m-2
#which are kept as a pair in list form
#We are using m-2 since on m-1 vertices, we only need m-2 differences
#to completely define the difference graph

preBirth:=[]:

for i from 0 to m-2 do
  listk:=[op(choose(m-2,i))]:
  for j from 1 to numbcomb(m-2,i) do
    listl:=convert({seq(z,z=1..m-2)} minus {op(op(j,listk))},list):
    preBirth:=[op(preBirth),[listk[j],listl]]:
  od:
od:

#Note that by Ramsey's theorem the while loop must be finite
#each loop of the while loop adds the next difference in line

addDiff:=m-2:


while flag<>0 do
  addDiff:=addDiff+1:
  afterBirth:=[]:
  
  for i from 1 to nops(preBirth) do
    Dk:=op(1,preBirth[i]):
    Dl:=op(2,preBirth[i]):
    
    #we now add the next difference to each of Dk and Dl and get the
    #  edge configurations
    EdgeConfigk:=mset(k,Dk,addDiff):
    EdgeConfigl:=mset(l,Dl,addDiff):
    
    #Now check to see if the resulting difference set
    #  survives, dies, or proliferates
    birth:=edgecheck(k,l,[EdgeConfigk,EdgeConfigl],[Dk,Dl],addDiff):
    
    #Now create the list of all surviving difference sets
    
    if birth<>0 then
      afterBirth:=[op(afterBirth),op(birth)]:
    fi:
    
  od:
  
  if nops(afterBirth)=0 then
    flag:=0:
    a:=op(1,preBirth[1]):
    b:=op(2,preBirth[1]):
    n:=nops({op(a)} union {op(b)})+1:
    RETURN([n,preBirth]):
  else
    preBirth:=afterBirth:
  fi:  
gc():    
od:
print(`You should never see this statement.`):    
end:







##multisets of differences, order matters as well.
##Dk is a single set of differences.
##mset returns a list of lists, where each entry is
#  an ordered multiset of the k-1 outer edges differences
#  with differences from Dk 
##Note: must call seperately for k and l

mset:=proc(k,Dk,addDiff)
local
i,j,a,t,s,g,c,Dchoose,b,Dlist,Parts,numbParts,templist,templistsum,permlist,ListOfDiffs1,ListOfDiffs:
with(combinat,partition,numbpart,permute,choose):
ListOfDiffs:=[]:
ListOfDiffs1:=[]:

#If we are searching for a red K_k where the edge differences are specified
#  then once we have the k-1 outer edges, the rest of the graph is determined.
#  Hence we can use the partition function on k-1 to partition the differences
#  of the k-1 outer edges in all possible configurations.

##partition returns a list of lists
##numbParts is the number of partitions
##Can only use those partitions where number or parts in the individual
#  partition is less than or equal to nops(Dlist)
#  (starting out, the set Dk may have less than k-1 elements
#  and we would get an invalid subscript selector error)

Dlist:=[op(Dk)]:

Parts:=partition(k-1):
numbParts:=numbpart(k-1):
 
#note below nops(a)=nops(b) 
 
for j from 1 to numbParts do
    a:=Parts[j]:
    
    if nops(a)<=nops(Dlist) then
      Dchoose:=choose(Dlist,nops(a)):
      
      for s from 1 to nops(Dchoose) do
        b:=[op(Dchoose[s])]:
        permlist:=permute(a):
        for g from 1 to nops(permlist) do
          c:=op(g,permlist):
          templist:=[]:
          for i from 1 to nops(b) do
            templist:=[op(templist),seq(b[i],t=1..c[i])]:
          od:
          #the following is put in for efficiency purposes
          #no need to use edgecheck if the sum of the k-1 edges
          #is out of bounds since it won't affect the
          #outcome of edgecheck
          
          templistsum:=convert(templist,`+`):
          if templistsum<=addDiff then
            ListOfDiffs1:=[op(ListOfDiffs1),templist]:
          fi:     
        od:  
      od:      
    fi:
od:
    
for i from 1 to nops(ListOfDiffs1) do
  ListOfDiffs:=[op(ListOfDiffs),op(permute(ListOfDiffs1[i]))]:
od:
 
ListOfDiffs:
end:




##need to check if adding the new element changes validity of difference sets
##S is the complete list of pairs of edge differences
#    (with order and multiplicity)
#    for a given pair of differences; i.e. the output of mset for both Dk and Dl
##In edgecheck we add all possible configurations of 
#    edge differences to see if we avoid K_k.
#    Note that the i-sums must be consecutive (draw a picture of the graph
#    and you'll see what i mean)
##T is the pre-addDiff (preBirth) pair of differences.
##edgecheck outputs the survivor(s) if any, or 0 if no survivors. 

edgecheck:=proc(k,l,S,T,addDiff)
local z,a,b,i,j,t,temp,tempsum,Dk,Dl,Edgek,Edgel,EdgekList,EdgelList,nogoodk,nogoodl,TempDk,TempDl:
EdgekList:=op(1,S):
EdgelList:=op(2,S):
Dk:=op(1,T):
Dl:=op(2,T):
nogoodk:=0:
nogoodl:=0:
TempDk:=convert({op(Dk)} union {addDiff},list):
TempDl:=convert({op(Dl)} union {addDiff},list):

for a from 1 to nops(EdgekList) do
Edgek:=EdgekList[a]:
  for i from k-1 to 2 by -1 do
    for t from 1 to k-i do
      temp:=[seq(Edgek[j],j=t..t+i-1)]:
      tempsum:=convert(temp,`+`):
      if member(tempsum,TempDk)=false then
        t:=k:
        i:=1:
      elif i=2 and t=k-2 and member(tempsum,TempDk)=true then
        nogoodk:=1:
        a:=nops(EdgekList)+1:
      fi:
    od:
  od:
od:

for b from 1 to nops(EdgelList) do
Edgel:=EdgelList[b]:
  for i from l-1 to 2 by -1 do
    for t from 1 to l-i do
      temp:=[seq(Edgel[j],j=t..t+i-1)]:
      tempsum:=convert(temp,`+`):
      if member(tempsum,TempDl)=false then
        t:=l:
        i:=1:
      elif i=2 and t=l-2and member(tempsum,TempDl)=true then
        nogoodl:=1:
        b:=nops(EdgelList)+1:
      fi:
    od:
  od:
od:


#if both nogoodk and nogoodl = 1 then cannot add addDiff to either
#hence the pair in T is taken out of possible maximals (unless it
#is the last step, but this is taken care of elsewhere)

#if nogoodk=0 and nogoodl=1 or then can add addDiff to Dk but not Dl
#if nogoodk=1 and nogoodl=0 or then can add addDiff to Dl but not Dk

#if both nogoodk and nogoodl are 0 then can add addDiff to either
#hence we add TWO pairs to possible maximals
#one pair is Dk union addDiff and Dl
#the other is Dk and Dl union addDiff
#as both of these are valid

if nogoodk=0 and nogoodl=0 then
  RETURN([[TempDk,Dl],[Dk,TempDl]]):
elif nogoodk=0 and nogoodl=1 then
  RETURN([[TempDk,Dl]]):
elif nogoodk=1 and nogoodl=0 then
  RETURN([[Dk,TempDl]]):
else
  RETURN(0):
fi:
end:



checkprogram:=proc(RamseyTemp,a,b,n,DkT,DlT)
local i,j,numk,numl,seqk,seql,RSize,BSize,k,l,Dk,Dl,RA,s:
k:=a:
l:=b:
Dk:={op(DkT)}:
Dl:={op(DlT)}:

writeline(RamseyTemp,`#n is the number of verticies of the graph`):
writeline(RamseyTemp,`#k and l are from the Ramsey number R(k,l)`):
writeline(RamseyTemp,`#Dk is the set of differences colored red.`):
writeline(RamseyTemp,`#where we are trying to avoid a red K_k.`):
writeline(RamseyTemp,`#the maple program has shown that by`):
fprintf(RamseyTemp,`#coloring Dk= %a red \n`,critexample):
writeline(RamseyTemp,`#However, you can alter this program to check`):
writeline(RamseyTemp,`#any 2-colored graph to see if it avoids`):
writeline(RamseyTemp,`#a red K_k and a blue K_l.`):
writeline(RamseyTemp,`#by deleting lines 4 (RSet:={}:) through 8 (od:od:)`):
writeline(RamseyTemp,`#changing line 9 to RList:=Dk:`):
writeline(RamseyTemp,`#and input the edge coloring list as Dk`):
writeline(RamseyTemp,``):
writeline(RamseyTemp,`ram:=proc(n,k,l,Dk)`):
writeline(RamseyTemp,`local i,j,A,RA,BList,test1,clk,hold,hold2,flag:`):
writeline(RamseyTemp,`with(combinat,choose):`):
writeline(RamseyTemp,`RSet:={}:`):
fprintf(RamseyTemp,`for i from 1 to %d do \n`,n):
fprintf(RamseyTemp,`for j from i+1 to %d do \n`,n):
writeline(RamseyTemp,`if member(j-i,Dk) then RSet:=RSet union {[i,j]}: fi:`):
writeline(RamseyTemp,`od:od:`):
writeline(RamseyTemp,`RList:=[op(RSet)]:`):
writeline(RamseyTemp,`BList:=[op(choose(seq(i,i=1..n),2) minus {op(RList)})]:`):

numk:=k*(k-1)/2:
numl:=l*(l-1)/2:
seqk:=seq(`od:`,i=1..numk):
seql:=seq(`od:`,i=1..numl):
RSize:=nops(Dk):
BSize:=nops(Dl):

for j from 1 to 2 do
     writeline(RamseyTemp,`test1:={}:clk:=[]:`):
     for i from 1 to numk do
	RA[i]:=RSize-numk+i:
	s:=i-1:
	
	if i=1 then
	  fprintf(RamseyTemp,`for A[%d] from 1 to %d do \n`,i,RA[i]):
  	else
    	  fprintf(RamseyTemp,`for A[%d] from A[%d]+1 to %d do \n`,i,s,RA[i]):
	fi:
	
	writeline(RamseyTemp,`flag:=1:`):
	writeline(RamseyTemp,`while flag<>0 do`):
	fprintf(RamseyTemp,`if A[%d]<=%d and nops(test1 union {op(op(A[%d],RList))}>%d then A[%d]:=A[%d]+1:\n`,i,RA[i],i,k,i,i):
	writeline(RamseyTemp,`else flag:=0: fi: od:`):
	fprintf(RamseyTemp,`if A[%d]<=%d then \n`,i,RA[i]):
	writeline(RamseyTemp,`hold:=test1:hold2:=clk:`):
	fprintf(RamseyTemp,`test1:=test1 union {op(op(A[%d],RList))}: \n`,i):
	fprintf(RamseyTemp,`clk:=[op(clk),op(A[%d],RList)]: \n`,i):
	
	if i=numk then
          if j=1 then
	    writeline(RamseyTemp,`if nops(test1)=k then RETURN(0,red,clk): fi:`):
          elif j=2 then
      	    writeline(RamseyTemp,`if nops(test1)=l then RETURN(0,blue,clk):  fi:`):
          fi:
	fi:	
	writeline(RamseyTemp,`else test1:=hold: clk:=hold2: fi:`):
     od:
     
writeline(RamseyTemp,seqk):
  if j=1 then
    writeline(RamseyTemp,`RList:=BList: RSize:=BSize:`):
  fi:
k:=l:
numk:=numl:
seqk:=seql:
od:

writeline(RamseyTemp,`1:`):
writeline(RamseyTemp,`end:`):

end:



autopaper:=proc(RamseyTempPaper,k,l,n,cset)
local critset,m:
critset:={op(cset)}:
m:=n+1:

writeline(RamseyTempPaper,`% A LaTeX document written by Aaron Robertson's`):
writeline(RamseyTempPaper,`% computer package, AUTORAMSEY.`):
writeline(RamseyTempPaper,``):
writeline(RamseyTempPaper,`\\documentstyle{article}`):
writeline(RamseyTempPaper,`\\textwidth=6.5in`):
writeline(RamseyTempPaper,`\\textheight=9in`):
writeline(RamseyTempPaper,`\\topmargin=-.75in`):
writeline(RamseyTempPaper,`\\oddsidemargin=0in`):
writeline(RamseyTempPaper,`\\evensidemargin=-.5in`):
writeline(RamseyTempPaper,`\\def\\Tilde{\\char126\\relax}`):
writeline(RamseyTempPaper,`\\begin{document}`):
fprintf(RamseyTempPaper,`\\begin{center}\\Large{A Lower Bound for the Ramsey Number R(%d,%d)} \n`,k,l):
writeline(RamseyTempPaper,`\\end{center}`):
writeline(RamseyTempPaper,`\\vskip 10pt`):
writeline(RamseyTempPaper,`\\begin{center}Aaron Robertson`):
writeline(RamseyTempPaper,`\\vskip 3pt`):
writeline(RamseyTempPaper,`Department of Mathematics, Temple University`):
writeline(RamseyTempPaper,`\\vskip 3pt`):
writeline(RamseyTempPaper,`Philadelphia, PA 19122`):
writeline(RamseyTempPaper,`\\vskip 3pt`):
writeline(RamseyTempPaper,`aaron@math.temple.edu`):
writeline(RamseyTempPaper,`\\end{center}`):
writeline(RamseyTempPaper,`\\vskip 30pt`):

writeline(RamseyTempPaper,`\\begin{abstract}`):
writeline(RamseyTempPaper,`In this article we show that the Ramsey number`):
fprintf(RamseyTempPaper,`$R(%d,%d) \\geq %d$. \n`,k,l,m):
writeline(RamseyTempPaper,`\\end{abstract}`):
writeline(RamseyTempPaper,`\\vskip 20pt`):
writeline(RamseyTempPaper,`This article is accompanied `):
writeline(RamseyTempPaper,`{\\tt AUTORAMSEY}, a Maple package available for download at `):
writeline(RamseyTempPaper,`{\\tt www.math.temple.edu/\\Tilde aaron}.`):
writeline(RamseyTempPaper,`(In fact, the computer wrote this paper.)`):
writeline(RamseyTempPaper,`\\vskip 20pt`):
writeline(RamseyTempPaper,`\\noindent`):
fprintf(RamseyTempPaper,`Using the call $R(%d,%d)$ in {\\tt AUTORAMSEY} \n`,k,l):
fprintf(RamseyTempPaper,`we produce a coloring of the complete graph $K_{%d}$ \n`,n):
fprintf(RamseyTempPaper,`that avoids both a red $K_{%d}$ and a blue $K_{%d}$. \n`,k,l):
fprintf(RamseyTempPaper,`Hence, we conclude that $R(%d,%d) \\geq %d$. \n`,k,l,m):
writeline(RamseyTempPaper,`\\vskip 20pt`):
writeline(RamseyTempPaper,`\\noindent`):
fprintf(RamseyTempPaper,`Let $i<j$ be vertices of $K_{%d}$.  Further, let \n`,n):
fprintf(RamseyTempPaper,`$A = \\{%a\\}$.  If $j-i \\in A$, then color the edge joining $i$ and $j$ \n`,critset):
writeline(RamseyTempPaper,`red.  Color the remaining edges blue.  This colored graph`):
fprintf(RamseyTempPaper,`avoids both a red $K_{%d}$ and a blue $K_{%d}$. \n`,k,l):
fprintf(RamseyTempPaper,`Hence, we can conclude that $R(%d,%d) \\geq %d$.\n`,k,l,m):
writeline(RamseyTempPaper,`\\vskip 20pt`):
writeline(RamseyTempPaper,`\\noindent`):
writeline(RamseyTempPaper,`To verify the above claim {\\tt AUTORAMSEY} also has a procedure that`):
writeline(RamseyTempPaper,`will write a Maple program tailored to this result.`):
writeline(RamseyTempPaper,`See {\\tt AUTORAMSEY} for more details.`):
writeline(RamseyTempPaper,`\\end{document}`):

end: