Número de Dedekind

En combinatoria, los números de Dedekind son una sucesión entera de rápido crecimiento cuyo nombre se dio póstumamente en honor a Richard Dedekind, quien las definió por primera vez en 1897.^[1]​ El número de Dedekind M(n) corresponde, equivalentemente, a lo siguiente:

• El número de funciones booleanas monótonas de n variables.
• El número de anticadenas de subconjuntos de un conjunto de n elementos.
• El número de elementos en un retículo distributivo libre con n generadores.
• El número de juegos simples irredundantes definibles sobre n jugadores.
• El número de hipergrafos minimales completos, definibles sobre un conjunto base de cardinalidad n.
• El número de familias de Sperner sobre un conjunto de n elementos.

Encontrar una expresión matemática de forma cerrada para M(n) se conoce como el Problema de Dedekind. Aunque existen aproximaciones asintóticas que estiman este número,^[2]​^[3]​^[4]​ y una expresión exacta en forma de sumatoria,^[5]​ el cómputo de M(n) sigue siendo ineficiente, y sus valores exactos sólo se conocen para valores n ≤ 9.^[6]​^[7]​^[8]​

Ejemplo

Para n = 2, existen seis funciones booleanas monótonas y seis anticadenas de subconjuntos del conjunto de dos elementos {x,y}:

• La función f(x,y) = falso, que ignora sus valores de entrada y siempre retorna falso, corresponde a la anticadena vacía Ø.
• La conjunción lógica f(x,y) = x ∧ y corresponde a la anticadena { {x,y} }, que contiene al conjunto {x,y}.
• La función f(x,y) = x, que ignora su segundo argumento y retorna el primero, corresponde a la anticadena { {x} } que contiene al conjunto {x}.
• La función f(x,y) = y, que ignora su primer argumento y retorna el segundo, corresponde a la anticadena { {y} } que contiene al conjunto {y}.
• La disyunción lógica f(x,y) = x ∨ y corresponde a la anticadena { {x}, {y} }, que contiene a los dos conjuntos {x} e {y}.
• La función f(x,y) = verdadero, que ignora sus valores de entrada y siempre retorna verdadero, corresponde a la anticadena {Ø} que contiene sólo al conjunto vacío.

Valores conocidos

Los valores exactos de los números de Dedekind se conocen para 0 ≤ n ≤ 9. La siguiente tabla muestra tales números, junto con el año y la publicación en que fueron calculados:

Si n es un número par, entonces M(n) también debería serlo.^[13]​ El cálculo de M(5) = 7581 fue el contraejemplo que desaprobó una conjetura realizada por Garrett Birkhoff que decía que M(n) es siempre divisible por (2n - 1)(2n - 2).^[9]​

Fórmula con sumatoria

Andrzej Kisielewicz en 1988 demostró la siguiente fórmula para los números de Dedekind:^[5]​

${\displaystyle M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{k}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i} b_{m}^{i}b_{m}^{j})\right),}$

donde

${\displaystyle b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i 1}}}\right\rfloor .}$

Sin embargo, esta fórmula no es útil para el cómputo de los valores de M(n) para n grandes, debido al gran número de términos en la sumatoria.

Asíntotas

El logaritmo de los números de Dedekind puede ser estimado exactamente mediante las cotas

${\displaystyle {n \choose \lfloor n/2\rfloor }\leq \log _{2}M(n)\leq {n \choose \lfloor n/2\rfloor }\left(1 O\left({\frac {\log n}{n}}\right)\right).}$

La inecuación de la izquierda cuenta el número de anticadenas en que cada conjunto tiene exactamente ${\displaystyle \lfloor n/2\rfloor }$ elementos, y la inecuación derecha fue demostrada por Kleitman y Markowsky.^[2]​

A. D. Korshunov encontró en 1981 una estimación aún mejor:^[14]​

${\displaystyle M(n)=(1 o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)}$

para n par, y

${\displaystyle M(n)=(1 o(1))2^{n \choose \lfloor n/2\rfloor }\exp(b(n) c(n))}$

para n impar, donde

${\displaystyle a(n)={n \choose n/2-1}(2^{-n/2} n^{2}2^{-n-5}-n2^{-n-4}),}$

${\displaystyle b(n)={n \choose (n-3)/2}(2^{-(n 3)/2}-n^{2}2^{-n-6}-n2^{-n 3}),}$

y

${\displaystyle c(n)={n \choose (n-1)/2}(2^{-(n 1)/2} n^{2}2^{-n-4}).}$

La principal idea detrás de estas estimaciones, es que en la mayoría de las anticadenas, todos los conjuntos tienen tamaños muy cercanos a n/2.^[15]​ Para n = 2, 4, 6 y 8, la fórmula de Korshunov provee una estimación imprecisa por un factor de 9.8%, 10.2%, 4.1%, y -3.3%, respectivamente.^[16]​

Referencias