Premium
Ramsey graphs cannot be defined by real polynomials
Author(s) -
Alon Noga
Publication year - 1990
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.3190140605
Subject(s) - combinatorics , mathematics , bipartite graph , ramsey's theorem , complement (music) , discrete mathematics , graph , phenotype , biochemistry , chemistry , complementation , gene
Let P ( x,y,n ) be a real polynomial and let { G n } be a family of graphs, where the set of vertices of G n is {1,2,…, n } and for 1 ≤ i < j ≤ n { i,j } is an edge of G n iff P ( i,j,n ) > 0. Motivated by a question of Babai, we show that there is a posit iv e constant c depending only on P such that either G n or its complement G n contains a complete subgraph on at least c 2 1/2√log n vertices. Similarly, either G n or G n contains a complete bipartite subgraph with at least cn 1/2 vertices in each color class. Similar results are proved for graphs defined by real polynomials in a more general way, showing that such graphs satisfy much stronger Ramsey bounds than do random graphs. This may partially explain the difficulties in finding an explicit construction for good Ramsey graphs.