In a graph G, a set S of V(G) is called s-independent if the subgraph
of G induced by S does not contain K_s. Let the s-independence number
of G, denoted by \alpha_s(G), be the size of the largest s-independent
set in G. (Hence, in particular, \alpha_2(G) is the standard
independence number.) The classical Ramsey number R(t,u) can be defined
in this language as the smallest integer n such that \alpha_2(G) ≥ u
for every K_t-free graph G of order n. A more general problem results
by replacing the standard independence number by the s-independence
number for some 2 ≤ s < t. Following this approach, in 1962
Erdős and Rogers introduced the function
f_{s,t}(n) = min { \alpha_s(G) : G is a graph of order n that does
not contain K_t }.
In this talk, we present some old and recent developments concerning
this function. In particular, we partially confirm an old conjecture of
Erdős by showing that
lim_{n → ∞} (f_{s+1,s+2}(n))(f_{s,s+2}(n)) = ∞
for any s ≥ 4 (joint work with John Retter and Vojta Rödl).
Furthermore, we discuss some extensions for hypergraphs (joint work
with Dhruv Mubayi).
The ACO Seminar (2012-2013)