Matroide de partición

En matemáticas, un matroide de partición o matroide particional es un matroide que es 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 : un número máximo de elementos permitidos de dicha categoría. Los conjuntos independientes de un matroide de partición son precisamente aquellos en los que, para cada categoría, el número de elementos de esta categoría es como máximo igual a la capacidad de la categoría.

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

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

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

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

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

Al igual que los matroides uniformes de los que se forman, el matroide dual de un matroide de partición también es un matroide de partición, y todo menor de un matroide de partición también es un matroide de partición. Las sumas directas de matroides de partición también son matroides de partición.

Un emparejamiento máximo en un grafo 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 extremo. En un grafo bipartito con bipartición${\displaystyle (U,V)}$, los conjuntos de aristas que satisfacen la condición de que no hay dos aristas que compartan un punto final en${\displaystyle U}$son los conjuntos independientes de un matroide de partición con un bloque por vértice en${\displaystyle U}$y con cada uno de los números${\displaystyle d_{i}}$igual a uno. Los conjuntos de aristas que satisfacen la condición de que no hay dos aristas que compartan un extremo en${\displaystyle V}$son los conjuntos independientes de un segundo matroide de partición. Por lo tanto, el problema de emparejamiento máximo bipartito puede representarse como una intersección de matroides de estos dos matroides. ^{[ 4 ]}

De manera más general, los emparejamientos de un grafo pueden representarse como la intersección de dos matroides si y solo si cada ciclo impar en el grafo es un triángulo que contiene dos o más vértices de grado dos. ^{[ 5 ]}

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

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

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${\displaystyle f(x)=\exp(e^{x}(x-1)+2x+1)}$. ^{[ 7 ]}