Alguns problemas com solução combinatória

De acordo com o que prometi, vou tentar descrever alguns problemas em cuja solução colaborei, tentando fazê-lo para um público geral, isto é, sem assumir conhecimentos mais especializados. Começarei por referir brevemente alguns trabalhos mais relevantes relacionados com o seguinte: é possível (e fácil) representar qualquer poliedro convexo numa esfera, no sentido de lhe associar um grafo esférico que tem a estrutura do grafo do poliedro e que determina na esfera faces que também estão em correspondência com as faces do poliedro: basta escolher um ponto O no interior do poliedro e pôr cada ponto P da superfície à mesma distância desse ponto, deslocando-o na semi-recta de origem O por P. Também se prova (de forma bem mais difícil!) que é sempre possível passar do grafo esférico para o poliedro (por um Teorema de Steinitz). Chama-se a isto *realizar geometricamente o grafo*. Pretendo falar um pouco sobre os limites desta operação, isto é sobre a sua possibilidade/impossibilidade em diferentes casos, e um pouco sobre o "espaço de realização" nos casos em que é possível. Nesta primeira parte pretendo unicamente dar uma ideia do trabalho realizado, dos problemas e das direcções das respostas. Numa segunda parte tentarei abordar com um pouco mais de pormenor outros trabalhos, de carácter mais elementar talvez, acerca das decomposições, de um dado tipo, do conjunto P(X) de todos os subconjuntos de um conjunto finito X dado. Vou expor um problema fácil de enunciar, muito natural. A sua solução é também fácil de enunciar e é também muito natural. O que é talvez invulgar, é que não parece haver uma ligação clara entre o problema e a solução encontrada, apesar da sua naturalidade. Esta situação aparece com alguma frequência em problemas combinatórios e é, para mim, um dos encantos deles.