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

Чтобы узнать о других значениях, см. Трансверсаль (значения) .

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

Другой пример трансверсали на основе разделения возникает, когда рассматривается отношение эквивалентности, известное как (теоретико-множественное) ядро ​​функции , определенное для функции $f$ с доменом X в качестве раздела домена $\operatorname {ker} f:=\left\{\,\left\{\,y\in X\mid f(x)=f(y)\,\right\}\mid x\in X\,\right\}$. который разбивает область определения f на классы эквивалентности так, что все элементы в классе сопоставляются через f с одним и тем же значением. Если f инъективен, существует только одна трансверсаль $\operatorname {ker} f$. Для не обязательно инъективного f , фиксируя трансверсальную T группы $\operatorname {ker} f$ индуцирует взаимно однозначное соответствие между T и образом f через , в дальнейшем обозначаемое $\operatorname {Im} f$. Следовательно, функция $g:(\operatorname {Im} f)\to T$ корректно определяется тем свойством, что для всех z в $\operatorname {Im} f,g(z)=x$ где x — единственный элемент в T такой, что $f(x)=z$; более того, g можно расширить (не обязательно единственным образом), так что он будет определен во всей кодомене f когда путем выбора произвольных значений для g(z), z находится вне образа f . Это простой расчет, позволяющий проверить, что определенное таким образом g обладает свойством, которое $f\circ g\circ f=f$, что является доказательством (когда область определения и область определения f являются одним и тем же множеством) того, что полугруппа полного преобразования является регулярной полугруппой . $g$ действует как (не обязательно единственный) квазиобратный для f ; в теории полугрупп это просто называется инверсией. Однако заметим, что для произвольного g с указанным выше свойством «двойственное» уравнение $g\circ f\circ g=g$ может не держаться. Однако если мы обозначим через $h=g\circ f\circ g$, то f является квазиобратной к h , т.е. $h\circ f\circ h=h$.

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

Общая трансверсаль наборов A и B (где $|A|=|B|=n$) — это множество, трансверсальное как A , так и B . Наборы A и B имеют общую трансверсаль тогда и только тогда, когда для всех $I,J\subset \{1,...,n\}$,

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

Обобщения

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

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

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

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

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

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

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

См. также

• Аксиома выбора
• Постоянный

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

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