Подписанный набор - Signed set

В математике подписанный набор это набор элементов вместе с присвоением знак (положительный или отрицательный) к каждому элементу набора.

Представление

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

Подписанные множества могут также называться ${ Displaystyle mathbb {Z} _ {2}}$ -градуированные наборы.^[2]

Заявление

Знаковые множества являются фундаментальными для определения ориентированные матроиды.^[1]

Их также можно использовать для определения лица из гиперкуб. Если гиперкуб состоит из всех точек в Евклидово пространство данного измерения, чья Декартовы координаты находятся в интервале ${ displaystyle [-1, + 1]}$ , то подписанное подмножество осей координат может использоваться для указания точек, координаты которых в подмножестве ${ displaystyle -1}$ или же ${ displaystyle +1}$ (согласно знаку в подписанном подмножестве) и чьи другие координаты могут быть где угодно в интервале ${ displaystyle [-1, + 1]}$ . Это подмножество точек образует грань, коразмерность это мощность подписанного подмножества.^[4]

Комбинаторика

Перечисление

Количество подписанных подмножеств данного конечный набор из ${ displaystyle n}$ элементы ${ displaystyle 3 ^ {n}}$ , а степень трех, потому что есть три варианта выбора для каждого элемента: он может отсутствовать в подмножестве, присутствовать с положительным знаком или присутствовать с отрицательным знаком.^[5] По той же причине количество подписанных подмножеств мощности ${ displaystyle r}$ является

{ displaystyle 2 ^ {r} { binom {n} {r}},}

и их суммирование дает пример биномиальная теорема,

{ displaystyle sum _ {r} 2 ^ {r} { binom {n} {r}} = 3 ^ {n}.}

Пересекающиеся семьи

Аналог Теорема Эрдеша – Ко – Радо. на пересекающихся семействах множеств верно и для множеств со знаком. Пересечение двух наборов со знаком определяется как набор элементов со знаком, которые принадлежат обоим и имеют одинаковый знак в обоих. Согласно этой теореме для любого набора подписанных подмножеств ${ displaystyle n}$ - набор элементов, все имеют мощность ${ displaystyle r}$ и всех пар, имеющих непустое пересечение, количество подписанных подмножеств в коллекции не превышает

{ displaystyle 2 ^ {r-1} { binom {n-1} {r-1}}.}

Например, пересекающееся семейство такого размера может быть получено путем выбора знака единственного фиксированного элемента и принятия в качестве семейства всех знаковых подмножеств мощности ${ displaystyle r}$ которые содержат этот элемент с этим знаком. За ${ Displaystyle г Leq п / 2}$ эта теорема немедленно следует из беззнаковой теоремы Эрдеша – Ко – Радо, поскольку беззнаковые версии подмножеств образуют пересекающееся семейство, и каждому беззнаковому набору может соответствовать не более ${ displaystyle 2 ^ {r-1}}$ подписанные наборы. Однако для больших значений ${ displaystyle r}$ требуется другое доказательство.^[3]

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

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

[lv-1] а ^б Лас Вергнас, Мишель (1980), «Выпуклость в ориентированных матроидах», Журнал комбинаторной теории, Серия B, 29 (2): 231–243, Дои:10.1016/0095-8956(80)90082-9, МИСТЕР 0586435

[b-2] а ^б Брини, А. (июль 2005 г.), «Комбинаторика, супералгебры, теория инвариантов и теория представлений», Séminaire Lotharingien de Combinatoire, 55, Изобразительное искусство. B55g, МИСТЕР 2373407; см., в частности, раздел 3.4, с. 15

[bl-3] а ^б Боллобаш, Б.; Лидер И. (1997), "Теорема Эрдеша – Ко – Радо для знаковых множеств", Компьютеры и математика с приложениями, 34 (11): 9–13, Дои:10.1016 / S0898-1221 (97) 00215-0, МИСТЕР 1486880

[mr-4] Метрополис, Н.; Рота, Джан-Карло (1978), «О решетке граней ${ displaystyle n}$ -куб », Бюллетень Американского математического общества, 84 (2): 284–286, Дои:10.1090 / S0002-9904-1978-14477-2, МИСТЕР 0462997

[k-5] Эта формула для количества подмножеств со знаком и количества граней гиперкуба обобщается на количество граней Многогранник Ханнера; видеть Калаи, Гил (1989), "Число граней центрально-симметричных многогранников", Графы и комбинаторика, 5 (1): 389–391, Дои:10.1007 / BF01788696, МИСТЕР 1554357

[1]

[2]

[3]

[4]

[5]