Введение

Множество, пересекающее каждый элемент семейства множеств.

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

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

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

Основной вопрос в исследовании SDR заключается в том, существует ли SDR. Теорема о браке Холла дает необходимые и достаточные условия для конечного набора множеств, некоторые из которых могут пересекаться, чтобы иметь поперечное сечение. Условие состоит в том, что для каждого целого числа k, любое сочетание из k множеств должно содержать в общем не менее k различных элементов. Теорема. Пусть S1, S2, ..., Sm – набор множеств, содержащий не менее k элементов для k = 1, 2, ..., m, и для всех k комбинаций {} целых чисел 1, 2, ..., m, предположим, что каждое из этих множеств содержит не менее t элементов. Если t ≤ m, то в наборе содержится не менее t! SDR, а если t > m, то в наборе содержится не менее t! / (t – m)! SDR.

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

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

Примеры

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

В общем случае, поскольку любое отношение эквивалентности на произвольном множестве порождает разбиение, выбор любого представителя из каждого класса эквивалентности дает поперечник. Другой пример поперечника, основанного на разбиении, возникает при рассмотрении отношения эквивалентности, известного как (теоретико-множественное) ядро функции, определенного для функции с областью определения X как разбиение области определения, которое разбивает область определения f на классы эквивалентности, такие, что все элементы в классе отображаются функцией f в одно и то же значение. Если f инъективна, существует только один поперечник. Для не обязательно инъективной f, фиксирование поперечника T для порождает взаимно однозначное соответствие между T и образом f, который далее обозначается как . Следовательно, функция хорошо определена свойством, что для всех z в , где x – единственный элемент в T, такой что ; кроме того, g можно расширить (не обязательно единственным образом) так, чтобы она была определена на всей области значений f, выбирая произвольные значения для g(z), когда z находится вне образа f. Легко проверить, что g, таким образом определенная, обладает свойством , что является доказательством (когда область определения и область значений f совпадают), что полная полугруппа преобразований является регулярной полугруппой. выступает в качестве (не обязательно единственного) квазиобратного для f; в теории полугрупп это просто называется обратным. Однако следует отметить, что для произвольного g с вышеупомянутым свойством "двойное" уравнение может не выполняться. Однако, если мы обозначаем , то f является квазиобратным для h, то есть .

Общие поперечные

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

Обобщения

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

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

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

Комплексность вычислений

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