ACO The ACO Seminar (2012-2013)

May 2, 3:30pm, Wean 8220
Andrzej Dudek, Western Michigan University
On Ramsey-type numbers


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

Back to the ACO home page