Título:

Irreducible classes and barycentric subdivision on triangle-free 3-connected matroids

Autor:

JAIME CESAR DOS SANTOS FILHO

Tipo de Trabalho de Conclusão:

TESE

Abreviatura:

FILHO, J. C. S.

Data da Defesa:

30/01/2020

Resumo:

As matroides 3-conexas, fundamentais na teoria das matroides, possuem duas família de irredutíveis com relação às operações de deleção e contração. Este resultado é conhecido como Teorema da Roda e do Redemoinho de Tutte [11]. Lemos, em [4], considerou sete operações de redução para classificar as matroides 3-conexas livre de triângulos irredutíveis, cinco além das duas consideradas por Tutte. Os resultados obtidos por Lemos generalizam os obtidos por Kriesell [2]. Considerando apenas as três primeiras operações de redução definidas em [4], provamos que 4 estruturas locais formadas por quadrados e triades se comportam como "blocos construtores" para estas famílias de irredutíveis. Subdividindo a sétima redução, acrescentamos mais uma família de matroides 3-conexas livre de triângulos irredutíveís: diamantic matroids, em inglês. Estabelecemos, de uma forma construtiva, que para cada matroide nesta família existe um única matroide totalmente triangular associada. A construção desta correspondência biunívoca é baseada na conexão em paralelo generalizada e passa por uma matroide, única a menos de isomorfismos, que corresponde a subdivisão baricêntrica no caso de matroides gráficas.

Palavras-chave:

Matroides. 3-conectividade. Triângulos. Triades. Quadrados.

Abstract:

The 3-connected matroids, fundamental in matroid theory, have two families of irreducible matroids with respect to the operations of deletion and contraction. This result is known as Tutte’s Wheels and Whirls Theorem, established in [11]. Lemos, in [4], considered seven reduction operations to classify the triangles-free 3-connected matroids, five in addition to the two considered by Tutte. The results obtained by Lemos generalize those obtained by Kriesell [2]. Considering only the first three reduction operations defined in [4], we prove that 4 local structures formed by squares and triads behave like "building blocks" for these families of irreducible. Subdividing the seventh reduction, we add another family of triangle-free 3-connected matoids: diamantic matroids. We have established, in a constructive way, that for each matroid in this family there is a unique totally triangular matoid associated. The construction of this one-to-one correspondence is based on the generalized parallel connection and passes through a matroid, unique up to isomorphisms, which corresponds to the barycentric subdivision in the case of graphic matroids.

Keywords:

Matroids. 3-connectivity. Triangles. Triads. Squares.

Volume:

01

Páginas:

76

Idioma:

INGLES

Biblioteca depositada:

Central e setorial

Autorização de divulgação:

O trabalho não possui divulgação autorizada

Área de Concentração:

COMBINATÓRIA

Linha de Pesquisa:

CONECTIVIDADE EM GRAFOS E MATRÓIDES

Projeto de Pesquisa:

CONECTIVIDADE EM GRAFOS E MATRÓIDES

Orientador:

MANOEL JOSE MACHADO SOARES LEMOS

O orientador principal compôs a banca do discente?:

Sim

Tipo de Vínculo Empregatício:

Servidor Público

Tipo de Instituição:

Instituição de Ensino e Pesquisa

Expectativa de Atuação:

Ensino e Pesquisa

Mesma Área de Atuação?

Sim