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

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

Título: Tiling with triangles

Palestrante: Julia Boettcher

Data: sexta, 09 de outubro de 2009, 14h00

Local: Auditório do NUMEC

Resumo:

A  well-known  theorem  of  Erdos  and  Gallai  answers  the
following  question: How  many edges  does a  graph  need in
order  to  guarantee a  matching  of  a  certain size?  More
precisely, for all  values of n and k,  what is the smallest
number e(n,k) such  that any graph G on  n vertices and with
e(n,k) edges contains a matching with k edges?

We consider the analogous question for vertex disjoint
triangles in G (instead of matching edges).

Joint work with Peter Allen, Jan Hladky, and Diana Piguet.