Speaker
Description
Um {\em clutter\/} é um par ${\cal C} \equiv (V,E)$, onde $E$ (os elementos de $\Cl$) denota uma família de subconjuntos, de um conjunto não vazio e finito $V$ (os vértices de $\Cl$),
tal que nenhum dos elementos está contido noutro.
A teoria de clutters, outrora referida como {\em blocking\/} e {\em antiblocking\/} (Fulkerson'70), permite abordar, de modo elegante, questões diversas relacionadas com problemas de {\em set packing\/} e
{\em set covering\/}, nomeadamente a caraterização de integralidade dos poliedros subjacentes a esses problemas e o estabelecimento de relações to tipo min-max em problemas de otimização combinatória (o valor
mínimo de um problema é igual ao valor máximo de um outro).
Um clutter ${\cal C}$ é ideal se o poliedro (das coberturas de $\Cl$) $Q(A) \equiv \{ \mathbf{x} \colon A \mathbf{x} \geq \mathbf{1},
\mathbf{x} \geq \mathbf{0} \}$ é inteiro, onde $A \equiv M({\cal C})$ denota uma matriz de zeros e uns cujas linhas são os vetores característicos dos elementos de $\Cl$.
Um menor de $\Cl$ é um outro clutter que resulta de ${\cal C}$ após uma ou mais operações de {\em remoção\/} ou {\em contração\/} de um vértice de $\Cl$.
Um clutter é minimalmente não ideal, ou simplesmente mni, se não for ideal mas todos os seus menores forem. Lehman'79 provou que todos os clutters mni têm uma estrutura precisa, são
a extensão de clutters definidos por uma matriz de Lehman. Uma matriz de Lehman é uma matriz $Y$ $r$-regular de zeros e uns tal que $YZ^T = d I + \mathbf{1} \mathbf{1}^T$, para algum
inteiro positivo $d$ e alguma matriz $Z$ de zeros e uns. Nesta palestra mostraremos que as matrizes associadas a planos projetivos, embora sendo definidas por matrizes de Lehman, não podem desempenhar esse papel.
