Gráficas de listones y delta-matroides: dualidad parcial y torsión

Abstract

Moffatt, en su artículo Excluded minors and the ribbon graphs of knots (Journal of Graph Theory, 2016), conjetura que toda familia de gráficas de listones cerrada bajo menores se puede caracterizar mediante un conjunto finito de menores excluidos. El autor respalda esta conjetura en varios trabajos, en particular en Ribbon graph minors and low-genus partial duals (Annals of Combinatorics, 2016), donde proporciona una lista finita de menores excluidos que caracteriza la clase de gráficas de listones con un dual parcial de género de Euler a lo más uno. El género de Euler de una gráfica de listones está determinado por el género de la superficie en la cual dicha gráfica está encajada y es el género de la superficie cuando ésta es no orientable y el doble del género cuando ésta es orientable. En esta tesis, se presenta una lista finita de menores excluidos que caracteriza a las gráficas de listones con un dual parcial de género de Euler a lo más dos, bajo la condición de que toda rueda de listones relacionada por dualidad parcial con la gráfica de listones cumpla que: i) la gráfica de intersección de la subgráfica inducida por sus lazos no orientables, y ii) el complemento de la gráfica de intersección de la subgráfica inducida por sus lazos orientables, sean ambas libres de 3-ciclos. Existe una compatibilidad natural entre las gráficas de listones (gráficas encajadas en una superficie) y ciertas clases de delta-matroides, ver los artículos: Matroids, deltamatroids and embedded graphs ( Journal of Combinatorial Theory, Series A, 2019) y Delta-matroids for graph theorists (Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 2019). Las gráficas de listones están relacionadas con los delta-matroides de un modo análogo a la relación existente entre las gráficas y los matroides. A una gráfica de listones se le asocia un delta-matroide relacionando los cuasiárboles generadores de la gráfica con los conjuntos factibles del delta-matroide. Un invariante básico de un delta-matroide es su anchura, definida como la diferencia de las cardinalidades entre un conjunto factible maximal y uno minimal, y es el análogo del género de Euler de una gráfica de listones. Una de las operaciones fundamentales en la teoría de los delta-matroides es la torsión, la cual es análoga a la dualidad parcial en las gráficas de listones. Por lo tanto, caracterizar las gráficas de listones que admiten un dual parcial de género de Euler menor o igual que k es análogo a caracterizar ciertos delta-matroides con una torsión de anchura menor o igual que k. En este trabajo, se obtiene una lista de menores excluidos que caracteriza dichos delta-matroides para el caso k ≤ 2.

Moffatt, in his article Excluded minors and the ribbon graphs of knots (Journal of Graph Theory, 2016), conjectures that every family of ribbon graphs closed under minors can be characterized by a finite set of excluded minors. The author supports this conjecture in several works, in particular in Ribbon graph minors and low-genus partial duals (Annals of Combinatorics, 2016), where he provides a finite list of excluded minors that characterizes the class of ribbon graphs having a partial dual of Euler genus at most one. The Euler genus of a ribbon graph is determined by the genus of the surface in which the graph is embedded, being equal to the genus of the surface when the latter is non-orientable, and twice the genus when it is orientable. In this thesis, a finite list of excluded minors is presented that characterizes ribbon graphs with a partial dual of Euler genus at most two, under the condition that every bouquet related by partial duality to the ribbon graph satisfies: i) the intersection graph of the subgraph induced by its non-orientable loops, and ii) the complement of the intersection graph of the subgraph induced by its orientable loops, are both 3-cycle-free. There exists a natural compatibility between ribbon graphs (graphs embedded in a surface) and certain classes of delta-matroids; see the papers: Matroids, delta-matroids and embedded graphs (Journal of Combinatorial Theory, Series A, 2019), and Delta-matroids for graph theorists (Surveys in Combinatorics, London Mathematical Society Lecture Note Series, 2019). Ribbon graphs are related to delta-matroids in a way analogous to the relationship between graphs and matroids. A delta-matroid can be associated with a ribbon graph by relating the spanning quasi-trees of the ribbon graph with the feasible sets of the delta-matroid. A basic invariant of a delta-matroid is its width, defined as the difference in cardinality between a maximal feasible set and a minimal feasible set, and it plays a role analogous to the Euler genus of a ribbon graph. One of the fundamental operations in delta-matroid theory is the twist, which is analogous to partial duality in ribbon graphs. Therefore, characterizing ribbon graphs that admit a partial dual of Euler genus less than or equal to k is analogous to characterizing certain delta-matroids with a twist of width less than or equal to k. In this work, a list of excluded minors is obtained that characterizes such delta-matroids for the case k ≤ 2.