Constructive bounds for a Ramsey-type problem

Noga Alon, Michael Krivelevich

Research output: Contribution to journalArticlepeer-review

49 Scopus citations

Abstract

For every fixed integers r, s satisfying 2 ≤ r < s there exists some ε = ε(r,s) > 0 for which we construct explicitly an infinite family of graphs Hr,s,n, where Hr,s,n has n vertices, contains no clique on s vertices and every subset of at least n1-ε of its vertices contains a clique of size r. The constructions are based on spectral and geometric techniques, some properties of Finite Geometries and certain isoperimetric inequalities.

Original languageEnglish (US)
Pages (from-to)217-225
Number of pages9
JournalGraphs and Combinatorics
Volume13
Issue number3
DOIs
StatePublished - 1997
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Constructive bounds for a Ramsey-type problem'. Together they form a unique fingerprint.

Cite this