Hostname: page-component-669899f699-cf6xr Total loading time: 0 Render date: 2025-05-03T08:27:12.378Z Has data issue: false hasContentIssue false
  • English
  • Français

Geometric structures in pseudo-random graphs

Part of: Finite fields and commutative rings (number-theoretic aspects) Discrete geometry

Published online by Cambridge University Press:  15 March 2024

Thang Pham Open the ORCID record for Thang Pham [Opens in a new window] ,
Steven Senger Open the ORCID record for Steven Senger [Opens in a new window] ,
Michael Tait Open the ORCID record for Michael Tait [Opens in a new window]  and
Vu Thi Huong Thu
Thang Pham*
Affiliation:
University of Science, Vietnam National University, Hanoi, Vietnam
Steven Senger
Affiliation:
Department of Mathematics, Missouri State University, Springfield, MO, United States e-mail: [email protected]
Michael Tait
Affiliation:
Department of Mathematics and Statistics, Villanova University, Villanova, PA, United States e-mail: [email protected]
Vu Thi Huong Thu
Affiliation:
University of Science, Vietnam National University, Hanoi, Vietnam e-mail: [email protected]
*
e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper, we provide a general framework for counting geometric structures in pseudo-random graphs. As applications, our theorems recover and improve several results on the finite field analog of questions originally raised in the continuous setting. The results present interactions between discrete geometry, geometric measure theory, and graph theory.

Keywords

Pseudo-random graphsgeometric structuresfinite fields

MSC classification

Primary: 52C10: Erdős problems and related topics of discrete geometry
Secondary: 11T06: Polynomials
Type
Article
Information
Canadian Journal of Mathematics , Volume 77 , Issue 3 , June 2025 , pp. 1041 - 1071
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press on behalf of Canadian Mathematical Society

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

Footnotes

T. Pham was supported by the Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 101.99–2021.09. M. Tait was partially supported by National Science Foundation Grant DMS-2011553 and a Villanova University Summer Grant.

References

Bannai, E., Shimabukuro, O., and Tanaka, H., Finite Euclidean graphs and Ramanujan graphs . Discret. Math. 309(2009), no. 20, 6126–6134.CrossRefGoogle Scholar
Bennett, M., Chapman, J., Covert, D., Hart, D., Iosevich, A., and Pakianathan, J., Long paths in the distance graph over large subsets of vector spaces over finite fields . J. Korean Math. 53(2016), 115–126.CrossRefGoogle Scholar
Bennett, M., Iosevich, A., and Taylor, K., Finite chains inside thin subsets of ${\mathbb{R}}^d$ . Anal. PDE 9(2016), no. 3, 597–614.CrossRefGoogle Scholar
Bourgain, J., Katz, N., and Tao, T., A sum-product estimate in finite fields, and applications . Geom. Funct. Anal. 14(2004), no. 1, 27–57.CrossRefGoogle Scholar
Covert, D. and Senger, S., Pairs of dot products in finite fields and rings . In: Combinatorial and additive number theory II, Springer, Cham, 2015, pp. 129–138.Google Scholar
Du, X., Iosevich, A., Yumeng, O., Wang, H., and Zhang, R., An improved result for Falconer’s distance set problem in even dimensions . Math. Ann. 380(2021), no. 3, 1215–1231.CrossRefGoogle Scholar
Du, X. and Zhang, R., Sharp ${L}^2$ estimates of the Schrödinger maximal function in higher dimensions. Ann. Math. 189(2019), no. 3, 837–861.CrossRefGoogle Scholar
Dvir, Z., On the size of Kakeya sets in finite fields . J. Amer. Math. Soc. 22(2009), no. 4, 1093–1097.CrossRefGoogle Scholar
Eswarathasan, S., Iosevich, A., and Taylor, K., Fourier integral operators, fractal sets, and the regular value theorem . Adv. Math. 228(2011), no. 4, 2385–2402.CrossRefGoogle Scholar
Garaev, M. Z., An explicit sum-product estimate in ${F}_p$ . Int. Math. Res. Not. IMRN 2007(2007), Article no. rnm035, 11 pp.Google Scholar
Haemers, W., Eigenvalue techniques in design and graph theory. Ph.D. thesis, Eindhoven University of Technology, 1980.Google Scholar
Hart, D., Iosevich, A., Koh, D., and Rudnev, M., Averages over hyperplanes, sum-product theory in vector spaces over finite fields and the Erdős–Falconer distance conjecture . Trans. Amer. Math. Soc. 363(2011), no. 6, 3255–3275.CrossRefGoogle Scholar
Hart, D., Iosevich, A., and Solymosi, J., Sum-product estimates in finite fields via Kloosterman sums . Int. Math. Res. Not. IMRN 2007(2007), Article no. rnm007. https://doi.org/10.1093/imrn/rnm007 Google Scholar
Iosevich, A., Jardine, G., and McDonald, B., Cycles of arbitrary length in distance graphs on ${F}_q^d$ . Proc. Steklov Inst. Math. 314(2021), no. 1, 27–43.CrossRefGoogle Scholar
Iosevich, A., Koh, D., and Lewko, M., Finite field restriction estimates for the paraboloid in high even dimensions . J. Funct. Anal. 278(2020), no. 11, 108450.CrossRefGoogle Scholar
Iosevich, A., Kolountzakis, M., Lyubarskii, Y., Mayeli, A., and Pakianathan, J., On Gabor orthonormal bases over finite prime fields . Bull. Lond. Math. Soc. 53(2021), no. 2, 380–391.CrossRefGoogle Scholar
Iosevich, A., Mayeli, A., and Pakianathan, J., The Fuglede conjecture holds in ${\mathbb{Z}}_p\times {\mathbb{Z}}_p$ . Anal. PDE 10(2017), no. 4, 757–764.CrossRefGoogle Scholar
Iosevich, A. and Rudnev, M., Erdős distance problem in vector spaces over finite fields . Trans. Amer. Math. Soc. 359(2007), no. 12, 6127–6142.CrossRefGoogle Scholar
Iwaniec, H. and Kowalski, E., Analytic number theory, Colloquium Publications, 53, American Mathematical Society, Providence, RI, 2004.Google Scholar
Koh, D., Lee, S., Pham, T., and Shen, C.-Y., Configurations of rectangles in a set in ${F}_q^2$ . Finite Fields and Their Applications, 86(2023), 102147.CrossRefGoogle Scholar
Krivelevich, M. and Sudakov, B., Pseudo-random graphs . In: More sets, graphs and numbers, Springer, Berlin–Heidelberg, 2006, pp. 199–262.CrossRefGoogle Scholar
Kwok, W. M., Character tables of association schemes of affine type . Eur. J. Comb. 13(1992), no. 3, 167–185.CrossRefGoogle Scholar
Lewko, M., New restriction estimates for the 3-d paraboloid over finite fields . Adv. Math. 270(2015), no. 1, 457–479.CrossRefGoogle Scholar
Lewko, M., Finite field restriction estimates based on Kakeya maximal operator estimates . J. Eur. Math. Soc. 21(2019), no. 12, 3649–3707.CrossRefGoogle Scholar
Liu, B., On Hausdorff dimension of radial projections . Rev. Mat. Iberoam. 37(2020), no. 4, 1307–1319.CrossRefGoogle Scholar
Lyall, N. and Magyar, Á., Weak hypergraph regularity and applications to geometric Ramsey theory . Trans. Amer. Math. Soc. Ser. B 9(2022), no. 5, 160–207.CrossRefGoogle Scholar
Merris, R., Multilinear algebra, CRC Press, Boca Raton, FL, 1997.CrossRefGoogle Scholar
Mockenhaupt, G. and Tao, T., Restriction and Kakeya phenomena for finite fields . Duke Math J. 121(2004), no. 1, 35–74.CrossRefGoogle Scholar
Rudnev, M. and Shkredov, I. D., On the restriction problem for discrete paraboloid in lower dimension . Adv. Math. 339(2018), 657–671.CrossRefGoogle Scholar
Soukup, D. M., Embeddings of weighted graphs in Erdős-type settings . Mosc. J. Combin. Number Theory 8(2019), no. 2, 117–123.CrossRefGoogle Scholar
Vinh, L. A., The solvability of norm, bilinear and quadratic equations over finite fields via spectra of graphs . Forum Math. 26(2014), no. 1, 141–175.CrossRefGoogle Scholar
Weil, A., On some exponential sums . Proc. Natl. Acad. Sci. USA 34(1948), 204–207.CrossRefGoogle ScholarPubMed
Wolff, T., Recent work connected with the Kakeya problem . In: Prospects in mathematics (Princeton, NJ, 1996). Vol. 2, American Mathematical Society, Providence, RI, 1999, pp. 129–162.Google Scholar