Combinatorics Seminar
Andrzej Dudek
Western Michigan
On the Ramsey-Turan number with small independence number
Abstract: In this talk we consider the following question motivated by the classical Turan and Ramsey theorems. What is the maximum number of edges in a K_t-free graph G of order n with the s-independence number smaller than f(n) (where the s-independence number is the maximum number of vertices in a K_s-free induced subgraph of G)? This problem attracted a considerable amount of attention and has been mainly studied for f not too much smaller than n. In this talk we consider f(n) = n^d for d<1. In particular, we show that the maximum number of edges in a K_{s+1}-free graph of order n with the s-independence number at most n^d (for any 1/2 < d < 1) is roughly speaking n^{1+d}.
Monday February 13, 2017 at 2:00 PM in SEO 612