M.Sc Thesis

M.Sc StudentBaum Tomer
SubjectThe Hamming Number of Graphs
DepartmentDepartment of Mathematics
Supervisor PROF. Roy Meshulam


This work is concerned with the following notion of vector representation of graphs.

Let G=(V,E) be a graph. Let d(x,y) denote the Hamming distance of two binary vectors

x,y{0,1}N. A Hamming representation of G is a function  φ:V→{0,1}N such that:

The threshold of a Hamming representation φ is

Define the Hamming number H(G) of G to be min T(φ) as φ ranges over all Hamming representations φ of G.

It is easy to see that H(G) is always finite.

In this work we study H(G) for various families of graphs and also provide some general lower and upper bounds.

Our first result deals with the graph tK2 - namely the union of t disjoint edges on n=2t vertices.

Boros, Gurvich and Meshulam showed that:


The proof of (#) depends on an important exterior algebra method of Lovàsz and on a set theoretic result of Füredi.

 In Chapter 1 we describe this result and its applications to the proof of .(#)

We then improve the arguments used by Boros, Gurvich and Meshulam to obtain:

Theorem 1

In chapter 2 we address the problem of estimating H(G) for bounded degree graphs. Let ∆(G) denote the max degree of G.

Using a probabilistic approach we show:

Theorem 2

Chapter 3 deals with Hamming representations of the disjoint union of two graphs. In particular we prove the following

Theorem 3.1.2

Coupling this estimate with construction based on symmetric Block Designs facilitates the exact determination of

for infinitely many pairs (n1,n2) .

In particular, by using construction based Hadamard matrices and on finite projective spaces, we show the following

two results:

Theorem 3.1.7

For infinitely many n's  

Theorem 3.1.12

For infinitely many pairs (k,n)  

Chapter 3 includes brief discussion of Hadamard matrices and of finite projective spaces.