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

  Tarde de Combinatória Extremal e Métodos Probabilísticos
============================================================

Título:      A Blow-up Lemma for arrangeable graphs
            
Palestrante: Julia Böttcher
             London School of Economics and Political Science

Hora e Data: 15h, sexta-feira, 05 de abril de 2013

Local:       Sala Multi-usos do Numec

Resumo:

The  Blow-up  Lemma  is  an  important  tool  for  embedding
spanning  graphs   H  into  dense  graphs  G.   One  of  its
+limitations is,  however, that it  can only be used  if the
maximum degree of  H is bounded by a  constant. We +recently
established a generalisation of  this lemma which can handle
even  H which are  only c-arrangeable  (and +observe  a very
weak  maximum  degree  bound).    Here  a  graph  is  called
c-arrangeable if its  vertices can be ordered in  such a way
that the  neighbours to the +right  of any vertex  v have at
most c neighbours to the left of v in total.

In the talk I will explain this lemma, discuss several
applications, and outline parts of the proof.

Joint work with Yoshiharu Kohayakawa, Anusch Taraz and
Andreas Würfl.