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 con signo también pueden denominarse conjuntos graduados . [ ^2] ${\displaystyle \mathbb {Z} _{2}}$

Solicitud

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

También pueden utilizarse 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 utilizar 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 con signo de cardinalidad es ${\displaystyle n}$ ${\displaystyle 3^{n}}$ ${\displaystyle r}$

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

y sumando estos obtenemos un ejemplo del teorema del binomio ,

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

Familias entrecruzadas

Un análogo del teorema de Erdős–Ko–Rado sobre familias de conjuntos que se intersectan se aplica también a los conjuntos con signo. La intersección de dos conjuntos con signo se define como el conjunto con signo de elementos 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, una familia de intersección de este tamaño se puede obtener eligiendo el signo de un único elemento fijo y tomando la familia como todos los subconjuntos con signo de cardinalidad que contienen este elemento con este signo. Este teorema se deduce inmediatamente del teorema de Erdős–Ko–Rado sin signo, ya que las versiones sin signo de los subconjuntos forman una familia de intersección y cada conjunto sin signo puede corresponder a lo sumo 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 , MR  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; véase en particular la sección 3.4, pág. 15
3. Bollobás, B. ; Leader, I. (1997), "Un teorema de Erdős–Ko–Rado para conjuntos con signo", Computers and Mathematics with Applications , 34 (11): 9–13, doi : 10.1016/S0898-1221(97)00215-0 , MR  1486880
4. Metropolis, N. ; Rota, Gian-Carlo (1978), "Sobre la red de caras del cubo", Boletín de la Sociedad Matemática Americana , 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