Almost spanning distance trees in subsets of finite vector spaces

Abstract

For d >= 2 and an odd prime power q, consider the vector space F-q(d) over the finite field F-q, where the distance between two points (x1, & mldr; , x(d)) and (y1, & mldr; , y(d)) is defined as & sum;(d)(i=1)(x(i) - y(i))(2). A distance graph is a graph associated with a nonzero distance to each of its edges. We show that large subsets of vector spaces over finite fields contain every nearly spanning distance tree with bounded degree in each distance. This quantitatively improves results by Bennett, Chapman, Covert, Hart, Iosevich, and Pakianathan on finding distance paths, and results by Pham, Senger, Tait, and Thu on finding distance trees. A key ingredient in proving our main result is to obtain a colorful generalization of a classical result of Haxell about finding nearly spanning bounded-degree trees in an expander.