Матроид раздела

В математике матроид разделов или матроид разделов — это матроид , который представляет собой прямую сумму однородных матроидов . Он определяется в базовом наборе, в котором элементы разделены на разные категории. Для каждой категории существует ограничение емкости — максимальное количество разрешенных элементов из этой категории. Независимыми множествами матроида разбиения являются именно те множества, в которых для каждой категории число элементов из этой категории не превосходит емкости категории.

Формальное определение

Позволять $C_{i}$ быть совокупностью непересекающихся множеств («категорий»). Позволять $d_{i}$ быть целыми числами с $0\leq d_{i}\leq |C_{i}|$ («мощности»). Определить подмножество $I\subset \bigcup _{i}C_{i}$ быть «независимым», когда для каждого индекса $i$, $|I\cap C_{i}|\leq d_{i}$. Множества, удовлетворяющие этому условию, образуют независимые множества матроида , называемого матроидом разбиения .

Наборы $C_{i}$ называются категориями или блоками матроида раздела.

Основой матроида разбиения является множество, пересечение которого с каждым блоком $C_{i}$ имеет точный размер $d_{i}$. Схема блока матроида является подмножеством одного $C_{i}$ точно с размером $d_{i}+1$. Ранг ​ матроида $\sum d_{i}$.

Каждый форменный матроид $U{}_{n}^{r}$ это матроид раздела с одним блоком $C_{1}$ из $n$ элементы и с $d_{1}=r$. Каждый матроид разбиения представляет собой прямую сумму набора однородных матроидов, по одному на каждый из его блоков.

В некоторых публикациях понятие матроида раздела определяется более строго: каждый $d_{i}=1$. Разделы, которые подчиняются этому более строгому определению, представляют собой трансверсальные матроиды семейства непересекающихся множеств, заданных их блоками.

Характеристики

Как и в случае с однородными матроидами, из которых они сформированы, двойной матроид матроида раздела также является матроидом раздела, и каждый минор матроида раздела также является матроидом раздела. Прямые суммы матроидов разбиений также являются матроидами разбиений.

Соответствие

Максимальное паросочетание в графе — это максимально большой набор ребер при условии, что никакие два ребра не имеют общей конечной точки. В двудольном графе с двудольным разделением $(U,V)$, наборы ребер, удовлетворяющие условию, что никакие два ребра не имеют общей конечной точки в $U$ — независимые множества матроида разбиения с одним блоком на вершину в $U$ и с каждым из чисел $d_{i}$ равен единице. Наборы ребер, удовлетворяющие условию, что никакие два ребра не имеют общей конечной точки в $V$ являются независимыми множествами матроида второго раздела. Следовательно, двудольную задачу о максимальном согласовании можно представить как матроидное пересечение этих двух матроидов.

В более общем смысле паросочетания графа можно представить как пересечение двух матроидов тогда и только тогда, когда каждый нечетный цикл в графе представляет собой треугольник, содержащий две или более вершин второй степени.

Кликовые комплексы

Кликовый комплекс — это семейство множеств вершин графа. $G$ которые индуцируют полные подграфы $G$. Кликовый комплекс образует матроид тогда и только тогда, когда $G$ — полный многодольный граф , и в этом случае результирующий матроид является матроидом разбиения. Кликовые комплексы — это именно те системы множеств, которые могут образовываться как пересечения семейств матроидов разбиений, для которых каждое $d_{i}=1$.

Перечисление

Число различных матроидов разделов, которые можно определить на множестве $n$ маркированные элементы, для $n=0,1,2,\dots$, является

1, 2, 5, 16, 62, 276, 1377, 7596, 45789, 298626, 2090910, ... (последовательность A005387 в OEIS ).

Экспоненциальная производящая функция этой последовательности равна $f(x)=\exp(e^{x}(x-1)+2x+1)$.