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 colecció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, la transversal también se denomina sistema de representantes distintos (SDR). [4] : 29
- La otra, menos comúnmente utilizado, no requiere una relación de 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 hipergráfico .
Existencia y número
Una cuestión fundamental en el estudio de los DEG es si existe o no. El teorema del matrimonio de Hall da las condiciones necesarias y suficientes para que los conjuntos de una colección finita, algunos posiblemente superpuestos, tengan 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 de HJ Ryser da límites más bajos en el número de tales SDR. [7] : 48
Teorema . Sea S 1 , S 2 , ..., S m una colección de conjuntos tales quecontiene al menos k elementos para k = 1,2, ..., my para todas las k- combinaciones {} de los enteros 1,2, ..., my supongamos que cada uno de estos conjuntos contiene al menos t elementos. Si t ≤ m, entonces la colección tiene al menos t ! SDR, y si t > m, entonces la colección tiene al menos t ! / ( t - m )! DEG.
Relación con emparejar y cubrir
Se puede construir un gráfico bipartito en el que los vértices de un lado son los conjuntos, los vértices del otro lado son los elementos y los bordes conectan un conjunto con los elementos que contiene. Entonces, una transversal (definida como un sistema de representantes distintos ) es equivalente a una coincidencia perfecta en este gráfico.
Se puede construir un hipergráfico en el que los vértices son los elementos y los hipergrafos son los conjuntos. Entonces, una transversal (definida como un sistema de representantes no necesariamente distintos ) es una cubierta de vértice en un hipergráfico .
Ejemplos de
En la teoría de grupos , dado un subgrupo H de un grupo G , un derecho (respectivamente izquierdo) transversal es un conjunto que contiene exactamente un elemento de cada derecha (izquierda, respectivamente) clase lateral de H . En este caso, los "conjuntos" (clases laterales) son mutuamente disjuntos, es decir, las clases 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 .
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.
Otra instancia de una transversal basada en particiones ocurre cuando se considera la relación de equivalencia conocida como el núcleo (teórico de conjuntos) de una función , definida para una funcióncon el 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 mapean a través de f con el mismo valor. Si f es inyectiva, solo hay una transversal de. Para una f no necesariamente inyectiva , la fijación de una transversal T deinduce una correspondencia uno a uno entre T y la imagen de f , de ahora en adelante denotada por. En consecuencia, una funciónestá bien definido por la propiedad de que para todo z endonde x es el elemento único en T tal que; además, g puede extenderse (no necesariamente de una manera única) de modo que se defina en todo el codominio de f seleccionando valores arbitrarios para g (z) cuando z está fuera de la imagen de f . Es un cálculo simple para verificar que g así definido tiene la propiedad de que, que 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 un cuasi-inverso (no necesariamente único) para f ; dentro de la teoría de semigrupos, esto simplemente se llama inverso. Sin embargo, tenga en cuenta que para una g arbitraria con la propiedad antes mencionada, la ecuación "dual"puede que no aguante. Sin embargo, si denotamos por, entonces f es un cuasi inverso de h , es decir.
Transversales comunes
Una transversal común de las colecciones A y B (donde) Es un conjunto que es una transversal de ambos A y B . Las colecciones A y B tienen una transversal común si y solo si, para todos,
Generalizaciones
A transversal parcial es un conjunto que contiene como máximo elemento de uno de cada miembro de la colección, o (en la forma más estricta del concepto) un conjunto con una inyección a partir del conjunto de C . Los transversales de una colección finita C de conjuntos finitos forman los conjuntos de base de un matroid , la transversal matroid de C . Los conjuntos independientes de la matroid transversal son los 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 figurativos, considere una facultad con m departamentos, donde el decano de la facultad quiere construir un comité de m miembros, un miembro por departamento. Dicho comité es transversal. Pero ahora, suponga que algunos miembros de la facultad no se agradan entre sí y no están de acuerdo en sentarse juntos en el comité. En este caso, el comité debe ser una transversal independiente, donde el gráfico subyacente describe las relaciones de "disgusto".
Otra generalización del concepto de una transversal sería un conjunto que sólo tiene una intersección no vacía con cada miembro de C . Un ejemplo de este ú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 que no contiene ningún conjunto de C , donde C es la colección de todos los conjuntos perfectos de un polaco topológico. 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
- ^ John Mackintosh Howie (1995). Fundamentos de la teoría de los semigrupos . Prensa de Clarendon. pag. 63. ISBN 978-0-19-851194-6. CS1 maint: parámetro desalentado ( enlace )
- ^ Clive Reis (2011). Álgebra abstracta: una introducción a grupos, anillos y campos . World Scientific. pag. 57. ISBN 978-981-4335-64-5.
- ^ 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. CS1 maint: parámetro desalentado ( enlace )
- ^ a b Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549
- ^ Roberts, Fred S .; Tesman, Barry (2009), Applied Combinatorics (2.a ed.), Boca Raton: CRC Press, ISBN 978-1-4200-9982-9
- ^ Brualdi, Richard A. (2010), Introducción a la combinatoria (5a ed.), Upper Saddle River, Nueva Jersey: Prentice Hall, ISBN 0-13-602040-2
- ^ Ryser, Herbert John (1963), Matemáticas combinatorias , The Carus Mathematical Monographs # 14, Asociación Matemática de América
- ^ EC Milner (1974), TEORÍA TRANSVERSAL, Actas del congreso internacional de matemáticos , p. 161 CS1 maint: parámetro desalentado ( enlace )
- ^ Oxley, James G. (2006), Matroid Theory , Textos de posgrado en matemáticas de Oxford , 3 , Oxford University Press, p. 48, ISBN 978-0-19-920250-8 CS1 maint: parámetro desalentado ( enlace ).
Otras lecturas
- Lawler, EL Optimización combinatoria: redes y matroides. 1976.
- Mirsky, León (1971). Teoría transversal: descripción de algunos aspectos de la matemática combinatoria. Prensa académica. ISBN 0-12-498550-5 .