Conjunto firmado

En matemáticas, un conjunto con signo es un conjunto de elementos junto con una asignación de un signo (positivo o negativo) a cada elemento del conjunto.

Representación

Los conjuntos con signo pueden representarse matemáticamente como un par ordenado de conjuntos disjuntos , un conjunto para sus elementos positivos y otro para sus elementos negativos. ^[1] Alternativamente, pueden representarse como una función booleana , una función cuyo dominio es el conjunto sin signo subyacente (posiblemente especificado explícitamente como una parte separada de la representación) y cuyo rango es un conjunto de dos elementos que representa los signos. ^{[2] [3]}

Los conjuntos firmados también pueden denominarse conjuntos graduados . ^[2] ${\displaystyle \mathbb {Z} _{2}}$

Solicitud

Los conjuntos con signo son fundamentales para la definición de matroides orientadas . ^[1]

También pueden usarse para definir las caras de un hipercubo . Si el hipercubo consta de todos los puntos en el espacio euclidiano de una dimensión dada cuyas coordenadas cartesianas están en el intervalo , entonces se puede usar un subconjunto con signo de los ejes de coordenadas para especificar los puntos cuyas coordenadas dentro del subconjunto son o (según el signo en el subconjunto con signo) y cuyas otras coordenadas pueden estar en cualquier parte del intervalo . Este subconjunto de puntos forma una cara, cuya codimensión es la cardinalidad del subconjunto con signo. ^[4] ${\displaystyle [-1,+1]}$ ${\displaystyle -1}$ ${\displaystyle +1}$ ${\displaystyle [-1,+1]}$

combinatoria

Enumeración

El número de subconjuntos con signo de un conjunto finito dado de elementos es una potencia de tres , porque hay tres opciones para cada elemento: puede estar ausente del subconjunto, estar presente con signo positivo o presente con signo negativo. ^[5] Por la misma razón, el número de subconjuntos de cardinalidad con signo es ${\displaystyle n}$ ${\displaystyle 3^{n}}$ ${\displaystyle r}$

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

y sumarlos da un ejemplo del teorema del binomio ,

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

Familias que se cruzan

Un análogo del teorema de Erdős-Ko-Rado sobre la intersección de familias de conjuntos también es válido para conjuntos con signo. La intersección de dos conjuntos con signo se define como el conjunto de elementos con signo que pertenecen a ambos y tienen el mismo signo en ambos. Según este teorema, para cualquier colección de subconjuntos con signo de un conjunto de elementos, todos con cardinalidad y todos los pares con una intersección no vacía, el número de subconjuntos con signo en la colección es como máximo ${\displaystyle n}$ ${\displaystyle r}$

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

Por ejemplo, se puede obtener una familia que se cruza de este tamaño eligiendo el signo de un único elemento fijo y considerando que la familia son todos los subconjuntos de cardinalidad con signo que contienen este elemento con este signo. Porque este teorema se deriva inmediatamente del teorema de Erdős-Ko-Rado sin signo, ya que las versiones sin signo de los subconjuntos forman una familia que se cruza y cada conjunto sin signo puede corresponder como máximo a conjuntos con signo. Sin embargo, para valores mayores se necesita una prueba diferente. ^[3] ${\displaystyle r}$ ${\displaystyle r\leq n/2}$ ${\displaystyle 2^{r-1}}$ ${\displaystyle r}$

Referencias

1. Las Vergnas, Michel (1980), "Convexidad en matroides orientadas", Journal of Combinatorial Theory , Serie B, 29 (2): 231–243, doi : 10.1016/0095-8956(80)90082-9 , SEÑOR  0586435
2. Brini, A. (julio de 2005), "Combinatoria, superálgebras, teoría invariante y teoría de la representación", Séminaire Lotharingien de Combinatoire , 55 , art. B55g, señor  2373407; ver en particular la Sección 3.4, p. 15
3. Bollobás, B .; Leader, I. (1997), "Un teorema de Erdős-Ko-Rado para conjuntos con signo", Computadoras y matemáticas con aplicaciones , 34 (11): 9–13, doi : 10.1016/S0898-1221(97)00215-0 , Señor  1486880
4. Metrópolis, N .; Rota, Gian-Carlo (1978), "Sobre el entramado de caras del cubo", Boletín de la Sociedad Matemática Estadounidense , 84 (2): 284–286, doi : 10.1090/S0002-9904-1978-14477-2 , señor  0462997 ${\displaystyle n}$
5. Esta fórmula para el número de subconjuntos con signo y el número de caras de un hipercubo se generaliza al número de caras de un politopo de Hanner ; ver Kalai, Gil (1989), "El número de caras de politopos centralmente simétricos", Graphs and Combinatorics , 5 (1): 389–391, doi :10.1007/BF01788696, MR  1554357