PDF
Discussiones Mathematicae Graph Theory 32(2) (2012)
279-287
DOI: https://doi.org/10.7151/dmgt.1597
On Kaleidoscopic Pseudo-randomness of Finite Euclidean Graphs
Le Anh Vinh
Faculty of Mathematics, Mechanics and Informatics |
Abstract
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.
References
[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
Close