The clique number of generalized Hamming graphs [Elektronische Ressource] / submitted by Elham Sharifiyazdi

Sujets

• Mathematics

Informations

• Publié par: technische_universitat_clausthal
• Publié le: 01 janvier 2007
• Nombre de lectures: 29
• Langue: English

Extrait

The Clique Number of Generalized Hamming
Graphs
Doctoral Thesis
(Dissertation)
to be awarded the degree of
Doctor rerum naturalium (Dr. rer. nat.)
submitted by
Elham Sharifiyazdi
from Iran
approved by the Faculty of Mathematics/Computer Sciences and Engineering
Clausthal University of Technology
Date of oral examination
5 October 2007Chairperson of the Board of Examiners
Prof. Dr.-Ing. N. Mu¨ller
Chief Reviewer
Prof. Dr. W. Klotz
Reviewer
Prof. Dr. J. W. SanderAcknowledgements
First and foremost, I would like to thank my supervisor, Prof. Walter Klotz.
The most influential and constructive ideas in this thesis came from him. I
am grateful to him for his enthusiastic supervision of all aspects from aca-
demic advice to correcting the punctuation in my thesis. I also thank Prof.
J. W. Sander, the second reader of this thesis, for his helpful comments.
I would like to thank the faculty and the staff of the Institute of Mathe-
matics at the Technical University of Clausthal.
Last but not least, I would like to express my love and gratitude to my
husband, my son and my parents for their love and support. This thesis is
dedicated to them.Contents
1 Introduction 3
2 Identities for Binomial Coefficients 7
3 Hamming Graphs with Even Distance 19
4 Hamming Graphs with Odd Distance 33
5 Binary Hamming Graphs 69
6 Further Results 79
7 Conclusion 95
12 CONTENTSChapter 1
Introduction
Let A ,...,A be non-empty, finite sets (alphabets). The elements of the1 n
Cartesian product
V =A ×...×A ={(x ,...,x ) : x ∈A for i = 1,...,n}1 n 1 n i i
areconsideredaswordszoflengthnwithentriesz(i) =x fromthealphabetsi
A , i = 1,...,n. The Hamming distance d(y,z) of words y,z ∈ V is thei
number of positions, in which their entries differ,
d(y,z) =|{i : y(i) =z(i),1≤i≤n}|.
Let D be a non empty subset of {1,2,...,n} and |A| = m for i = 1,...,n.i i
The (generalized) Hamming graph HG(A ,...,A ;D) has vertex set V and1 n
edge set
E ={{x,y} : x,y ∈V,d(x,y)∈D}.
We arrive at the usual definition of Hamming graphs, which we now call
’ordinary Hamming graphs’, if D ={1} (see [5]).
The structure of HG(A ,...,A ;D) does not depend on the special nature of1 n
the elements of the alphabets A , but only on their cardinalities |A| = m ,i i i
i = 1,...,n. Therefore, we write
HG(A ,...,A ;D) =HG(m ,...,m ;D)1 n 1 n
unless otherwise stated, our standard alphabet A isi
A =Z ={0,1,...,m −1}.i m ii
By the addition of integers modulo m the alphabet Z becomes a groupi mi
and V may be considered as the direct product (direct sum) of the cyclic
3
64 CHAPTER 1. INTRODUCTION
groupsZ , i = 1,...,n.mi
The zero word 0∈V has all entries equal to zero. The weight w(z) of z ∈V
is the number of nonzero entries of z. We have
w(z) =d(0,z), d(x,y) =w(x−y) for x,y,z ∈V.
Hamming graphs are Cayley graphs, [3]. The (undirected) Cayley graph
Cay(H,S) has as its vertex set the elements of the (here: additive) group
H. The set S is a subset of H, which does not contain the zero element of
H and has the property S∪(−S) = S. Vertices x,y ∈ H are connected by
an edge, if x−y ∈S.
The Hamming graph HG(m ,...,m ;D) has the additive group1 n
V =Z ⊗...⊗Zm m1 n
as its vertex set. To generate its edge set define
S ={x∈V : w(x)∈D}.
Then we have 0∈/ S, x∈S implies −x∈S and
HG(m ,...,m ;D) =Cay(V,S).1 n
The group of the Cayley graph induces a group of automorphisms acting
transitively on the vertices of the graph. Cayley graphs Cay(H,S) are ver-
tex transitive, i.e. for any two vertices x,y ∈H there is an automorphism ϕ
with y = ϕ(x). Vertices of vertex transitive graphs have isomorphic neigh-
borhoods. Therefore, these graphs are regular. The Cayley graphCay(H,S)
is regular of degree |S|.
A clique in a graph G is a complete subgraph of G, i.e. a subgraph, in
which any two vertices are connected by an edge. The clique number ω(G)
is the largest number of vertices in a clique of G.
The following proposition is a consequence of the vertex transitivity of
HG(m ,...,m ;D).1 n
Proposition 1.1. The Hamming graph HG(m ,...,m ;D) has a maximal1 n
clique C, ω(HG(m ,...,m ;D)) =|C|, which contains the zero word 0.1 n
The standard Hamming graphs we are going to investigate here have the
same alphabet Z in each position, i.e. m = ... = m = m. Moreover, them 1 n5
set of distances D consists of all distances from 1 up to a positive integer
d≤n, D ={1,2,...,d}. We simplify our notation,
HG(m,...,m;{1,...,d}) =HG(m,n,d).
| {z }
n positions
nSoHG(m,n,d) has vertex setV =Z . Distinct verticesx andy are conec-m
cted by an edge, if their Hamming distance d(x,y) is at most d.
The main subject of this thesis is the clique number ω(HG(m,n,d)).
dClearly, all words of weight at most b c induce a clique in HG(m,n,d). If
2
d+1d is odd then this clique may be extended by all words of weight with
2
a nonzero entry in the first position. So one can easily deduce the following
lower bound ω (m,n,d) for ω(HG(m,n,d)).0
Proposition 1.2. Let d = 2t+ε≥ 1, ε∈{0,1}, t∈{0}∪N,N ={1,2,...},
m,n∈N, n≥d, m≥ 2. Then we have
t
X n n−1j t+1ω(HG(m,n,d))≥ω (m,n,d) = (m−1) +ε (m−1) .0
j t
j=0
Webelievethatω(HG(m,n,d))coincideswiththelowerboundinPropo-
sition 1.2, if n is sufficient large.
ω -Conjecture:0
For fixed parameters m,d∈N there is n =n (m,d)∈N such that0 0
ω(HG(m,n,d)) =ω (m,n,d) for every n≥n .0 0
Our main results state that the ω -conjecture is true for m = 2, i.e. for0
binary Hamming graphs, and for d≤ 6.
Theorem 1.1.
1. For positive integers m, d, m≥ 2, d≤ 6, there is n ∈N (depending0
only on d and m) such that for every n≥n0
ω(HG(m,n,d)) =ω (m,n,d).0
2. For every positive integer d there is n ∈ N (depending only on d)0
such that for every n≥n0
ω(HG(2,n,d)) =ω (2,n,d).06 CHAPTER 1. INTRODUCTION
Theproofsfrequentlyusebinomialidentities,whicharestudiedinchapter
2. Theexpressionforω (m,n,d)indicatesthatthereareprincipaldifferences0
between Hamming graphs with even or odd distance parameter d. So we de-
vote different chapters, 3 and 4, to the even and odd case. In these chapters
the ω -conjecture is proved up to d = 6 and the main tools are developed to0
prove the ω -conjecture for binary Hamming graphs in chapter 5. Finally,0
in chapter 6 we state some further results on the clique number and also
on the chromatic number of HG(m,n,d) and of its complementary graph
HG(m,n,d).
The generalized Hamming graph HG(m,n,d) is defined in [7] as the d-th
ndistance power of the ordinary Hamming graph H(m,n) = K , which ism
the n-fold Cartesian product [5] of the complete graph K . The distancem
(d)power G of an undirected graph G is obtained from G by drawing an
edge between any two distinct vertices x,y of G at distance d(x,y) ≤ d. So
(d)H (m,n) in [7] is another notation for HG(m,n,d).
In the literature little effort has been made to determine the clique num-
ber ofHG(m,n,d). More attention has been payed to the chromatic number
χ(HG(m,n,d)) [6-11,14]. Here ω (m,n,d) appears as a lower bound for the0
chromatic number. A proper coloring of HG(m,n,d) is sometimes called a
ndistance d coloring of K . Especially, distanced colorings of the hypercubem
nK or equivalently χ(HG(2,n,d)) have been investigated. But only very2
few exact values of χ(HG(m,n,d)) are known [9,10].
Definitions from graph theory omitted in this thesis can be found in [13].