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...
| Author: | |
|---|---|
| Format: | Master's thesis |
| Publication date: | 2023 |
| Country: | España |
| Institution: | Universitat Politècnica de Catalunya (UPC) |
| Repository: | UPCommons. Portal del coneixement obert de la UPC |
| Language: | English |
| OAI Identifier: | oai:upcommons.upc.edu:2117/388663 |
| Online Access: | https://hdl.handle.net/2117/388663 |
| Access Level: | Open access |
| Keyword: | 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 |
| _version_ | 1878733012632338432 |
|---|---|
| author | Sorinas Capdevila, Ernest |
| author_browse | Sorinas Capdevila, Ernest |
| author_facet | Sorinas Capdevila, Ernest |
| author_role | author |
| collection | UPCommons. Portal del coneixement obert de la UPC |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | masterThesis |
| id | ES_4e5dae7b277468b4e1b650eac9fad2ef |
| institution | Universitat Politècnica de Catalunya (UPC) |
| instname_str | Universitat Politècnica de Catalunya (UPC) |
| language | eng |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:upcommons.upc.edu:2117/388663 |
| publishDate | 2023 |
| publishDateSort | 2023 |
| publisher | Universitat Politècnica de Catalunya |
| publisherStr | Universitat Politècnica de Catalunya |
| reponame_str | UPCommons. Portal del coneixement obert de la UPC |
| spelling | Extensions of transversal matroids Sorinas Capdevila, Ernest 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 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. En este trabajo introducimos las nociones básicas de teoría de matroides, matroides transversales y extensiones de un solo elemento. Nuestro primer objetivo es estudiar las extensiones de matroides transversales que también son transversales. En particular, centramos nuestro estudio en la familia de las matroides uniformes. El conjunto de extensiones de una matroide es un retículo bajo el llamado weak order. Intentamos responder a la pregunta de si el conjunto de extensiones transversales de un matroide uniforme es también un retículo o no. También diseñamos un algoritmo que cataloga y cuenta matroides transversales hasta un tamaño fijo del ground set. Para ello, las construimos desde cero extendiendo iterativamente presentaciones minimales utilizando las herramientas que hemos visto anteriormente. Dado que la estrategia no cuenta realmente todas las matroides transversales, estudiamos también qué matroides no son alcanzables utilizando esta estrategia y qué propiedades satisfacen. In this work we introduce the basic notions of matroid theory, transversal matroids and single-element extensions. Our first objective is to study which extensions of a given transversal matroid are also transversal. In particular, we focus our study on the family of uniform matroids. The set of single-element extensions of a matroid is a lattice under the so-called weak order. We try to answer the question of whether the set of transversal extensions of a uniform matroid is also a lattice or not. We also design an algorithm that catalogs and counts transversal matroids up to a fixed size of the ground set. To do so, we build them from scratch by iteratively extending minimal presentations using the tools that we have previously seen. In view that the strategy does not actually count all transversal matroids, we also study which matroids are not reachable using this strategy and what properties do they satisfy. Universitat Politècnica de Catalunya https://hdl.handle.net/2117/388663 |
| spellingShingle | Extensions of transversal matroids Sorinas Capdevila, Ernest 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 |
| title | Extensions of transversal matroids |
| title_full | Extensions of transversal matroids |
| title_fullStr | Extensions of transversal matroids |
| title_full_unstemmed | Extensions of transversal matroids |
| title_short | Extensions of transversal matroids |
| title_sort | Extensions of transversal matroids |
| topic | 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 |
| topic_facet | 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 |
| url | https://hdl.handle.net/2117/388663 |