Ramsey simplicity of random graphs

A graph G is q-Ramsey for another graph H if in any q-edge-colouring of G there is a monochromatic copy of H, and the classic Ramsey problem asks for the minimum number of vertices in such a graph. This was broadened in the seminal work of Burr, Erdős, and Lovász to the investigation of other extremal parameters of Ramsey graphs, including the minimum degree. It is not hard to see that if G is minimally q-Ramsey for H we must have δ(G) ≥ q(δ(H) − 1) + 1, and we say that a graph H is q-Ramsey simple if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving that the random graph G(n, p) is almost surely 2-Ramsey simple when lognn p n−2/3. In this paper, we explore this question further, asking for which pairs p = p(n) and q = q(n, p) we can expect G(n, p) to be q-Ramsey simple. We first extend Grinshpun’s result by showing that G(n, p) is not just 2-Ramsey simple, but is in fact q-Ramsey simple for any q = q(n), provided p n−1 or lognn p n−2/3. Next, when p lognn1/2, we find that G(n, p) is not q-Ramsey simple for any q ≥ 2. Finally, we uncover some interesting behaviour for intermediate edge probabilities. When n−2/3 p n−1/2, we find that there is some finite threshold q = q (H), depending on the structure of the instance H ∼ G(n, p) of the random graph, such that H is q-Ramsey simple if and only if q ≤ q. Aside from a couple of logarithmic factors, this resolves the qualitative nature of the Ramsey simplicity of the random graph over the full spectrum of edge probabilities.

Subjects

minimum degree | Ramsey Theory | random graphs

DDC Class

510: Mathematics

Publication version

publishedVersion

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

ramsey-simplicity-of-random-graphs.pdf

Type

Main Article

Size

526.58 KB

Format

Adobe PDF

Options

Ramsey simplicity of random graphs