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 language | English (US) |
---|---|
Pages (from-to) | 217-225 |
Number of pages | 9 |
Journal | Graphs and Combinatorics |
Volume | 13 |
Issue number | 3 |
DOIs | |
State | Published - 1997 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics