Extensions of transversal matroids
En aquest treball s'introdueixen les principals nocions de teoria de matroides, matroides transversals i extensions d'un sol element. El nostre primer objectiu és estudiar quines extensions d'una matroide transversal són també transversals. En particular, centrem el nostre estudi en la família de ma...
| Autor: | |
|---|---|
| Tipo de documento: | Dissertação de mestrado |
| Data de publicação: | 2023 |
| País: | España |
| Recursos: | Universitat Politècnica de Catalunya (UPC) |
| Repositório: | UPCommons. Portal del coneixement obert de la UPC |
| Idioma: | Inglês |
| OAI Identifier: | oai:upcommons.upc.edu:2117/388663 |
| Acesso em linha: | https://hdl.handle.net/2117/388663 |
| Nível de acesso: | Acesso aberto |
| Palavra-chave: | Combinatorial analysis matroid theory transversal matroids presentations uniform matroids matroid extensions matroid enumeration Combinacions (Matemàtica) Classificació AMS::05 Combinatorics::05E Algebraic combinatorics Àrees temàtiques de la UPC::Matemàtiques i estadística |
| Resumo: | En aquest treball s'introdueixen les principals nocions de teoria de matroides, matroides transversals i extensions d'un sol element. El nostre primer objectiu és estudiar quines extensions d'una matroide transversal són també transversals. En particular, centrem el nostre estudi en la família de matroides uniformes. El conjunt d'extensions d'una matroide és un reticle sota l'anomenat weak order. Intentem respondre a la pregunta de si el conjunt d'extensions transversals d'una matroide uniforme és també un reticle o no. També dissenyem un algoritme per catalogar i contar matroides transversals fins a una certa mida del ground set. Per fer-ho, les construim a partir de la més petita, a base de iterativament extendre presentacions minimals, fent servir les eines que hem desenvolupat anteriorment. En vista que l'estratègia no troba realment totes les matroides transversals, també estudiem com són les matroides que no es poden construir amb aquesta estratègia i quines propietats satisfan. |
|---|