Conjunto firmado

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

Representación

Los conjuntos con signo se pueden representar matemáticamente como un par ordenado de conjuntos disjuntos , uno 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]}

Conjuntos firmados también pueden ser llamados - series graduadas . ^[2]${\displaystyle \mathbb {Z} _{2}}$

Solicitud

Los conjuntos firmados son fundamentales para la definición de matroides orientados . ^[1]

También se pueden utilizar 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, presente con signo positivo o presente con signo negativo. ^[5] Por la misma razón, el número de subconjuntos firmados de cardinalidad es${\displaystyle n}$${\displaystyle 3^{n}}$${\displaystyle r}$

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

y sumando estos da una instancia del teorema binomial ,

${\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 se aplica a los 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. De acuerdo con 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, una familia de intersección de este tamaño puede obtenerse eligiendo el signo de un solo elemento fijo y tomando la familia como todos los subconjuntos firmados de cardinalidad 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 a la mayoría de los 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 , MR  0586435
2. Brini, A. (julio de 2005), "Combinatoria, superalgebras, teoría invariante y teoría de la representación" , Séminaire Lotharingien de Combinatoire , 55 , Art. B55g, MR 2373407 ; ver en particular la Sección 3.4, p. 15
3. Bollobás, B .; Líder, 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), "En el enrejado de las caras del -cube", Boletín de la American Mathematical Society , 84 (2): 284-286, doi : 10.1090 / S0002-9904-1978-14477-2 , MR 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 ; véase 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