A random model for the Paley graph

DOI10.1093/QMATH/HAW037zbMATH Open1427.11011arXiv1603.00684OpenAlexW2963425882MaRDI QIDQ2987019FDOQ2987019

Authors: Rudi Mrazović 

Publication date: 17 May 2017

Published in: The Quarterly Journal of Mathematics (Search for Journal in Brave)

Abstract: For a prime $p$ we define the Paley graph to be the graph with the set of vertices $mathbbZ/pmathbbZ$, and with edges connecting vertices whose sum is a quadratic residue. Paley graphs are notoriously difficult to study, particularly finding bounds for their clique numbers. For this reason, it is desirable to have a random model. A well known result of Graham and Ringrose shows that the clique number of the Paley graph is $Omega(logplogloglogp)$ (even $Omega(logploglogp)$, under the generalized Riemann hypothesis) for infinitely many primes $p$ -- a behaviour not detected by the random Cayley graph which is hence deficient as a random model for for the Paley graph. In this paper we give a new probabilistic model which incorporates some multiplicative structure and as a result captures the Graham-Ringrose phenomenon. We prove that if we sample such a random graph independently for every prime, then almost surely (i) for infinitely many primes $p$ the clique number is $Omega(logploglogp)$, whilst (ii) for almost all primes the clique number is $(2+o(1))logp$.

Full work available at URL: https://arxiv.org/abs/1603.00684

Recommendations

• Counting sets with small sumset, and the clique number of random Cayley graphs
• CLIQUE NUMBERS OF PALEY GRAPHS
• On the clique number of Paley graphs of prime power order
• Extractors in Paley graphs: a random model
• On certain induced subgraphs of Paley graphs

zbMATH Keywords

clique numberPaley graphquadratic residues

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Strong limit theorems (60F15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial probability (60C05) Power residues, reciprocity (11A15) Arithmetic combinatorics; higher degree uniformity (11B30)

Cited In (4)

• Extractors in Paley graphs: a random model
• Title not available (Why is that?)
• The Paley graph conjecture and Diophantine \(m\)-tuples
• Title not available (Why is that?)

This page was built for publication: A random model for the Paley graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2987019)