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

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

Título:      Independent sets in hypergraphs
            
Palestrante: Wojciech Samotij
             University of Cambridge

Hora e Data: 14h, sexta-feira, 24 de fevereiro de 2012

Local:       Sala Multi-usos do Numec

Resumo: 

Let  V be  a  finite set.  A family  F  of subsets  of V  is
increasing if for  every A in F, all  sets containing A also
belong to F. We say that  a hypergraph H on the vertex set V
is (F,\epsilon)-stable if  every A in F induces  at least an
\epsilon fraction  of all the  edges of H.  Hypergraphs that
arise naturally in many  classical settings posses the above
property.  For example, the famous theorem of Mantel and the
`supersaturation' theorem of Erdos and Simonovits imply that
the hypergraph on the vertex set E(K_n) whose hyperedges are
the edge sets of all triangles in K_n is (F,\epsilon)-dense,
where F  is the collection of  all subgraphs of  K_n with at
least (1/4+\delta)n^2  edges. In  the talk, we  will present
the  following   theorem:  Suppose  that  H   is  a  uniform
hypergraph   which  is  (F,\epsilon)-dense   (and  satisfies
certain technical  conditions). Then each  independent set I
of H can be `labeled' by a very small set g(I) in such a way
that all independent sets labeled by some S are contained in
a member of the complement  of F. The above abstract theorem
has  many interesting  corollaries,  some of  which we  will
discuss. Among other things, it provides alternate proofs of
a range  of results obtained recently by  Conlon and Gowers,
and Schacht: Turan's  theorem and Erdos-Simonovits stability
theorem  in  random graphs,  Szemeredi's  theorem in  sparse
random sets of integers.

Joint work with Jozsef Balogh and Robert Morris.