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
[editar]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
[editar]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:
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
[editar]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
[editar]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
[editar]- ↑ a b c d e f Dedekind, Richard (1897), Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler 2, Gesammelte Werke, pp. 103-148..
- ↑ a b 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..
- ↑ a b 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..
- ↑ a b Wiedemann, Doug (1991), «A computation of the eighth Dedekind number», Order 8 (1): 5-6, doi:10.1007/BF00385808, MR1129608..
- ↑ a b Jäkel, Christian (5 de abril de 2023). «A computation of the ninth Dedekind Number». arXiv:2304.00895 [math].
- ↑ a b Van Hirtum, Lennart (6 de abril de 2023). «A computation of D(9) using FPGA Supercomputing». arXiv:2304.03039 [math].
- ↑ a b 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..