<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
On a Furstenberg-Katznelson-Weiss Type Theorem over Finite Fields
Le Anh Vinh
Department of Mathematics, Harvard University, Cambridge, MA 02138, USA
Annals of Combinatorics 15 (3) pp.541-547 July, 2011
AMS Subject Classification: 05C15, 05C80
Using Fourier analysis, Covert, Hart, Iosevich, and Uriarte-Tuero (2008) showed that if the cardinality of a subset of the 2-dimensional vector space over a finite field with q elements is ≥ρq2, with q−1/2≤ρ ≤ then it contains an isometric copy of ≥cρq3 triangles. In this note, we give a graph theoretic proof of this result.
Keywords: finite Euclidean graphs, pseudo-random graphs


1. Alon, N., Spencer, J.H.: The Probabilistic Method. 2nd Ed., Willey-Interscience, New York (2000)

2. Bannai, E., Shimabukuro, O., Tanaka, H.: Finite Euclidean graphs and Ramanujan graphs. Discrete Math. 309(20), 6126–6134 (2009)

3. Bourgain, J., Katz, N., Tao, T.: A sum product estimate in finite fields and Applications, Geom. Funct. Analysis 14, 27–57 (2004)

4. Chapman, J., Erdogan, M.B., Hart, D., Iosevich, A., Koh, D.: Pinned distance sets, ksimplices, Wolff’s exponent in finite fields and sum-product estimates. Math. Z. (2009) DOI:10.1007/s00209-011-0852-4

5. Covert, D., Hart, D., Iosevich, A., Uriarte-Tuero, I.: An analog of the Furstenberg- Katznelson-Weiss theorem on triangles in sets of positive density in finite field geometries. European J. Combin. (to appear)

6. Dvir, Z.: On the size of Kakeya sets in finite fields. J. Amer. Math. Soc. 22(4), 1093–1097 (2009)

7. Furstenberg, H., Katznelson, Y., Weiss, B.: Ergodic theory and configurations in sets of positive density. In: Nesetril, J., Rodl, V. (eds.) Mathematics of Ramsey Theory, pp. 184–198. Springer, Berlin (1990)

8. Hart, D., Iosevich, A.: Ubiquity of simplices in subsets of vector spaces over finite fields. Anal. Math. 34(1), 29–38 (2008)

9. Hart, D., Iosevich, A.: Sums and products in finite fields: an integral geometric viewpoint. In: Olafsson, G. et al. (eds.) Radon Transforms, Geometry, and Wavelets, pp. 129–135. Amer. Math. Soc., Providence, RI (2008)

10. Hart, D., Iosevich, A., Koh, D., Rudnev, M.: Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdos-Falconer distance conjecture, Trans. Amer. Math. Soc. 363(6), 3255–3275 (2011)

11. Iosevich, A., Koh, D.: Erdos-Falconer distance problem, exponential sums, and Fourier analytic approach to incidence theorem in vector spaces over finite fields. SIAMJ. Discrete Math. 23(1), 123–135 (2008)

12. Iosevich, A., Rudnev, M.: Erdos distance problem in vector spaces over finite fields. Trans. Amer. Math. Soc. 359(12), 6127–6142 (2007)

13. Iosevich, A., Shparlinski, I.E., Xiong, M.: Sets with integral distances in finite fields. Trans. Amer. Math. Soc. 362(4), 2189–2204 (2010)

14. Iosevich, A., Senger, S.: Orthogonal systems in vector spaces over finite fields. Electron. J. Combin. 15(1), #R151 (2008)

15. Krivelevich, M., Sudakov, B.: Pseudo-random graphs. In: Gyori, E., Katona, G.O.H., Lovász, L. (Eds.) More Sets, Graphs and Numbers, pp. 1–64. Springer, Berlin (2006)

16. Medrano, A., Myers, P., Stark, H.M., Terras, A.: Finite analogues of Euclidean space. J. Comput. Appl. Math. 68(1-2), 221–238 (1996)

17. Shparlinski, I.E.: On point sets in vector spaces over finite fields that determine only acute angle. Bull. Austral. Math. Soc. 81(1), 114–120 (2010)

18. Vinh, L.A.: Explicit Ramsey graphs and Erd˝os distance problem over finite Euclidean and non-Euclidean spaces. Electron. J. Combin. 15(1), #R5 (2008)

19. Vinh, L.A.: On the number of orthogonal systems in vector spaces over finite fields. Electron. J. Combin. 15, #N32 (2008)

20. Vinh, L.A.: On k-simplexes in (2k−1)-dimensional vector spaces over finite fields. Discrete Math. Theor. Comput. Sci. Proc. AK, 871–880 (2009)

21. Vinh, L.A.: The sovability of norm, bilinear and quadratic equations over finite fields via spectra of graphs. arXiv:0904.0441 (2009)