Naslov
A Random Model for the Paley Graph

Autori
Mrazović, Rudi

Izvornik
Quarterly journal of mathematics (0033-5606) 68 (2017), 1; 193-206

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Paley graph

Sažetak
For a prime $p$ we define the Paley graph to be the graph with the set of vertices $\mathbb{; ; ; ; Z}; ; ; ; /p\mathbb{; ; ; ; Z}; ; ; ; $, 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(\log p\log\log\log p)$ (even $\Omega(\log p\log\log 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 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(\log p\log\log p)$, whilst (ii) for almost all primes the clique number is $(2+o(1))\log p$.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA