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

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

Título:      On Erdös-Ko-Rado type theorems
            
Palestrante: Peter Frankl 
             Hungarian Academy of Sciences

Hora e Data: 14h, sexta-feira, 10 de maio de 2013

Local:       Sala Multi-usos do Numec

Resumo:

The lecture  will focus on extremal set  theory. The general
problem concerns  the maximum possible  size of a  subset of
the power set  of a finite set X of  $n$ elements subject to
some  conditions.   The  simplest  result  is  probably  the
following.

Proposition 0. If F is a subset of 2^X such that any two
sets in F have non-empty intersection, then 

      |F| \leq 2^{n-1}.

One way to achieve equality is by taking all subsets
containing a fixed element.

Erdös-Ko-Rado  Theorem. If  F is  a collection  of k-element
subsets  of X such  that any  two sets  in F  have non-empty
intersection and, moreover, 2k < n, then

      |F| \leq {n-1 \choose k-1}, 

with  equality holding  if  and  only if  all  subsets in  F
contain a fixed element.

We shall discuss various generalisations and extensions of
this result, some of which are still unsolved.