Transversal (combinatoria)

Conjunto que interseca a cada uno de una familia de conjuntos.

En matemáticas , particularmente en combinatoria , dada una familia de conjuntos , aquí llamada colección C , una transversal (también llamada sección transversal ^{[1] [2] [3]} ) es un conjunto que contiene exactamente un elemento de cada miembro de la recopilación. Cuando los conjuntos de la colección son mutuamente disjuntos, cada elemento de la transversal corresponde exactamente a un miembro de C (el conjunto del que es miembro). Si los conjuntos originales no son disjuntos, existen dos posibilidades para la definición de una transversal:

• Una variación es que hay una biyección f de la transversal a C tal que x es un elemento de f ( x ) para cada x en la transversal. En este caso, a la transversal también se le llama sistema de representantes distintos (DEG). ^{[4] : 29}
• El otro, menos utilizado, no requiere una relación uno a uno entre los elementos de la transversal y los conjuntos de C. En esta situación, los miembros del sistema de representantes no son necesariamente distintos. ^{[5] : 692  [6] : 322}

En informática , la computación transversal es útil en varios dominios de aplicación, y la familia de conjuntos de entrada a menudo se describe como un hipergrafo .

Existencia y número

Una cuestión fundamental en el estudio de los DEG es si existe o no un DEG. El teorema del matrimonio de Hall da las condiciones necesarias y suficientes para que una colección finita de conjuntos, algunos posiblemente superpuestos, tenga una transversal. La condición es que, para cada entero k , cada colección de k conjuntos debe contener en común al menos k elementos diferentes. ^{[4] : 29}

El siguiente refinamiento realizado por HJ Ryser proporciona límites inferiores al número de dichos DEG. ^{[7] : 48}

Teorema . Sea S ₁ , S ₂ , ..., S _m una colección de conjuntos tal que contenga al menos k elementos para k = 1,2,..., my para todas las k -combinaciones { } de los enteros 1, 2,..., m y supongamos que cada uno de estos conjuntos contiene al menos t elementos. Si t ≤ m entonces la colección tiene al menos t  ! DEG, y si t > m entonces la colección tiene al menos t  ! / ( t - m )! DEG. ${\displaystyle S_{i_{1}}\cup S_{i_{2}}\cup \dots \cup S_{i_{k}}}$ ${\displaystyle i_{1},i_{2},\ldots ,i_{k}}$

Relación con el emparejamiento y la cobertura

Se puede construir un gráfico bipartito en el que los vértices de un lado sean los conjuntos, los vértices del otro lado sean los elementos y las aristas conecten un conjunto con los elementos que contiene. Entonces, una transversal (definida como un sistema de distintos representantes) equivale a una coincidencia perfecta en este gráfico.

Se puede construir un hipergrafo en el que los vértices sean los elementos y los hiperaristas sean los conjuntos. Entonces, una transversal (definida como un sistema de representantes no necesariamente distintos ) es una cobertura de vértice en un hipergrafo .

Ejemplos

En teoría de grupos , dado un subgrupo H de un grupo G , una transversal derecha (respectivamente izquierda) es un conjunto que contiene exactamente un elemento de cada clase lateral derecha (respectivamente izquierda) de H. En este caso, los "conjuntos" (conjuntos laterales) son mutuamente disjuntos, es decir, los conjuntos laterales forman una partición del grupo.

Como caso particular del ejemplo anterior, dado un producto directo de grupos , entonces H es una transversal para las clases laterales de K . ${\displaystyle G=H\times K}$

En general, dado que cualquier relación de equivalencia en un conjunto arbitrario da lugar a una partición, elegir cualquier representante de cada clase de equivalencia da como resultado una transversal.

Otro ejemplo de transversal basada en partición ocurre cuando se considera la relación de equivalencia conocida como núcleo (teórico de conjuntos) de una función , definida para una función con dominio X como partición del dominio . que divide el dominio de f en clases de equivalencia de modo que todos los elementos de una clase se asignan a través de f al mismo valor. Si f es inyectiva, solo hay una transversal de . Para una f no necesariamente inyectiva , fijar una T transversal de induce una correspondencia uno a uno entre T y la imagen de f , en adelante denotada por . En consecuencia, una función está bien definida por la propiedad de que para todo z en donde x es el elemento único en T tal que ; además, g se puede extender (no necesariamente de una manera única) para que se defina en todo el codominio de f eligiendo valores arbitrarios para g(z) cuando z está fuera de la imagen de f . Es un cálculo simple verificar que g así definido tiene la propiedad de que , lo cual es la prueba (cuando el dominio y el codominio de f son el mismo conjunto) de que el semigrupo de transformación completa es un semigrupo regular . actúa como una cuasi-inversa (no necesariamente única) para f ; dentro de la teoría de semigrupos, esto simplemente se llama inversa. Sin embargo, tenga en cuenta que para una g arbitraria con la propiedad antes mencionada, es posible que la ecuación "dual" no se cumpla. Sin embargo, si denotamos por , entonces f es una cuasi inversa de h , es decir . ${\displaystyle f}$ ${\displaystyle \operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X\,\right\}}$ ${\displaystyle \operatorname {ker} f}$ ${\displaystyle \operatorname {ker} f}$ ${\displaystyle \operatorname {Im} f}$ ${\displaystyle g:(\operatorname {Im} f)\to T}$ ${\displaystyle \operatorname {Im} f,g(z)=x}$ ${\displaystyle f(x)=z}$ ${\displaystyle f\circ g\circ f=f}$ ${\displaystyle g}$ ${\displaystyle g\circ f\circ g=g}$ ${\displaystyle h=g\circ f\circ g}$ ${\displaystyle h\circ f\circ h=h}$

Transversales comunes

Una transversal común de las colecciones A y B (donde ) es un conjunto que es transversal tanto de A como de B . Las colecciones A y B tienen una transversal común si y sólo si, para todos , ${\displaystyle |A|=|B|=n}$ ${\displaystyle I,J\subset \{1,...,n\}}$

${\displaystyle |(\bigcup _{i\in I}A_{i})\cap (\bigcup _{j\in J}B_{j})|\geq |I|+|J|-n}$^[8]

Generalizaciones

Una transversal parcial es un conjunto que contiene como máximo un elemento de cada miembro de la colección, o (en la forma más estricta del concepto) un conjunto con una inyección del conjunto a C . Las transversales de una colección finita C de conjuntos finitos forman los conjuntos básicos de una matroide , la matroide transversal de C. Los conjuntos independientes de la matroide transversal son las transversales parciales de C . ^[9]

Una transversal independiente (también llamada conjunto independiente del arco iris o sistema independiente de representantes ) es una transversal que también es un conjunto independiente de un gráfico dado. Para explicar la diferencia en términos figurados, considere una facultad con m departamentos, donde el decano de la facultad quiere formar un comité de m miembros, un miembro por departamento. Un comité así es transversal. Pero ahora supongamos que algunos profesores no se agradan entre sí y no aceptan sentarse juntos en el comité. En este caso, el comité debe ser transversal independiente, donde el gráfico subyacente describe las relaciones de "disgusto". ^[10]

Otra generalización del concepto de transversal sería un conjunto que simplemente tiene una intersección no vacía con cada miembro de C . Un ejemplo de esto último sería un conjunto de Bernstein , que se define como un conjunto que tiene una intersección no vacía con cada conjunto de C , pero no contiene ningún conjunto de C , donde C es la colección de todos los conjuntos perfectos de un conjunto topológico polaco . espacio . Como otro ejemplo, supongamos que C consta de todas las líneas de un plano proyectivo , entonces un conjunto de bloqueo en este plano es un conjunto de puntos que intersecta cada línea pero no contiene ninguna línea.

Teoría de categorías

En el lenguaje de la teoría de categorías , una transversal de una colección de conjuntos mutuamente disjuntos es una sección del mapa de cocientes inducido por la colección.

Complejidad computacional

Se ha estudiado la complejidad computacional de calcular todas las transversales de una familia de conjuntos de entrada, en particular en el marco de los algoritmos de enumeración .

Ver también

• Axioma de elección
• Permanente

Referencias

1. John Mackintosh Howie (1995). Fundamentos de la teoría de semigrupos . Prensa de Clarendon. pag. 63.ISBN _ 978-0-19-851194-6.
2. Clive Reis (2011). Álgebra abstracta: introducción a grupos, anillos y campos . Científico mundial. pag. 57.ISBN _ 978-981-4335-64-5.
3. Bruno Courcelle ; Joost Engelfriet (2012). Estructura gráfica y lógica monádica de segundo orden: un enfoque teórico del lenguaje . Prensa de la Universidad de Cambridge. pag. 95.ISBN _ 978-1-139-64400-6.
4. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, señor  0859549
5. Roberts, Fred S.; Tesman, Barry (2009), Combinatoria aplicada (2ª ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
6. Brualdi, Richard A. (2010), Combinatoria introductoria (5ª ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 978-0-13-602040-0
7. Ryser, Herbert John (1963), Matemáticas combinatorias , The Carus Mathematical Monographs #14, Asociación Matemática de América
8. EC Milner (1974), TEORÍA TRANSVERSAL, Actas del congreso internacional de matemáticos , p. 161
9. Oxley, James G. (2006), Teoría matroide , textos de posgrado en matemáticas de Oxford, vol. 3, Oxford University Press, pág. 48, ISBN 978-0-19-920250-8.
10. Haxell, P. (1 de noviembre de 2011). "Sobre la formación de comités". El Mensual Matemático Estadounidense . 118 (9): 777–788. doi : 10.4169/amer.math.monthly.118.09.777. ISSN  0002-9890. S2CID  27202372.

Otras lecturas

• Lawler, EL Optimización combinatoria: redes y matroides. 1976.
• Mirsky, León (1971). Teoría transversal: una explicación de algunos aspectos de las matemáticas combinatorias. Prensa académica. ISBN 0-12-498550-5 .