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

M. Bennett; J. Chapman; D. Covert; D. Hart; A. Iosevich; J. Pakianathan

paper

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

arXiv:1406.0107

Abstract

Let $E \subset 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 \in E$ by an edge if $∣∣ x - y ∣∣ = (x_{1} - y_{1})^{2} + \dots + (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.