Ramsey graphs cannot be defined by real polynomials

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Let P(x,y,n) be a real polynomial and let {Gn} be a family of graphs, where the set of vertices of Gn is {1,2,…,n} and for 1 ≤ i < j ≤ n {i,j} is an edge of Gn iff P(i,j,n) > 0. Motivated by a question of Babai, we show that there is a positive constant c depending only on P such that either Gn or its complement Gn contains a complete subgraph on at least c21/2√log n vertices. Similarly, either Gn or Gn contains a complete bipartite subgraph with at least cn1/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.

Original languageEnglish (US)
Pages (from-to)651-661
Number of pages11
JournalJournal of Graph Theory
Volume14
Issue number6
DOIs
StatePublished - Dec 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

Fingerprint

Dive into the research topics of 'Ramsey graphs cannot be defined by real polynomials'. Together they form a unique fingerprint.

Cite this