Improved bounds for embedding certain configurations in subsets of vector spaces over finite fields

2023/08/18 by Paige Bright, Bright, Paige, Xinyu Fang +7
Computer Science · Engineering · Mathematics · #52C10 #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2308.09215

openalex publication_date 2023/08/18 · openalex created_date 2023/08/22 · openalex updated_date 2026/07/28

Abstract

The fourth listed author and Hans Parshall (\citeIosevichParshall) proved that if E ⊂ \mathbb F_q^d, d ≥ 2, and G is a connected graph on k+1 vertices such that the largest degree of any vertex is m, then if |E| ≥ C q^m+(d-1)/(2), for any t>0, there exist k+1 points x¹, …, x^k+1 in E such that ||xⁱ-x^j||=t if the i'th vertex is connected to the j'th vertex by an edge in G. In this paper, we give several indications that the maximum degree is not always the right notion of complexity and prove several concrete results to obtain better exponents than the Iosevich-Parshall result affords. This can be viewed as a step towards understanding the right notion of complexity for graph embeddings in subsets of vector spaces over finite fields.

Related

• Embedding distance graphs in finite field vector spaces
• Generalized point configurations in \mathbb F_q^d
• Reducing the maximum degree of a graph: comparisons of bounds
• Paley-like graphs over finite fields from vector spaces
• Long paths in the distance graph over large subsets of vector spaces over finite fields