Paley-like quasi-random graphs arising from polynomials

2024/05/15 by Seoyoung Kim, Chi Hoi Yip, Kim, Seoyoung +3 · 1 citation
Mathematics · #05C48 #05C50 #05D10 #11B30 #11T06 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Number Theory (math.NT) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2405.09319

openalex publication_date 2024/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Paley graphs and Paley sum graphs are classical examples of quasi-random graphs. In this paper, we provide new constructions of families of quasi-random graphs that behave like Paley graphs but are neither Cayley graphs nor Cayley sum graphs. These graphs give a unified perspective of studying various graphs arising from polynomials over finite fields, such as Paley graphs, Paley sum graphs, and graphs arising from Diophantine tuples and their generalizations. We also obtain lower bounds on the clique and independence numbers of the graphs in these families.

Cited by

• Van Lint-MacWilliams' conjecture and maximum cliques in Cayley graphs over finite fields, II

Related

• A Paley-like graph in characteristic two
• Infinite Paley graphs
• A random model for the Paley graph
• Paley Graphs and Their Generalizations
• A degree 4 sum-of-squares lower bound for the clique number of the Paley graph