 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
UBC Theses and Dissertations
Hypercube coloring and the structure of binary codes Rix, James Gregory
Abstract
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 mcolorable is NPcomplete for m ≥ 3. The graph studied in this thesis is a wellknown combinatorial object, the kdimensional hypercube, Qk. The hypercube itself is 2colorable 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 13coloring 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.
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 mcolorable is NPcomplete for m ≥ 3.
The graph studied in this thesis is a wellknown combinatorial object,
the kdimensional hypercube, Qk. The hypercube itself is 2colorable 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 13coloring 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; kdimensional 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  20081124 
Provider  Vancouver : University of British Columbia Library 
Rights  AttributionNonCommercialNoDerivatives 4.0 International 
DOI  10.14288/1.0066806 
URI  
Degree  Master of Science  MSc 
Program  Interdisciplinary Studies 
Affiliation  Graduate Studies, College of (Okanagan) 
Degree Grantor  University of British Columbia 
Graduation Date  200811 
Campus  UBCO 
Scholarly Level  Graduate 
Rights URI  
Aggregated Source Repository  DSpace 
Item Media
Item Citations and Data
License
AttributionNonCommercialNoDerivatives 4.0 International