Discussiones Mathematicae Graph Theory 32(2) (2012) 279-287
doi: 10.7151/dmgt.1597

[BIBTex] [PDF] [PS]

On Kaleidoscopic Pseudo-randomness of Finite Euclidean Graphs

Le Anh Vinh

Faculty of Mathematics, Mechanics and Informatics
Hanoi University of Science
Vietnam National University, Hanoi


D. Hart, A. Iosevich, D. Koh, S. Senger and I. Uriarte-Tuero (2008) showed that the distance graphs has kaleidoscopic pseudo-random property, i.e. sufficiently large subsets of d-dimensional vector spaces over finite fields contain every possible finite configurations. In this paper we study the kaleidoscopic pseudo-randomness of finite Euclidean graphs using probabilistic methods.

Keywords: finite Euclidean graphs, kaleidoscopic pseudo-randomness

2010 Mathematics Subject Classification: 05C15, 05C80.


[1]N. Alon and J.H. Spencer, The Probabilistic Method (Willey-Interscience, 2000).
[2]E. Bannai, O. Shimabukuro and H. Tanaka, Finite Euclidean graphs and Ramanujan graphs, Discrete Math. 309 (2009) 6126--6134, doi: 10.1016/j.disc.2009.06.008.
[3]D. Hart, A. Iosevich, D. Koh, S. Senger and I. Uriarte-Tuero, Distance graphs in vector spaces over finite fields, coloring and pseudo-randomness preprint, arXiv:0804.3036v1.
[4]A. Iosevich and M. Rudnev, Erdös distance problem in vector spaces over finite fields, Trans. Amer. Math. Soc. 359 (2007) 6127--6142, doi: 10.1090/S0002-9947-07-04265-1.
[5]M. Krivelevich and B. Sudakov, Pseudo-random graphs, in: Conference on Finite and Infinite Sets Budapest, Bolyai Society Mathematical Studies X, (Springer, Berlin 2006) 1--64.
[6]S. Li and L.A. Vinh, On the spectrum of unitary finite-Euclidean graphs, Ars Combinatoria, to appear.
[7]A. Medrano, P. Myers, H.M. Stark and A. Terras, Finite analogues of Euclidean space, Journal of Computational and Applied Mathematics 68 ( 1996) 221--238, doi: 10.1016/0377-0427(95)00261-8.
[8]L.A. Vinh and D.P. Dung, Explicit tough Ramsey graphs, in: Proceedings of the International Conference on Relations, Orders and Graphs: Interaction with Computer Science, ( Nouha Editions, 2008) 139--146.
[9]L.A. Vinh, Explicit Ramsey graphs and Erdös distance problem over finite Euclidean and non-Euclidean spaces, Electronic J. Combin. 15 (2008) R5.
[10]L.A. Vinh, Szemeredi-Trotter type theorem and sum-product estimate in finite fields, European J. Combin., to appear.
[11]V. Vu, Sum-product estimates via directed expanders, Mathematical Research Letters, 15 (2008) 375--388.

Received 15 September 2008
Revised 11 May 2011
Accepted 23 May 2011