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)|
|Number of pages||9|
|Journal||Graphs and Combinatorics|
|State||Published - 1997|
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics