2016/03/02 by Rudi Mrazović, Mrazović, Rudi · 1 citation
Mathematics · #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Number Theory (math.NT) #math.NT
paper · pdf · doi:10.48550/arxiv.1603.00684
13 pages
arxiv created 2016/03/02 · openalex publication_date 2016/03/02 · arxiv updated 2016/03/03 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
For a prime p we define the Paley graph to be the graph with the set of vertices ℤ/pℤ, 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 Ω(log plogloglog p) (even Ω(log ploglog p), 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 Ω(log ploglog p), whilst (ii) for almost all primes the clique number is (2+o(1))log p.