Premium
A Disproof of a Conjecture of Erdős in Ramsey Theory
Author(s) -
Thomason Andrew
Publication year - 1989
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/s2-39.2.246
Subject(s) - conjecture , combinatorics , ramsey's theorem , mathematics , counterexample , complement (music) , ramsey theory , monochromatic color , graph , order (exchange) , discrete mathematics , physics , biochemistry , chemistry , finance , complementation , optics , economics , gene , phenotype
Denote by k t ( G ) the number of complete subgraphs of order t in the graph G . Let c(t) = min { k t (G) + k t (G) ; | G | = n}(nt)− 1whereG ¯denotes the complement of G and | G | the number of vertices. A well‐known conjecture of Erdős, related to Ramsey's theorem, is that lim n →∞ c t ( n ) = 2 1−(½) . This latter number is the proportion of monochromatic K t 's in a random colouring of K n . We present counterexamples to this conjecture and discuss properties of the extremal graphs.