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

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

Título:      Hypergraph containers and counting independent 
             sets
            
Palestrante: David William Saxton
             Instituto de Matemática Pura e Aplicada

Hora e Data: 09h00m, quarta-feira, 31 de outubro de 2012

Local:       Sala Multi-usos do Numec

Resumo:

Many  problems  in   combinatorics  come  down  to  counting
independent sets in an appropriately defined hypergraph, for
example: counting H-free graphs, and counting subsets of [N]
with no solution  to a given linear equation.  Some of these
problems  are still  open, such  as counting  the  number of
H-free graphs for general bipartite H.

We present a structural  result, namely that the independent
sets of a hypergraph are  contained in a small collection of
'containers',   which  implies   a   corresponding  counting
result.  The general  counting  problem is  thus reduced  to
calculating  an  appropriate  parameter of  the  hypergraph,
which controls  the number  of containers required  to cover
the independent sets.

This is joint work with Andrew Thomason.