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.
![](../I/Monotone_Boolean_functions_0%252C1%252C2%252C3.svg.png.webp)
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:
![](../I/Numeros_Dedekind.jpg.webp)
n | Número M(n) | Año |
---|---|---|
0 | 2 | 1940[1] |
1 | 3 | 1940[1] |
2 | 6 | 1940[1] |
3 | 20 | 1940[1] |
4 | 168 | 1940[1] |
5 | 7 581 | 1940[9] |
6 | 7 828 354 | 1946[10] |
7 | 2 414 682 040 998 | 1965[11] y 1976[12] |
8 | 56 130 437 228 687 557 907 788 | 1991[6] |
9 | 286 386 577 668 298 411 128 469 151 667 598 498 812 366 | 2023[7][8] |
(sucesión A000372 en OEIS) |
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]
donde
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
La inecuación de la izquierda cuenta el número de anticadenas en que cada conjunto tiene exactamente 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]
para n par, y
para n impar, donde
y
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
- Dedekind, Richard (1897), Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler 2, Gesammelte Werke, pp. 103-148..
- Kleitman, D.; Markowsky, G. (1975), «On Dedekind's problem: the number of isotone Boolean functions. II», Transactions of the American Mathematical Society 213: 373-390, MR0382107..
- Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855..
- Kahn, Jeff (2002), «Entropy, independent sets and antichains: a new approach to Dedekind's problem», Proceedings of the American Mathematical Society 130 (2): 371-378, doi:10.1090/S0002-9939-01-06058-0, MR1862115..
- Kisielewicz, Andrzej (1988), «A solution of Dedekind's problem on the number of isotone Boolean functions», Journal für die Reine und Angewandte Mathematik 386: 139-144, doi:10.1515/crll.1988.386.139, MR936995..
- Wiedemann, Doug (1991), «A computation of the eighth Dedekind number», Order 8 (1): 5-6, doi:10.1007/BF00385808, MR1129608..
- Jäkel, Christian (5 de abril de 2023). «A computation of the ninth Dedekind Number». arXiv:2304.00895 [math].
- Van Hirtum, Lennart (6 de abril de 2023). «A computation of D(9) using FPGA Supercomputing». arXiv:2304.03039 [math].
- Church, Randolph (1940), «Numerical analysis of certain free distributive structures», Duke Mathematical Journal 6: 732-734, MR0002842..
- Ward, Morgan (1946), «Note on the order of free distributive lattices», Bulletin of the American Mathematical Society 52: 423..
- Church, Randolph (1965), «Enumeration by rank of the free distributive lattice with 7 generators», Notices of the American Mathematical Society 11: 724.. Citado por Wiedemann, 1991.
- Berman, Joel; Köhler, Peter (1976), «Cardinalities of finite distributive lattices», Mitt. Math. Sem. Giessen 121: 103-124, MR0485609..
- Yamamoto, Koichi (1953), «Note on the order of free distributive lattices», Science Reports of the Kanazawa University 2 (1): 5-6, MR0070608..
- Korshunov, A. D. (1981), «The number of monotone Boolean functions», Problemy Kibernet. 38: 5-108, MR0640855..
- Zaguia, Nejib (1993), «Isotone maps: enumeration and structure», en Sauer, N. W.; Woodrow, R. E.; Sands, B., eds., Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991), Kluwer Academic Publishers, pp. 421-430, MR1261220..
- Brown, K. S., Generating the monotone Boolean functions, archivado desde el original el 18 de diciembre de 2010, consultado el 3 de octubre de 2010..