M.Sc Thesis | |

M.Sc Student | Baum Tomer |
---|---|

Subject | The Hamming Number of Graphs |

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

_{}

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 *tK _{2}* -
namely the union of

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 *(n _{1},n_{2})*
.

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.