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 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, hay dos posibilidades para la definición de una transversal:

• Una variación es que existe una biyección f desde 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 utilizada, no requiere una relación biunívoca 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 , el cálculo de transversales es útil en varios dominios de aplicación, y la familia de entrada de conjuntos suele describirse como un hipergrafo .

Existencia y numero

Una cuestión fundamental en el estudio de la SDR es si existe o no una SDR. El teorema del matrimonio de Hall proporciona 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 de HJ Ryser proporciona límites inferiores al número de dichos SDR. ^{[7] : 48}

Teorema . Sea S ₁ , S ₂ , ..., S _m una colección de conjuntos tales que contiene al menos k elementos para k = 1,2,..., m y 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  ! SDR, y si t > m entonces la colección tiene al menos t  ! / ( t - m )! SDR. ${\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 la coincidencia y la cobertura

Se puede construir un grafo bipartito en el que los vértices de un lado son los conjuntos, los vértices del otro lado son los elementos y las aristas conectan un conjunto con los elementos que contiene. Entonces, una transversal (definida como un sistema de representantes distintos ) es equivalente a una correspondencia perfecta en este grafo.

Se puede construir un hipergrafo en el que los vértices son los elementos y las hiperaristas son los conjuntos. Entonces, una transversal (definida como un sistema de representantes no necesariamente distintos ) es una cobertura de vértices 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" (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 . ${\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 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ón con dominio X como la partición del dominio . que divide el dominio de f en clases de equivalencia tales que todos los elementos en una clase se mapean 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 transversal T de induce una correspondencia biunívoca entre T y la imagen de f , denotada de ahora en adelante por . En consecuencia, una función está bien definida por la propiedad de que para todo z en donde x es el único elemento en T tal que ; además, g puede extenderse (no necesariamente de manera única) de modo 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 codominio de f son el mismo conjunto) de que el semigrupo de transformación completo 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 un g arbitrario con la propiedad antes mencionada, la ecuación "dual" puede no cumplirse. Sin embargo, si denotamos por , entonces f es un cuasi-inverso 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 solo si, para todo , ${\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 base de un matroide , el matroide transversal de C . Los conjuntos independientes del 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 grafo 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. Tal comité es una transversal. Pero ahora, supongamos que algunos miembros de la facultad se desagradan 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 grafo subyacente describe las relaciones de "desagrado". ^[10]

Otra generalización del concepto de transversal sería un conjunto que solo 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 espacio polaco topológico . Como otro ejemplo, sea C consiste en todas las líneas de un plano proyectivo , entonces un conjunto de bloqueo en este plano es un conjunto de puntos que interseca 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 cociente inducido por la colección.

Complejidad computacional

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

Véase también

• Axioma de elección
• Permanente

Referencias

1. John Mackintosh Howie (1995). Fundamentos de la teoría de semigrupos . Clarendon Press. pág. 63. ISBN 978-0-19-851194-6.
2. Clive Reis (2011). Álgebra abstracta: Introducción a grupos, anillos y cuerpos . World Scientific. pág. 57. ISBN. 978-981-4335-64-5.
3. Bruno Courcelle ; Joost Engelfriet (2012). Estructura de grafos y lógica monádica de segundo orden: un enfoque teórico del lenguaje . Cambridge University Press. pág. 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, Sr.  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ág. 161
9. Oxley, James G. (2006), Matroid Theory , Textos de posgrado de Oxford en matemáticas, 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". The American Mathematical Monthly . 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN  0002-9890. S2CID  27202372.

Lectura adicional

• Lawler, EL Optimización combinatoria: redes y matroides. 1976.
• Mirsky, Leon (1971). Teoría transversal: una descripción de algunos aspectos de las matemáticas combinatorias. Academic Press. ISBN 0-12-498550-5 .