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

Множество, пересекающее каждое из семейства множеств

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

• Один из вариантов заключается в том, что существует биекция f из трансверсали в C, такая, что x является элементом f ( x ) для каждого x в трансверсали. В этом случае трансверсаль также называется системой различных представителей (SDR). ^{[4] : 29}
• Другой, менее распространенный, не требует однозначного отношения между элементами трансверсали и множествами C. В этой ситуации члены системы представителей не обязательно различны. ^{[5] : 692  [6] : 322}

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

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

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

Следующее уточнение, предложенное HJ Ryser, дает нижние границы числа таких SDR. ^{[7] : 48}

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

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

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

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

Примеры

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

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

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

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

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

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

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

Обобщения

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

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

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

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

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

Сложность вычислений

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

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

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

Ссылки

1. Джон Макинтош Хауи (1995). Основы теории полугрупп . Clarendon Press. стр. 63. ISBN 978-0-19-851194-6.
2. Клайв Рейс (2011). Абстрактная алгебра: Введение в группы, кольца и поля . World Scientific. стр. 57. ISBN 978-981-4335-64-5.
3. Бруно Курсель ; Йост Энгельфрит (2012). Структура графа и монадическая логика второго порядка: подход к теории языка . Cambridge University Press. стр. 95. ISBN 978-1-139-64400-6.
4. Ловаш, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
5. Робертс, Фред С.; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), Бока-Ратон: CRC Press, ISBN 978-1-4200-9982-9
6. Бруальди, Ричард А. (2010), Введение в комбинаторику (5-е изд.), Аппер Сэддл Ривер, Нью-Джерси: Prentice Hall, ISBN 978-0-13-602040-0
7. Райзер, Герберт Джон (1963), Комбинаторная математика , Математические монографии Каруса № 14, Математическая ассоциация Америки
8. EC Milner (1974), ТРАНСВЕРСАЛЬНАЯ ТЕОРИЯ, Труды международного конгресса математиков , стр. 161
9. Оксли, Джеймс Г. (2006), Теория матроидов , Оксфордские тексты по математике, т. 3, Oxford University Press, стр. 48, ISBN 978-0-19-920250-8.
10. Хакселл, П. (2011-11-01). «О формировании комитетов». The American Mathematical Monthly . 118 (9): 777–788. doi :10.4169/amer.math.monthly.118.09.777. ISSN  0002-9890. S2CID  27202372.

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

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