Premium
There exist graphs with super‐exponential Ramsey multiplicity constant
Author(s) -
Fox Jacob
Publication year - 2008
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20256
Subject(s) - combinatorics , mathematics , conjecture , ramsey's theorem , monochromatic color , multiplicity (mathematics) , graph , discrete mathematics , counterexample , ramsey theory , upper and lower bounds , physics , mathematical analysis , optics
The Ramsey multiplicity M ( G ; n ) of a graph G is the minimum number of monochromatic copies of G over all 2‐colorings of the edges of the complete graph K n . For a graph G with a automorphisms, ν vertices, and E edges, it is natural to define the Ramsey multiplicity constant C ( G ) to be $\lim_{{n} \to \infty} {M}(G;n){a/v}!{n \choose v}$ , which is the limit of the fraction of the total number of copies of G which must be monochromatic in a 2‐coloring of the edges of K n . In 1980, Burr and Rosta showed that 0 ≥ C ( G ) ≤ 2 1− E for all graphs G , and conjectured that this upper bound is tight. Counterexamples of Burr and Rosta's conjecture were first found by Sidorenko and Thomason independently. Later, Clark proved that there are graphs G with E edges and 2 E −1 C ( G ) arbitrarily small. We prove that for each positive integer E , there is a graph G with E edges and C ( G ) ≤ E − E /2 + o ( E ) . © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 89–98, 2008