 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  
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

Genre  
Type  
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  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Graduation Date 
200811

Campus  
Scholarly Level 
Graduate

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionNonCommercialNoDerivatives 4.0 International