Submission date: 3 April 2022

Abstract:

Szemerédi's regularity lemma is a powerful tool in graph theory. It states that for every large enough graph, there exists a partition of the edge set with bounded size such that most induced subgraphs are quasirandom. When the graph is a definable set φ(x, y) in a finite field F_q, Tao's algebraic graph regularity lemma shows that there is a partition of the graph φ(x, y) such that all induced subgraphs are quasirandom and the error bound on quasirandomness is O(q^{-1/4}). In this work we prove an algebraic hypergraph regularity lemma for definable sets in finite fields, thus answering a question of Tao. We also extend the algebraic regularity lemma to definable sets in the difference fields (F_q^{alg}, x^q) and we offer a new point of view on the geometric content of the algebraic regularity lemma.

Mathematics Subject Classification:

Keywords and phrases:

Full text arXiv 2204.01158: pdf, ps.