The sequence of prime gaps is graphic

Abstract

Let us call a simple graph on $n\ge 2$ vertices a prime gap graph if its vertex degrees are $1$ and the first $n-1$ prime gaps. We show that such a graph exists for every large $n$, and in fact for every $n\ge 2$ if we assume the Riemann hypothesis. Moreover, an infinite sequence of prime gap graphs can be generated by the so-called degree preserving growth process. This is the first time a naturally occurring infinite sequence of positive integers is identified as graphic. That is, we show the existence of an interesting, and so far unique, infinite combinatorial object.

arXiv comment14 pages, LaTeX2e; v2: revised version incorporating suggestions by the referee (e.g. the formal remarks below Theorems 2.2 and 2.4 are new)

References in corpus (1)

• Fourier optimization and prime gaps

Cited by in corpus (2)

• New results on graph matching from degree preserving growth
• Degree-preserving graph dynamics -- a versatile process to construct random networks