Minimum-degree Ramsey lower bound
ID: minimum-degree-ramsey-lower-bound
For a finite simple graph of minimum degree of a graph , its ordinary two-colour graph Ramsey number satisfiesThe lower bound also applies when contains a subgraph of minimum degree at least , since a monochromatic copy of would contain a monochromatic copy of that subgraph. The paragraph before Corollary1.7 of Ordered Ramsey numbers by David Conlon and others records this ordinary Ramsey bound before comparing it with ordered Ramsey numbers.[ref]
Ordered Ramsey numbers by David Conlon and others. Printed p.5, paragraph immediately before Corollary1.7
For , this gives . Thus even without using the entire degree sequence, a large minimum degree already forces an exponential obstruction to guaranteeing a monochromatic copy.
New to topics? Read the docs here!