============================================================
   Seminário de Teoria da Computação e Combinatória (TCC)

============================================================

Título:      Rescuing Burr and Erdös by restricting expansion

            
Palestrante: Peter D. Allen
             IME-USP

Hora e Data: 14h, sexta-feira, 24 de setembro de 2010

Local:       auditório do NUMEC

Resumo:

The  Ramsey number $R(G,H)$  is defined  to be  the smallest
number $N$ of  vertices such that whenever the  edges of the
complete graph  $K_N$ are coloured with red  and blue, there
must exist either  a red $G$ or a  blue $H$.  The systematic
study of this  parameter was initiated in the  1970s by Burr
and  Erd\H{o}s.  Their  results dealt  only with  some quite
restricted classes of sparse graphs,  but led them to make a
general conjecture.  There is  a simple construction of Burr
giving  a  lower  bound  on $R(G,H)$.   Burr  and  Erd\H{o}s
conjectured that  this bound is tight for  every fixed graph
$H$ and every sufficiently large bounded degree graph $G$.

In the 1980s Brandt gave a construction using bounded degree
expander graphs showing that the conjecture is very far from
true.  We show that the  use of expansion is necessary: when
$G$ is a large graph  whose maximum degree and expansion are
restricted, the conjecture of Burr and Erd\H{o}s is true.

This is joint work with Graham Brightwell and Jozef Skokan.