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.

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

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

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

Cada matroide uniforme es un matroide de partición, con un único bloque de elementos y con . Cada matroide de partición es la suma directa de una colección de matroides uniformes, uno por 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 cumplen esta definición más restrictiva son los matroides transversales de la familia de conjuntos disjuntos dados por sus bloques. ^{[ 3 ]}${\displaystyle d_{i}=1}$

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 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 , los conjuntos de aristas que satisfacen la condición de que no haya dos aristas que compartan un extremo en son los conjuntos independientes de un 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 extremo en son los conjuntos independientes de un segundo matroide de partición. Por lo tanto, el problema del emparejamiento máximo bipartito puede representarse como la intersección de estos dos matroides. ^{[ 4 ]}${\displaystyle (U,V)}$${\displaystyle U}$${\displaystyle U}$${\displaystyle d_{i}}$${\displaystyle V}$

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 que inducen subgrafos completos de . Un complejo de cliques forma un matroide si y solo si 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 . ^{[ 6 ]}${\displaystyle G}$${\displaystyle G}$${\displaystyle G}$${\displaystyle d_{i}=1}$

El número de matroides de partición distintos 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)}$