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

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

Представительство

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

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

Приложение

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

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

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

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

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

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

и их суммирование дает пример биномиальной теоремы :

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

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

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

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

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

Ссылки

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

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

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

[bl-3] Перейти обратно: Перейти обратно: ^а ^б Боллобас, Б. ; Лидер, И. (1997), «Теорема Эрдеша – Ко – Радо для знаковых множеств», Computers and Mathematics with Applications , 34 (11): 9–13, doi : 10.1016/S0898-1221(97)00215-0 , МР 1486880

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

[k-5] Эта формула для количества подписанных подмножеств и количества граней гиперкуба обобщается на количество граней многогранника Ханнера ; видеть Калаи, Гил (1989), «Число граней центрально-симметричных многогранников», Graphs and Combinatorics , 5 (1): 389–391, doi : 10.1007/BF01788696 , MR 1554357

[1]

[2]

[3]

[4]

[5]