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

Transversal (combinatorics)
Для использования в других целях см. Поперечный (значения).

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

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

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

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

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

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

Теорема. Позволять S1, S2, ..., Sм набор таких множеств, что содержит как минимум k элементы для k = 1,2,...,м и для всех k-combinations {} целых чисел 1,2, ...,м и предположим, что каждое из этих множеств содержит не менее т элементы. Если т ≤ м то в коллекции не менее т ! СДР, и если т > м то в коллекции не менее т ! / (т - м)! СДР.

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

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

Можно построить гиперграф в котором вершины - элементы, а гиперребра - множества. Тогда трансверсаль эквивалентна крышка вершины в гиперграфе.

Примеры

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

Как частный случай предыдущего примера, учитывая прямое произведение групп , тогда ЧАС трансверсаль для смежных классов K.

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

Другой пример трансверсалии на основе разбиения возникает, когда рассматривается отношение эквивалентности, известное как (теоретико-множественное) ядро ​​функции, определенная для функции с домен Икс как раздел домена . который разделяет домен ж в классы эквивалентности, так что все элементы в классе отображаются через ж к той же стоимости. Если ж инъективен, есть только одна трансверсальность . Для необязательно инъективного ж, фиксируя поперечный Т из индуцирует взаимно однозначное соответствие между Т и изображение из ж, далее обозначаемый . Следовательно, функция хорошо определяется тем свойством, что для всех z в куда Икс уникальный элемент в Т такой, что ; более того, грамм может быть расширен (не обязательно уникальным образом) так, чтобы он был определен в целом codomain из ж выбирая произвольные значения для г (г) когда z вне образа ж. Это простой расчет, чтобы убедиться, что грамм таким образом определенное имеет свойство, что , что является доказательством (когда область и область значений ж один и тот же набор), что полугруппа полного преобразования это регулярная полугруппа. действует как (не обязательно уникальный) квазиобратный за ж; в теории полугрупп это просто называется обратным. Однако обратите внимание, что для произвольного грамм с указанным свойством «двойственное» уравнение может не выдержать. Однако если обозначить через , тогда ж является квазиобратным к час, т.е. .

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

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

[8]

Обобщения

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

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

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

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

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

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

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

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

Рекомендации

  1. ^ Джон Макинтош Хауи (1995). Основы теории полугрупп. Кларендон Пресс. п. 63. ISBN 978-0-19-851194-6.
  2. ^ Клайв Рейс (2011). Абстрактная алгебра: введение в группы, кольца и поля. World Scientific. п. 57. ISBN 978-981-4335-64-5.
  3. ^ Бруно Курсель; Йост Энгельфриет (2012). Структура графа и монадическая логика второго порядка: теоретико-языковой подход. Издательство Кембриджского университета. п. 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 0-13-602040-2
  7. ^ Райзер, Герберт Джон (1963), Комбинаторная математика, The Carus Mathematical Monographs # 14, Математическая ассоциация Америки
  8. ^ Э. К. Милнер (1974), ТРАНСВЕРСАЛЬНАЯ ТЕОРИЯ, Труды международного конгресса математиков, п. 161
  9. ^ Оксли, Джеймс Г. (2006), Теория матроидов, Оксфордские выпускные тексты по математике, 3, Oxford University Press, стр. 48, ISBN 978-0-19-920250-8.

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

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