Paley graphs

Paley graphs play a role in my research, and they are an important family of graphs in combinatorics and graph theory. They are examples of quasi-random graphs: explicit, deterministic networks exhibiting properties we typically expect to see asymptotically in random graphs.

Consider a prime power p congruent to 1 (mod 4), and let vertices be the elements of the finite field of order p.  Two distinct vertices are adjacent if their difference is a non-zero square in the field.  This is the p–Paley graph.

For example, in the case of p = 5, the finite field has elements 0, 1, 2, 3, and 4, and the non-zero squares are 1 and 4 (which equals -1 (mod 5)). So differences should be 1 or -1. Thus, in the 5-Paley graph each vertex i is adjacent to i+1 and i-1 (mod 5). This is just the 5-cycle, as depicted below.

Paley graphs are isomorphic to their complements and are strongly regular. We also know their eigenvalues, and understand several graph-theoretic parameters for these graphs.

My own interest in them comes from adjacency properties. They are an explicit family of finite graphs witnessing the n-e.c. properties, which are satisfied by the infinite random or Rado graph.

Paley and BIRS

I just spoke at the Banff International Research Station (or BIRS) on a new class of infinite random geometric graphs, co-discovered with co-authors Jeannette Janssen and Anthony Quas. These graphs arise from random graphs arising from finite- and infinite-dimensional Banach spaces, and I implicitly referenced Paley graphs in my talk. Tomasz Luczak commented at the end of my talk that Paley’s grave is in the Old Banff Cemetery, which is a five-minute walk from the institute.

I was intrigued!

I visited there the cemetery the following morning, and after some searching, found his grave by the main entrance gateway.

Who was Raymond Edward Alan Christopher Paley?

Paley was a young British mathematician who studied at Trinity College, Cambridge University. He was taught by the famous pair of Hardy and Littlewood at Cambridge, and became Littlewood’s student. He won several awards at Cambridge, and soon began making important mathematical progress with Littlewood and others.  For a junior mathematician, he collaborated with a stellar group of mathematicians including Zygmund, Wiener, and Pólya. His work focused mainly on analysis, and there are theorems that bear his name in complex analysis and harmonic analysis. He also discovered what are now called Paley Hadamard matrices, which inspired the Paley graph construction defined above (named in his honor).

Paley died at the too young age of 26. He was killed by an avalanche while skiing at Deception Pass, Fossil Mountain in Banff National Park. He was on vacation there while visiting Norbert Weiner at M.I.T., after winning a Rockefeller International Research Fellowship to study in the U.S.

Below is the only photo I could find of Raymond Paley.

Paley showed incredible promise as an up-and-coming mathematician, and who knows how he would have influenced twentieth century mathematics if he had lived longer. Visiting his grave in Banff was a profound experience, bringing full circle a thread of my own research that began over twenty years ago.

I dedicate this blog to his memory.

Anthony Bonato