Geodesic
Long paths in the distance graphs in vector spases over finite fields
Čebyševskij sbornik, Tome 19 (2018) no. 3, pp. 311-317.

Voir la notice de l'article provenant de la source Math-Net.Ru

We study the following task. Let $E \subset \mathbb{F}_{q}^{d}$, be the subset of the $d-$ dimensional vector space over the finite field with $q$ elements. We define so-called distance graph of the set $E$ with distance equal to one. The distance between the vertices $x,y \in E$ is defined as follows $\parallel x - y \parallel=(x_{1}-y_{1})^{2}+\ldots +(x_{d}-y_{d})^{2}$. The vertices of the distance graph are the elements of $E$ and a pair of vertices $x,y \in E$ are connected by an edge if the distance between them is equal to one. In this paper long paths in the graph are studied. Namely the lower estimate for the length of the longest non-overlapping path in this graph is obtained. Under certain conditions, it is proved that the length of such path consists of the most of vertices of the set $E$. This complements the result from the paper of A. Iosevich and co-authors. In the proof we use some combinatoric arguments and results obtained by M. Rudnev and A. Iosevich and also joint result of M. Bennett, J. Chapman, D. Covert, D. Hart, A. Iosevich and J. Pakianathan. The main idea of constructing a long path in such a graph is as follows. We construct many paths of shorter length by standard methods. Further, based on the joint result of M.Rudnev and A. Iosevich on the distribution of distances between elements of the set $E$, we conclude that there exist a pair of vertices of two different paths with distance one. Thus, it is possible to connect some two paths already constructed for their vertices and get a longer path. This procedure is repeated iteratively until the path of the given length is constructed. We note that this method and the main result remains true for such distance graphs with any non-zero distance.
Keywords: finite fields, distance, distance graph, graph paths. 
@article{CHEB_2018_19_3_a24,
     author = {Yu. N. Shteinikov},
     title = {Long paths in the distance graphs in vector spases over finite fields},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {311--317},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a24/}
}
TY  - JOUR
AU  - Yu. N. Shteinikov
TI  - Long paths in the distance graphs in vector spases over finite fields
JO  - Čebyševskij sbornik
PY  - 2018
SP  - 311
EP  - 317
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a24/
LA  - ru
ID  - CHEB_2018_19_3_a24
ER  - 
%0 Journal Article
%A Yu. N. Shteinikov
%T Long paths in the distance graphs in vector spases over finite fields
%J Čebyševskij sbornik
%D 2018
%P 311-317
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a24/
%G ru
%F CHEB_2018_19_3_a24
Yu. N. Shteinikov. Long paths in the distance graphs in vector spases over finite fields. Čebyševskij sbornik, Tome 19 (2018) no. 3, pp. 311-317. http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a24/

[1] S. D. Adhikari, A. Mukhopadhyay, M. Ram Murty, “The analog of the Erdos distance problem in finite fields”, Int. J. Number Theory, 13:9 (2017), 2319–2334 | MR

[2] M. Bennett, J. Chapman, D. Covert, D. Hart, A. Iosevich, J. Pakianathan, “Long paths in the distance graph over large subsets of vector spaces over finite fields”, J. Korean Math. Soc., 53 (2016), 115–126 | MR | Zbl

[3] J. Chapman, M. B. Erdogan, D. Hart, A. Iosevich, D. Koh, “Pinned distance sets, k-simplices, Wolff's exponent in finite fields and sum-product estimates”, Math Z, 271:1–2 (2012), 63–93 | MR | Zbl

[4] A. Iosevich, M. Rudnev, “Erdos distance problem in vector spaces over finite fields”, Transactions of the AMS, 359:12 (2007), 6127–6142 | MR | Zbl