Universidade de Lisboa Repositório da Universidade de Lisboa

Repositório da Universidade de Lisboa >
Faculdade de Ciências (FC) >
FC - Dissertações de Mestrado >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10451/1271

Título: Partições de inteiros e dualidade em estruturas combinatórias
Autor: Martins, Inês Neves Louro Legatheaux
Orientador: Torres, Maria Manuel Correia
Palavras-chave: Álgebra
Lógica
Teses de mestrado
Issue Date: 2007
Resumo: Nos anos oitenta, M. Albertson apresenta um contexto geral para formular problemas de dualidade, considerando hipergrafos e associando-lhes as sucessões das diferenças entre dois termos consecutivos da sucessão das dimensões e da sucessão de estabilidade. Os teoremas de dualidade traduzem-se pela igualdade do primeiro termo de uma das sucessões com o comprimento da outra. Surge naturalmente a questão de saber para que estruturas combinatórias as sucessões das diferenças formam partições e que relação existe entre as duas. Em 1986, M. Saks observa que os teoremas de dualidade provêm de pares antibloco de hipergrafos, colocando a questão anterior neste contexto. Esta dissertação pretende mostrar que a linguagem dos hipergrafos permite unificar resultados clássicos e recentes sobre diversas estruturas combinatórias. Nesse sentido, são apresentados teoremas de C. Greene e D. Kleitman que generalizam os teoremas duais de Dilworth e Mirsky sobre conjuntos parcialmente ordenados. Verifica-se que esta generalização é consequência das sucessões das diferenças associadas ao par antibloco dos hipergrafos das anticadeias e cadeias serem partições conjugadas. O estudo do par antibloco dos hipergrafos dos emparelhamentos e estrelas de um multigrafo bipartido permite reencontrar um resultado de D. de Werraque estabelece que a sucessão das diferenças dos emparelhamentos forma uma partição da cardinalidade do conjunto de arestas. Segundo M. Saks, permite ainda determinar a relação entre esta partição e a sucessão das diferenças das estrelas. Por último, é verificado que a partição característica de um matróide, noção desenvolvida por J. A. Dias da Silva em 1990, pode ser encarada como sucessão das diferenças das dimensões de um hipergrafo. Embora a tradução do problema de dualidade enquanto par antibloco nem sempre seja possível para esta estrutura, apresenta-se uma classe particular de matróides para os quais existe um par antibloco de hipergrafos cujas sucessões das diferenças são partições conjugadas.
In the eighties, M. Albertson defines a general context for duality questions by taking hypergraphs and considering the difference sequences of their rank sequence and their stability sequence. Duality theorems arise if the first term of one of these sequences equals the length of the other. It is natural to ask for which combinatorial structures these difference sequences are integer partitions and what relationship may hold between them. M. Saks noted that duality theorems arise from antiblocking pairs of hypergraphs, stating the previous question in this context. The present thesis aims to unify some classical and recent results about several combinatorial structures through the language of hypergraphs. For partially ordered sets, theorems by C. Greene and D. Kleitman that extend the Dilworth's decomposition theorem and its dual are presented. The extension is a consequence of a conjugacy relationship between the difference sequences associated with the antiblocking pair of the hypergraphs of antichains and chains. The study of the antiblocking pair of the matching and star hypergraphs of a bipartite multigraph enables to see the matching difference sequence as a partition of the cardinality of the edge set, translating a result established by D. de Werra. According to M. Saks, it also allows to determine the relationship between the latter partition and the star difference sequence. Finally, the previous procedures are used to verify that the rank partition of a matroid, notion established by J. A. Dias da Silva in 1990, may be considered as a difference sequence associated with a certain hypergraph. Although the translation of the duality problem as an antiblocking pair is not always possible for this structure, a particular class of matroids is presented for which there exists an antiblocking pair of hypergraphs whose difference sequences are conjugate partitions.
Descrição: Tese de mestrado em Matemática (Álgebra, Lógica e Fundamentos), apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2008
URI: http://catalogo.ul.pt/F/?func=item-global&doc_library=ULB01&type=03&doc_number=000561454
http://hdl.handle.net/10451/1271
Appears in Collections:FC - Dissertações de Mestrado

Files in This Item:

File Description SizeFormat
19116_ulfc091301_tm_tese.pdf852,65 kBAdobe PDFView/Open
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

  © Universidade de Lisboa / SIBUL
Alameda da Universidade | Cidade Universitária | 1649-004 Lisboa | Portugal
Tel. +351 217967624 | Fax +351 217933624 | repositorio@reitoria.ul.pt - Feedback - Statistics
DeGóis
  Estamos no RCAAP Governo Português separator Ministério da Educação e Ciência   Fundação para a Ciência e a Tecnologia

Financiado por:

POS_C UE