May 2, 3:30pm, Wean 8220

Andrzej Dudek, Western Michigan University

On Ramsey-type numbers

Andrzej Dudek, Western Michigan University

On Ramsey-type numbers

Abstract:

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