Трансверсаль (комбинаторика) - Transversal (combinatorics)

В математике , особенно в комбинаторике , учитывая семейство множеств , здесь называемое коллекцией C , трансверсаль (также называемая поперечным сечением ) - это набор, содержащий ровно один элемент из каждого члена коллекции. Когда наборы коллекции попарно не пересекаются, каждый элемент трансверсали соответствует ровно одному члену C (набору, членом которого он является). Если исходные множества не пересекаются, есть две возможности для определения трансверсали:

Один из вариантов состоит в том, что существует биекция f из трансверсали в C, такая что x является элементом f ( x ) для каждого x в трансверсали. В этом случае трансверсаль также называют системой различных представителей (SDR).
Другие, менее широко используются, не требуют отношений один-к-одному между элементами поперечного и наборами C . В этой ситуации члены системы представителей не обязательно различны.

В информатике вычисление трансверсалей полезно в нескольких прикладных областях, при этом входное семейство наборов часто описывается как гиперграф .

Существование и количество

Фундаментальный вопрос при изучении SDR заключается в том, существует ли SDR. Теорема Холла о браке дает необходимые и достаточные условия для того, чтобы конечный набор множеств, некоторые из которых, возможно, перекрывались, имел трансверсаль. Условие состоит в том, что для каждого целого числа k каждый набор из k множеств должен содержать не менее k различных элементов.

Следующее уточнение Х. Дж. Райзера дает нижние оценки количества таких SDR.

Теорема . Пусть S ₁ , S ₂ , ..., S _m - набор множеств, содержащий не менее k элементов для k = 1,2, ..., m и для всех k- комбинаций { } целых чисел 1, 2, ..., m и предположим, что каждое из этих множеств содержит не менее t элементов. Если t ≤ m, то в наборе не менее t ! SDR, и если t > m, то в коллекции не менее t ! / ( т - м )! СДР. ${\ Displaystyle S_ {i_ {1}} \ чашка S_ {i_ {2}} \ чашка \ точки \ чашка S_ {i_ {k}}}$ ${\ displaystyle i_ {1}, i_ {2}, \ ldots, i_ {k}}$

Отношение к соответствию и покрытию

Можно построить двудольный граф, в котором вершины на одной стороне - это множества, вершины на другой стороне - это элементы, а ребра соединяют набор с элементами, которые он содержит. Тогда трансверсаль (определенная как система различных представителей) эквивалентна совершенному паросочетанию в этом графе.

Можно построить гиперграф, в котором вершины - элементы, а гиперребра - множества. Тогда трансверсаль (определенная как система необязательно различных представителей) является вершинным покрытием гиперграфа .

Примеры

В теории групп , дан подгруппа H из группы G , правый (соответственно слева) трансверсально представляет собой набор , содержащий ровно один элемент из каждых справа (соответственно слева) смежного класса из Н . В этом случае «множества» (смежные классы) попарно не пересекаются, т. Е. Смежные классы образуют разбиение группы.

В частном случае предыдущего примера, учитывая прямое произведение групп , то Н является трансверсален для смежных классов K . ${\ displaystyle G = H \ times K}$

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

Другой пример трансверсали на основе разбиения возникает, когда рассматривается отношение эквивалентности, известное как (теоретико-множественное) ядро функции , определенное для функции с областью определения X как разбиение области . который разбивает область определения f на классы эквивалентности, так что все элементы в классе отображаются через f в одно и то же значение. Если f инъективен, есть только одна трансверсаль к . Для не-обязательно-инъективного F , фиксирующий поперечная T из индуцирует взаимно однозначное соответствие одному между Т и изображениями из F , далее обозначается . Следовательно, функция корректно определяется тем свойством, что для всех z in, где x - единственный элемент в T такой, что ; кроме того, g может быть расширен (не обязательно уникальным образом), так что он определен во всей области области f путем выбора произвольных значений для g (z), когда z находится вне образа f . Это простое вычисление, чтобы проверить, что определенная таким образом g обладает свойством , которое является доказательством (когда область определения и область значений f - одно и то же множество), что полугруппа полного преобразования является регулярной полугруппой . действует как (не обязательно единственный) квазиобратный для f ; в теории полугрупп это просто называется обратным. Однако обратите внимание, что для произвольного g с вышеупомянутым свойством «двойственное» уравнение может не выполняться. Однако , если мы обозначим через , то е является квазиобратным ч , т.е. . ${\ displaystyle f}$ ${\ Displaystyle \ OperatorName {ker} f: = \ left \ {\, \ left \ {\, y \ in X \ mid f (x) = f (y) \, \ right \} \ mid x \ in X \,\верно\}}$ ${\ 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 е (х) = г}$ ${\ Displaystyle е \ сирк г \ сирк е = е}$ ${\ displaystyle g}$ ${\ Displaystyle г \ сирк е \ сирк г = г}$ ${\ Displaystyle ч = г \ сирк е \ сирк г}$ ${\ Displaystyle ч \ сирк е \ сирк ч = ч}$

Общие трансверсалии

Общие трансверсальна коллекции А и Б (где ) представляет собой набор , который является трансверсалью как A и B . Коллекции A и B имеют общую трансверсаль тогда и только тогда , когда для всех , ${\ Displaystyle | A | = | B | = п}$ ${\ displaystyle I, J \ subset \ {1, ..., n \}}$

{\ displaystyle | (\ bigcup _ {я \ in I} A_ {i}) \ cap (\ bigcup _ {j \ in J} B_ {j}) | \ geq | I | + | J | -n}

Обобщения

Частичная трансверсально представляет собой набор , содержащий не более одного элемента из каждого члена коллекции, или (в более строгой форме концепции) в комплекте с инъекцией из множества в C . Трансверсали конечного набора C конечных множеств образуют основу наборы в матроиде , то трансверсальна матроиды из C . Независимые наборы поперечной матроиды являются частичными трансверсалями С .

Независимая трансверсально (также называемый радужный-независимый набор или независимая система представителей ) является трансверсально который также является независимым множеством данного графа. Чтобы объяснить разницу в переносных терминах, рассмотрим факультет с m отделениями, где декан факультета хочет создать комитет из m членов, по одному члену на факультет. Такой комитет является трансверсальным. Но теперь предположим, что некоторые преподаватели не любят друг друга и не соглашаются вместе заседать в комитете. В этом случае комитет должен быть независимым трансверсалом, где лежащий в основе граф описывает отношения «неприязни».

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

Теория категорий

На языке теории категорий , трансверсально из совокупности непересекающихся множеств является раздел о факторизации индуцированной коллекции.

Вычислительная сложность

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

Смотрите также

дальнейшее чтение

Лоулер, Э.Л. Комбинаторная оптимизация: сети и матроиды. 1976 г.
Мирский, Леон (1971). Трансверсальная теория: изложение некоторых аспектов комбинаторной математики. Академическая пресса. ISBN 0-12-498550-5 .

Languages

In other projects