Gamoide

Abstracción de caminos disjuntos en grafos dirigidos

En la teoría de matroides , un campo dentro de las matemáticas, un gammoide es un cierto tipo de matroide, que describe conjuntos de vértices a los que se puede llegar mediante caminos disjuntos en sus vértices en un gráfico dirigido .

El concepto de gammoide fue introducido y demostrado como un matroide por Hazel Perfect  (1968), basándose en consideraciones relacionadas con el teorema de Menger que caracteriza los obstáculos a la existencia de sistemas de caminos disjuntos. ^[1] Los gammoides recibieron su nombre de Pym (1969) ^[2] y Mason (1972) los estudió con más detalle. ^[3]

Definición

Sea un grafo dirigido, un conjunto de vértices iniciales y un conjunto de vértices de destino (no necesariamente disjuntos de ). El gammoide derivado de estos datos tiene como conjunto de elementos . Un subconjunto de es independiente en si existe un conjunto de caminos disjuntos en vértices cuyos puntos iniciales pertenecen todos a y cuyos puntos finales son exactamente . ^[4] ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle \Gamma }$ ${\displaystyle T}$ ${\displaystyle I}$ ${\displaystyle T}$ ${\displaystyle \Gamma }$ ${\displaystyle S}$ ${\displaystyle I}$

Un gammoide estricto es un gammoide en el que el conjunto de vértices de destino consiste en cada vértice en . Por lo tanto, un gammoide es una restricción de un gammoide estricto a un subconjunto de sus elementos. ^{[4] [5]} ${\displaystyle T}$ ${\displaystyle G}$

Ejemplo

Consideremos el matroide uniforme sobre un conjunto de elementos, en el que cada conjunto de o menos elementos es independiente. Una forma de representar este matroide como un gammoide sería formar un grafo bipartito completo con un conjunto de vértices en un lado de la bipartición, con un conjunto de vértices en el otro lado de la bipartición, y con cada arista dirigida de a En este grafo, un subconjunto de es el conjunto de puntos finales de un conjunto de caminos disjuntos si y solo si tiene o menos vértices, ya que de lo contrario no hay suficientes vértices en para iniciar los caminos. La estructura especial de este grafo muestra que el matroide uniforme es un matroide transversal además de ser un gammoide. ^[6] ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle K_{r,n}}$ ${\displaystyle S}$ ${\displaystyle r}$ ${\displaystyle T}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle T.}$ ${\displaystyle T}$ ${\displaystyle r}$ ${\displaystyle S}$

Alternativamente, el mismo matroide uniforme puede representarse como un gammoide en un gráfico más pequeño, con solo vértices, eligiendo un subconjunto de vértices y conectando cada uno de los vértices elegidos con cada uno de los demás vértices del gráfico. Nuevamente, un subconjunto de los vértices del gráfico puede ser puntos finales de caminos disjuntos si y solo si tiene o menos vértices, porque de lo contrario no hay suficientes vértices que puedan ser inicios de caminos. En este gráfico, cada vértice corresponde a un elemento del matroide, lo que demuestra que el matroide uniforme es un gammoide estricto. ^[7] ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle r}$ ${\displaystyle r}$

Teorema de Menger y rango gammoide

El rango de un conjunto en un gammoide definido a partir de un grafo y subconjuntos de vértices y es, por definición, el número máximo de caminos disjuntos en vértices desde hasta . Por el teorema de Menger , también es igual a la cardinalidad mínima de un conjunto que interseca cada camino desde hasta . ^[4] ${\displaystyle X\subset T}$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle S}$ ${\displaystyle X}$

Relación con las matroides transversales

Un matroide transversal se define a partir de una familia de conjuntos : sus elementos son los elementos de los conjuntos, y un conjunto de estos elementos es independiente siempre que exista una correspondencia biunívoca de los elementos de con conjuntos disjuntos que los contienen, llamado sistema de representantes distintos . De manera equivalente, un matroide transversal puede representarse mediante un tipo especial de gammoide, definido a partir de un grafo bipartito dirigido que tiene un vértice en para cada conjunto, un vértice en para cada elemento y una arista desde cada conjunto hasta cada elemento contenido en él. ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle (S,T,E)}$ ${\displaystyle S}$ ${\displaystyle T}$

Menos trivialmente, los gammoides estrictos son exactamente los matroides duales de los matroides transversales. Para ver que cada gammoide estricto es dual a un matroide transversal, sea un gammoide estricto definido a partir de un grafo dirigido y un conjunto de vértices de inicio , y considere el matroide transversal para la familia de conjuntos para cada vértice , donde vértice pertenece a si es igual o tiene una arista a . Cualquier base del gammoide estricto, que consiste en los puntos finales de algún conjunto de caminos disjuntos desde , es el complemento de una base del matroide transversal, haciendo coincidir cada uno con el vértice tal que es una arista del camino (o él mismo, si no participa en uno de los caminos). A la inversa, cada base del matroide transversal, que consiste en un representante para cada , da lugar a una base complementaria del gammoide estricto, que consiste en los puntos finales de los caminos formados por el conjunto de aristas . Este resultado se debe a Ingleton y Piff. ^{[4] [8]} ${\displaystyle \gamma }$ ${\displaystyle G}$ ${\displaystyle S}$ ${\displaystyle N_{v}}$ ${\displaystyle v\in V(G)\setminus S}$ ${\displaystyle u}$ ${\displaystyle N_{v}}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle |S|}$ ${\displaystyle S}$ ${\displaystyle N_{v}}$ ${\displaystyle u}$ ${\displaystyle uv}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle u_{v}}$ ${\displaystyle N_{v}}$ ${\displaystyle u_{v}v}$

Para ver, a la inversa, que todo matroide transversal es dual a un gammoide estricto, hay que encontrar una subfamilia de los conjuntos que definen al matroide tal que la subfamilia tenga un sistema de representantes distintos y defina al mismo matroide. Se forma un grafo que tenga como vértices la unión de los conjuntos y que tenga una arista con el elemento representativo de cada conjunto de los otros miembros del mismo conjunto. Entonces, los conjuntos formados como se indicó anteriormente para cada elemento representativo son exactamente los conjuntos que definen al matroide transversal original, por lo que el gammoide estricto formado por este grafo y por el conjunto de elementos representativos es dual al matroide transversal dado. ^{[4] [8]} ${\displaystyle N_{v}}$ ${\displaystyle v}$

Como consecuencia sencilla del teorema de Ingleton-Piff, cada gammoide es una contracción de un matroide transversal. Los gammoides son la clase más pequeña de matroides que incluye a los matroides transversales y está cerrada bajo dualidad y toma menores . ^{[4] [9] [10]}

Representabilidad

No es cierto que todo gammoide sea regular , es decir, representable sobre cualquier cuerpo. En particular, el matroide uniforme no es un matroide binario y, de manera más general, la línea de puntos sólo puede representarse sobre cuerpos con o más elementos. Sin embargo, todo gammoide puede representarse sobre casi cualquier cuerpo finito . ^{[3] [4]} Más específicamente, un gammoide con un conjunto de elementos puede representarse sobre cualquier cuerpo que tenga al menos elementos. ^{[4] [11] [12]} ${\displaystyle U{}_{4}^{2}}$ ${\displaystyle n}$ ${\displaystyle U{}_{n}^{2}}$ ${\displaystyle n-1}$ ${\displaystyle S}$ ${\displaystyle 2^{|S|}}$

Referencias

1. Perfect, Hazel (1968), "Aplicaciones del teorema de grafos de Menger", Journal of Mathematical Analysis and Applications , 22 : 96-111, doi : 10.1016/0022-247X(68)90163-7 , MR  0224494.
2. Pym, JS (1969), "La vinculación de conjuntos en gráficos", Journal of the London Mathematical Society , s1-44 (1): 542–550, doi :10.1112/jlms/s1-44.1.542.
3. Mason, JH (1972), "Sobre una clase de matroides que surgen de caminos en grafos", Actas de la London Mathematical Society , Tercera serie, 25 (1): 55–74, doi :10.1112/plms/s3-25.1.55, MR  0311496.
4. Schrijver, Alexander (2003), Optimización combinatoria: poliedros y eficiencia. Vol. B: Matroides, árboles, conjuntos estables, algoritmos y combinatoria, vol. 24, Berlín: Springer-Verlag, págs. 659–661, ISBN 3-540-44389-4, Sr.  1956925.
5. Oxley 2006, pág. 100
6. Oxley, James G. (2006), Matroid Theory , Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, págs. 48-49, ISBN 9780199202508.
7. Oxley (2006), pág. 100.
8. Ingleton, AW; Piff, MJ (1973), "Gammoideas y matroides transversales", Journal of Combinatorial Theory , Serie B, 15 : 51–68, doi : 10.1016/0095-8956(73)90031-2 , MR  0329936.
9. Oxley 2006, pág. 115
10. Welsh, DJA (2010), Teoría de matroides, Courier Dover Publications, págs. 222-223, ISBN 9780486474397.
11. Atkin, AOL (1972), "Observación sobre un artículo de Piff y Welsh", Journal of Combinatorial Theory , Serie B, 13 (2): 179–182, doi : 10.1016/0095-8956(72)90053-6 , MR  0316281.
12. Lindström, Bernt (1973), "Sobre las representaciones vectoriales de matroides inducidas", The Bulletin of the London Mathematical Society , 5 : 85–90, doi :10.1112/blms/5.1.85, MR  0335313.