Hypercube Coloring and the Structureof Binary CodesbyJames Gregory RixA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Interdisciplinary Studies)The University Of British Columbia(Okanagan)July 2008c James Gregory Rix 2008AbstractA coloring of a graph is an assignment of colors to its vertices so that notwo adjacent vertices are given the same color. The chromatic number of agraph is the least number of colors needed to color all of its vertices. Graphcoloring problems can be applied to many real world applications, such asscheduling and register allocation. Computationally, the decision problemof whether a general graph is m-colorable is NP-complete for m 3.The graph studied in this thesis is a well-known combinatorial object,the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for allk; however, coloring the square of the cube is a much more interesting prob-lem. This is the graph in which the vertices are binary vectors of length k,and two vertices are adjacent if and only if the Hamming distance betweenthe two vectors is at most 2.Any color class in a coloring of Q2k is a binary (k;M;3) code. This thesiswill begin with an introduction to binary codes and their structure. Oneof the most fundamental combinatorial problems is nding optimal binarycodes, that is, binary codes with the maximum cardinality satisfying a spec-i ed length and minimum distance. Many upper and lower bounds havebeen produced, and we will analyze and apply several of these. This leadsto many interesting results about the chromatic number of the square of thecube.The smallest k for which the chromatic number of Q2k is unknown isk = 8; however, it can be determined that this value is either 13 or 14.Computational approaches to determine the chromatic number of Q28 wereperformed. We were unable to determine whether 13 or 14 is the true value;however, much valuable insight was learned about the structure of this graphand the computational di culty that lies within. Since a 13-coloring of Q28must have between 9 and 12 color classes being (8;20;3) binary codes, thisled to a thorough investigation of the structure of such binary codes.iiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . viiChapter 1. Coding Theory . . . . . . . . . . . . . . . . . . . . . . 11.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 An Introduction to Codes . . . . . . . . . . . . . . . . . . . . 51.3 Optimal Binary Codes . . . . . . . . . . . . . . . . . . . . . 111.3.1 The Sphere-Packing Bound . . . . . . . . . . . . . . . 181.3.2 Delsarte’s Linear Programming Bound . . . . . . . . 191.4 Applications of Delsarte’s Linear Programming Bound . . . . 24Chapter 2. Graph Theory . . . . . . . . . . . . . . . . . . . . . . 272.1 Elementary Concepts . . . . . . . . . . . . . . . . . . . . . . 272.2 Graph Isomorphisms and Automorphisms . . . . . . . . . . . 302.3 Vertex Coloring . . . . . . . . . . . . . . . . . . . . . . . . . 332.4 Algorithms to Solve Vertex Coloring Problems . . . . . . . . 352.4.1 An Introduction to Algorithms and E ciency . . . . 362.4.2 Integer Programming . . . . . . . . . . . . . . . . . . 382.4.3 Column Generation . . . . . . . . . . . . . . . . . . . 392.4.4 The Petford-Welsh Algorithm . . . . . . . . . . . . . 41Chapter 3. The Hypercube . . . . . . . . . . . . . . . . . . . . . 433.1 Automorphisms of the Cube and its Square . . . . . . . . . . 453.2 The Chromatic Number of the Cube and its Square . . . . . 53iiiTable of Contents3.2.1 The Asymptotic Behavior of the Chromatic Numberof the Square of the Cube . . . . . . . . . . . . . . . 623.3 Applying Computational Methods to Determine the Chro-matic Number of the Square of 8-Dimensional Cube . . . . . 643.3.1 Integer Programming . . . . . . . . . . . . . . . . . . 653.3.2 Column Generation . . . . . . . . . . . . . . . . . . . 673.3.3 The Petford-Welsh Algorithm . . . . . . . . . . . . . 68Chapter 4. The Structure of Optimal Binary Codes . . . . . . 694.1 Computationally Determining all Weight Distributions . . . 694.2 Structural Results . . . . . . . . . . . . . . . . . . . . . . . . 764.2.1 On the Size of Shortened Codes . . . . . . . . . . . . 764.2.2 Bounds on the Weight Distributions of Color Classes 774.3 The Number of Nonequivalent Codes . . . . . . . . . . . . . 784.4 Another De nition of Equivalence . . . . . . . . . . . . . . . 79Chapter 5. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 82Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85Appendix A. Current Status of Coloring the Square of the Cube . 86Appendix B. A 14-coloring of the Square of the 8-Cube . . . . . . 88Appendix C. Weight Distributions of (8;20;3) Binary Codes . . . 89Appendix D. Hougardy.cpp . . . . . . . . . . . . . . . . . . . . . . 92Appendix E. CPDist.cpp . . . . . . . . . . . . . . . . . . . . . . . 97ivList of TablesTable 3.1: A 4-coloring of Q23 using Wan’s construction . . . . . . . 58Table 4.1: Distance Distributions of (8;20;3) Binary Codes . . . . 79Table A.1: Current Status of Coloring the Square of the Cube . . . 86Table B.1: A 14-coloring of Q28 . . . . . . . . . . . . . . . . . . . . 88Table C.1: Weight Distributions of (8;20;3) Binary Codes . . . . . 89vList of FiguresFigure 2.1: Venn Diagram of the Complexity Classes . . . . . . . . 37Figure 3.1: Computation Times Using Integer Programming . . . . 66Figure 4.1: Computation Times for Feasible Distributions . . . . . 74Figure 4.2: Computation Times for Infeasible Distributions . . . . 75viAcknowledgementsFirst and foremost, I would like to thank my supervisor, Dr. Donovan Hare,for both introducing me to the beauty of optimization from a real worldperspective, and for giving me the opportunity to pursue my research inthis eld. His in nite patience was extremely helpful over the course of myeducational experience. In addition, I would like to give thanks to every-one who has had an invaluable impact on my educational experience: Dr.Wayne Broughton, Dr. Heinz Bauschke, Dr. Shawn Wang, Dr. Yves Lucet,Dr. Yong Gao, and Dr. Blair Spearman.This thesis was partially supported by the Natural Sciences and Engi-neering Research Council of Canada, the Paci c Institute for the Mathe-matical Sciences and the U.B.C. Okanagan College of Graduate Studies.viiChapter 1Coding TheoryIn this chapter, we recall background material from coding theory that willbe used in subsequent chapters. The chapter will conclude with the sphere-packing bound and Delsarte’s linear programming bound, two very usefulbounds in determining optimal binary code size. We will also include a proofof A(9;4) = 20 that uses Delsarte’s linear programming bound. This valuewill be very important in later chapters. We will now introduce the notationand de nitions that will be used throughout, which closely follow those usedin [20] and [13].It will be assumed throughout this thesis that reader has a basic knowl-edge of eld theory, set theory, linear and integer programming, and prob-ability.1.1 PreliminariesNotation 1.1. Let Z denote the set of all integers, and Z+ denote the setof all positive integers.Notation 1.2. For any positive integer n, let [n] denote the set of integersf1;2;:::;ng.Consider a nite eld F with addition and multiplication de ned, sat-isfying jFj = q. Recall that all elds have an additive identity, 0, anda multiplicitave identity, 1. Now consider the vector space Fn. Clearly,jFnj= qn. A vector u in Fn is of the following form:u =0BBB@u1u2...un1CCCA:For notational convenience, this will also be denoted u1u2:::un. We willrefer to ui as the ith coordinate of u.1Chapter 1. Coding TheoryNotation 1.3. Let ~0n and ~1n denote the vectors in Fn in which everycoordinate is 0 and 1, respectively.Notation 1.4. Let ni denote the vector in Fn in which the ith coordinateis 1, and every other coordinate is 0.De nition 1.5. Consider two vectors u and v in Fn. The (Hamming)distance between u and v, denoted d(u;v), is de ned to be the number ofcoordinates in which u and v di er.Let u;v;w2Fn. We state without proof the following properties of theHamming distance function: 0 d(u;v) n, d(u;v) = 0 if and only if u = v, d(u;v) = d(v;u), d(u;w) d(u;v) +d(v;w) (the triangle inequality).De nition 1.6. Let u2Fn and t be a positive integer. The (Hamming)sphere of radius t centered at u, denoted St(u), is the following set of vectors:St(u) =fv2f0;1gn jd(u;v) tg:De nition 1.7. Consider a vector u in Fn. The (Hamming) weight of u,denoted wt(u), is de ned to be the number of coordinates of u that arenonzero. The parity of u is even if wt(u) is even, and odd if wt(u) is odd.Consider two vectors u and v in Fn. The following properties of theHamming weight function are immediate: 0 wt(u) n, wt(u) = 0 if and only if u =~0n, wt(u) = n if and only if u =~1n, wt(u v) = d(u;v).De nition 1.8. Consider a vector u in Fn. We de ne pu and qu to befollowing elements of F:pu =(0 wt(u) is even,1 wt(u) is odd,2Chapter 1. Coding Theoryqu =(1 wt(u) is even,0 wt(u) is odd.Lemma 1.9. Let u;v;w2Fn. Then d(u;v) = d(u+w;v +w).Proof.d(u+w;v +w) = wt((u+w) (v +w))= wt((u v) + (w w))= wt(u v)= d(u;v):Notation 1.10. Let Sn, for all positive integers n, denote the symmetricgroup of degree n (i.e. the set of all permutations on the integers [n]).De nition 1.11. Let 2 Sn and u 2 Fn with coordinates de ned byu = u1u2:::un. Then (u)2Fn is de ned as follows: (u) = u (1)u (2):::u (n):For any vectors u and v in Fn, and permutation 2Sn, the followingproperties are immediate: wt( (u)) = wt(u), d( (u); (v)) = d(u;v). (u) + (v) = (u+v).De nition 1.12. Let u 2 Fm and v 2 Fn have coordinates de ned byu = u1u2:::um and v = v1v2:::vn. We de ne u concatenated with v,denoted u v, to be:u v = u1u2:::umv1v2:::vn;an element of the vector space Fm+n.Let u;u02Fm and v;v02Fn. Clearly, from the distance functions oftheir respective vector spaces:d(u v;u0 v0) = d(u;u0) +d(v;v0):One technique used often in the study of codes is to concatenate a vectoru2Fn with a parity coordinate, that is, create the vector u pu. It is clearthat wt(u pu) is even for any u2Fn.3Chapter 1. Coding TheoryDe nition 1.13. Consider two vectors u and v in Fn with their coordinatesde ned by u = u1u2:::un and v = v1v2:::vn. The inner product of u andv is de ned as follows:<u;v> =nXi=1uivi:Note: the inner product of u and v is an element of the eld F.Let u;v;w 2 Fn and c 2 F. As this is an inner product, it satis esseveral key properties: <u;v>=<v;u>, <u;v +w>=<u;v> + <u;w>, c<u;v>=<cu;v>.In this thesis, we will often be dealing with the eld Z2 = f0;1g, withbinary addition and multiplication de ned normally. When dealing withthis eld, we can de ne the intersection of two vectors. This will give riseto several useful results.De nition 1.14. Let u and v be binary vectors in f0;1gn with their coor-dinates de ned by u = u1u2:::un and v = v1v2:::vn. The intersection ofu and v is de ned to be:u\v =0BBB@u1v1u2v2...unvn1CCCA:Thus the ith coordinate of u\v is 1 if and only if the ith coordinate of bothu and v are 1.Let u and v be binary vectors in f0;1gn. We have the following proper-ties: wt(u\v) wt(u) and wt(u\v) wt(v), u\~0n =~0n and u\~1n = u.Lemma 1.15. Let u and v be binary vectors in f0;1gn. Then d(u;v) =wt(u) +wt(v) 2wt(u\v).4Chapter 1. Coding TheoryProof. Let U be the number of coordinates in which u is 1 and v is 0,and let V be the number of coordinates in which v is 1 and u is 0. Thend(u;v) = U + V. Since wt(u\v) represents the number of coordinates inwhich u and v are both 1, we have:d(u;v) = U +V= (wt(u) wt(u\v)) + (wt(v) wt(u\v))= wt(u) +wt(v) 2wt(u\v):Corollary 1.16. Let u and v be binary vectors in f0;1gn. Then u and vare of the same parity if and only if d(u;v) is even.Proof.u and v are of the same parity,wt(u) +wt(v) is even,wt(u) +wt(v) 2wt(u\v) is even,d(u;v) is even by Lemma 1.15:For notational convenience, we will often represent a binary vector byits integer representation.De nition 1.17. Let v be a binary vector inf0;1gn whose coordinates arede ned by v1v2:::vn. Consider the nonnegative integer i satisfying:i = 2n 1v1 + 2n 2v2 +:::+ 2vn 1 +vn:This integer i is the integer representation of the vector v.De nition 1.18. For any positive integer k, the binary representation ma-trix of order k is thedlog2(k+ 1)e k matrix in which column i, for i2[k],is the binary vector of length dlog2(k + 1)e whose integer representation isi. This matrix is denoted BRMk. For example, the binary representationmatrix of order 6 is de ned as follows:BRM6 =0@0 0 0 1 1 10 1 1 0 0 11 0 1 0 1 01A:1.2 An Introduction to CodesWe will now de ne a code over a nite eld F.5Chapter 1. Coding TheoryDe nition 1.19. Let F be a eld. A code C over F is a subset of Fn. Theelements u2C are the codewords of C. If F = f0;1g, then C is a binarycode.De nition 1.20. Let C =fu1;u2;:::;uMg, where ui2Fn for all i2[M].The (code) length is the length of the vectors, n, whereas the (code) size isthe number of codewords in the code, jCj= M.In addition to code length and size, a third parameter is usually speci edwhen referring to a code.De nition 1.21. Let C be an (n;M) code over a eld F. The minimumdistance of C, denoted d(C), is de ned to be:d(C) = minfd(u;v) ju;v2C;u6= vg:If M = 1 then d(C) =1.Notation 1.22. An (n;M) code is a code with length n and size M. An(n;M;d) code is a code with length n, size M, and minimum distance atleast d.De nition 1.23. Let C be an (n;M) code over a eld F, and let 2Sn.Then (C) is de ned to be: (C) =f (u) ju2Cg:Clearly, (C) is an (n;M) binary code. Moreover, d( (C)) = d(C).De nition 1.24. Let C be an (n;M) code over a eld F, and let w2Fn.Then C +w is the (n;M) code over F satisfying:C +w =fu+wju2Cg:Proposition 1.25. Let C be an (n;M) code over a eld F, and let w2Fn.Then d(C +w) = d(C).Proof. To determine the minimum distance of C +w, we have:d(C +w) = minfd(u;v) ju;v2C +w;u6= vg= minfd(x+w;y +w) jx;y2C;x6= yg= minfd(x;y) jx;y2C;x6= yg by Lemma 1.9= d(C):6Chapter 1. Coding TheoryIn the following de nitions, we will introduce techniques to create longeror shorter codes from a given code.De nition 1.26. Let C be an (n;M) code over a eld F, and let v2Fmfor some m 2 Z+. Then C v is the (n + m;M) code over F de ned asfollows:C v =fu vju2Cg:It is clear that d(C v) = d(C).De nition 1.27. Let C be an (n;M;2) code over a eld F, and let i2[n].The punctured code C(i) is de ned to be the (n 1;M) code overF containingall codewords of C with the ith coordinate removed. That is:C(i) =fu1u2:::ui 1ui+1:::un ju2Cg:Clearly, d(C) 1 d(C(i)) d(C).De nition 1.28. Let C be an (n;M) code over a eld F. Moreover, letx2F and i2[n]. The shortened code Ci;x is de ned to be the (n 1;M0 M) code over F containing all codewords of C with the eld element x incoordinate i, then punctured at i. That is:Ci;x =fu1u2:::ui 1ui+1:::un ju1u2:::ui 1xui+1:::un2Cg:Clearly, d(Ci;x) d(C).Codes are used in real world applications every day. In practice, in-formation is sent in the form of codewords from some (n;M) code C overa eld F, where di erent codewords represent di erent meanings. The re-quired codeword u2C is sent over a channel, over which errors can occur inany and all of the coordinates that change the coordinate to a di erent eldelement. Therefore, it is possible that one or more errors have transformedthe original codeword into a vector in Fn that is not in the code. When avector x2Fn is received at the other end of this channel, x is then decodedto some codeword v2C, generally the one that maximizes the likelihoodof receiving x (in the hopes that u = v). Assuming the probability of errorin every coordinate is the same, this codeword v will be the v 2 C thatminimizes d(x;v) with ties broken arbitrarily. Formally, this is expressed asin the following de nition.7Chapter 1. Coding TheoryDe nition 1.29. Let C be an (n;M) code over a eld F. A decoder is afunction D : Fn !C. The decoder D is a nearest codeword decoder if itsatis es:D(x) = v)d(x;v) = minfd(x;v0) jv02Cg:It is clear that the higher the minimum distance of a code, the higherthe probability that a received vector will be decoded correctly. The resultof Corollary 1.31 will specify explicitly the error correcting capability of acode with xed minimum distance. The following two proofs are similar tothose used in [13, Ch. 1, Theorem 2].Proposition 1.30. Let C be an (n;M;d) code over a eld F, and t = d 12 . For any u;v2C such that u6= v, St(u)\St(v) =;.Proof. Suppose, by way of contradiction, that there exists w2Fn such thatd(u;w) t and d(v;w) t. We have:d(u;v) d(u;w) +d(w;v) by the triangle inequality d 12 + d 12 d 12 + d 12= d 1;a contradiction to the minimum distance of C.Corollary 1.31. Let C be an (n;M;d) code over a eld F. A nearestcodeword decoder will correctly recover any pattern of up to d 12 errors.Proof. Let C be an (n;M;d) code over F. Suppose codeword u 2 C issent over a channel and t d 12 errors occur to yield vector w2Fn.Thus w2St(u). Take any v2Cnfug. By the result of Proposition 1.30,w =2St(v), implying:d(v;w) >t = d(u;w):Therefore a nearest codeword decoder will decode w to u.8Chapter 1. Coding TheoryDe nition 1.32. A constant weight code C is an (n;M;d) code in whichevery codeword in C has the same weight w. C can then be referred to asan (n;M;d;w) code.De nition 1.33. An even weight code C is a code in which every codewordu2C is of even weight. Similarly, an odd weight code C is a code in whichevery codeword u2C is of odd weight.For the remainder of this thesis, we will be strictly using binary codes.For binary vectors u and v, note that u v = u+v.Corollary 1.34. Even weight binary codes and odd weight binary codes haveeven minimum distance.Proof. Since every codeword is of the same parity, the proof of this corollaryfollows directly from Corollary 1.16.De nition 1.35. The weight distribution of an (n;M) binary code C withrespect to a vector u 2 f0;1gn is the sequence of nonnegative integers(Wi(u))ni=0, where Wi(u) for i = 0;1;:::;n is the number of codewords v2Csuch that d(u;v) = i. Symbolically, this de nition may be represented as:Wi(u) =Xv2Cd(u;v)=i1=Xv2Cwt(u+v)=i1:When u is not speci ed, it will be assumed that u =~0n. We will denote(Wi(~0n))ni=0 as simply (Wi)ni=0.Let C be an (n;M) binary code, u2f0;1gn, and 2Sn. Moreover,let (Wi(u))ni=0 denote the weight distribution of C with respect to u. Theweight distribution satis es the following properties: nXi=0Wi = M, The weight distribution of (C) with respect to u is also (Wi(u))ni=0, Letting (W0i)ni=0 denote the weight distribution of C + u, (W0i)ni=0 =(Wi(u))ni=0.9Chapter 1. Coding TheoryDe nition 1.36. The distance distribution of an (n;M) binary code C isthe list of nonnegative, rational numbers (Ai)ni=0, where Ai represents theaverage number of pairs of codewords in C at distance i from each other.Thus each Ai satis es:Ai = 1MXu;v2Cd(u;v)=i1= 1MXu2CXv2Cd(u;v)=i1= 1MXu2CWi(u):The following statements are clear for any (n;M;d) binary code withdistance distribution (Ai)ni=0: A0 = 1, Ai 0, Ai = 0 for i2[d 1], nXi=0Ai = M, or equivalently,nXi=dAi = M 1.De nition 1.37. Let C and D be (n;M;d) binary codes. C and D areequivalent if C = (D) +v for some 2Sn and v2f0;1gn. C is unique ifevery (n;M;d) binary code is equivalent to C.It is clear that code equivalence is re exive, symmetric, and transitive.Therefore, it is an equivalence relation on the set of all binary codes.The notion of equivalent codes will be very important throughout thisthesis. One very important property of equivalent codes is that they sharethe same distance distribution.Lemma 1.38. Let C and D be equivalent (n;M;d) binary codes. Then Cand D have the same distance distributions.Proof. Let 2 Sn and w 2 f0;1gn satisfy D = (C) + w. Moreover,let (ACi )ni=0 and (ADi )ni=0 denote the distance distributions of C and D,respectively. For any i2[n], we have:10Chapter 1. Coding TheoryACi = 1MXu;v2Cd(u;v)=i1= 1MXu;v2Cd( (u); (v))=i1= 1MXu;v2Cd( (u)+w; (v)+w)=i1 by Lemma 1.9= 1MXx;y2Dd(x;y)=i1= ADi :1.3 Optimal Binary CodesFinding binary codes of optimal size when length and minimum distanceare held xed has become a well-known and di cult combinatorial problem.Such optimal codes allow for a maximum number of possible messages to besent e ciently, while maintaining a speci ed error correcting ability.Notation 1.39. The size of the largest possible binary code of length n andminimum distance at least d is denoted A(n;d). An (n;M;d) binary codein which M = A(n;d) is optimal.The following trivial values of A(n;d) can easily be veri ed for any pos-itive integers n and d: A(n;1) = 2n, A(n;2) = 2n2 = 2n 1, A(n;d) = 1 if d>n.When d is su ciently large (2n3 <d n), it is known that A(n;d) = 2.Proposition 1.40 proves this result.Proposition 1.40. A(n;d) = 2 for n;d2Z+ with 2n3 <d n.11Chapter 1. Coding TheoryProof. Fix n and d as speci ed. First, we will show the existence of an(n;2;d) binary code. Consider any v 2f0;1gn with wt(v) = d (if d = nthen v =~1n). The code f~0n;vg is an example of an (n;2;d) binary code.We now show that an (n;3;d) code can’t exist. Suppose, by way ofcontradiction, that it does, and is de ned by C =fu;v;wg. We have:d(u;v) d(u;w +~1n) +d(v;w +~1n) by the triangle inequality= wt(u+w +~1n) +wt(v +w +~1n)= d(u+w;~1n) +d(v +w;~1n)= wt(u+w) +wt(~1n) 2wt((u+w)\~1n)+wt(v +w) +wt(~1n) 2wt((v +w)\~1n)= wt(u+w) +wt(~1n) 2wt(u+w)+wt(v +w) +wt(~1n) 2wt(v +w)= 2n d(u;w) d(v;w)< 2n 2n3 2n3= 2n3 ;a contradiction to the minimum distance of C.In fact, this result is tight with respect to d, as will be proven in Propo-sition 1.41.Proposition 1.41. A(n;d) 3 for n;d2Z+ with d 2n3 .Proof. Fix n and d as speci ed, and de ne t =ln3m. We will prove thisresult by exhibiting an (n;3;d) binary code. Consider C = fu1;u2;u3g,where the vectors ui are de ned as follows:u1 =tXi=1 ni; u2 =2tXi=t+1 ni; u3 =nXi=2t+1 ni:For any i;j2[3] with i6= j we have:ui\uj =~0n;12Chapter 1. Coding Theoryand hence by Lemma 1.15:d(ui;uj) = wt(ui) +wt(uj):The minimum distance of C is calculated as follows:d(C) = minfd(u1;u2);d(u1;u3);d(u2;u3)g= minfwt(u1) +wt(u2);wt(u1) +wt(u3);wt(u2) +wt(u3)g= minn2ln3m;2ln3m;ln3m+ n 2ln3m o= n ln3m= 2n3 :Therefore C is an (n;3;d) binary code.Propositions 1.42 and 1.43 show how values of A(n;d) can be boundedabove by A(n+ 1;d) and A(n 1;d).Proposition 1.42. A(n;d) A(n+ 1;d) for any n;d2Z+.Proof. Let C be an (n;M;d) binary code of optimal size M = A(n;d).Consider the code C 0, an (n + 1;M;d) binary code. The existence of thiscode proves A(n+ 1;d) A(n;d).Proposition 1.43. A(n;d) 2A(n 1;d) for any n;d2Z+.Proof. Let C be an (n;M;d) binary code of optimal size M = A(n;d).Consider the shortened codes Ci;0 and Ci;1 for any i2 [n]. It is clear thatjCi;0j M2 orjCi;1j M2 . Let D be the code formed by taking the larger ofCi;0 and Ci;1. D is clearly an (n 1;M0;d) binary code with size M0 M2 ,and hence:A(n 1;d) A(n;d)2 :The search of the values of A(n;d) for less trivial n and d is a classiccombinatorial problem. The result of Theorem 1.44 will show that we needonly nd A(n;d) for even d.Theorem 1.44. A(n;d) = A(n + 1;d + 1) for n;d2Z+ with d n and dodd.13Chapter 1. Coding TheoryProof. We will prove equality holds by rst proving A(n;d) A(n+1;d+1),then by proving A(n;d) A(n+ 1;d+ 1).Let C be an (n;M;d) binary code of optimal size M = A(n;d). To proveA(n;d) A(n+ 1;d+ 1), we will show the existence of an (n+ 1;M;d+ 1)binary code. Let C p de ned as follows:C p =fu pu ju2Cg:It is clear that C p is an (n + 1;M;d) binary code. However, C p isalso an even weight code, and therefore d(C p) is even. C p is hence an(n+ 1;M;d+ 1) binary code, which completes the rst half of the proof.Let D be an (n + 1;M;d + 1) binary code of optimal size M = A(n +1;d+ 1). To prove A(n;d) A(n+ 1;d+ 1), we will show the existence ofan (n;M;d) binary code. Since d is odd, d+1 2, and hence the puncturedcode D(i) for any i2 [n + 1] is an (n;M) binary code. In addition, sinceonly one coordinate has been punctured, d(D(i)) d. Therefore D(i) is an(n;M;d) binary code for any i2[n+ 1].A table of values of A(n;d) for n 28 and d 14 (for even d) canbe found in [2, Table I]. The listed entries of A(n;4) have been includedin Appendix A (included as A(n 1;3)). When n 17, many of thesevalues are currently unknown. That so few values are actually known is atestament to the di culty of this problem. However, various bounds havebeen developed. Lower bounds most often arise due to construction of aspeci c binary code attaining the given parameters, and upper bounds canbe proven through a number of di erent methods, two of which we will showin the following sections.Furthermore, many optimal binary codes are unique, that is, every bi-nary code attaining the given parameters is equivalent. For example, con-sider the (16;256;6), (15;256;5), (15;128;6), (14;128;5), (14;64;6), (13;64;5),(13;32;6), and (12;32;5) binary codes. All are seen to be optimal in [2, Ta-ble I]; moreover, all are unique with the exception of the (12;32;5) code [13,pp.74-75]. Osterg ard, Baicheva, and Kolev developed an algorithm in [18] that candetermine the number of nonequivalent binary codes for certain code pa-rameters. The number of nonequivalent (n;M;3) and (n;M;4) binary codeswere then calculated for various values of n and M, as seen in [18, Table I].14Chapter 1. Coding TheoryIn addition to bounds on the size of binary codes, another commonproblem in coding theory is determining the size of the largest possibleconstant weight binary code attaining given parameters.Notation 1.45. The size of the largest possible constant weight binary codeof length n, minimum distance at least d, and codeword weight w, for w n,is denoted A(n;d;w). An (n;M;d;w) constant weight binary code in whichM = A(n;d;w) is optimal.The following properties of A(n;d;w) can be easily veri ed for any pos-itive integers n and d, and nonnegative integer w n: A(n;2;w) = nw , A(n;d;w) = 1 if d>n, A(n;d;w) = A(n;d+ 1;w) for d odd, A(n;d;w) = A(n;d;n w).The nal statement is proven to hold by adding ~1n to either optimalcode. Due to these properties, the search for A(n;d;w) to be restricted toeven d and w jn2k. We also make use of the results of Propositions 1.46and 1.47 (see [13, Ch. 17, Theorem 1]):Proposition 1.46. A(n;d;w) = 1 for n;d2Z+ and w2Z+[f0gsatisfying2w<d n.Proof. The existence of a code meeting this bound is trivial (as it containsa single codeword). Thus we need only prove A(n;d;w) 1. To proveA(n;d;w) 1, assume by way of contradiction there are two vectors u;v2f0;1gn satisfying wt(u) = wt(v) = w and d(u;v) d. Then, by the triangleinequality:d(u;v) d(u;~0n) +d(~0n;v)= wt(u+~0n) +wt(u+~0n)= wt(u) +wt(v)< d2 + d2= d;a contradiction to the minimum distance of d, and hence A(n;d;w) = 1.15Chapter 1. Coding TheoryProposition 1.47. A(n;2w;w) =jnwkfor n;w2Z+.Proof. To show A(n;2w;w) jnwk, we need only show the existence of an(n;t;2w;w) binary code where t =jnwk. Consider C = fv1;v2;:::;vtg,where vi 2f0;1gn is the vector with a 1 in coordinates (i 1)w + 1;(i 1)w+ 2;:::;(i 1)w+w. It is clear that these vectors all exist as, for i t:(i 1)w +w jnwk 1 w +w n w +w = n:Moreover, d(vi;vj) = 2w for i6= j. Therefore C is an (n;t;2w;w) binarycode.To show A(n;2w;w) jnwk, assume by way of contradiction thereexists an (n;t + 1;2w;w) binary code D, with t de ned as above. LetD =fv1;v2;:::;vt+1g. For any i;j2[t+ 1];i6= j, by Lemma 1.15 we have:wt(vi\vj) = wt(vi) +wt(vj) d(vi;vj)2 w +w 2w2= 0:Thus wt(vi\vj) = 0, and hencet+1Xi=1wt(vi) n. However:t+1Xi=1wt(vi) =t+1Xi=1w = jnwk+ 1 w>n;a contradiction. Therefore A(n;2w;w) =jnwk.Agrell, Vardy, and Veger improved bounds on A(n;d;w) for many valuesin [1]. This article includes tables of A(n;d;w) for values of and bounds onA(n;d;w) for even values of d between 4 and 14. Recall that for odd valuesof d, A(n;d;w) = A(n;d + 1;w). Later in this thesis, we will refer back tothese tables.The following theorem and corollary show how the weight and distancedistribution of any binary code can be bounded above by the sizes of appro-priate optimal constant weight codes.16Chapter 1. Coding TheoryTheorem 1.48. Let C be an (n;M;d) binary code and x u 2 f0;1gn.Moreover, let Wi(u) be the weight distribution of C with respect to u. ThenWi(u) A(n;d;i) for i = 0;1;:::;n.Proof. Assume, by way of contradiction, that Wi(u) >A(n;d;i) for some i.Let k = Wi(u). Next, let fv1;v2;:::;vkg C be the set of codewords atdistance i from u. Consider the set of vectors D =fw1;w2;:::;wkgde nedby wj = vj +u for j2[k]. We claim that D is an (n;k;d;i) constant weightbinary code with code size k>A(n;d;i), a contradiction.To show that wj has weight i for all j2[k], take arbitrary j2[k]. Wehave:wt(wj) = wt(vj +u)= d(vj;u)= i:Thus D is constant weight with weight i. Finally, for j1;j22[k];j16= j2:d(wj1;wj2) = d(vj1 +u;vj2 +u)= d(vj1;vj1) by Lemma 1.9 d:Corollary 1.49. Let C be an (n;M;d) binary code, and let (Ai)ni=0 be thedistance distribution of C. Then Ai A(n;d;i) for all i2f0;1;:::;ng.Proof. For any i2f0;1;:::;ng we have:Ai = 1MXu2CWi(u) 1MXu2CA(n;d;i) by Theorem 1.48= 1M(M)A(n;d;i)= A(n;d;i):We will now introduce two useful upper bounds on A(n;d), the sphere-packing bound and Delsarte’s linear programming bound.17Chapter 1. Coding Theory1.3.1 The Sphere-Packing BoundThe sphere-packing bound is a well-known bound on optimal code size, andcan be useful when d is small. While the bound can be calculated for codesover any eld, we will o er the binary simpli cation. This bound will thengive rise to the notion of perfect codes. The proof of the sphere-packingbound used follows that in [20, Theorem 4.3].Theorem 1.50 (Sphere-Packing Bound). For any n;d2 Z+ with d n,let t = d 12 . Then:A(n;d) 66642n tXi=0 ni ! 17775:Proof. Let C be any (n;M;d) binary code, with optimal code size M =A(n;d). Proposition 1.30 implies that the spheres St(u) are distinct for allu2C. Thus we have the following:2n Xu2CjSt(u)j=Xu2Cjfv2f0;1gn jd(u;v) tgj=Xu2CtXi=0 ni ;since for a xed i, there are ni ways to choose i of the n coordinates of uto be di erent. Thus we have:2n A(n;d)tXi=0 ni :Since A(n;d) must be an integer, we arrive at the desired result.De nition 1.51. An (n;M;d) binary code C is called perfect if it attainsthe sphere-packing bound.One well-known class of codes are the class of (binary) Hamming codes,as de ned in [13, p.25]. The Hamming code is de ned for any n 2 Z+satisfying n 2, and is a (2n 1;22n n 1;3) binary code. Note that asthe Hamming code is a linear code (not de ned in this thesis), its second18Chapter 1. Coding Theoryparameter is usually expressed in terms of code dimension, rather than codesize. The dimension of a linear code of size M over a eld F is de ned tobe logjFj(M). The Hamming code attains the sphere-packing bound, andtherefore gives rise to the following result.Theorem 1.52. A(2n 1;3) = 22n n 1 for any n2Z+.Proof. First, note that A(21 1;3) = A(1;3) = 1 = 221 1 1 is triviallysatis ed. We now x n 2 Z+ with n 2. The sphere-packing bound(Theorem 1.50) implies:A(2n 1;3) 666422n 1 1Xi=0 2n 1i ! 17775= 22n 11 + 2n 1= 22n n 1:However, the existence of the Hamming code implies that A(2n 1;3) =22n n 1.1.3.2 Delsarte’s Linear Programming BoundAnother useful upper bound on A(n;d) is Delsarte’s linear programmingbound, developed by Delsarte in [8] and [7]. Recall that, for any (n;M;d)binary code with distance distribution (Ai)ni=0:nXi=dAi = M 1:These Ai will thus be treated as variables in Delsarte’s linear program.The result of Theorem 1.55 will produce the constraints of this linear pro-gram. We closely follow the notation used in [5].De nition 1.53. The Krawtchouk polynomial Kk(i), for i;k2f0;1;:::;ng,is de ned to be:Kk(i) =kXj=0( 1)j n ik j ij :The Krawtchouk polynomial can be rewritten as we will see in Theorem1.54. The proof given is similar to that used in [14, Lemma 3.5.5].19Chapter 1. Coding TheoryTheorem 1.54. For any w2f0;1gn satisfying wt(w) = i, the Krawtchoukpolynomial, for k2f0;1;:::;ng, satis es:Kk(i) =Xx2f0;1gnwt(x)=k( 1)<w;x>:Proof. Take arbitrary w2f0;1gn with wt(w) = i. De ne K f0;1gn tobe:K =fx2f0;1gn jwt(x) = kg:Next, de ne Kj K for j2f0;1;:::;maxfi;kgg to be:Kj =fx2Kjwt(w\x) = jg:It is clear that the Kj form a partition of K. This implies:Xx2f0;1gnwt(x)=k( 1)<w;x> =Xx2f0;1gnwt(x)=k( 1)wt(w\x)=jK0j jK1j+jK2j ::: jKmaxfi;kg 1j jKmaxfi;kgj=maxfi;kgXj=0( 1)jjKjj: (1.1)For any j2f0;1;:::;maxfi;kgg, we determinejKjj. Fix j and considerx2Kj. Of the i coordinates where w is 1, we have j choices of coordinateswhere we can let x be 1. Then, of the n i coordinates where w is 0, wehave n j choices of coordinates where we can let x be 1. From equation(1.1):Xx2f0;1gnwt(x)=k( 1)<w;x> =maxfi;kgXj=0( 1)jjKjj=maxfi;kgXj=0( 1)j ij n ik j =kXj=0( 1)j ij n ik j = Kk(i):20Chapter 1. Coding TheoryThe constraints of Delsarte’s linear program are proven to hold with aproof similar to that used in [5, Theorem 3], but rearranged and expressedin the same manner as in [2].Theorem 1.55. Let C be an (n;M;d) binary code with distance distribution(Ai)ni=0. Then, for k2f0;1;:::;ng:nXi=dAiKk(i) nk :Proof. For arbitrary w2f0;1gn satisfying wt(w) = i, we have:nXi=dAiKk(i) =nXi=0AiKk(i) A0Kk(0)=nXi=00BB@1MXu;v2Cd(u;v)=i11CCA0BB@Xx2f0;1gnwt(x)=k( 1)<w;x>1CCA (1)0BB@Xx2f0;1gnwt(x)=k( 1)<~0;x>1CCA:Moreover, since wt(u+v) = d(u;v) = i:nXi=dAiKk(i) = 1MnXi=0Xu;v2Cd(u;v)=iXx2f0;1gnwt(x)=k( 1)<u+v;x> Xx2f0;1gnwt(x)=k( 1)0= 1MXx2f0;1gnwt(x)=knXi=0Xu;v2Cd(u;v)=i( 1)<u;x>( 1)<v;x> nk = 1MXx2f0;1gnwt(x)=kXu;v2C( 1)<u;x>( 1)<v;x> nk 21Chapter 1. Coding Theory= 1MXx2f0;1gnwt(x)=k Xu2C( 1)<u;x>! Xv2C( 1)<v;x>! nk = 1MXx2f0;1gnwt(x)=k Xu2C( 1)<u;x>!2 nk (1.2) nk :In the case where M is odd, these constraints can be strengthened. Thiswill be seen in the following corollary, a result rst shown in [5, Theorem 5].Corollary 1.56. Let C be an (n;M;d) code with M odd. Then, for k 2f0;1;:::;ng:nXi=dAiKk(i) 1 MM nk :Proof. Recall from equation (1.2) in the proof of Theorem 1.55:nXi=dAiKk(i) 1MXx2f0;1gnwt(x)=k Xu2C( 1)<u;x>!2 nk :If M is odd,Xu2C( 1)<u;x> is odd and thus nonzero. Hence we reach thefollowing conclusion:nXi=dAiKk(i) 1MXx2f0;1gnwt(x)=k1 nk = 1M nk nk = 1 MM nk :Delsarte’s linear programming bound (Version 1) ofA(n;d) is then statedin Theorem 1.57.22Chapter 1. Coding TheoryTheorem 1.57. [Delsarte’s Linear Programming Bound (Version 1)]A(n;d) 1+bM c, where M is the optimal objective value of the followinglinear program:Maximize M =nXi=dAi subject to:nXi=dAiKk(i) nk for k2n0;1;:::;jn2ko;Ai 0 for i2fd;d+ 1;:::;ng:However, this linear program can indeed be further simpli ed. The fol-lowing theorem will show how all odd-indexed variables of the linear programcan be eliminated.Theorem 1.58. Let d 2 Z+ be even. Any (n;M;d) binary code can betransformed into an (n;M;d) even weight binary code.Proof. Let C be an (n;M;d) binary code, and take any i 2 [n]. Sinced is even, we have d 2. Thus we consider the (n 1;M;d 1) codeC(i). We now (as in the rst half of the proof of Theorem 1.44) create the(n;M;d) even weight code C(i) p that results from concatenating pw withevery codeword w of C(i). Since d 1 is odd, C(i) p is an (n;M;d) evenweight binary code.We now have, by Theorem 1.44, that the search for the values of A(n;d)can be restricted to even d. Moreover, Theorem 1.58 implies that the searchwith even d can be restricted to codes in which Ai = 0 for odd i. Therefore,the rst version of Delsarte’s linear programming bound given in Theorem1.57 can be restricted as in Theorem 1.59.Theorem 1.59. [Delsarte’s Linear Programming Bound (Version 2)] Letd 2 Z+ be even. A(n;d) 1 +bM c, where M is the optimal objectivevalue of the following linear program:23Chapter 1. Coding TheoryMaximizebn=2cXi=d=2A2i subject to:bn=2cXi=d=2A2iKk(2i) nk for k2n0;1;:::;jn2ko;A2i 0 for i2 d2;d2 + 1;:::;jn2k :Additional bounds can also be imposed, which can help lower the bound.For example, if A(n;d;w) is known for some (or all) w, the result of Corollary1.49 can be imposed as a constraint (or constraints). This will be seen inTheorem 1.60 in the following section.1.4 Applications of Delsarte’s LinearProgramming BoundDelsarte’s linear programming bound has been crucial in determining manynew bounds for A(n;d). One result that will be used often throughout thisthesis is the result A(9;4) = 20 (and hence by Theorem 1.44 A(8;3) =20). This result was rst proved in [5, Theorem 6], and our proof will beanalogous.Theorem 1.60. A(9;4) = 20.Proof. To prove that A(9;4) 20, we will exhibit a (9;20;4) binary code.Let C be the code where each codeword is a column of the following matrix:0BBBBBBBBBBBB@0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 10 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 1 1 1 10 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 10 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 0 1 11 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 11 1 1 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 01 0 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 1 1 01 0 0 1 1 0 0 1 1 0 0 0 1 0 1 1 0 1 0 10 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 01CCCCCCCCCCCCA:The vectors in C can also be represented by their integer representations as24Chapter 1. Coding Theoryfollows:C =f30;57;77;83;102;149;160;175;202;252;257;300;311;340;363;390;408;479;485;498g:It is easily veri ed that C is a (9;20;4) binary code.We will now apply Version 2 of Delsarte’s linear programming boundgiven in Theorem 1.59. We will also be using the result of Proposition 1.46(with Corollary 1.48) to impose the additional constraint A8 1. We seethat:A(9;4) 1 +bmaxfM gc;where M is the optimal objective value of the following linear program:Maximize A4 +A6 +A8 subject to:A4 +A6 +A8 1;A4 3A6 7A8 9; 4A4 + 20A8 36; 4A4 + 8A6 28A8 84;6A4 6A6 + 14A8 126;A8 1;A4;A6;A8 0:Upon nding the optimal objective value of this linear program, we obtain:A(9;4) 1 + 613 = 21:We now claim that a (9;21;4) binary code can’t exist. Assume, by wayof contradiction, that C is a (9;21;4) binary code with distance distribution(Ai)9i=0. Since 21 is odd, the result of Corollary 1.56 allows us to transformour rst ve constraints to:A4Kk(4) +A6Kk(6) +A8Kk(8) 1 2121 9k , 2120A4 Kk(4) + 2120A6 Kk(6) + 2120A8 Kk(8) 9k :25Chapter 1. Coding TheoryAlso, by de nition ofAi, we can also similarly transform our sixth constraint.SinceXu;v2Cd(u;v)=81 must be even (due to the symmetry of every pair of codewordsu and v), we have:A8 1,A8 2021, 2120A8 1:Thus, the optimal solution of the new linear program is simply 2021 times theoriginal optimal solution. Therefore:A(9;4) 1 + 2021 613 = 20:The optimal (9;20;4) code is not unique, as 2 nonequivalent (9;20;4)codes were exhibited in [13, p.57]. In fact, there exist exactly 3, as seen in[18, Table I].Recall the result of Theorem 1.52, A(n;d) = A(2n 1;3) = 22n n 1 forn2 Z+. This result can be generalized as in Theorem 1.61. This will bestated without proof, but is the main result proved by Best and Brouwerin [4]. The 0, 1, 2, and 3 times shortened Hamming codes are the optimalcodes that attain this value, and it was proven to hold as an upper boundthrough the use of Delsarte’s linear programming bound.Theorem 1.61. Let i;n2Z+ satisfy n 3 and i2[4]. Then:A(2n i;3) = 22n n i:The result of Theorem 1.61 allows for the values of A(n;3) to be calcu-lated for 28 n 31, which are included in Appendix A.26Chapter 2Graph TheoryIn this chapter we will review parts of graph theory needed throughout thisthesis. The de nitions and notation closely follow those used in [22]. We willalso introduce the concept of vertex coloring, and introduce three algorithmsthat solve various vertex coloring problems.2.1 Elementary ConceptsDe nition 2.1. A graph G is de ned by a vertex set and an edge set, whereelements of the edge set are unordered pairs of vertices.Notation 2.2. For any graph G, V(G) denotes the vertex set of G, andn(G) =jV(G)j, the number of vertices of G. In addition E(G) denotes theedge set of G, and e(G) =jE(G)j, the number of edges of G.De nition 2.3. The null graph is the graph whose vertex set and edge setare both empty.De nition 2.4. Let u;v2V(G) and e =fu;vg2E(G). Then u and v arethe endpoints of e, and u and v are incident to e. Equivalently, u and v areadjacent to each other. For notational convenience, we will commonly writean edge fu;vg as uv.De nition 2.5. In a graph G, a loop is an edge e 2 E(G) where bothendpoints of e are the same vertex v 2 V(G). Multiple edges are edgese1;e2 2E(G) satisfying e1 = e2. If G has no loops or multiple edges, thenG is a simple graph.De nition 2.6. A nite graph is a graph with both its vertex set and edgeset nite.For the remainder of this paper, we will assume all graphs are nite,simple graphs.27Chapter 2. Graph TheoryDe nition 2.7. Consider a graph G, and let v2V(G). The neighbourhoodof v, denoted NG(v), is the set of all vertices adjacent to V. That is:NG(v) =fu2V(G) juv2E(G)g:The degree of vertex v, denoted dG(v), is de ned to be jNG(v)j. This is thenumber of edges in E(G) that are incident to v. If, for some k2Z+[f0g,dG(v) = k for every v2V(G), then G is k-regular.The following proposition allows for the number of edges of a k-regulargraph to be calculated directly.Proposition 2.8. Let G be an n-vertex, k-regular graph. Then:e(G) = nk2 :Proof. Since summing the degrees of all vertices of a graph counts eachedge twice, the following result is clear (and commonly referred to as thedegree-sum formula):2e(G) =Xv2V(G)dG(v):However, since G is k-regular, we have the following:2e(G) =Xv2V(G)k= nk:De nition 2.9. A graph G0 is a subgraph of a graph G (denoted G0 G)if and only if:V(G0) V(G);E(G0) E(G):De nition 2.10. Let G be a graph and let V0 V(G) be a subset of thevertices of G. The subgraph of G induced by V0, denoted G[V0], is the graphsatisfying the following:V(G[V0]) = V0;E(G[V0]) =fuv2E(G) ju;v2V0g:28Chapter 2. Graph TheoryDe nition 2.11. The complement of a graph G, denoted G, is the graphthat satis es the following criteria:V(G) = V(G);E(G) =fuvju;v2V(G);uv =2E(G)g:De nition 2.12. A clique in a graph G is a set of vertices V0 V(G) suchthat any two distinct vertices in V0 are adjacent in G. The clique number ofG, denoted !(G), is the number of vertices in a clique of largest cardinalityof G.De nition 2.13. An independent set in a graph G is a set of verticesV0 V(G) such that any two distinct vertices in V0 are non-adjacent inG. V0 is a maximal independent set if V0[fvg is not independent for anyv2V(G)nV0. The independence number of G, denoted (G), is the numberof vertices in an independent set of largest cardinality G.De nition 2.14. A graph G is bipartite if and only if the vertex set of Gcan be expressed as V(G) = V1[V2, where both V1 and V2 are independent.De nition 2.15. The n-vertex complete graph, denoted Kn, is the graphsuch that any two distinct vertices in V(Kn) are adjacent.Since every pair of distinct vertices in the complete graph are adjacent,!(Kn) = n for all n2Z+.De nition 2.16. Let G be a graph. A walk in G is an alternating sequenceof vertices and edges W = (v0;e1;v1;e2;v2;:::;en;vn) such that ei = vi 1vifor all i2[n]. The length of W is n, the number of edges in W. W is denoteda v0;vn-walk in G, and the vertices v0 and vn are called the endpoints of W.The vertices vi, for i2[n 1], are called the internal vertices of W.De nition 2.17. A path in a graph G is a walk in G such that every edgeand every vertex in the walk are distinct. A cycle in G is a path whoseendpoints are the same vertex.De nition 2.18. Let u;v 2 V(G) be two vertices in a graph G. Thedistance from u to v in G, denoted dG(u;v), is the length of the shortestu;v-path in G (the path of least length). If there exists no u;v-path in G,then dG(u;v) =1.Let u;v;w 2V(G) for some graph G. Similarly to the Hamming dis-tance, the graph theoretical distance satis es the following properties:29Chapter 2. Graph Theory dG(u;v) = 0 if and only if u = v, dG(u;v) = dG(v;u), dG(u;w) dG(u;v) +dG(v;w) (the triangle inequality).De nition 2.19. Thekth power ofGis de ned for any graphGandk2Z+.Denoted Gk, it is the graph that satis es:V(Gk) = V(G);E(Gk) =fuvju;v2V(G);dG(u;v) kg:2.2 Graph Isomorphisms and AutomorphismsDe nition 2.20. An isomorphism from a graph G to a graph H is a bijec-tion : V(G)!V(H) that satis es:uv2E(G), (u) (v)2E(H):If there exists an isomorphism from G to H, then G is isomorphic to H.This is denoted G = H.If there is an isomorphism from G to H, then the function 1 is anisomorphism from H to G. In addition, = is both re exive (through theidentity function) and transitive (through functional composition). There-fore, = is an equivalence relation on the set of all graphs. It is clear that, inorder for G = H, both of the following must hold:n(G) = n(H);e(G) = e(H):De nition 2.21. For any graphs G and H, a copy of H in G is a subgraphG0 G such that H = G0.De nition 2.22. An automorphism of a graph G is an isomorphism fromG onto itself. The automorphism group of a graph G is the set of all auto-morphisms of G, with functional composition as the group operation. It isdenoted Aut(G).Clearly, any permutation of the vertices in the complete graph Kn is anautomorphism. Therefore jAut(Kn)j=jSnj= n!.30Chapter 2. Graph TheoryDe nition 2.23. A graph G is vertex transitive if, for all u;v2V(G), thereexists an automorphism : V(G)!V(G) such that (u) = v.The notion of vertex transitivity will be very important later in thisthesis. If a graph is vertex transitive, then it \looks the same" from everyvertex. What this means is that many times we can prove a result for everyvertex in the graph by simply proving the result for a single, arbitrary vertex.De nition 2.24. Let V0 V(G) be a set of vertices of a graph G, and : V(G)!V(G) be a function of the vertices of G. Then the image of V0under , denoted (V0), is de ned to be: (V0) =f (v) jv2V0g:We will now prove several results about automorphisms that will beneeded later in this thesis.Proposition 2.25. Let V0 V(G) be a set of vertices of a graph G, and : V(G)!V(G) be an automorphism of G. Then V0 is independent if andonly if (V0) is independent. Similarly, V0 is a clique if and only if (V0)is a clique.Proof. Take any u;v2V0. We have the following:V0 is independent,uv =2E(G), (u) (v) =2E(G) since is an automorphism, (V0) is independent.The result, as applied to a clique rather than an independent set, is provenin an analogous manner.Theorem 2.26. For any graph G, Aut(G) = Aut(G).Proof. We will show that : V(G) ! V(G) is an automorphism of Gif and only if is an automorphism of G. We rst assume that is anautomorphism of G. We now take arbitrary uv2E(G). We have:uv2E(G),uv =2E(G), (u) (v) =2E(G), (u) (v)2E(G);and thus is an automorphism of G.31Chapter 2. Graph TheoryWe now assume that is an automorphism of G, and take arbitraryuv2E(G). We have:uv2E(G),uv =2E(G), (u) (v) =2E(G), (u) (v)2E(G):Therefore is an automorphism of G.Theorem 2.27. Let : V(G1)!V(G2) be an isomorphism between graphsG1 and G2. Then, for all u;v2V(G1), dG1(u;v) = dG2( (u); (v)).Proof. This theorem will be proven by induction on dG1(u;v). Base Case:For all u;v 2 V(G1) such that dG1(u;v) = 1, we prove thatdG2( (u); (v)) = 1.Take arbitrary u;v 2 V(G1) such that dG1(u;v) = 1. Thus uv 2E(G1), and this case is trivial by the de nition of an isomorphism. Inductive Hypothesis:Assume, for some k2Z+, that if u;v2V(G1) satisfy dG1(u;v) k, then dG2( (u); (v)) = dG1(u;v).We now prove the result for k + 1. Take arbitrary u;v 2V(G1) suchthat dG1(u;v) = k + 1 (if dG1(u;v) < k + 1, then the statement is true bythe inductive hypothesis).First, to show that dG2( (u); (v)) k + 1, we will show the existenceof a (u); (v)-path in G2 of length at most k + 1. Let P be a shortestu;v-path in G1 having length k + 1, and let w be the vertex on P adjacentto v. We have that dG1(u;w) = k; otherwise there would be a shorter u;v-path. By the inductive hypothesis, dG2( (u); (w)) = k. Also, since isan isomorphism, (w) (v)2E(G2). Therefore, there is a (u); (v)-pathof length at most k + 1, and thus dG2( (u); (v)) k + 1.Next, to show that dG2( (u); (v)) k + 1, we will show that thereexists no (u); (v)-path in G2 of length less than k + 1. Assume, byway of contradiction, that there exists some (u); (v) path P of lengthat most k. Let w be the vertex on P adjacent to (v). Thus we havedG2( (u);w) k 1, and therefore:32Chapter 2. Graph TheorydG1(u;v) dG1(u; 1(w)) +dG1( 1(w);v) by the triangle inequality= dG2( (u);w) +dG2(w; (v)) by the inductive hypothesis (k 1) + 1= k;a contradiction to dG1(u;v) = k+1. Therefore dG2( (u); (v)) = k+1, andthe induction proof is complete.Note that the previous result also holds when G1 = G2 and is anautomorphism of this graph. This speci c case of Theorem 2.27 leads to thefollowing corollary.Corollary 2.28. Let : V(G)!V(G) be an automorphism of a graph G.Then, for any v2V(G), (NG(v)) = NG( (v)).Proof. Recall that:NG(v) =fu2V(G) jdG(u;v) = 1g;and therefore the result is immediate from Theorem 2.27.Theorem 2.29. For any graph G, Aut(G) Aut(Gk) for all k2Z+.Proof. Let : V(G)!V(G) be an automorphism of a graph G. Considerthe graph Gk for arbitrary k2Z+, and take arbitrary u;v2V(Gk). Thefollowing then holds:uv2E(Gk),dG(u;v) k,dG( (u); (v)) k by Theorem 2.27, (u) (v)2E(Gk);and thus is an automorphism of Gk.2.3 Vertex ColoringThe eld of graph coloring is one that is very interesting and heavily studiedin discrete mathematics, and it contains many unsolved problems. In addi-tion, many applications, such as timetabling, scheduling, register allocation,and frequency assignment problems, can be formulated as graph coloring33Chapter 2. Graph Theoryproblems. Vertex coloring problems are the most common type of graphcoloring problems. For de nitions of other graph coloring problems, suchas edge and total colorings, we refer the reader to [22]. For the remainderof this thesis, it will be assumed that graph coloring refers speci cally tovertex coloring.A coloring of a graph can be thought of as assigning a color to eachvertex of the graph so that no two adjacent vertices are given the samecolor. Formally, this can be represented as in the following de nition.De nition 2.30. A k-coloring of a graph G, for any k2Z+, is a functionf : V(G)![k] such that:uv2E(G))f(u)6= f(v):G is k-colorable if and only if a k-coloring of G exists.De nition 2.31. Let G be a graph with k-coloring f. The ith color classof G (with respect to f) is the set of vertices fv 2 V(G) j f(v) = ig fori2[k].It is clear that any color class of a coloring of G is an independent set ofvertices.Proposition 2.32. A graph G is 2-colorable if and only if it is bipartite.Proof. Assume G is 2-colorable, and let V1 and V2 be the color classes of a2-coloring of G. Then V(G) = V1[V2, the union of two independent sets ofvertices. Thus G is bipartite.Next, assume G is bipartite with V(G) = V1[V2, with V1 and V2 inde-pendent sets of vertices. Next, de ne f : V(G)![2] as follows:f(v) =(1 if v2V1;2 if v2V2:Clearly the function f is a 2-coloring of G.Let G be an n-vertex graph. Since a set consisting of a single vertex istrivially independent, it is clear that G has an n-coloring, the coloring whereevery vertex of G forms a distinct color class. However, in general, we can nd k-colorings of G with k<n.34Chapter 2. Graph TheoryDe nition 2.33. The chromatic number of a graph G, denoted (G), isthe least integer k such that G is k-colorable.Theorem 2.34. Let G be an n-vertex graph. Then (G) n (G) .Proof. Let f : V(G) ! [k] be an optimal coloring of G, that is, k = (G).We have:n =kXi=1jfv2V(G)jf(v) = igj kXi=1 (G)= k (G):Rearranging, and applying the fact that k2Z+:k n (G) :The chromatic number of a graph can be bounded below by its cliquenumber, as we will see in Theorem 2.35.Theorem 2.35. For any graph G, (G) !(G).Proof. Let V V(G) be an optimal clique of V(G), that is jVj = !(G).Then, since every pair of vertices in V are adjacent, every vertex v2V(G)must be in a distinct color class of any coloring of G. Thus (G) !(G).Corollary 2.36. For any n2Z+, (Kn) = n.Proof. Since !(Kn) = n, by the result of Theorem 2.35, (Kn) n. How-ever, asn(Kn) = n, Kn is clearlyn-colorable. Hence we have (Kn) = n.2.4 Algorithms to Solve Vertex ColoringProblemsSuppose we wish to determine the chromatic number of a graph, the smallestinteger k such that G is k-colorable. This, and a variety of other problems inthe eld of graph theory, are often solved algorithmically. Much e ort is putinto the study and development of these algorithms. The desired result is,of course, to determine the solution in as computationally e cient manneras possible.35Chapter 2. Graph Theory2.4.1 An Introduction to Algorithms and E ciencyDe nition 2.37. The running time of an algorithm, expressed as a functionof the size of the input, is the maximum possible number of basic computa-tional steps used in the execution of the algorithm.When dealing with graph theoretic problems, the size of the input refersto the number of vertices in the graph. The running time of an algorithmis commonly measured as follows.De nition 2.38. Suppose the running time of an algorithm with input sizen is bounded by the expression g(n). Let f(n) be an expression such that,for any N2Z+, there exists c2Z+ such that g(n) cf(n) for all n>N.Then the running time of this algorithm is O(f(n)).It is widely considered that an algorithm is computationally e cient ifit has a polynomial running time. There are methods to determine if agraph is 2-colorable that are computationally e cient. It is known thata graph is 2-colorable if and only if it contains no odd cycles (for a proofof this statement we refer the reader to [22, Theorem 1.2.18]). Becauseof this nice characterization of 2-colorability, determining if any n-vertexgraph G is 2-colorable is solvable in polynomial time. One algorithm thataccomplishes this is the DSatur Algorithm [6, p.252], whose running time isO(n2). However, for k 3, whether or not the problem of determining if agraph is k-colorable can be solved e ciently is unknown.De nition 2.39. A P (polynomial) problem is a problem that is solvablein polynomial time, that is, there exists an e cient algorithm to solve it.An NP (non-deterministic polynomial) problem is a problem such that apotential solution can be veri ed in polynomial time. An NP-hard problemis a problem that, if solvable by a polynomial time algorithm, then thisalgorithm could be used to construct a polynomial time algorithm for allNP problems. An NP-complete problem is a problem that is both NP andNP-hard.The class of NP-hard problems can informally be thought of as the classof problems at least as hard as the hardest problems in NP, and possiblyharder. The class of NP-hard problems also include not only decision prob-lems, but those problems that are posed as optimization problems. Clearly,all P problems are also NP problems, as a P problem can verify a solutionin polynomial time. It is currently unknown if that converse is true, that is,if any of the many NP-complete problems can be solved in polynomial time.36Chapter 2. Graph TheoryHowever, if there exists a polynomial time algorithm for one then thereexists a polynomial time algorithm for all NP problems, and hence the classof NP problems is equal to the class of all P problems. This P=NP questionhas become one of the most famous problems in applied mathematics andcomputer science. The Clay Mathematics Institute, a nonpro t educationfoundation in Cambridge, Mass., is currently o ering a million dollar prizefor a solution to this problem.1 A Venn diagram for the P, NP, NP-complete,and NP-hard set of problems is included in Figure 2.12.Figure 2.1: Venn Diagram of the Complexity ClassesDetermining if an n-vertex graph G is k-colorable, for k 3, is an NP-complete problem[9, p.191]. A solution to the problem can be veri ed inpolynomial time. Given a function f : V(G) ! [k], to determine if thissatis es the de nition of a vertex coloring, one merely needs to check everyedge of the graph and make sure its endpoints are not in the same colorclass. Since a simple, nite graph has at most n2 < n2 edges, this can bedone e ciently. However, the decision problem of nding a k-coloring in agraph is NP-complete. Hence it is not known, for a xed k 3, if thereexists a polynomial time algorithm to determine whether or not a graph hasa k-coloring. Currently, the only general algorithm to prove that a graph isnot k-colorable, for k 3, is equivalent to an exhaustive search. In fact, onemay have to test every function from V(G) to [k], of which there are kn, toprove the existence or non-existence of a k-coloring.1http://www.claymath.org/millennium/2Source: http://en.wikipedia.org/wiki/Np-hard/37Chapter 2. Graph Theory2.4.2 Integer ProgrammingInteger programming is also an NP-complete problem. Therefore, as dis-cussed in the previous section, it is computationally equivalent to graphcoloring with respect to e ciency. Modeling a graph coloring problem as aninteger program (IP), however, can provide some practical computationalimprovements over an exhaustive search for a given graph. We explore thismodel here.Let G be a n-vertex graph (for simplicity, let V(G) = [n]). The rst,and most simple, algorithm to determine if G is k-colorable is a basic integerprogramming model. The variables of the IP are xi;j where i 2 [n] andj2[k]. We let xi;j be a binary variable that equals 1 if vertex i is assignedcolor j and 0 otherwise. The problem is then equivalent to determining ifthe following system (which we will refer to as VC) has a feasible solution.xi1;j +xi2;j 1 for all i1i22E(G) and j2[k];kXj=1xi;j 1 for all i2[n];xi;j2f0;1g for all i2[n] and j2[k]:The rst constraint forces that no two adjacent vertices can be assignedthe same color. The second constraint forces each vertex to be assignedto at least one color (if it is assigned two colors then it can be assignedeither color arbitrarily). Trivially, (G) is the smallest value of k such thatthis integer program has a feasible solution. The model is simple to design;however, it can be very computationally ine cient in execution. Graphcoloring problems are a very speci c kind of integer program, and this basicmodel has inherent symmetry associated with it. For example, suppose V1and V2 are color classes in a coloring of G. Assigning V1 color j1 and V2color j2, according to the VC model, is a completely di erent solution thanassigning V1 color j2 and V2 color j1. It becomes apparent that a basicinteger program can waste much computational time searching for \new"solutions that are actually the same, or search branches of the search treewhere prior knowledge should imply that these branches contain no feasiblesolution. The following algorithm attempts to rectify this problem.38Chapter 2. Graph Theory2.4.3 Column GenerationIn this section, we will introduce a model that avoids some of the symmetryinherent in graph coloring problems. This model is introduced in [15], andwe will adopt the same notation. Consider a graph G and let S be the setof all maximal independent sets of G. Now de ne xs to be a binary variablefor all s2S that equals 1 if that set is used as a color class in an optimalcoloring of G, and 0 otherwise. Now, since all of these sets are by de nitionindependent, so long as every vertex is in some set s that is assigned a color,we have a coloring of G. Note that a vertex can appear in more than oneset s that is assigned a label, as we are able to break the tie of which label itgets arbitrarily. The problem, denoted IS, that determines (G) is outlinedbelow.MinimizeXs2Sxs subject to:Xs2Sji2sxs 1 for all i2V(G);xs2f0;1g for all i2V(G):Minimizing this objective function minimizes the number of colors used.The rst constraint forces each vertex to be in at least one color class of theoptimal coloring found, and the second constraint forces the xs to be binary.Note that this model treats a coloring as a collection of maximal indepen-dent sets with no speci c color assigned to each set. Therefore, it loses thesymmetry problem discussed in the integer programming approach. How-ever, the number of variables (one for every maximal independent set) isexponential in general and expensive to determine. Thus, we will look at acolumn generation method that reduces the number of variables immenselyat the start, and generates new ones as needed. In this method, S is ex-tended to be all independent sets (rather than only maximal independentsets).First, we must come up with a collection of sets that produces a col-oring. Many times there is a coloring previously found that we are tryingto improve on, so its color classes could be a good starting point. Or, thesimple approach is to let the initial S be all the singleton sets of vertices,which trivially results in an n-coloring of an n-vertex graph.39Chapter 2. Graph TheoryWe then solve a linear relaxation of IS with the restriction that S isour predetermined collection of independent sets. Solving this relaxationgenerated a dual value, i, for each constraint (each of which represents avertex of G). We then use these dual values as input for the following integerprogram, denoted MWIS, below.MaximizeXi2V(G) izi subject to:zi1 +zi2 1 for all i1i22E(G);zi2f0;1g for all i2V(G):The optimal zi values correspond to a new independent set of vertices(the vertex i is in this set if and only if zi = 1). The rst constraint forcesthat no two adjacent vertices can be included in this set, and the secondforces the zi to be binary. The algorithm solves the IS relaxation with thepredetermined set of independent sets S, and uses the dual values of thislinear program as input for MWIS. Solving MWIS generates an independentset, which is added to S. IS is then solved with the new set S, and its dualvalues are again used as input for MWIS.The algorithm terminates when the optimal objective function value ofMWIS is less than or equal to 1. Linear programming duality, discussed inthe next paragraph, tells us that no new independent set will improve thecoloring of the graph.To understand why this algorithm works, suppose the Simplex Algorithmon the relaxation of IS was applied with all independent sets included in S.An independent set (a variable) would enter the basis (thus improving oursolution) if and only if it has a negative reduced cost. The reduced cost of avariable s is given by 1 As, where is the row vector of dual values fromthe previous Simplex iteration and As is the column of the constraint matrixA corresponding to possible entering set s. The entries of the columns of Asare 1 if that vertex is in the set and 0 otherwise. This, however, is exactlywhat the zi from MWIS represent. Thus we have:1 Xi2v izi < 0;or equivalently;Xi2v izi > 1:40Chapter 2. Graph TheoryUpon termination of the algorithm, we then look at the nal IS relax-ation solved. If it has an integral solution, we are done the original problemand (G) is determined. Otherwise, integrality must be enforced.To enforce integrality, we treat the solved problem as the initial node on abranch and bound tree. We then examine our fractional solution achieved inthe algorithm, and consider an independent set s1 such that xs1 is fractional.There must exist another independent set s2 6= s1 such that s1\s2 6= ;;otherwise the vertices in s1 would have their only nonnegative variable be-ing xs1 < 1, an infeasible solution to the relaxed linear program. Considervertices i1;i22V(G) such that i12s1\s2 and i22s1ns2 or i22s2ns1. Wethen create two subproblems, denoted DIFFER(i1;i2) and SAME(i1;i2).DIFFER(i1;i2) requires that i1 and i2 are given di erent colors, whereasSAME(i1;i2) requires that i1 and i2 are given the same color. It is clearthat any feasible coloring (and thus, an optimal coloring) of G occurs in oneof these two cases. These subproblems can be thought of graph theoreti-cally: DIFFER(i1;i2) corresponds to adding the edge i1i2 to the graph,and SAME(i1;i2) corresponds to collapsing vertices i1 and i2 into a singlevertex j, with NG(j) = NG(i1)[NG(i2).The column generation algorithm is then solved in each subproblem, inthe hopes that an integral solution is found. If not, subproblems are againcreated and solved through column generation, and the branch and boundtree is explored until an optimal value is found. This optimal value is (G).This algorithm is in most cases superior to the straight integer program-ming approach discussed in Chapter 2.4.2 (see [15] for a comparison on atest bed of graphs). However, the algorithm can still be very computation-ally expensive. While it is a simpler integer program than the one outlinedin Chapter 2.4.2, the MWIS model is still an integer program which are inthe class of NP-Complete problems. Since MWIS may be repeated manytimes over the course of the algorithm, it is vital to be able to solve it inas e cient a manner as possible. Mehrotra and Trick discuss ways of doingthis in [15, pp.345{346].2.4.4 The Petford-Welsh AlgorithmPetford and Welsh introduced an algorithm in [19] that searches for a 3-coloring of a graph. The generalization of the algorithm to search for ak-coloring is trivial, and we o er this generalization. Consider an n-vertex41Chapter 2. Graph Theorygraph G. The algorithm rst assigns every vertex of G a random number(color) in [k] (note that this is simply a random assignment of k colors andnot likely to be a proper k-coloring). At any instant, for all vertices v andevery i in [k], we de ne Si(v) to be the subset of NG(v) that are coloredi. In addition, si(v) is de ned to be jSi(v)j. A transition function p is alsode ned that satis es, for s1;s2:::;sk2[n]:p(s1;s2;:::;sk;j) 0 for all j in [k];kXj=1p(s1;s2;:::;sk;j) = 1:Note that this satis es the de nition of a probability mass functionP(X = j) of a discrete random variable X that can take on values in [k].One example of such a transition function is:p(s1;s2;:::;sk;j) = 1k 10@1 sj kXi=1si! 11A:Every iteration, a vertex v is chosen at random out of all \bad" vertices,that is, all vertices adjacent to another vertex currently assigned the samecolor. Next, a (not necessarily new) color is randomly generated accordingto the probability mass function de ned by p(s1(v);s2(v);:::;sk(v);j), andthis color is assigned to the vertex v. The algorithm continues until there areno more bad vertices to choose from, in which case it has found a k-coloring,or the running time goes beyond a predetermined stopping time. If it doesnot nd a k-coloring in the allotted time, then the algorithm is inconclusive.Obviously, this algorithm can’t be used to prove that a graph is notk-colorable. However, for \good" choices of the transition function p, thisalgorithm was shown to nd 3-colorings on randomly generated 3-colorablegraphs in a relatively short length of time (see [19] for more details on thesegraphs and choices of transition functions). The preliminary results forlarger k were not very promising, and one possible reason that was givenwas that much more experimentation was needed to nd a good transitionfunction. However, this algorithm will be revisited in Chapter 3.3.3, in whichit is applied successfully to nd a 14-coloring of Q28, a graph that will bede ned next.42Chapter 3The HypercubeWe now discuss the main combinatorial object studied in this thesis.De nition 3.1. For any k 2 Z+, the k-dimensional hypercube (k-cube),denoted Qk, is the graph satisfying the following:V(Qk) =f0;1gk;E(Qk) =fuv2f0;1gk jd(u;v) = 1g:This is the graph in which the vertices are all binary vectors of length k,and two vertices are adjacent if and only if the Hamming distance betweenthem is 1. Often, we will be dealing with the jth power of the k-cube (whenj k), Qjk. This graph satis es:V(Qjk) =f0;1gk;E(Qjk) =fu;v2f0;1gk jd(u;v) jg:It is clear that n(Qjk) = 2k for any j;k2Z+. The result of the followingproposition will allow us to enumerate e(Qjk).Proposition 3.2. Let j;k2Z+ with j k. Then e(Qjk) = 2k 1t where tsatis es:t =jXi=1 ki :Proof. First, we note that Qjk is t-regular since, by de nition, t sums up allbinary vectors of distance at most j from any vertex. Thus Proposition 2.8implies:e(Qjk) = n(Qjk)t2= 2kt2= 2k 1t:43Chapter 3. The HypercubeNote that if j k then every vertex of Qjk is adjacent. Therefore Qjk =K2k, and hence:e(Qjk) = 2k2 = (2k)(2k 1)2 = 2k 1(2k 1):This agrees with the result of Proposition 3.2 as:2k 1jXi=1 ki = 2k 1kXi=1 ki = 2k 1(2k 1);by the binomial theorem.We will most often be discussing the case j = 2, the graph Q2k. In thiscase:t = k1 + k2 = k + 12 ;and hencee(Q2k) = 2k 1 k + 12 :The number of vertices and edges of Q2k have been calculated for allk 31 in Appendix A.We now note the following results, and our rst connections betweenChapter 1 and Chapters 2 3.Lemma 3.3. (Qjk) = A(k;j + 1) for any j;k2Z+ with j k.Proof. As two vertices of Qjk are adjacent if and only if their Hammingdistance is at most j, any independent set V of Qjk is a set of verticessatisfying d(u;v) j + 1 for all u;v 2 V. This is a binary code withminimum distance at least j + 1, which leads to the desired result.This leads to the following proposition.Proposition 3.4. Let :f0;1gk!f0;1gk be an automorphism of Qjk, andC be a (k;M;j + 1) binary code. (C) is then a (k;M;j + 1) binary code,where (C) is de ned as follows: (C) =f (u) ju2Cg:44Chapter 3. The HypercubeProof. Clearly, C is an independent set of Qjk. Moreover, by Proposition2.25, (C) is an independent set of Qjk. Therefore (C) is a (k;M;j + 1)binary code.3.1 Automorphisms of the Cube and its SquareIn this section, we will de ne the automorphism groups of Qk and Q2k. Theresult of Theorem 2.29 implies that Aut(Qk) Aut(Qjk) for all j 2 Z+.Therefore every automorphism of Qk is, in addition, an automorphism ofQjk. Consider the following function.De nition 3.5. Let x2f0;1gk. Then the vector addition function: x :f0;1gk!f0;1gk;is de ned to be: x(v) = v +x:This function is an automorphism of Qk, as will be seen in the Theorem3.6.Theorem 3.6. For any x2f0;1gk, x is an automorphism of the graphQk .Proof. Consider an arbitrary x2f0;1gk. To prove x is an automorphismof Qk, we rst prove that x is a permutation of f0;1gk.To prove x is a permutation, assume (for u;v2f0;1gk) that x(u) = x(v). We have: x(u) = x(v),u+x = v +x,u = v;and hence x is one-to-one. Since f0;1gk is nite, it is therefore onto andthus a permutation. Note that throughout this thesis, we will prove a func-tion from f0;1gk to f0;1gk is a permutation by simply proving it is one-to-one.45Chapter 3. The HypercubeTo prove x is an automorphism of Qk, take u;v 2f0;1gk such thatuv2E(Qk). We have:uv2E(Qk),d(u;v) = 1,d(u+x;v +x) = 1 (by Lemma 1.9),d( x(u); x(v)) = 1, x(u) x(v)2E(Qk);and therefore x preserves edges and is hence an automorphism.Corollary 3.7. Qjk is vertex transitive for any j;k2Z+.Proof. Consider arbitrary u;v2f0;1gk. By Theorem 3.6, the vector addi-tion function u+v is an automorphism of Qk. Theorem 2.29 then impliesthat u+v2Aut(Qjk) for all j2Z+. Moreover: u+v(u) = u+ (u+v)= v;and hence, u+v maps u to v. Since this holds for any choices of u;v 2f0;1gk, Qjk is vertex transitive.Permuting the coordinates of the vertices of Qk is also an automorphism,as we will prove in Theorem 3.8.Theorem 3.8. Permuting the vertex coordinates under the permutation ,for any 2Sk, is an automorphism of Qk.Proof. To prove is an automorphism of Qk, we rst prove that permutingthe coordinates under also permutes the vertices in f0;1gk. Assume, foru;v2f0;1gk, that (u) = (v). Since is a permutation, it by de nitionhas an inverse 1, satisfying 1( (u)) = u and 1( (v)) = v. Now since (u)i = (v)i for all coordinates i2[k], ui = vi for all coordinates i. There-fore is a permutation.To prove is an automorphism of Qk, consider u;v2f0;1gk such thatuv 2E(Qk). By de nition of Qk, d(u;v) = 1. Thus there is exactly onecoordinate i 2 [k] where ui 6= vi. Therefore (u) and (v) di er only incoordinate (i), and hence d( (u); (v)) = 1. Clearly (u) (v)2E(Qk).Now consider u;v2f0;1gk such that (u) (v) 2E(Qk). By de nitionof Qk, d( (u); (v)) = 1. Thus there is exactly one coordinate i2[k] where46Chapter 3. The Hypercube (u)i6= (v)i. Therefore u and v di er only in coordinate 1(i), and henced(u;v) = 1. Clearly uv2E(Qk).Lemma 3.9. Let x;y2f0;1gk and 1; 22Sk such that x6= y or 16= 2.Then: 1 x6= 2 y:Proof. Assume that 1 x = 2 y and, by way of contradiction, x6= yor 16= 2. Thus the following holds:( 1 x)(x) = ( 2 y)(x), 1(~0) = 2(x+y),~0 = 2(x+y),~0 = x+y,x = y;and therefore 1 6= 2, so it must be the case that x = y. Then there issome v2f0;1gk such that: 1(v)6= 2(v), 1( x(v +x))6= 2( y(v +y)), 1( x(v +x))6= 2( y(v +x)) since x = y) 1 x6= 2 y;a contradiction.Since jSkj= k! and jf0;1gkj= 2k, the result of Lemma 3.9 implies thatwe can create 2kk! distinct automorphisms of Qk through composing vectoraddition and coordinate permutation automorphisms. As we will see inTheorem 3.11, every automorphism of Qk is of this form. The proofs of thefollowing lemma and theorem are of a combinatorial nature similar to thatused in the solution manual to [22, Exercise 1.3.29]. An alternative proof ofthe result that has an algebraic avor can be found in [16].Lemma 3.10. Let j;k2Z+ with j k. Every copy of Qj in Qk is Qk[V]where V f0;1gk satis es:V =fv2f0;1gk jv has speci ed values in a xed set of k j coordinatesg:Proof. Let H be any subgraph of Qk such that H is a copy of Qj inQk. There then exists some isomorphism from Qj (de ned normally)to H. Since H is a subgraph of Qk, for every x1;x2 2V(H), dH(x1;x2) dQk(x1;x2). Let u = (~0j) and v = (~1j). We will prove by induction on jthat d(u;v) = j.47Chapter 3. The Hypercube Base Case(s):If j = 1, then H = Q1, which contains simply two vertices connectedby an edge. Thus dQk(u;v) = 1 and hence d(u;v) = 1. If j = 2, thenu and v have the common neighbour (01) in H since ~02 and ~12 havethe common neighbour 01 in Q2. Now if d(u;v) = 1 then uv2E(Qk),and since H Qk, uv (01)u would form a cycle of length 3 in thebipartite graph Qk, a contradiction. Thus d(u;v) = 2. Inductive Hypothesis:Suppose for some positive integer j > 2, if is an isomor-phism from Ql, for some l2[j 1], to a subgraph of Qk, thend( (~0l); (~1l)) = l.We now prove the result for j. Consider the isomorphism : Qj !H.For all i2 [j], let wi = ( ji). Now since ~0j ji 2E(Qj), uwi2E(H), andhence d(u;wi) = 1.Now let Wi = fx 2 V(Qj) j xi = 1g. Then Qj 1 = Qj[Wi] underthe isomorphism i that lengthens the vector by inserting a 1 in the ithcoordinate. Thus i i is an isomorphism from Qj 1 to a subgraph of Qkwhere i is the restriction of to Wi. By the induction hypothesis, fori2[j]:d( i i(~0j 1); i i(~1j 1)) = j 1:Moreover, i(~0j 1) = ji and i(~1j 1) =~1j. Therefore we have d(wi;v) =j 1 for i2[j]. Thus for each i2[j], wi is di erent from v in j 1 coordi-nates and is di erent from u in one coordinate.If for some i2[j], the j 1 coordinates in which wi is di erent from vdo not include the one coordinate in which wi is di erent from u, then u andv di er in all these j coordinates and hence d(u;v) = j. So, suppose to thecontrary that there are distinct i1;i22[j] such that wi1 and wi2 di er fromu only in coordinates j1 and j2, respectively, and additionally that uj1 = vj1and uj2 = vj2.Since wi1 di ers from v in j 1 coordinates and di ers from u in exactlyone of these coordinates, wi1 di ers from v in j 2 coordinates but is thesame as u in these same j 2 coordinates. Thus u and v di er in these j 248Chapter 3. The Hypercubecoordinates. Hence d(u;v) j 2.Consider now = ji1 + ji2 and its image z = ( ji1 + ji2). Since ji1 ; ji2 2E(Qj), wi1z;wi2z2E(H). Thus:d(wi1;z) = 1 = d(wi2;z):If d(u;z) = 1, then uwi1zu is a cycle of length 3 in the H. Since H Qkthis is also a cycle of length 3 in the bipartite graph Qk, a contradiction.Thus d(u;z) = 2.Suppose z di ers from u in coordinate j3 where j3 =2fj1;j2g. Then uand wi1, and u and wi2, all agree in coordinate j3. However:d(wi1;z) = 1 = d(wi2;z);and so wi1 = wi2, a contradiction. Therefore j32fj1;j2g.Since d(u;z) = 2, z therefore di ers from u only in coordinates j1 andj2. Since uj1 = vj1 and uj2 = vj2, z di ers from v in coordinates j1 and j2.Moreover, z di ers from v in all the coordinates in which v di ers from u,since in those coordinates z agrees with u. Thus:d(v;z) d(u;z) +d(u;v) 2 + (j 2)= j:With 2V(Qj), we have:j 2 = dQj(~1j; )= dH( (~1j); ( )) by Theorem 2.27= dH(v;z) dQk(v;z) since H Qk= d(v;z) j;a contradiction. Thus no such i1 and i2 exist, and d(u;v) = j. Hence byinduction, the statement holds for all j.49Chapter 3. The HypercubeNext, let S be the set of coordinates in which u and v are the same.By the preceding inductive proof, jSj = k j. Consider w2V(H). Since 1(w) is in Qj and for all y1;y22V(Qj), d(y1;y2) = dQj(y1;y2), we have:dQj(~0j; 1(w)) +dQj(~1j; 1(w)) = d(~0j; 1(w)) +d(~1j; 1(w))= j:By Theorem 2.27, it then follows that dH(u;w) + dH(v;w) = j. Henced(u;w) + d(v;w) j. Moreover, the coordinates in [k]nS (as they are thecoordinates in which u and v di er) contribute j to the sum d(u;w)+d(v;w).Thus u and w must be the same in all coordinates in S. Hence every vertexin H has the same values in S and therefore H is of the form Qk[V] for Vde ned as in the theorem statement.Theorem 3.11. jAut(Qk)j= 2kk! for k2Z+.Proof. As shown earlier, the result of Lemma 3.9 implies that jAut(Qk)j 2kk!. Thus, we need only prove that jAut(Qk)j 2kk!, that is, that everyautomorphism of Qk can be expressed as a composition of a vector additionand coordinate permutation automorphism.Let be an automorphism of Qk, and consider ~0k. De ne v = (~0k).Corollary 2.28 implies that (NQk(~0k)) = NQk(v). Consider w 2f0;1gksuch that wt(w) 2, and let j = wt(w). Then ~0k and w are vertices in acopy of Qj in Qk, call this copy G. De ne H = Qk[ (G)]. Since is anautomorphism, H = Qj. By Lemma 3.10, H is a subgraph induced by a setof 2j vertices having speci ed values on a xed set of k j coordinates, callthis set S. Let x be the vector attaining these speci ed values in S and witha 0 in the j coordinates not in S. Moreover, consider x + ki for all i notin S. These vertices are in H since their coordinates in S are as speci ed,and their images under provide j vertices that di er from v in exactly 1place. Thus once these images are chosen, the k j coordinates that arethe same in all vertices of H have been determined. Since (w) is di erentfrom v in exactly j places, and the k j coordinates in which v and (w)are the same have already been determined by the choice of the images ofNQk(v), (w) is completely determined.Thus every automorphism of Qk has at most 2k choices to map~0k, and atmost k! choices to map NQk(~0k), after which the rest of the automorphism isdetermined. Therefore,jAut(Qk)j 2kk!, and we conclude with the desiredresult.50Chapter 3. The HypercubeDe nition 3.12. For every i in [k], the function: i :f0;1gk!f0;1gk;satis es the following, for all v in f0;1gk with coordinates de ned by v =v1v2;:::;vn: i(v) =8><>:v; if wt(v) is even and vi = 0,v; if wt(v) is odd and vi = 1,v + ki; otherwise.Note that if vi = 0, then i(v) is of even parity. Moreover, if vi = 1, then i(v) is of odd parity.It is clear that i is not an automorphism of Qk, as it can’t be expressedas a composition of vector addition and coordinate permutation. However, i is in fact an automorphism of Q2k, as we will see in Theorem 3.13, rstproved by Miller in [16, Lemma 3.1].Theorem 3.13. The function i is an automorphism of Q2k for all i2[k].Proof. Fix i2 [k]. To prove i is an automorphism of Q2k, we rst provethat i is a permutation of f0;1gk.To prove i is a permutation, assume by way of contradiction that thereexist u;v2f0;1gk such that i(u) = i(v) and u6= v. We must have uj = vjfor all j2[k]ni and ui6= vi. Assume, without loss of generality, that ui = 0and vi = 1. Thus d(u;v) = 1, and therefore u and v are of di ering par-ity. If wt(u) is even, then i(u) = u and i(v) = v by de ntion and henceu = v, a contradiction. Similarly, if wt(u) is odd, then i(u) = u + ki and i(v) = v+ ki , and hence u+ ki = v+ ki . Then by Lemma 1.9, u = v, alsoa contradiction. Thus i is a permutation.We will now prove that i is an automorphism of Q2k. Consider u;v2f0;1gk such that uv2E(Q2k). We consider two cases: Case 1: d(u;v) = 1.This case is trivial since i only alters one coordinate of both u and v.Thus d( i(u); i(v)) 2 and hence i(u) i(v)2E(Q2k). Case 2: d(u;v) = 2.By Corollary 1.16, u and v are either both of even weight or both of51Chapter 3. The Hypercubeodd weight. Thus, if u and v di er in coordinate i we have:d( i(u); i(v)) = wt( i(u) + i(v))= wt(u+v + ki )as ki will be added to exactly one of u;v= wt(u+v) 1 as (u+v)i = 1= d(u;v) 1 2;and therefore i(u) i(v)2E(Q2k).Now, if u and v are the same in coordinate i, since they are of thesame parity, i performs the same operation (either adding ki or notadding ki ) on both u and v. Therefore d( i(u); i(v)) = d(u;v) = 2,and hence i(u) i(v)2E(Q2k).Now consider u;v 2f0;1gk such that i(u) i(v) 2 E(Q2k). We againconsider two cases: Case 1: d( i(u); i(v)) = 1.This case is trivial since i only alters one coordinate of both u and v.Thus d(u;v) 2 and hence uv2E(Q2k). Case 2: d( i(u); i(v)) = 2.Again by Corollary 1.16, i(u) and i(v) are either both of even weightor both of odd weight. Thus, if i(u) and i(v) di er in coordinate iwe have:d(u;v) = wt(u+v)= wt( i(u) + i(v) + ki )as ki will be added to exactly one of u;v= wt( i(u) + i(v)) 1 as ( i(u) + i(v))i = 1= d(u;v) 1 2;and therefore uv2E(Q2k).52Chapter 3. The HypercubeNow, if i(u) and i(v) are the same in coordinate i, since they also areof the same parity, i performs the same operation (either adding kior not adding ki ) on both u and v. Thus d(u;v) = d( i(u); i(v)) = 2,and hence uv2E(Q2k).For any i 2 [k], since i 2 Aut(Q2k)nAut(Qk), we have Aut(Qk) Aut(Q2k), with equality not holding. In fact, Miller proved in [16] that theautomorphism group of the square of the k-cube can be generated by vectoraddition, coordinate permutation, and a single i automorphism. Using this,he was then able to prove the following result.Theorem 3.14. For any positive integer k at least 4:jAut(Q2k)j= (jf0;1gkj)(jSk+1j) = 2k(k + 1)!:3.2 The Chromatic Number of the Cube and itsSquareDetermining the chromatic number of a graph, as discussed in Chapter 2.4,can be very computationally expensive. This, however, does not hold forthe k-cube, Qk.Theorem 3.15. (Qk) = 2 for all k2Z+.Proof. De ne Ve;Vo f0;1gk as follows:Ve =fv2f0;1gkjwt(v) is eveng;Vo =fv2f0;1gkjwt(v) is oddg:Trivially, Ve[Vo =f0;1gk. No two vertices in either set can be adjacent,since d(u;v) = 1 implies that u and v are of di ering parity. Thus Qk isbipartite, and hence 2-colorable. Moreover, we can trivially have no 1-coloring of Qk as there is at least one pair of adjacent vertices (for example,consider ~0k and k1). Therefore (Qk) = 2.The chromatic number of the k-cube is thus 2 for any k2Z+. However,higher powers of the k-cube are not bipartite (for k 2). Thus, determining (Qjk) for j;k 2 and j k 2 can’t necessarily be done in polynomial time.We consider speci cally the square of the k-cube, whose chromatic num-ber is unknown for many k. Included in Appendix A is a table of known53Chapter 3. The Hypercubevalues of and bounds on (Q2k) for k 31, as well as other relevant in-formation. Due to the result of Lemma 3.3, any coloring of Q2k partitionsthe vertices into binary codes of length k and minimum distance at least 3.Theorem 2.34 then allows us to determine the lower bound on (Q2k) seenin Proposition 3.16.Proposition 3.16. (Q2k) 2kA(k;3) for any k2Z+.Proof. The proof of this proposition is immediate from the results of Theo-rem 2.34 and Lemma 3.3.As discussed in Chapter 1, A(k;3) is not known for many k 16. If notknown, we can still apply the sphere-packing bound to Proposition 3.16, aswill be seen in Theorem 3.19 and Corollary 3.20. However, consider the casewhere k = 2n i for some i;n2Z+ with n 3 and i2[4]. A(k;3) is knownexplicitly from the result of Theorem 1.61. This allows for the followingcorollary to Proposition 3.16.Corollary 3.17. Let k = 2n i for some i;n2Z+ with n 3 and i2[4].Then: (Q2k) 2n:Proof. By Theorem 1.61 and Proposition 3.16 we have: (Q2k) 22n i22n n i = 2n:Another way to determine a lower bound on (Q2k) is by exhibiting anoptimal clique in Q2k, and then applying the result of Theorem 2.35.Lemma 3.18. !(Q2k) = k + 1 for any k2Z+ with k 3.Proof. Let k 3. We will rst exhibit a clique of size k + 1. Consider theset of vertices V f0;1gk de ned as follows:V =f~0k; k1; k2;:::; kkg:It is clear that any two vertices in V have distance at most 2, and thus V isa clique of size k + 1 in Q2k.54Chapter 3. The HypercubeNow assume, by way of contradiction, that !(Q2k) k + 2. Let K bea clique of Q2k with jKj = k + 2. Since Q2k is vertex transitive, we can as-sume ~0k 2K. Thus every vertex in k has weight at most 2. Since thereare at most k vertices in K of weight 1, namely ones from f k1; k2;:::; kkg,some vertex v2K has weight 2. Let v = ki1 + ki2 for i1;i22[k] with i1 <i2.Now let 12Sk be a permutation that satis es 1(i1) = 1 and 1(i2) =2. Clearly 1(v) = k1 + k2. De ne K0 = 1(K) and v0 = 1(v). It is clearthat ~0k;v02K0, jK0j= k + 2, and, by Proposition 2.25, K0 is also a cliqueof Q2k. Thus ki =2K0 for i2[k] with i 3, since then:d(v0; ki ) = wt(v0) +wt( ki ) 2wt(v0\ ki ) = 2 + 1 + 0 = 3:Therefore, the only vertices of weight 1 possibly contained in K0 are k1and k2. Since k + 2 4 1, K0 has another vertex of weight 2, w06= v0.Let w0 = kj1 + kj2 for some j1;j2 2 [k] with j1 < j2. Since d(v0;w0) 2and w06= v0, jfj1;j2g\f1;2gj= 1. Therefore j12f1;2g and j2 3. De nej32f1;2g where j36= j1.Now let 2 2Sk be a permutation that satis es 2(j1) = 1, 2(j3) = 2,and 2(j2) = 3. Clearly 2(w0) = k1 + k3 and 2(v0) = v0. We de new00 = 2(w0), v00 = 2(v0) = v0, and K00 = 2(K). It is clear that~0k;v02K0,jK0j = k + 2 and, again by Proposition 2.25, K00 is a clique of Q2k. Hence,the only vertex of weight 1 possibly contained in K00 is k1 as d(w00; k2) = 3and d(v00; ki ) = 3 for i 3.If k1 2K00, then all vertices of weight 2 in K00 have the form k1 + kiwith 2 i k; otherwise we would have two of distance 3 in K00. But thereare only k 1 such weight 2 vertices forcing jK00j k + 1, a contradiction.Meanwhile, if k1 =2K00, we consider any two vertices of weight 2, x;y2K00nfv;wg with x 6= y. Let x = ka + kb and y = kc + kd for somea;b;c;d2 [k] with a < b and c < d. Since d(v00;x) 2 and d(v00;y) 2,a;c 2f1;2g and b;d 3. If a = 2, then since d(x;w00) 2, it must bethe case that b = 3. Similarily, if c = 2, then d = 3. If a = 2 then c = 1;moreover d(x;y) 2 implies that d = 3 giving y = w00, a contradiction.Thus a = 1. A similar argument shows that c = 1. Since a = c = 1,then every vertex of weight 2 in K00 has the form k1 + ki for 2 i k.Again, there are only k 1 such weight 2 vertices, and hence jK00j k, acontradiction. Therefore, every clique in Q2k, for k 3, has at most k + 1vertices.55Chapter 3. The HypercubeNote that for k = 1;2, since (Q2k) = K2k, we have !(Q21) = 2 and!(Q22) = 4.The result of Theorem 2.25 then implies that (Q2k) k + 1 for allk2Z+. This will be stated again in Theorem 3.19; however, a second proofwill be o ered that leads to the strengthened bound of Corollary 3.20.Theorem 3.19. (Q2k) k + 1 for any k2Z+.Proof 1. The result of Lemma 3.18 proved that !(Q2k) = k + 1. Thus, bythe result of Theorem 2.35, (Q2k) k + 1.Proof 2. The result of Proposition 3.16 implies that: (Q2k) 2kA(k;3) 2kb2k(k + 1) 1c by the sphere-packing bound (Theorem 1.50)(3.1) 2k2k(k + 1) 1 = k + 1:Corollary 3.20. Consider any k2Z+ such that k6= 2n 1 for any n2Z.Then (Q2k) k + 2.Proof. Consider line (3.1) in the second proof of Theorem 3.19. We have,if k + 1 6= 2n, that 2k(k + 1) 1 is non-integral. We then have the desiredresult.In addition to the aforementioned lower bounds on (Q2k), it is alsopossible to determine upper bounds on (Q2k), as will be seen in the followingtheorems.Theorem 3.21. (Q2k) (Q2k+1) for any k2Z+.Proof. Assume, by way of contradiction, that (Q2k) > (Q2k+1), and let (Q2k+1) = n. Consider the copy of Qk in Qk+1 induced by the vectors witha 0 in the last coordinate. Applying an n-coloring of Q2k+1 to this copy ofQk yields an m-coloring of this copy for some m n, a contradiction to thechromatic number of Qk.56Chapter 3. The HypercubeAnother well-known upper bound on (Q2k) will be proved in Theorem3.22. Linial, Meshulam, and Tarsi proved this result in [12], and anotherproof was o ered by Wan in [21, Theorem 2] that exhibits an appropriatecoloring with the use of the binary representation matrix, as de ned inDe nition 1.18. We will prove this result in an analogous method to Wan,and show an example of this coloring applied to Q23 in Example 3.23. Notethat we have de ned our binary representation matrix to be the transposeof that used by Wan, as we have represented our vectors as columns ratherthan rows.Theorem 3.22. (Q2k) 2dlog2(k+1)e for any k2Z+.Proof. Consider the binary representation matrix of order k, BRMk, andde ne n =dlog2(k+1)e. Now de ne the following function for all v2f0;1gk:f(v) = (BRMk)(v);with matrix vector multiplication de ned normally over the binary eld.Note that (BRMk)(v) is a binary vector of length n, and hence f :f0;1gk!f0;1gn. Since jf0;1gnj = 2n, we claim f is a 2n-coloring of Q2k. In fact, fcould be an m-coloring of Q2k for some m< 2n, which still yields the upperbound of 2n. Consider arbitrary vertices u and v with uv2E(Q2k), that is,1 d(u;v) 2. We prove f(u)6= f(v). We consider two cases.If d(u;v) = 1, u and v di er in exactly one coordinate in [k], which wedenote i. We have:(BRMk)(u) (BRMk)(v) = (BRMk)(u v)= (BRMk)( ki )= (BRMk)i:where (BRMk)i represents the ith column of BRMk. However, (BRMk)i isthe binary vector of length n whose integer representation is i. Since i6= 0 byde nition of the binary representation matrix, (BRMk)(u) (BRMk)(v)6=~0n and hence f(u)6= f(v).If d(u;v) = 2, u and v di er in exactly two coordinates in [k], which wedenote i1 and i2. We have:(BRMk)(u) (BRMk)(v) = (BRMk)(u v)= (BRMk)( ki1 + ki2)= (BRMk)i1 + (BRMk)i2;57Chapter 3. The Hypercubewhich represents the sum of the binary vectors of length n with integer repre-sentations i1 and i2. However, since i16= i2, (BRMk)(u) (BRMk)(v)6=~0n.Therefore f(u)6= f(v).Example 3.23. Consider the case k = 3. Theorem 3.22 implies that: (Q23) 2dlog2(4)e = 22 = 4:We will therefore exhibit a 4-coloring of Q23. The binary representationmatrix of order 3 is:BRM3 = 0 1 11 0 1 :The coloring f described in Theorem 3.22 is applied as in Table 3.1 (forsimplicity we will convert f(v) to its integer representation i).Table 3.1: A 4-coloring of Q23 using Wan’s constructionv2f0;1g3 (BRM3)(v) i v2f0;1g3 (BRM3)(v) i0@0001A 00 00@0011A 11 30@0101A 10 20@0111A 01 10@1001A 01 10@1011A 10 20@1101A 11 30@1111A 00 0This divides f0;1g3 into the following 4 color classes:fvj (BRM3)(v) = 0g=f000;111g;fvj (BRM3)(v) = 1g=f011;100g;fvj (BRM3)(v) = 2g=f010;101g;fvj (BRM3)(v) = 3g=f001;110g:58Chapter 3. The HypercubeIt is easily veri ed that this is a 4-coloring of Q23. In fact, by Theorem3.19, (Q23) 4 so this coloring is optimal.Theorem 3.22 will now allow us to determine exactly (Q2k) when k =2n i for some i;n2Z+ with n 3 and i2[4].Theorem 3.24. Let k = 2n i for any i;n2Z+ with n 3 and i2 [4].Then: (Q2k) = 2n:Proof. The result of Theorem 3.22 implies that: (Q2k) 2dlog2(2n i+1)e 2dlog2(2n)e= 2n;and therefore, in addition with the result of Corollary 3.17, we have thedesired result.One useful upper bound on (Q2n) occurs when n is odd. In this case,de ning n = 2k+1, (Q22k+1) 2 (Q2k), as we will prove in Theorem 3.26 bymeans of the technique used in [17, Theorem 1]. An example of this boundapplied to Q23 will be seen in Example 3.27. The u (u+v) construction usedin the following lemma and theorem was introduced in [13, p.76], and is acommon technique in building longer codes from shorter codes.Lemma 3.25. Let V be a (k;M;3) binary code for positive integers k andM. De ne the following sets (where pu and qu are de ned as in Chapter 1):Vp =fu pu (u+v) ju2f0;1gk;v2Vg;Vq =fu qu (u+v) ju2f0;1gk;v2Vg;Vp and Vq are (2k + 1;2kM;3) binary codes.Proof. The code length and size of Vp and Vq are trivially 2k + 1 and 2kM,respectively. We will prove the minimum distance of Vp is at least 3. SinceVq = Vp + 2k+1k+1 , the result for Vq will follow immediately from Proposition1.25.59Chapter 3. The HypercubeConsider distinct v2k+11 ;v2k+12 2Vp. For v1;v2 2V and u1;u2 2f0;1gk,let:v2k+11 = u1 pu1 (u1 +v1);v2k+12 = u2 pu2 (u2 +v2):We will show that d(v2n+11 ;v2n+12 ) 3. First note the following:d(u1;u2) +d(u1 +v1;u2 +v2) = d(u1;u2) +wt(u1 +v1 +u2 +v2)= d(u1;u2) +d(u2;u1 +v1 +v2) d(u1;u1 +v1 +v2)by the triangle inequality= wt(u1 +v1 +u1 +v2)= d(u1 +v1;u1 +v2)= d(v1;v2) by Lemma 1.9:Therefore, depending on whether or not v1 = v2 is satis ed, we have:d(v2k+11 ;v2k+12 ) = d(u1;u2) +d(pu1;pu2) +d(u1 +v1;u2 +v2) maxf2d(u1;u2) +d(pu1;pu2);d(v1;v2)g:If v1 = v2, then u1 6= u2. Moreover, d(u1;u2) = 1 implies d(pu1;pu2) = 1(by Corollary 1.16), and thus:d(v2k+11 ;v2k+12 ) 2d(u1;u2) +d(pu1;pu2) 3:If v16= v2, then d(v1;v2) 3 since v1;v22V. Hence:d(v2k+11 ;v2k+12 ) d(v1;v2) 3:Theorem 3.26. (Q22k+1) 2 (Q2k) for any positive integer k.Proof. Fix k2Z+. We will show this upper bound on (Q22k+1) by creatinga 2 (Q2k)-coloring of Q22k+1. Take an optimal coloring of Q2k and denote itscolor classes as Vkj f0;1gk for j2[ (Q2k)]. Clearly, we have: (Q2k)Xj=1jVkj j= 2k:60Chapter 3. The HypercubeWe will use these color classes to build color classes in a coloring ofQ22k+1. To create our color classes of Q22k+1, we de ne (for j2[ (Q2k)]):V2k+1p;j =fu pu (u+v) ju2f0;1gk;v2Vkj g;V2k+1q;j =fu qu (u+v) ju2f0;1gk;v2Vkj g:Obviously, we have created 2 (Q2k) such sets. We claim these sets arecolor classes in a 2 (Q2k)-coloring of Q22k+1. The sum of the vertices in thesets can be determined as follows:X 2fp;qg (Q2k)Xj=1jV2k+1 ;j j=X 2fp;qg (Q2k)Xj=12kjVkj j=X 2fp;qg(2k)(2k)=X 2fp;qg22k= (2)(22k)= 22k+1= n(Q22k+1):Moreover, Lemma 3.25 implies that these sets have minimum distance3, and are thus independent in Q22k+1. Therefore, we need only prove thatthey are pairwise disjoint, and as such their union contains every vertex ofQ22k+1. Assume, by way of contradiction, that for some ; 2fp;qg andj1;j22[ (Q2k)]:V2k+1 ;j1 \V2k+1 ;j2 6=;;V2k+1 ;j1 6= V2k+1 ;j2 :Take v2k+1 2V2k+1 ;j1 \V2k+1 ;j2 . We have, for some u1;u2 2f0;1gk, v1 2Vkj1,and v22Vkj2:u1 u1 (u1 +v1) = u2 u2 (u2 +v2):Thus we must have u1 = u2. Trivially, u1 and u2 then are of the sameparity; so for u1 = u2, we must have = . Finally, since u1 = u2 andu1 +v1 = u2 +v2, Lemma 1.9 implies that v1 = v2. Since v1 = v2, we must61Chapter 3. The Hypercubehave j1 = j2 as the Vkj form a partition of f0;1gk. Thus V2k+1 ;j1 = V2k+1 ;j2 , acontradiction. Therefore these sets form color classes of a 2 (Q2k)-coloringof Q22k+1.Example 3.27. Let us look at the case k = 1. (Q21) = 2, with the optimalcoloring having the following trivial color classes:V11 =f0g;V12 =f1g:We use these sets to build our color classes for an optimal coloring ofQ23. So, we apply our general formula:V3p;j =fu pu (u+v)ju2f0;1g;v2V1jg;V3q;j =fu qu (u+v)ju2f0;1g;v2V1jg;to build:V3p;1 =f000;111g;V3q;1 =f010;101g;V3p;2 =f001;110g;V3q;2 =f011;100g:It is easily determined that these are the color classes of a 4-coloring ofQ23. In fact, these color classes are the same as those realized in the optimalcoloring of Q23 determined in Example 3.23.3.2.1 The Asymptotic Behavior of the Chromatic Numberof the Square of the CubeThe result of Theorem 3.21 states that (Q2k) is nondecreasing as k increases.In fact, Osterg ard proved the following result in [17, Theorem 5].Theorem 3.28.limk!1 (Q2k)k = 1:Therefore, as k increases, (Q2k) approaches k. From Theorem 3.24, ifk = 2n i for n 3 and i2[4], then (Q2k) = 2n. Moreover, if k = 2n forn2Z+, then Corollary 3.20 yields (Q2k) 2n+2. Therefore we can think of62Chapter 3. The Hypercube2n i as a \tail" of values satisfying (Q22n i) = 2n, with i = 1 representingthe uppermost value at the base of the tail. We will now describe the lengthof this tail, T. Let T : Z+nf1;2g!Z+ be the maximum positive integer isuch that (Q22n i) = 2n. It must be the case that:4 T(n) 2n 2n 1 = 2n 1:Based on the bounds in Appendix A we have T(3) = 4, 4 T(4) 7,and 4 T(5) 14. The result of Theorem 3.28 implies that T(n) getsrelatively smaller as n tends to 1, as we will show in Corollary 3.29. Inother words, the lengths of these tails of values of k in which the chromaticnumber of Q2k is a power of 2 gets relatively smaller as k increases.Corollary 3.29. For every 2(0;1), there exists some N2Z+ such thatT(n)2n < for all n>N.Proof. Take arbitrary 2(0;1) and de ne 0 = 2blog2( )c. Clearly 0 .Given a positive integer n, let k = 2n 1+(1 2 0)2n 1. Clearly, there existsa positive integer N1 such that k is an integer for all n>N1. Moreover, byTheorem 3.19, we have: (Q2k)k 1 k + 1k 1 > 0:We now apply Theorem 3.28. For all > 0 there exists a positive integerN2 such that n>N2 implies: (Q2k)k 1 < : (3.2)Take = 22 2 0 1 and x theN2 that satis es (3.2). LetN = maxfN1;N2g,and hence n>N implies: (Q2k) < 1 + 22 2 0 1 k= 22 2 0 2n 1 + (1 2 0)2n 1 = 22 2 0 (2 2 0) 2n 1 = (2)2n 1= 2n:63Chapter 3. The HypercubeSince (Q2k) < 2n, by the de nition of T(n), n>N implies:T(n) < 2n k= 2n 2n 1 + (1 2 0)2n 1 2n (2 2 0)(2n 1)= 2n 2n + 2 0(2n 1)= 02n 2n:3.3 Applying Computational Methods toDetermine the Chromatic Number of theSquare of 8-Dimensional CubeAs seen in Appendix A, the smallest k such that (Q2k) is unknown is k =8. This graph has 28 = 256 vertices and 27 92 = 4608 edges. Althoughthe actual value of (Q2k) is unknown, we know from Theorem 1.60 thatA(8;3) = 20 (by Theorem 1.44 we have A(8;3) = A(9;4)). Thus, we canuse Theorem 3.16 to determine a lower bound on (Q28) as follows: (Q28) 25620 =d12:8e= 13:Moreover, 14-colorings of Q28 are known to exist. This was rst exhibitedby Hougardy in 1991 [23, p.168] from an adaptation of the Petford-Welshalgorithm described in Chapter 2.4.4. This adaptation will be covered inmore detail in Chapter 3.3.3. Another 14-coloring was found independentlyby Royle in 1993 by means of a randomized search [11, p.157]. Hence, thesecolorings provide an upper bound on its chromatic number, so (Q28) is ei-ther 13 or 14. Therefore, in order to determine the chromatic number, oneeither needs to nd a 13-coloring, or prove that one does not exist.Also, since there can be no color class of size greater than 20, if a 13-coloring exists, its color classes must be of one of the following 5 cases: 12 independent sets of size 20 and 1 of size 16, 11 independent sets of size 20, 1 of size 19, and 1 of size 17, 11 independent sets of size 20 and 2 of size 18,64Chapter 3. The Hypercube 10 independent sets of size 20, 2 of size 19, and 1 of size 18, and 9 independent sets of size 20 and 4 of size 19.These cases show that, if searching for a 13-coloring of Q28, independentsets of size 15 or less can be ignored, as they could not possibly be a colorclass of a 13-coloring.The three algorithms introduced in Chapter 2.4 were then applied tothe graph Q28 in an e ort to determine the chromatic number. However,the computational di culty associated with this graph turned out to be fargreater than expected.3.3.1 Integer ProgrammingConsider the IP model to determine the existence of an m-coloring in agraph described in Chapter 2.4.2. We can denote every vertex of Q2k byits integer representation, and create the binary variables xi;j for all i inf0;1;:::;2k 1gand j in [m]. A feasible solution to the following IP wouldthen be an m-coloring of Q2k (letting d(i1;i2) denote the Hamming distancebetween the binary representations of i1 and i2):xi1;j +xi2;j 1for all i1 and i2 in f0;1;:::;2k 1g and j in [m];such that 1 d(i1;i2) 2mXj=1xi;j 1 for all i in f0;1;:::;2k 1g;xi;j2f0;1g for all i in f0;1;:::;2k 1g and j in [m]:We then applied this model to determine if Q28 is 13-colorable (i.e. thecase where k = 8 and m = 13). Computationally, we modeled this IP inC++ with CPLEX 9.0, a powerful mixed integer program optimizer designedby ILOG, the world’s leading combinatorial optimization tool provider.However, the number of variables in this IP are 13n(Q28) = (13)(256) =3;328 and the number of constraints are e(Q28) + n(Q28) = 4;608 + 256 =60;160. After CPLEX’s internal presolver was applied, the reduced IP ma-trix contained 13;607 rows, 3;328 columns, and 72;722 nonzero entries.However, it is possible to impose several additional constraints.65Chapter 3. The HypercubeConsider the clique in Q2k de ned as V = f~08; 81; 82;:::; 8kg (this wasproven to be a clique in Lemma 3.18). It is clear that every vertex in V mustbe in a separate color class. Without loss of generality, we can therefore addthe following constraints:x0;1 = 1; x20;2 = 1; x21;3 = 1; x22;4 = 1;::: ; x2k;k+1 = 1:Including these constraints allowed CPLEX’s presolve to eliminate manymore variables and constraints (such the variables representing vertices ad-jacent to vertex ki in color class i + 1, which must of course equal 0). Weapplied this IP to nd optimal colorings for all 3 k 7 (that is, a 4-coloring of Q23 and 8-colorings of Q2k for 4 k 7). The times to nd thesecolorings are included in Figure 3.1, and were obviously very reasonable.Figure 3.1: Computation Times Using Integer ProgrammingHowever, applied to Q28, the new reduced IP matrix contained 8;431rows, 2;959 columns, and 47;784 nonzero entries. This problem was unfor-tunately too large to compute in a reasonable amount of time. After runningfor over 23 hours, CPLEX had only explored 1;040 out of a maximum pos-sible 22;959 nodes of the branch and bound tree. No e ort was made to helpCPLEX determine the variable choice in the branch and bound. Instead,the defaults were used. Given the vertex transitivity of the graph and largenumber of symmetries of the IP model previously discussed, it seemed moreworthwhile to use another computational method.66Chapter 3. The Hypercube3.3.2 Column GenerationWe then applied the column generation algorithm described in Chapter2.4.3, again implemented in C++ with CPLEX 9.0. This was done rstwith the initial set S being the singleton sets of vertices. Moreover, wecould impose the restriction on the MWIS phase of the algorithm that weonly needed to generate independent sets of size 16 or greater, as priorknowledge indicated that a 13-coloring of Q2k could not contain any colorclasses of size less than 16. This approach showed much promise; however,the computation time at each node of the tree turned out to be prohibitive.For example, to solve the initial node of branch and bound tree, it took2;388 iterations of the IS-MWIS column generation method. This processtook just over 35 minutes on a 2 G.Hz. Pentium processor with 2 G.B. ofR.A.M. After approximately 19 hours, 18 nodes had been explored. Thebranch and bound tree for this method has maximum size of 232;640 nodes(as 2562 = 32;640). This approach was abandoned since it seemed thatan optimal coloring was unlikely to be determined in a reasonable about oftime. Varying the choice of the initial set of independent sets S showed nonoticeable improvement.On the other hand, when applied to Q27, the initial node took only 18iterations and 1 second to perform on the same machine. It also turned outto nd the optimal coloring with the independent sets generated in the rstnode.Part of the reason we were unable to bring the computation time at eachnode down to a manageable length of time is due to the immense numberof columns available for the MWIS portion of the algorithm to choose from.From Proposition 2.25, we know that, given an independent set V and auto-morphism , that (V) is independent. Therefore, given any independentset V, we can generate a collection of independent sets by producing theindependent set (V) for every automorphism . It is unlikely that every (V) will be distinct. However, if a graph has many automorphisms, thenumber of generated independent sets that are distinct will still likely bevery large. Recall from Theorem 3.14 that jAut(Q2k)j = 2k(k + 1)!. There-fore, there exist 289! = 92;897;280 automorphisms of Q28, and given a singleindependent set V, we can immediately generate over 90 million (again, notnecessarily distinct) independent sets of the same size.67Chapter 3. The HypercubeThe challenges associated with the column generation algorithm for de-termining a 13-coloring of Q28 led us naturally to looking at properties ofthese independent sets. In Chapter 4, we will attempt to determine theirstructure.3.3.3 The Petford-Welsh AlgorithmRecall the Petford-Welsh algorithm described in Chapter 2.4.4. As statedpreviously, Hougardy exhibited a 14-coloring of Q28 with an adaptation ofthis algorithm. We were able to reproduce his results, and nd a 14-coloringof Q28 with a running time of within several seconds. The C++ code of ourimplementation of Hougardy’s adaptation is included in Appendix D, underthe le name Hougardy.cpp. The 14-coloring generated with this algorithmis included in Appendix B. However, attempts with varying values for theprobability input parameter did not yield a 13-coloring. This, of course,does not prove the non-existence of such a coloring.68Chapter 4The Structure of OptimalBinary CodesRecall from the Chapter 3.3 that if a 13-coloring of Q28 exists, it contains atleast 9 independent sets of size 20, and possibly as many as 12. Therefore,it contains at least 9 disjoint (8;20;3) binary codes. The knowledge of thestructure of these codes is thus very important in proving the existenceor non-existence of a 13-coloring, or providing MIP cuts to speed up theexploration of the branch and bound (cut) tree.4.1 Computationally Determining all WeightDistributionsWe know from Chapter 1 that every binary code has a weight distribu-tion with respect to any vector u. One may wish to determine how manysequences of integers are a feasible weight distribution of some (n;M;d)binary code C. Since C +u is an (n;M;d) binary code whose weight distri-bution (with respect to~0n) is the same as the weight distribution of C withrespect to u, a sequence of integers is a feasible weight distribution withrespect to any vector u if and only if it is a feasible weight distribution withrespect to ~0n.Given a speci c sequence of integers, (Wi)ni=0, it is easy to set up anIP that determines if there is some (n;M;d) binary code with that weightdistribution. We create a binary variable vj for all j in f0;1;:::;2n 1g.This variable is set to equal 1 if the binary representation of integer j isincluded in C, and 0 otherwise. We will let wt(j) and d(j1;j2) be de nedwith respect to the appropriate binary representations. We then determineif the following system of constraints has a feasible solution:69Chapter 4. The Structure of Optimal Binary Codes2n 1Xj=0vj = M;Xjjwt(j)=ivj = Wi for all i in f0;1;:::;ng;vj1 +vj2 1 for all j1 and j2 in f0;1;:::;ngsatisfying 1 d(j1;j2) d 1:It is clear that if there is a feasible solution to these constraints, thenC =fjjvj = 1gis an (n;M;d) binary code. Otherwise, if this IP is infeasible,then no such code exists. However, this can be a very computationallyexpensive procedure. Fortunately, the knowledge of permutations can allowus to x at least one of the codewords in C and speed this up dramatically.Proposition 4.1. Let C f0;1gn be a binary (n;M;d) code with weightdistribution (Wi)ni=0. Let v 2 C with wt(v) = w and consider any u inf0;1gn with wt(u) = w. Then there exists another binary (n;M;d) code C0such that u2C0 and C0 also has weight distribution (Wi)ni=0.Proof. Consider the permutation in Sk such that (v) = u, which existssince wt(u) = wt(v). De ne C0 = (C). It is clear that C0 is an (n;M;d)binary code that also has weight distribution (Wi)ni=0. In addition, sincev2C, we have u2C0.In this chapter, we will be determining the feasible weight distributionsof optimal binary codes of length 8 and minimum distance 3. It was provenin Theorem 1.60 that these are (8;20;3) binary codes. From [1, Table II],it is known that A(8;6;4) = 2. Therefore, in determining if (Wi)8i=0 is afeasible weight distribution of an (8;20;3) binary code C, consider the casewhere W4 3. In this case, we can in fact x two codewords to any u andv in C such that wt(u) = wt(v) = 4 and d(u;v) = 4. We will be usingthe codewords 00001111 and 00110011, whose integer representations are 15and 51, respectively. The IP to determine if (Wi)8i=0 is a feasible weightdistribution of an (8;20;3) binary code C is then de ned by the followingsystem of constraints, denoted (FD) for feasible distributions:70Chapter 4. The Structure of Optimal Binary Codes255Xj=0vj = 20;Xjjwt(j)=ivj = Wi for all i in f0;1;:::;8g;vj1 +vj2 1 for all j1 and j2 in f0;1;:::;8gsatisfying 1 d(j1;j2) 2;v15 = 1 if W4 1;v51 = 1 if W4 3:Thus we could run this IP on every sequence of positive integers (Wi)8i=0,where8Xi=0Wi = 20. Unfortunately, there are 288 = 3;108;105 such se-quences. However, the result of Theorem 1.48 allows us to impose Wi A(8;3;i) = A(8;4;i) for all i.Proposition 1.46 implies that A(8;3;0) = A(8;3;1) = 1, and henceA(8;3;8) = A(8;3;7) = 1. In addition, Proposition 1.47 implies thatA(8;3;2) = A(8;4;2) = 82 = 4, and hence A(8;3;6) = 4. Finally, [1,Table I] contains the values A(8;3;3) = A(8;3;5) = 8 and A(8;3;4) = 14.Applying all of these constraints on the Wi dramatically reduces the numberof sequences that must be tested. In addition, we will apply the result ofthe following theorem and corollary.Theorem 4.2. Let C be an (8;M;3) binary code with distance distribution(Wi)8i=0. Then W0 +W1 +W2 4.Proof. Assume, by way of contradiction, there exists an (8;M;3) binarycode with weight distribution (Wi)8i=0 with W0 + W1 + W2 5. If ~08 2C,W1 = W2 = 0 as all v in f0;1g8 with wt(v) 2 is at distance at most 2from ~08. Thus ~08 =2C as W1 +W2 4.Since W1 A(8;3;1) = 1 and W2 A(8;3;2) = 4, we must have W1 = 1and W2 = 4. Let u;v1;v2;v3;v42C with wt(u) = 1 and wt(vi) = 2 for all i71Chapter 4. The Structure of Optimal Binary Codesin [4]. We have wt(vi\vj) = 0 for i and j in [4] with i6= j as otherwise:d(vi;vj) = wt(vi) +wt(vj) 2wt(vi\vj) by Lemma 1.15 2 + 2 2= 2:Therefore4Xi=1vi = ~18, and hence wt(u\vi) = 1 for some i in [4]. Thisimplies:d(u;vi) = wt(u) +wt(vi) 2wt(u\vi) = 1 + 2 2 = 1;a contradiction.Corollary 4.3. Let C be an (8;M;3) binary code with weight distribution(Wi)8i=0. Then W6 +W7 +W8 4.Proof. Assume, by way of contradiction, there exists an (8;M;3) binary codewith weight distribution (Wi)8i=0 with W6+W7+W8 5. Let (W0i)8i=0 be theweight distribution of C +~18. We have W00 +W01 +W02 = W8 +W7 +W6 5; however, C +~18 is an (8;M;3) binary code by Proposition 1.25. Thiscontradicts the result of Theorem 4.2.Therefore, to determine all sequences of integers to test as feasible weightdistributions for an (8;20;3) binary code, we must enumerate all feasiblesolutions to the following system, denoted (WD) for weight distributions:8Xi=0Wi = 20 (4.1)W0 1; (4.2)W1 1; (4.3)W2 4; (4.4)W3 8; (4.5)W4 14; (4.6)W5 8; (4.7)W6 4; (4.8)W7 1; (4.9)W8 1; (4.10)W0 +W1 +W2 4; (4.11)72Chapter 4. The Structure of Optimal Binary CodesW6 +W7 +W8 4; (4.12)W0 = 1)W1 +W2 = 0 (4.13)W8 = 1)W6 +W7 = 0 (4.14)Wi2Z+[f0g for all i in f0;1;:::;8g;zi2f0;1g for all i in [4]:Constraint (4:1) forces the code to have size 20. Constraints (4:2) through(4:10) enforce the Wi A(8;3;i) inequalities. Constraints (4:11) and (4:12)follow from Theorem 4.2 and Corollary 4.3, respectively. Moreover, con-straint (4:13) encodes the statement that if W0 = 1, then W1 = W2 = 0,as was determined in the proof of Theorem 4.2. Finally, constraint (2:14)analogously encodes the statement that if W8 = 0, then W6 = W7 = 0.3These constraints were then inputted into the constraint programmingsolver ILOG Solver 6.0, and 7;539 possible solutions were enumerated. Eachof these solutions were then inputted into the (FD) IP, and solved for feasi-bility as a weight distribution using the mixed IP optimizer ILOG CPLEX9.0. The C++ code that solved both (WD), and every (FD) iteration, isnamed CPDist.cpp, and included in Appendix E. In the end, 111 of thedistributions were proven feasible, whereas 7;428 of the distributions wereproven infeasible. All of the feasible weight distributions found are thenincluded in Appendix C. All computation was done on a computer with a2:19 G.Hz. A.M.D. processor with 1:0 G.B. of R.A.M.To show how important the codeword xing constraints are in the (FD)model, we reexecuted the IP without the two conditional constraints forall 111 feasible distributions, and 102 of the 7;428 infeasible distributionsselected at random. The computation times with and without the condi-tional constraints for these 111 feasible and 102 infeasible distributions werecompared.3Implications are allowed in CP models and are implemented quite di erently from thestandard ways they are modeled in MIPs.73Chapter 4. The Structure of Optimal Binary CodesThe computation times with and without the conditional constraints forthe feasible distributions are shown in Figure 4.1.Figure 4.1: Computation Times for Feasible DistributionsThe mean computation time with the constraints was 0:52 seconds,with a maximum of 2:28 seconds. The mean computation time with theconstraints removed was 2:16 seconds, with a maximum of 40:49 seconds.Clearly the relative increase in times is signi cant; however, with only 111distributions it did not make much di erence in absolute terms.74Chapter 4. The Structure of Optimal Binary CodesThe computation times with and without the conditional constraints forthe randomly selected infeasible distributions are shown in Figure 4.2.Figure 4.2: Computation Times for Infeasible DistributionsHere, it can be seen that including these constraints had a substan-tial impact on computation time. The mean computation time with theconstraints was 12:62 seconds, with a maximum of 425:64 seconds, or ap-proximately 7 minutes. The mean computation time with the constraintsremoved was 2;064 seconds, or about 34 minutes. The longest computationtook 116;872 seconds, or over 32 hours. With over 7000 distributions inwhich to determine infeasibility, it is apparent that determining infeasibilityin all such distributions would be extremely impractical without applyingthe knowledge of permutations to x codewords.75Chapter 4. The Structure of Optimal Binary Codes4.2 Structural Results4.2.1 On the Size of Shortened CodesIt is easily determined from the table in Appendix C that every (8;20;3)binary code contains between 8 and 12 codewords of even weight (and thusbetween 8 and 12 codewords of odd weight). This knowledge can be usedto prove the result that every (8;20;3) binary code has between 8 and 12codewords with a speci ed value in each coordinate, as will be proved inCorollary 4.5.Theorem 4.4. Let C be an (n;M;3) binary code with n 3, and x t =jn2k. For any i in [n] and x inf0;1g, C can be transformed into an (n;M;3)binary code D whose weight distribution satis es, letting (Wi)ni=0 denote theweight distribution of D:tXi=0W2i =jfu2C j the ith coordinate of u is xgj:Proof. First consider the case where x = 0. Fix an arbitrary i in [n], andlet D be de ned as follows:D =f i(u) ju2Cg:Recall from the de nition of i that if the ith coordinate of u is 0, then i(u) is of even parity. Moreover, if the ith coordinate of u is 1, then i(u) isof odd parity. In addition, by Theorem 3.13, i is an automorphism of Q2n.Therefore, by Proposition 3.4, since C is an (n;M;3) binary code, D is an(n;M;3) binary code. We then have:tXi=0W2i =jfv2Djwt(v) is evengj=jfu2Cj the ith coordinate of u is 0gj:In the case where x = 1, we instead de ne D to be:D =f i(u) + ni ju2Cg:D is again an (n;M;3) binary code and in this case:tXi=0W2i =fv2Djwt(v) is eveng=jfu2Cj the ith coordinate of u is 1gj:76Chapter 4. The Structure of Optimal Binary CodesCorollary 4.5. Let C be an (8;20;3) binary code. Then, for any i in [8]and x in f0;1g,:8 jfu2C j the ith coordinate of u is xgj 12:Proof. Assume by way of contradiction, for arbitrary i in [8] and x inf0;1gthat:jfu2Cj the ith coordinate of u is xgj= M0;where M0 7 or M0 13. Then, by Theorem 4.4, C can be transformedinto an (8;20;3) binary code D with M0 codewords of even weight. This,however, can’t exist due to the computational results of Chapter 4.1.Another way of expressing this result is that for any (8;20;3) binarycode C, consider the shortened code Ci;x for any i in [8] and x in f0;1g.The code size of this shortened code must satisfy:8 jCi;xj 12:4.2.2 Bounds on the Weight Distributions of Color ClassesThe weight distributions listed in Appendix C can provide many interestingresults about the color classes of what a 13-coloring of Q28 must look like.First and foremost, assume there exists a 13-coloring of Q28 and denote itscolor classes Cj for j 2 [13]. Moreover, let (Wji )8i=0 denote the weightdistribution of Cj. It is clear that:13Xj=0Wji = 8i ;for all i 2f0;1;:::;8g. Since between 9 and 12 of these Cj must be ofsize 20, this greatly restricts the combinations of weight distributions thatcould form a possible 13-coloring of Q28. In fact, the algorithm describedin Chapter 4.1 can trivially be modi ed to generate the weight distribu-tions of all (8;M;3) codes for M < 20. Unfortunately, this led to too manycases to reasonably keep track of. However, useful bounds can still be found.For example, recall from [1, Table I] that A(8;3;4) = 14. Therefore,any binary code with length 8 and minimum distance at least 3 can have amaximum of 14 codewords whose weight is 8. However, as can be seen in77Chapter 4. The Structure of Optimal Binary CodesAppendix C, any optimal (8;20;3) binary code C with weight distribution(Wi)8i=0 must satisfy W4 10. Moreover, if W4 9, then W0 + W8 1.Therefore at least one of ~08 and ~18 must belong to C. Therefore, if a 13-coloring of Q28 exists, at most 2 of the minimum 9 color classes of size 20can have at least 9 codewords of weight 4. Therefore, at least 7 color classesof size 20 must have no more than 8 codewords of weight 4.Moreover, if W3 = A(8;3;3) = 8, then C follows weight distribution 109or 110. Therefore W0 = 1, and hence there can be at most one color classwith 8 codewords of weight 3. An analogous argument shows that there canbe at most one color class with 8 codewords of weight 5.Bounds like these can be added to MIPs or other models for nding, orproving the non-existence of, a 13-coloring of Q28. Attempts were made inthis direction.4.3 The Number of Nonequivalent CodesConsider the following ve (8;20) binary codes (given in terms of their in-teger representations), which can be easily veri ed to be (8;20;3) binarycodes.C1 =f0;7;25;30;42;53;75;84;97;108;114;127;140;147;169;182;194;221;231;248g;C2 =f0;7;25;30;42;53;75;84;97;108;114;127;140;147;166;169;176;194;197;216g:C3 =f0;43;53;62;79;83;92;102;121;135;154;157;172;179;201;214;229;234;240;255g;C4 =f15;26;38;51;66;73;84;101;120;127;133;144;172;185;206;211;221;224;235;246g;C5 =f15;20;26;37;40;51;67;76;118;121;134;145;171;188;201;210;223;224;238;245g:78Chapter 4. The Structure of Optimal Binary CodesThe distance distributions of these ve codes are easily calculated, andseen in Table 4.1.Table 4.1: Distance Distributions of (8;20;3) Binary CodesCode Distance DistributionA0 A1 A2 A3 A4 A5 A6 A7 A8C1 1 0 0 5:8 7:4 3:4 1:4 0:8 0:2C2 1 0 0 6:1 7:5 2:9 1:5 0:9 0:1C3 1 0 0 5:6 8 3:2 1:2 0:8 0:2C4 1 0 0 6 7:2 3 1:8 1 0C5 1 0 0 5:6 7:6 3:2 1:6 0:8 0:2As these distance distributions are all distinct, by the result of Lemma1.38, these codes are pairwise nonequivalent. Therefore there are at least ve nonequivalent (8;20;3) binary codes. In fact, ve was the exact numberdetermined computationally in [18] (Baicheva and Kolev rst proved thisresult in [3]). Thus every (8;20;3) binary code is equivalent to one of these ve aforementioned codes.Therefore every weight distribution listed in Appendix C is realized in acode (or codes) equivalent to at least one Ci for i in [5]. To determine whichCi, we calculated Ci +v for all i in [5] and v in f0;1g8. This yielded 1;280(not necessarily distinct) (8;20;3) binary codes, and the weight distributionof each one was calculated. Each of the 111 weight distributions appearedat least once in these codes, and for each of the 111, the Ci that generated itwere also recorded in this appendix. Note that, as some weight distributionscan be generated by more than one Ci, two (8;20;3) binary codes with thesame weight distribution need not be equivalent.4.4 Another De nition of EquivalenceThe hypercube coloring problem leads to another de nition of code equiva-lence.De nition 4.6. Let C and D be (n;M;d) binary codes. C and D are Qjn-equivalent if C = (D) for some in Aut(Qjn). C is Qjn-unique if every(n;M;d) binary code is Qjn-equivalent to C.79Chapter 4. The Structure of Optimal Binary CodesAnalogous to equivalence in the code theoretical sense, Qjn-equivalenceis an equivalence relation on the set of all binary codes.Since coordinate permutation and vector addition functions are auto-morphisms of Qn, and hence Qjn, for any choices of positive integers j andn, it is clear that if two codes are equivalent in the code theoretical sense,then they are also Qjn-equivalent. In fact, for j = 1, these two de nitionsare equal.While there are ve nonequivalent (8;20;3) binary codes, Hougardy de-termined via an exhaustive search that there are only two that are Q28-nonequivalent [10]. The two codes exhibited by Hougardy are C1 and C2above. Therefore C3, C4, and C5 must each be Q28-equivalent to exactly oneof C1 and C2. This can indeed be veri ed. Let 3, 4, and 5 be the permu-tations in S8 de ned by (2 6)(5 8), (1 3 2)(4 7 8)(5 6), and (2 8)(3 4 7 6),respectively. We then have: 3 1(C3 + 255) = C2; 4 1(C4 + 73) = C1; 5 1(C5 + 67) = C1;where the addition, of course, corresponds to the addition of the binary vec-tor with the appropriate integer representation. Since the functions usedare all automorphisms of the square of the cube (as seen in Chapter 3.1),C2 and C3 are Q28-equivalent. Moreover, so are C1, C4, and C5.As stated previously, two (8;20;3) binary codes with the same weightdistribution need not be equivalent from a code theoretical perspective. Infact, they need not even be Q28-equivalent. Consider, for example, weightdistribution 14 in Appendix C. It can be realized in codes equivalent toboth C3 and C5. C3 is Q28-equivalent to C2 and C5 is Q28-equivalent to C1.Therefore, these codes are not Q28-equivalent.Knowing the structure of equivalent codes invites further computationalinvestigation into resolving whether or not a 13-coloring of Q28 exists. Wehave looked at this only brie y. One can produce a large number of (8;20;3)codes chosen randomly by rst choosing at randomly one of the Ci, for iin [5], then choosing randomly a v in [255], and then choosing randomlya permutation from S8. The set of these codes are then put into a MIPsimilar to the IS method of the column generation algorithm described in80Chapter 4. The Structure of Optimal Binary CodesChapter 2.4.3 to see if they can produce a 13-coloring. A column generationapproach could be used to increase the size of the set using this randommethod. Unfortunately, even if no such 13-coloring is found, it will notprove that one doesn’t exist. On the other hand, the only algorithm knownto nd even a 14-coloring of Q28 was the modi ed Petford-Welsh randomizedalgorithm. Therefore if a 13-coloring exists, then it may very well be foundby a random method.81Chapter 5ConclusionWe introduced the study of graph theory, and speci cally, vertex coloringproblems. The decision problem of determining whether or not a generalgraph is m-colorable for m 3 is NP-complete. Our main focus was ondetermining the chromatic number of the square of the hypercube, Q2k. Ourcomputational e ort was focused on the smallest value of k for which thisis currently unknown, k = 8. To determine the chromatic number of Q28,based on current knowledge, requires either exhibiting a 13-coloring, or prov-ing that one can’t exist.While our computational approaches did not determine this value, theydid serve to direct our attention to the study of binary codes. The knowledgeof binary codes and their structure further strengthened our understandingof the combinatorial nature of this class of graphs. We then directed ourcomputational e orts on determining the structure of optimal binary codeswith length 8 and minimum distance at least 3, of which there must be atleast 9 representing the color classes of a 13-coloring of Q28.Future work may focus on the following: Investigating further the link between weight and distance distribu-tions of binary codes, Applying these results to develop new adaptations of graph coloringalgorithms to determine the chromatic number of Q28, Generalize our research to determine values of, or narrow bounds on,other unknown values of the chromatic number of Q2k.82Bibliography[1] E. Agrell, A. Vardy, and K. Zeger. Upper bounds for constant-weightcodes. IEEE Trans. Inform. Theory, 46(7):2373{2395, 2000.[2] E. Agrell, A. Vardy, and K. Zeger. A table of upper bounds for binarycodes. IEEE Trans. Inform. Theory, 47(7):3004{3006, 2001.[3] T. Baicheva and E. Kolev. Binary codes of length eight, minimum dis-tance three and twenty codewords. In Proc. II Int. Workshop OptimalCodes and Related Topics, pages 5{8, Sozopol, Bulgaria, 1998.[4] M. R. Best and A. E. Brouwer. The triply shortened binary Hammingcode is optimal. Discrete Math., 17(3):235{245, 1977.[5] M. R. Best, A. E. Brouwer, F. J. MacWilliams, F. Jessie, A. M. Odlyzko,and N. J. A. Sloane. Bounds for binary codes of length less than 25.IEEE Trans. Infomation Theory, IT-24(1):81{93, 1978.[6] D. Br elaz. New methods to color the vertices of a graph. Comm. ACM,22(4):251{256, 1979.[7] P. Delsarte. Bounds for unrestricted codes, by linear programming.Philips Res. Rep., 27:272{289, 1972.[8] P. Delsarte. An algebraic approach to the association schemes of codingtheory. Philips Res. Rep. Suppl., (10):vi+97, 1973.[9] M. R. Garey and D. S. Johnson. Computers and intractability. W. H.Freeman and Co., San Francisco, Calif., 1979. A guide to the theory ofNP-completeness, A Series of Books in the Mathematical Sciences.[10] S. Hougardy. Personal email communication, 2008.[11] T. R. Jensen and B. Toft. Graph coloring problems. Wiley-InterscienceSeries in Discrete Mathematics and Optimization. John Wiley & SonsInc., New York, 1995. A Wiley-Interscience Publication.83Bibliography[12] N. Linial, R. Meshulam, and M. Tarsi. Matroidal bijections betweengraphs. J. Combin. Theory Ser. B, 45(1):31{44, 1988.[13] F. J. MacWilliams and N. J. A. Sloane. The theory of error-correctingcodes. II. North-Holland Publishing Co., Amsterdam, 1977. North-Holland Mathematical Library, Vol. 16.[14] S. McKinley. The hamming codes and delsarte’s linear programmingbound. Master’s thesis, Portland State University, May 2003.[15] A. Mehrotra and M. A. Trick. A column generation approach for graphcoloring. INFORMS Journal on Computing, 8:344{354, 1996.[16] Z. Miller and M. Perkel. A stability theorem for the automorphismgroups of powers of the n-cube. Australas. J. Combin., 10:17{28, 1994.[17] P. R. J. Osterg ard. On a hypercube coloring problem. J. Combin.Theory Ser. A, 108(2):199{204, 2004.[18] P. R. J. Osterg ard, T. Baicheva, and E. Kolev. Optimal binary one-error-correcting codes of length 10 have 72 codewords. IEEE Trans.Inform. Theory, 45(4):1229{1231, 1999.[19] A. D. Petford and D. J. A. Welsh. A randomised 3-colouring algorithm.Discrete Math., 74(1-2):253{261, 1989. Graph colouring and variations.[20] R. M. Roth. Introduction to coding theory. Cambridge University Press,New York, second edition, 2006.[21] P.-J. Wan. Near-optimal con ict-free channel set assignments for anoptical cluster-based hypercube network. J. Comb. Optim., 1(2):179{186, 1997.[22] D. B. West. Introduction to graph theory. Prentice Hall, Inc., UpperSaddle River, New Jersey, second edition, 2001.[23] G. M. Ziegler. Coloring Hamming graphs, optimal binary codes, andthe 0=1-Borsuk problem in low dimensions. In Computational discretemathematics, volume 2122 of Lecture Notes in Comput. Sci., pages 159{171. Springer, Berlin, 2001.84Appendices85Appendix ACurrent Status of Coloringthe Square of the CubeTable A.1: Current Status of Coloring the Square of the Cubek n(Q2k) e(Q2k) A(k;3) !(Q2k) n(Q2k)A(k;3) (Q2k)1 2 1 1a 2 2 22 4 6 1a 4 4 43 8 24 2a 4 4 44 16 80 2a 5 4 8e5 32 240 4a 6 8 8e6 64 672 8a 7 8 8e7 128 1;792 16a 8 8 8e8 256 4;608 20a 9 12:8 13d 14c9 512 11;520 40a 10 12:8 13d 16g10 1;024 28;160 72a 11 14:2 15d 16g11 2;048 67;584 144a 12 14:2 15d 16g12 4;096 159;744 256a 13 16 16e13 8;192 372;736 512a 14 16 16e14 16;384 860;160 1;024a 15 16 16e15 32;768 1;966;080 2;048a 16 16 16eContinued on next pagea [2, Table I]. e Theorem 3.24.b Theorem 1.61. f Theorem 3.26.c Exhibited 14-colorings. g Theorem 3.21.d Proposition 3.16.86Appendix A. Current Status of Coloring the Square of the CubeTable A.1{ continued from previous pagek n(Q2k) e(Q2k) A(k;3)16 65;536 4;456;448 2;720a 3;276a17 131;072 10;027;008 5;312a 6;552a18 262;144 22;413;312 10;496a 13;104a19 524;288 49;807;360 20;480a 26;208a20 1;048;576 110;100;480 36;864a 43;689a21 2;097;152 242;221;056 73;728a 87;378a22 4;194;304 530;579;456 147;456a 173;491a23 8;388;608 1;157;627;904 294;912a 344;308a24 16;777;216 2;516;582;400 524;288a 599;185a25 33;554;432 5;452;595;200 1;048;576a 1;198;370a26 67;108;864 11;777;605;632 2;097;152a 2;396;740a27 134;217;728 25;367;150;592 4;194;304a 4;793;480a28 268;435;456 54;492;397;568 8;388;608b29 536;870;912 116;769;423;360 16;777;216b30 1;073;741;824 249;644;974;080 33;554;432b31 2;147;483;648 532;575;944;704 67;108;864bk !(Q2k) n(Q2k)A(k;3) (Q2k)16 17 20:004884 24:094 21d 28g17 18 20:004884 24:675 21d 28f18 19 20:004884 24:976 21d 32g19 20 20:004884 25:6 21d 32g20 21 24:00091556 28:4 25d 32g21 22 24:00091556 28:4 25d 32g22 23 24:17591691 28:4 25d 32g23 24 24:36367438 28:4 25d 32g24 25 28:00006008 32 29d 32g25 26 28:00006008 32 29d 32g26 27 28:00006008 32 29d 32g27 28 28:00006008 32 29d 32g28 29 32 32e29 30 32 32e30 31 32 32e31 32 32 32e87Appendix BA 14-coloring of the Squareof the 8-CubeTable B.1: A 14-coloring of Q28V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V11 V12 V13 V1413 4 2 22 12 3 16 5 14 6 15 0 7 119 24 17 27 18 8 29 11 23 9 21 41 10 2034 31 30 48 35 37 39 28 36 32 40 46 25 2662 42 47 61 57 59 44 50 43 55 54 51 33 3875 53 56 78 65 60 79 63 49 58 70 71 52 4580 77 69 88 94 68 83 64 67 74 73 81 76 66103 82 91 98 106 87 96 86 72 95 90 92 85 93104 97 99 105 116 89 117 110 84 113 101 100 107 115125 102 108 119 139 111 130 121 109 124 127 122 126 120142 123 118 132 149 112 133 134 114 144 138 131 128 135152 147 137 143 166 141 158 136 129 155 156 159 150 140171 160 151 145 176 148 169 161 146 174 173 165 172 153183 175 164 163 191 154 179 205 157 195 187 188 186 170194 182 178 168 196 162 180 209 167 213 192 200 201 181197 185 189 190 216 177 204 218 184 228 215 214 211 203223 199 207 210 237 193 217 235 198 233 227 226 231 208244 202 220 221 243 206 230 247 219 242 238 239 240 222250 212 234 229 232 255 252 224 248 249 225236 241 251 246 245253 254The Vi for i in [14] given are the color classes of the 14-coloring of Q28determined by the Hougardy.cpp code of Appendix D, with the vectors givenby their integer representations.88Appendix CWeight Distributions of(8; 20; 3) Binary CodesTable C.1: Weight Distributions of (8;20;3) Binary CodesDistribution W0 W1 W2 W3 W4 W5 W6 W7 W8Realizedin code(s)equivalent to0 0 0 1 5 5 5 3 1 0 C21 0 0 2 4 6 4 3 1 0 C22 0 0 2 5 6 4 2 1 0 C1;C43 0 0 2 6 4 4 3 1 0 C24 0 0 2 6 5 3 3 1 0 C1;C45 0 0 2 7 3 4 3 1 0 C36 0 0 2 7 4 4 2 1 0 C57 0 0 3 3 4 6 4 0 0 C28 0 0 3 3 6 4 3 1 0 C39 0 0 3 4 4 6 3 0 0 C110 0 0 3 4 6 4 3 0 0 C511 0 0 3 5 3 5 4 0 0 C412 0 0 3 5 4 4 3 1 0 C1;C413 0 0 3 5 5 3 3 1 0 C214 0 0 3 5 6 2 3 1 0 C3;C515 0 0 3 6 3 4 3 1 0 C216 0 0 3 6 4 4 3 0 0 C117 0 0 3 6 5 2 3 1 0 C218 0 0 3 6 5 3 2 1 0 C1;C419 0 0 3 7 2 4 3 1 0 C520 0 0 3 7 3 3 3 1 0 C221 0 0 3 7 3 4 2 1 0 C322 0 0 3 7 4 2 3 1 0 C1;C423 0 0 3 7 4 3 2 1 0 C224 0 0 4 2 4 6 4 0 0 C325 0 0 4 4 2 6 4 0 0 C126 0 0 4 4 3 5 4 0 0 C227 0 0 4 4 4 4 4 0 0 C3;C528 0 0 4 5 3 4 4 0 0 C229 0 0 4 5 3 5 3 0 0 C4Continued on next page89Appendix C. Weight Distributions of (8;20;3) Binary CodesTable C.1{ continued from previous pageDistribution W0 W1 W2 W3 W4 W5 W6 W7 W8Realizedin code(s)equivalent to30 0 0 4 6 2 4 4 0 0 C131 0 0 4 6 3 3 3 1 0 C432 0 0 4 6 4 2 3 1 0 C233 0 0 4 6 4 2 4 0 0 C334 0 0 4 6 4 3 3 0 0 C235 0 1 0 0 10 8 0 0 1 C236 0 1 0 5 5 5 3 1 0 C337 0 1 1 3 7 7 0 0 1 C238 0 1 1 3 8 6 0 0 1 C1;C439 0 1 1 4 6 5 2 1 0 C240 0 1 1 4 6 7 0 0 1 C341 0 1 1 4 7 4 2 1 0 C1;C442 0 1 1 5 5 5 2 1 0 C343 0 1 1 5 6 5 1 1 0 C544 0 1 2 2 7 7 0 0 1 C1;C445 0 1 2 2 8 6 0 0 1 C246 0 1 2 2 9 5 0 0 1 C3;C547 0 1 2 3 4 7 3 0 0 C248 0 1 2 3 5 6 3 0 0 C1;C449 0 1 2 3 6 4 3 1 0 C250 0 1 2 3 6 5 2 1 0 C1;C451 0 1 2 3 6 7 0 0 1 C252 0 1 2 3 7 4 2 1 0 C253 0 1 2 3 8 3 2 1 0 C3;C554 0 1 2 3 8 5 0 0 1 C255 0 1 2 4 3 7 3 0 0 C356 0 1 2 4 4 7 2 0 0 C557 0 1 2 4 5 4 3 1 0 C1;C458 0 1 2 4 5 5 2 1 0 C259 0 1 2 4 5 7 0 0 1 C560 0 1 2 4 6 5 2 0 0 C1;C461 0 1 2 4 7 3 2 1 0 C262 0 1 2 4 7 4 1 1 0 C1;C463 0 1 2 4 7 5 0 0 1 C1;C464 0 1 2 5 4 5 2 1 0 C565 0 1 2 5 5 4 2 1 0 C266 0 1 2 5 5 5 1 1 0 C367 0 1 2 5 6 3 2 1 0 C1;C468 0 1 2 5 6 4 1 1 0 C269 0 1 3 2 4 6 4 0 0 C270 0 1 3 2 4 7 3 0 0 C1;C471 0 1 3 2 5 6 3 0 0 C272 0 1 3 2 6 5 3 0 0 C3;C573 0 1 3 3 3 6 4 0 0 C4Continued on next page90Appendix C. Weight Distributions of (8;20;3) Binary CodesTable C.1{ continued from previous pageDistribution W0 W1 W2 W3 W4 W5 W6 W7 W8Realizedin code(s)equivalent to74 0 1 3 3 3 7 3 0 0 C275 0 1 3 3 5 5 3 0 0 C276 0 1 3 3 5 6 2 0 0 C1;C477 0 1 3 3 6 3 3 1 0 C578 0 1 3 3 6 6 0 0 1 C479 0 1 3 4 2 7 3 0 0 C580 0 1 3 4 3 6 3 0 0 C281 0 1 3 4 3 7 2 0 0 C382 0 1 3 4 4 5 3 0 0 C1;C483 0 1 3 4 4 6 2 0 0 C284 0 1 3 4 5 4 2 1 0 C1;C485 0 1 3 4 6 3 2 1 0 C286 0 1 3 4 6 3 3 0 0 C387 0 1 3 4 6 4 2 0 0 C288 0 1 3 5 5 5 0 0 1 C289 0 1 3 5 5 5 0 1 0 C390 0 1 3 5 5 5 1 0 0 C291 1 0 0 0 10 8 0 0 1 C392 1 0 0 4 8 6 0 0 1 C193 1 0 0 4 9 5 0 0 1 C294 1 0 0 4 10 4 0 0 1 C3;C595 1 0 0 5 5 5 3 1 0 C296 1 0 0 5 7 4 2 1 0 C1;C497 1 0 0 5 8 3 2 1 0 C298 1 0 0 5 9 2 2 1 0 C3;C599 1 0 0 5 9 4 0 0 1 C2100 1 0 0 6 6 3 3 1 0 C4101 1 0 0 6 8 2 2 1 0 C2102 1 0 0 6 8 3 1 1 0 C1;C4103 1 0 0 6 8 4 0 0 1 C1104 1 0 0 7 5 4 2 1 0 C5105 1 0 0 7 6 3 2 1 0 C2106 1 0 0 7 6 4 1 1 0 C3107 1 0 0 7 7 2 2 1 0 C1;C4108 1 0 0 7 7 3 1 1 0 C2109 1 0 0 8 10 0 0 0 1 C3110 1 0 0 8 10 0 0 1 0 C291Appendix DHougardy.cpp1 #include <i l c p l e x / i l o c p l e x . h>2 #include <string>34 ILOSTLBEGIN56 typedef IloArray<IloIntArray> IloIntMatrix ;78 I l o I n t lastTime = 0 ;9 I l o I n t timePeriod = 5 ;10 int maxTotalColored = 0 ;1112131415 int b i t S t r i n g D i f f ( IloIntArray string1 , IloIntArrays t r i n g 2 )f16 int count = 0 ;17 for ( int i = 0 ; i < s t r i n g 1 . g e t S i z e ( ) ; i++)f18 i f ( s t r i n g 1 [ i ] != s t r i n g 2 [ i ] )f19 count++;20 g21 g22 return count ;23 g;242526 void main ( )27 f28 IloEnv env ;2930 try f92Appendix D. Hougardy.cpp31 I l o I n t nBits = 8 ;32 I l o I n t nVertices = int (pow(2 , nBits ) ) ;33 I l o I n t nColorClasses = int (pow(2 , int ( c e i l f ( log (float ( nBits +1)) / log ( 2 . 0 ) ) ) ) ) ;34 cout << "number of b i t s = " << nBits << endl ;3536 IloIntMatrix b i t S t r i n g s ( env , nVertices ) ;37 for ( int v = 0 ; v < nVertices ; v++)f38 b i t S t r i n g s [ v ] = IloIntArray ( env , nBits ) ;39 int remainder = v ;40 for ( int b = nBits 1 ; b >= 0 ; b )f41 i f ( remainder >= pow(2 , b) )f42 b i t S t r i n g s [ v ] [ nBits 1 b ] = 1 ;43 remainder = pow(2 , b) ;44 g45 elsef46 b i t S t r i n g s [ v ] [ nBits 1 b ] = 0 ;47 g48 g49 g5051 IloIntMatrix neighbors ( env , nVertices ) ;52 for ( int v = 0 ; v < nVertices ; v++)f53 neighbors [ v ] = IloIntArray ( env ) ;54 IloIntArray bitStringOfv = b i t S t r i n g s [ v ] ;55 for ( int n = 0 ; n < nVertices ; n++)f56 i f (n != v )f57 i f ( b i t S t r i n g D i f f ( bitStringOfv , b i t S t r i n g s [ n] ) <= 2)f58 neighbors [ v ] . add (n) ;59 g60 g61 g62 g6364 double c = 0 . 0 0 6 ;65 IloNumArray prob val ( env , nBits +1) ;66 prob val [ 0 ] = 1 . 0 ;67 for ( int i = 1 ; i < prob val . g e t S i z e ( ) ; i++)f68 prob val [ i ] = prob val [ i 1] c ;93Appendix D. Hougardy.cpp69 g7071 I l o I n t nColors = 14;727374 IloRandom random ( env ) ;7576 IloIntArray c o l o r i n g ( env , nVertices ) ;77 for ( int i = 0 ; i < nVertices ; i++)f78 c o l o r i n g [ i ] = random . getInt ( nColors ) ;79 g8081 IloIntArray num col ( env , nColors ) ;82 I l o I n t num bad ;83 I l o I n t num trials = 0 ;84 dof85 num bad = nVertices ;86 for ( int i = 0 ; i < nVertices ; i++)f87 for ( int j = 0 ; j < nColors ; j++)f88 num col [ j ] = 0 ;89 g90 for ( int ni = 0 ; ni < neighbors [ i ] . g e t S i z e ( ) ;ni++)f91 i f ( neighbors [ i ] [ ni ] < nVertices )f92 num col [ c o l o r i n g [ neighbors [ i ] [ ni ]]]++;93 g94 g95 i f ( num col [ c o l o r i n g [ i ] ] == 0)f96 num bad ;97 g98 elsef99 double sum = 0 . 0 ;100 for ( int c = 0 ; c < nColors ; c++)f101 sum += prob val [ num col [ c ] ] ;102 g103 double r = random . getFloat ( ) sum ;104 double temp = 0 . 0 ;105 int index = 1;106 dof107 index++;94Appendix D. Hougardy.cpp108 temp += prob val [ num col [ index ] ] ;109 g110 while ( temp < r ) ;111 c o l o r i n g [ i ] = index ;112 g113 g114 num trials++;115 g116 while ( num bad > 0) ;117118 IloIntMatrix c o l o r C l a s s e s ( env , nColors ) ;119 for ( int c = 0 ; c < nColors ; c++)f120 c o l o r C l a s s e s [ c ] = IloIntArray ( env ) ;121 cout << " c o l o r " << c << " : " ;122 for ( int v = 0 ; v < nVertices ; v++)f123 i f ( c o l o r i n g [ v ] == c )f124 cout << v << " " ;125 c o l o r C l a s s e s [ c ] . add ( v ) ;126 g127 g128 cout << endl ;129 g130131 bool goodColoring = true ;132 for ( int c = 0 ; c < nColors ; c++)f133 for ( int v1 = 0 ; v1 < c o l o r C l a s s e s [ c ] . g e t S i z e ( ) ;v1++)f134 for ( int v2 = v1 + 1 ; v2 < c o l o r C l a s s e s [ c ] .g e t S i z e ( ) ; v2++)f135 i f ( b i t S t r i n g D i f f ( b i t S t r i n g s [ c o l o r C l a s s e s [ c] [ v1 ] ] , b i t S t r i n g s [ c o l o r C l a s s e s [ c ] [ v2 ] ] )<= 2)f136 goodColoring = false ;137 g138 g139 g140 g;141 i f ( goodColoring )f142 cout << " assignments are a good c o l o r i n g " <<endl ;95Appendix D. Hougardy.cpp143 g144 elsef145 cout << " assignments are NOT a good c o l o r i n g " <<endl ;146 g147148149150151 g152 catch ( IloException& ex ) f153 cout << " Error : " << ex << endl ;154 g155 env . end ( ) ;156 g96Appendix ECPDist.cpp1 #include <i l c p l e x / i l o c p l e x . h>2 #include <i l s o l v e r / i l o s o l v e r i n t . h>3 #include <string>4 #include <fstream>5 #include <time . h>6 #include <s t d l i b . h>7 #include <s t d i o . h>89 ILOSTLBEGIN10 typedef IloArray<IloIntArray> IloIntMatrix ;11 typedef IloArray<IloIntVarArray> IloIntVarMatrix ;1213 int b i t S t r i n g D i f f ( IloIntArray string1 , IloIntArrays t r i n g 2 )f14 int count = 0 ;15 for ( int i = 0 ; i < s t r i n g 1 . g e t S i z e ( ) ; i++)f16 i f ( s t r i n g 1 [ i ] != s t r i n g 2 [ i ] )f17 count++;18 g19 g20 return count ;21 g2223 int main ( ) f2425 IloEnv env ;2627 int nBits = 8 ;28 int nVertices = int (pow(2 , nBits ) ) ;29 int Dist [ 1 0 0 0 0 ] [ 9 ] ;30 int f e a s D i s t [ 1 0 0 0 0 ] [ 9 ] ;97Appendix E. CPDist.cpp31 int f e a s [ 1 0 0 0 0 ] ;32 int solutionCounter = 0 ;33 int s e t S i z e = 20;34 try f35 IloModel CPmodel( env ) ;3637 IloIntVarArray x ( env , nBits +1 ,0 ,14) ;3839 CPmodel . add ( IloSum ( x ) == s e t S i z e ) ;4041 CPmodel . add ( x [ 0 ] <= 1) ;42 CPmodel . add ( x [ 1 ] <= 1) ;43 CPmodel . add ( x [ 2 ] <= 4) ;44 CPmodel . add ( x [ 3 ] <= 8) ;45 CPmodel . add ( x [ 4 ] <= 14) ;46 CPmodel . add ( x [ 5 ] <= 8) ;47 CPmodel . add ( x [ 6 ] <= 4) ;48 CPmodel . add ( x [ 7 ] <= 1) ;49 CPmodel . add ( x [ 8 ] <= 1) ;5051 CPmodel . add ( x [ 0 ] + x [ 1 ] + x [ 2 ] <= 4) ;52 CPmodel . add ( x [ 6 ] + x [ 7 ] + x [ 8 ] <= 4) ;5354 CPmodel . add ( IloIfThen ( env , x [ 0 ] == 1 , x [ 1 ] + x [ 2 ]== 0) ) ;55 CPmodel . add ( IloIfThen ( env , x [ 8 ] == 1 , x [ 6 ] + x [ 7 ]== 0) ) ;5657 I l o S o l v e r s o l v e r (CPmodel) ;58 s o l v e r . startNewSearch ( ) ;59 while ( s o l v e r . next ( ) ) f60 s o l v e r . out ( ) << " Dist [ " << solutionCounter << " ]= ( " ;61 for ( int i = 0 ; i < nBits ; i++) f62 Dist [ solutionCounter ] [ i ] = s o l v e r . getValue ( x [ i] ) ;63 s o l v e r . out ( ) << s o l v e r . getValue ( x [ i ] ) << " , " ;64 g65 Dist [ solutionCounter ] [ nBits ] = s o l v e r . getValue ( x[ nBits ] ) ;98Appendix E. CPDist.cpp66 s o l v e r . out ( ) << s o l v e r . getValue ( x [ nBits ] ) << " ) ";67 s o l v e r . out ( ) << endl ;68 solutionCounter++;69 g70 s o l v e r . endSearch ( ) ;71 cout << endl << endl << endl << endl ;72 g73 catch ( IloException& e ) f74 c e r r << " Concert exception caught : " << e << endl ;75 g76 catch ( . . . ) f77 c e r r << "Unknown exception caught " << endl ;78 g7980 for ( int i = 0 ; i < solutionCounter ; i++) f8182 try f83 c l o c k t start , f i n i s h ;84 long double duration ;85 s t a r t = clock ( ) ;86 IloModel MIPmodel( env ) ;87 IloIntArray xDist ( env , nBits +1) ;88 for ( int b = 0 ; b < nBits +1; b++) f89 xDist [ b ] = Dist [ i ] [ b ] ;90 g9192 IloIntMatrix b i t S t r i n g s ( env , nVertices ) ;93 for ( int v = 0 ; v < nVertices ; v++)f94 b i t S t r i n g s [ v ] = IloIntArray ( env , nBits ) ;95 int remainder = v ;96 for ( int b = nBits 1 ; b >= 0 ; b )f97 i f ( remainder >= pow(2 , b) )f98 b i t S t r i n g s [ v ] [ nBits 1 b ] = 1 ;99 remainder = pow(2 , b) ;100 g101 elsef102 b i t S t r i n g s [ v ] [ nBits 1 b ] = 0 ;103 g104 g99Appendix E. CPDist.cpp105 g106107 IloIntMatrix wt( env , nBits + 1) ;108 for ( int b = 0 ; b < nBits +1; b++)f109 wt [ b ] = IloIntArray ( env , nVertices ) ;110 for ( int v = 0 ; v < nVertices ; v++)f111 i f ( b i t S t r i n g D i f f ( b i t S t r i n g s [ v ] , b i t S t r i n g s[ 0 ] ) == b) f112 wt [ b ] [ v ] = 1 ;113 g114 else wt [ b ] [ v ] = 0 ;115 g116 g117118 IloIntVarArray x ( env , nVertices , 0 , 1) ;119 MIPmodel . add ( IloSum ( x ) == s e t S i z e ) ;120 for ( int b = 0 ; b < nBits +1; b++) f121 MIPmodel . add ( IloScalProd (wt [ b ] , x ) == xDist [ b ] );122 g123124 for ( int v1 = 0 ; v1 < nVertices ; v1++) f125 char xName [ 1 0 ] ;126 s p r i n t f (xName , " x %d" , v1 ) ;127 x [ v1 ] . setName (xName) ;128 for ( int v2 = v1 + 1 ; v2 < nVertices ; v2++)f129 i f ( b i t S t r i n g D i f f ( b i t S t r i n g s [ v1 ] , b i t S t r i n g s [v2 ] ) <= 2) f130 MIPmodel . add ( x [ v1 ] + x [ v2 ] <= 1) ;131 g132 g133 g134135 i f ( xDist [ 4 ] >= 1) f136 MIPmodel . add ( x [ 1 5 ] == 1) ;137 g138 i f ( xDist [ 4 ] >= 3) f139 MIPmodel . add ( x [ 5 1 ] == 1) ;140 g141100Appendix E. CPDist.cpp142 IloCplex cplex (MIPmodel) ;143 cplex . setParam ( IloCplex : : MIPInterval ,10000) ;144 cplex . setParam ( IloCplex : : MIPEmphasis , 1 ) ;145 i f ( cplex . s o l v e ( ) ) f146 f i n i s h = clock ( ) ;147 long double persec = CLOCKS PER SEC;148 duration = ( f i n i s h s t a r t ) / persec ;149 cout << " " << endl ;150 cout << " This took " << duration << " seconds ." << endl ;151 f e a s [ i ] = 1 ;152 for ( int b = 0 ; b < nBits +1; b++) f153 f e a s D i s t [ i ] [ b ] = Dist [ i ] [ b ] ;154 g155 cout << endl << endl << " D i s t r i b u t i o n " << i<< " > [ " ;156 for ( int b = 0 ; b < nBits ; b++) f157 cout << Dist [ i ] [ b ] << " , " ;158 g159 cout << Dist [ i ] [ nBits ] << " ] " ;160 cout << " : " << endl << endl ;161 for ( int v1 = 0 ; v1 < nVertices ; v1++) f162 i f ( cplex . getValue ( x [ v1 ] ) > 0 . 5 ) f163 int d i f f = b i t S t r i n g D i f f ( b i t S t r i n g s [ v1 ] ,b i t S t r i n g s [ 0 ] ) ;164 cout << v1 << " " << b i t S t r i n g s [ v1 ] ;165 cout << " " << d i f f ;166 cout << endl ;167 g168 g169 g170 else f171 f i n i s h = clock ( ) ;172 duration = ( f i n i s h s t a r t ) /100 0.0;173 cout << " " << endl ;174 cout << " This took " << duration << " seconds .101Appendix E. CPDist.cpp" << endl ; ;175 f e a s [ i ] = 0 ;176 for ( int b = 0 ; b < nBits +1; b++) f177 f e a s D i s t [ i ] [ b ] = 0 ;178 g179 cout << " D i s t r i b u t i o n " << i << " > [ " ;180 for ( int b = 0 ; b < nBits ; b++) f181 cout << Dist [ i ] [ b ] << " , " ;182 g183 cout << Dist [ i ] [ nBits ] << " ] " ;184 cout<< " : " << " i n f e a s i b l e " << endl << endl <<endl ;185 g186 cout << endl ;187 cout << " " << endl ;188 MIPmodel . end ( ) ;189 g190 catch ( IloException& e ) f191 c e r r << " Concert exception caught : " << e <<endl ;192 g193 catch ( . . . ) f194 c e r r << "Unknown exception caught " << endl ;195 g196 g197 cout << endl << endl << endl << endl ;198 cout << " "<< endl ;199 cout << " "<< endl ;200 cout << " "<< endl ;201 cout << " F e a s i b l e D i s t r i b u t i o n s : " << endl << endl ;202 int feasSolutionCounter = 0 ;203 for ( i = 0 ; i < solutionCounter ; i++) f102Appendix E. CPDist.cpp204 i f ( f e a s [ i ] > 0 . 5 ) f205 cout << " F e a s i b l e D i s t r i b u t i o n " <<feasSolutionCounter << " ( D i s t r i b u t i o n " << i<< " ) > [ " ;206 for ( int b = 0 ; b < nBits ; b++) f207 cout << f e a s D i s t [ i ] [ b ] << " , " ;208 g209 cout << f e a s D i s t [ i ] [ nBits ] << " ] " << endl ;210 feasSolutionCounter++;211 g212 g213 env . end ( ) ;214 g103
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Hypercube coloring and the structure of binary codes
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Hypercube coloring and the structure of binary codes Rix, James Gregory 2008-11-24
pdf
Page Metadata
Item Metadata
Title | Hypercube coloring and the structure of binary codes |
Creator |
Rix, James Gregory |
Publisher | University of British Columbia |
Date Issued | 2008 |
Description | A coloring of a graph is an assignment of colors to its vertices so that no two adjacent vertices are given the same color. The chromatic number of a graph is the least number of colors needed to color all of its vertices. Graph coloring problems can be applied to many real world applications, such as scheduling and register allocation. Computationally, the decision problem of whether a general graph is m-colorable is NP-complete for m ≥ 3. The graph studied in this thesis is a well-known combinatorial object, the k-dimensional hypercube, Qk. The hypercube itself is 2-colorable for all k; however, coloring the square of the cube is a much more interesting problem. This is the graph in which the vertices are binary vectors of length k, and two vertices are adjacent if and only if the Hamming distance between the two vectors is at most 2. Any color class in a coloring of Q2k is a binary (k;M, 3) code. This thesis will begin with an introduction to binary codes and their structure. One of the most fundamental combinatorial problems is finding optimal binary codes, that is, binary codes with the maximum cardinality satisfying a specified length and minimum distance. Many upper and lower bounds have been produced, and we will analyze and apply several of these. This leads to many interesting results about the chromatic number of the square of the cube. The smallest k for which the chromatic number of Q2k is unknown is k = 8; however, it can be determined that this value is either 13 or 14. Computational approaches to determine the chromatic number of Q28 were performed. We were unable to determine whether 13 or 14 is the true value; however, much valuable insight was learned about the structure of this graph and the computational difficulty that lies within. Since a 13-coloring of Q28 must have between 9 and 12 color classes being (8; 20; 3) binary codes, this led to a thorough investigation of the structure of such binary codes. |
Extent | 716189 bytes |
Subject |
Combinatorial object k-dimensional hypercube Color class Binary codes structure Chromatic number of the square of the cube Graph coloring Maximum cardinality Chromatic number Binary vectors |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-11-24 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0066806 |
URI | http://hdl.handle.net/2429/2809 |
Degree |
Master of Science - MSc |
Program |
Interdisciplinary Studies |
Affiliation |
Graduate Studies, College of (Okanagan) |
Degree Grantor | University of British Columbia |
Graduation Date | 2008-11 |
Campus |
UBCO |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 24-ubc_2008_fall_rix_james.pdf [ 699.4kB ]
- Metadata
- JSON: 24-1.0066806.json
- JSON-LD: 24-1.0066806-ld.json
- RDF/XML (Pretty): 24-1.0066806-rdf.xml
- RDF/JSON: 24-1.0066806-rdf.json
- Turtle: 24-1.0066806-turtle.txt
- N-Triples: 24-1.0066806-rdf-ntriples.txt
- Original Record: 24-1.0066806-source.json
- Full Text
- 24-1.0066806-fulltext.txt
- Citation
- 24-1.0066806.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.24.1-0066806/manifest