Long paths in the distance graph over large subsets of vector spaces over finite fields

Abstract: Let

E s u b s e t {B b b F}_{q}^{d}

, the

d

-dimensional vector space over a finite field with

q

elements. Construct a graph, called the distance graph of

E

, by letting the vertices be the elements of

E

and connect a pair of vertices corresponding to vectors

x, y i n E

by an edge if

| | x - y | | = {(x_{1} - y_{1})}^{2} + d o t s + {(x_{d} - y_{d})}^{2} = 1

. We shall prove that if the size of

E

is sufficiently large, then the distance graph of

E

contains long non-overlapping paths and vertices of high degree.

Recommendations

Cited In (13)

This page was built for publication: Long paths in the distance graph over large subsets of vector spaces over finite fields