В математике набор со знаком - это набор элементов вместе с присвоением знака (положительного или отрицательного) каждому элементу набора.
Представление
Подписанные наборы могут быть математически представлена в виде упорядоченной пары из множества непересекающихся , один набор для их положительных элементов , а другой для их отрицательных элементов. [1] В качестве альтернативы, они могут быть представлены как логическая функция , функция, домен которой является лежащим в основе беззнаковым набором (возможно, явно заданным как отдельная часть представления) и чей диапазон представляет собой набор из двух элементов, представляющий знаки. [2] [3]
Подписанные множества также могут называться - градуированные наборы . [2]
Заявление
Знаковые множества являются фундаментальными для определения ориентированных матроидов . [1]
Они также могут быть использованы для определения лица из более гиперкуба . Если гиперкуб состоит из всех точек евклидова пространства данного измерения, декартовы координаты которых находятся в интервале, то подписанное подмножество осей координат может использоваться для указания точек, координаты которых в подмножестве равны или же (согласно знаку в подписанном подмножестве) и чьи другие координаты могут быть где угодно в интервале . Это подмножество точек образует грань, коразмерность которой равна мощности подписанного подмножества. [4]
Комбинаторика
Перечисление
Количество подписанных подмножеств данного конечного множества из элементы , степень трех , потому что есть три варианта для каждого элемента: он может отсутствовать в подмножестве, присутствовать с положительным знаком или присутствовать с отрицательным знаком. [5] По той же причине количество подписанных подмножеств мощности является
и их суммирование дает пример биномиальной теоремы ,
Пересекающиеся семьи
Аналог теоремы Эрдеша – Ко – Радо о пересечении семейств множеств верен и для знаковых множеств. Пересечение двух наборов со знаком определяется как набор элементов со знаком, которые принадлежат обоим и имеют одинаковый знак в обоих. Согласно этой теореме для любого набора знаковых подмножеств-элементный набор, у всех есть мощность и всех пар, имеющих непустое пересечение, количество подмножеств со знаком в коллекции не превышает
Например, пересекающееся семейство такого размера можно получить, выбрав знак одного фиксированного элемента и взяв в качестве семейства все подписанные подмножества мощности которые содержат этот элемент с этим знаком. Для эта теорема немедленно следует из беззнаковой теоремы Эрдеша – Ко – Радо, поскольку беззнаковые версии подмножеств образуют пересекающееся семейство, и каждому беззнаковому набору может соответствовать не более подписанные наборы. Однако для больших значенийтребуется другое доказательство. [3]
Рекомендации
- ^ Б Лас Vergnas, Мишель (1980), "Выпуклость в ориентированных матроидов", Журнал комбинаторной теории , серии B, 29 (2): 231-243, DOI : 10,1016 / 0095-8956 (80) 90082-9 , М.Р. 0586435
- ^ а б Брини, А. (июль 2005 г.), "Комбинаторика, супералгебры, теория инвариантов и теория представлений" , Séminaire Lotharingien de Combinatoire , 55 , Art. B55g, Руководство по ремонту 2373407; см., в частности, раздел 3.4, с. 15
- ^ а б Боллобаш, Б .; Лидер, И. (1997), " О теореме Эрдеша-Ко-Радо для подписанных наборов", компьютеры и математики с приложениями , 34 (11): 9-13, DOI : 10.1016 / S0898-1221 (97) 00215-0 , Руководство по ремонту 1486880
- ^ Метрополис, Н .; Рота, Джан-Карло (1978), "О решетке граней-CUBE», Бюллетень Американского математического общества , 84 (2): 284-286, DOI : 10,1090 / S0002-9904-1978-14477-2 , MR 0462997
- ^ Эта формула для количества подмножеств со знаком и количества граней гиперкуба обобщается на количество граней многогранника Ханнера ; видеть Калай, Гир (1989), "Число граней центрально-симметричных многогранников", графов и комбинаторика , 5 (1): 389-391, DOI : 10.1007 / BF01788696 , МР 1554357