A random model for the Paley graph

DOI10.1093/QMATH/HAW037MaRDI QIDQ2987019zbMATH OpenOpenAlexFDO

Authors Rudi Mrazović

Publication date 17 May 2017

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

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

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)

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$.

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

Cited in

(4)

• Extractors in Paley graphs: a random model
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• The Paley graph conjecture and Diophantine \(m\)-tuples
• scientific article; zbMATH DE number 17680 (Why is no real title available?)

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)