matroide de partición

Suma directa de matroides uniformes

En matemáticas, una matroide de partición o matroide particional es una matroide que es una suma directa de matroides uniformes . ^[1] Se define sobre un conjunto base en el que los elementos se dividen en diferentes categorías. Para cada categoría, existe una restricción de capacidad : una cantidad máxima de elementos permitidos de esta categoría. Los conjuntos independientes de una matroide de partición son exactamente aquellos conjuntos en los que, para cada categoría, el número de elementos de esta categoría es como máximo la capacidad de la categoría.

Definicion formal

Sea una colección de conjuntos disjuntos ("categorías"). Sean números enteros con ("capacidades"). Defina un subconjunto para que sea "independiente" cuando, para cada índice , . Los conjuntos que satisfacen esta condición forman los conjuntos independientes de una matroide , llamados matroide de partición . ${\displaystyle C_{i}}$ ${\displaystyle d_{i}}$ ${\displaystyle 0\leq d_{i}\leq |C_{i}|}$ ${\displaystyle I\subset \bigcup _{i}C_{i}}$ ${\displaystyle i}$ ${\displaystyle |I\cap C_{i}|\leq d_{i}}$

Los conjuntos se denominan categorías o bloques de la partición matroide. ${\displaystyle C_{i}}$

Una base de la matroide de partición es un conjunto cuya intersección con cada bloque tiene un tamaño exacto . Un circuito de la matroide es un subconjunto de un solo bloque con tamaño exacto . El rango de la matroide es . ^[2] ${\displaystyle C_{i}}$ ${\displaystyle d_{i}}$ ${\displaystyle C_{i}}$ ${\displaystyle d_{i}+1}$ ${\displaystyle \sum d_{i}}$

Cada matroide uniforme es una matroide de partición, con un solo bloque de elementos y con . Cada matroide de partición es la suma directa de una colección de matroides uniformes, una para cada uno de sus bloques. ${\displaystyle U{}_{n}^{r}}$ ${\displaystyle C_{1}}$ ${\displaystyle n}$ ${\displaystyle d_{1}=r}$

En algunas publicaciones, la noción de matroide de partición se define de manera más restrictiva, con cada . Las particiones que obedecen a esta definición más restrictiva son las matroides transversales de la familia de conjuntos disjuntos dada por sus bloques. ^[3] ${\displaystyle d_{i}=1}$

Propiedades

Al igual que con las matroides uniformes a partir de las cuales se forman, la matroide dual de una matroide de partición también es una matroide de partición, y cada matroide menor de una matroide de partición también es una matroide de partición. Las sumas directas de matroides de partición también son matroides de partición.

Pareo

Una coincidencia máxima en un gráfico es un conjunto de aristas que es lo más grande posible sujeto a la condición de que no haya dos aristas que compartan un punto final. En un gráfico bipartito con bipartición , los conjuntos de aristas que satisfacen la condición de que no haya dos aristas que compartan un punto final son los conjuntos independientes de una matroide de partición con un bloque por vértice en y con cada uno de los números igual a uno. Los conjuntos de aristas que satisfacen la condición de que no haya dos aristas que compartan un punto final son los conjuntos independientes de una segunda matroide de partición. Por lo tanto, el problema de coincidencia máxima bipartita se puede representar como una intersección matroide de estas dos matroides. ^[4] ${\displaystyle (U,V)}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle d_{i}}$ ${\displaystyle V}$

De manera más general, las coincidencias de un gráfico pueden representarse como una intersección de dos matroides si y solo si cada ciclo impar en el gráfico es un triángulo que contiene dos o más vértices de grado dos. ^[5]

complejos de camarilla

Un complejo de camarilla es una familia de conjuntos de vértices de un gráfico que inducen subgrafos completos de . Un complejo de camarilla forma una matroide si y solo si es un grafo multipartito completo y, en este caso, la matroide resultante es una matroide de partición. Los complejos de camarilla son exactamente los sistemas de conjuntos que pueden formarse como intersecciones de familias de matroides de partición para las cuales cada . ^[6] ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle d_{i}=1}$

Enumeración

El número de matroides de partición distintas que se pueden definir sobre un conjunto de elementos etiquetados, para , es ${\displaystyle n}$ ${\displaystyle n=0,1,2,\dots }$

1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... (secuencia A005387 en el OEIS ).

La función generadora exponencial de esta secuencia es . ^[7] ${\displaystyle f(x)=\exp(e^{x}(x-1)+2x+1)}$

Referencias

1. Recski, A. (1975), "Sobre matroides particionales con aplicaciones", Conjuntos infinitos y finitos (Colloq., Keszthely, 1973; dedicado a P. Erdős en su 60 cumpleaños), vol. III , coloq. Matemáticas. Soc. János Bolyai, vol. 10, Amsterdam: Holanda Septentrional, págs. 1169-1179, SEÑOR  0389630.
2. Lawler, Eugene L. (1976), Optimización combinatoria: redes y matroides , Rinehart y Winston, Nueva York: Holt, p. 272, señor  0439106.
3. Por ejemplo, consulte Kashiwabara, Okamoto & Uno (2007). Lawler (1976) utiliza la definición más amplia pero señala que la restricción es útil en muchas aplicaciones. ${\displaystyle d_{i}=1}$
4. Papadimitriou, Christos H .; Steiglitz, Kenneth (1982), Optimización combinatoria: algoritmos y complejidad , Englewood Cliffs, Nueva Jersey: Prentice-Hall Inc., págs. 289–290, ISBN 0-13-152462-3, señor  0663728.
5. Fekete, Sándor P.; Firla, Robert T.; Spille, Bianca (2003), "Caracterización de coincidencias como la intersección de matroides", Métodos matemáticos de investigación de operaciones , 58 (2): 319–329, arXiv : math/0212235 , doi :10.1007/s001860300301, MR  2015015.
6. Kashiwabara, Kenji; Okamoto, Yoshio; Uno, Takeaki (2007), "Representación matroide de complejos de camarilla", Matemáticas aplicadas discretas , 155 (15): 1910-1929, doi : 10.1016/j.dam.2007.05.004 , MR  2351976. Para obtener los mismos resultados en una forma complementaria utilizando conjuntos independientes en lugar de camarillas, consulte Tyshkevich, RI ; Urbanovich, OP; Zverovich, I. È. (1989), "Descomposición matroidal de un grafo", Combinatoria y teoría de grafos (Varsovia, 1987) , Banach Center Publ., vol. 25, Varsovia: PWN, págs. 195-205, MR  1097648.
7. Recski, A. (1974), "Enumeración de matroides particionales", Studia Scientiarum Mathematicarum Hungarica , 9 : 247–249 (1975), MR  0379248.