Constructive bounds for a Ramsey-type problem

Noga Alon; Michael Krivelevich

doi:10.1007/BF03352998

Constructive bounds for a Ramsey-type problem

Noga Alon, Michael Krivelevich

Research output: Contribution to journal › Article › peer-review

52 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 H_r,s,n, where H_r,s,n has n vertices, contains no clique on s vertices and every subset of at least n^1-ε 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 language	English (US)
Pages (from-to)	217-225
Number of pages	9
Journal	Graphs and Combinatorics
Volume	13
Issue number	3
DOIs	https://doi.org/10.1007/BF03352998
State	Published - 1997
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1007/BF03352998

Cite this

@article{3dca7e2279c24e6294d5a82fe60222fa,

title = "Constructive bounds for a Ramsey-type problem",

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.",

author = "Noga Alon and Michael Krivelevich",

year = "1997",

doi = "10.1007/BF03352998",

language = "English (US)",

volume = "13",

pages = "217--225",

journal = "Graphs and Combinatorics",

issn = "0911-0119",

publisher = "Springer Japan",

number = "3",

}

TY - JOUR

T1 - Constructive bounds for a Ramsey-type problem

AU - Alon, Noga

AU - Krivelevich, Michael

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0001257756

UR - https://www.scopus.com/inward/citedby.url?scp=0001257756&partnerID=8YFLogxK

U2 - 10.1007/BF03352998

DO - 10.1007/BF03352998

M3 - Article

AN - SCOPUS:0001257756

SN - 0911-0119

VL - 13

SP - 217

EP - 225

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

IS - 3

ER -

Constructive bounds for a Ramsey-type problem

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this