Número de topologías válidas en un conjunto finito de n elementos

Question

He oído que el problema de contar topologías es difícil, pero no he podido encontrar nada al respecto en el resto de Internet. ¿Se ha resuelto este problema? Si no es así, ¿hay alguna característica que lo hace bastante intratable?

Answer 1

Es wiiiiiiide abierto calcularlo exactamente. Por lo que yo sé, la "característica que lo hace intratable" es que no hay ninguna característica real que lo haga trazable. A grandes rasgos, si quieres contar las formas en que un tipo genérico de estructura se puede poner en un conjunto de n elementos, no hay una forma eficiente de hacerlo: básicamente tienes que enumerar las estructuras una por una. Esto se debe esencialmente a que "dada una descripción de un tipo de estructura y $n$ Contar el número de estructuras en un conjunto de n elementos" es un problema ridículamente amplio que acaba reduciéndose a montones y montones de problemas de recuento y decisión diferentes. Como alternativa, creo que se puede argumentar a través de la complejidad de Kolmogorov y todo eso, pero ese no es mi estilo

Así que, en cualquier caso, la carga de la prueba recae en la persona que afirma que debería existir un algoritmo de recuento eficiente. (Si crees en algunas cosas locas de la teoría de la complejidad, como P = PSPACE, esto empieza a ser menos cierto, ya que los tipos de estructuras difíciles de enumerar serán normalmente difíciles de describir. Pero si crees eso eres una causa perdida en cualquier caso :P) Sin embargo, sigue siendo razonable pedir una mayor justificación. Intentaría dar alguna, pero llevo como 30 horas despierto y sería aún más manoseado que lo anterior. La versión corta: Si haces suficiente combinatoria enumerativa, empiezas a ver que las buenas fórmulas para enumerar estructuras surgen de una de unas pocas situaciones. Algunas de las más importantes son:

1. La capacidad de derivar una relación de recurrencia suficientemente agradable. Esta es una propiedad bastante nebulosa, y algunos tipos de estructuras sorprendentes tienen bonitas relaciones de recurrencia. Realmente no puedo decir una buena razón sólida de por qué el número de topologías finitas no admite una relación de recurrencia agradable; si trabajas con él un tiempo, simplemente no parece que lo haga.
2. Un teorema de clasificación tal que las estructuras de cada clase tienen fórmulas agradables. A veces son profundas, a veces no. Un ejemplo no profundo es la prueba habitual (de álgebra no lineal) de la fórmula de Cayley sobre el número de árboles. La topología de conjuntos de puntos es extraño y es bastante extraño incluso en el caso finito. Esto está fuera de toda duda.
3. Si el conjunto de estructuras sobre un conjunto de n elementos es muy rígido, puede haber una forma "algebraica" de contarlas. De nuevo, la topología de conjuntos de puntos es demasiado extraña para que esto funcione.

Así que mi respuesta se reduce a: Es intratable porque lo es. No es una razón especialmente satisfactoria, pero a veces la combinatoria funciona así. Perdona si has leído todo el post -- pretendía que fuera más corto y tuviera más contenido, pero ha acabado como la mayoría de los cuentos contados por idiotas. Pero espero que hayas aprendido algo, o al menos te hayas divertido con él.

Answer 2

El mejor resultado que conozco se encuentra en el artículo El número de topologías finitas de D. Kleitman y B. Rothschild, donde afirman que el logaritmo de base 2 del número de topologías distintas en un conjunto de $n$ elementos es asintótica a $n^2/4$ .

Answer 3

Voy a ampliar un poco la respuesta de Harrison. Hay varias técnicas en la combinatoria algebraica que permiten la enumeración exacta de estructuras desordenadas; entre ellas se encuentran

• Escribir la función generadora en términos de funciones elementales. Esto suele requerir que su estructura tenga algo que ver con la estructura $e^x$ de conjuntos, la estructura $\frac{1}{1 - x}$ de órdenes lineales, o estructuras relacionadas. Algunas formas importantes de combinar estructuras son la suma, el producto, la composición y la derivada, todas ellas con significados combinatorios conocidos. Pero, a primera vista, parece que no hay forma de codificar la estructura de una topología de esta manera.

• Escribir una ecuación funcional que satisfaga la función generadora. Esto es muy útil con las estructuras arbóreas, ya que la naturaleza recursiva de su definición se refleja en ciertas ecuaciones funcionales. Por ejemplo, la función generadora $f$ de árboles etiquetados satisface famosamente $f = xe^f$ y junto con la inversión de Lagrange obtenemos fácilmente la fórmula de Cayley. Pero las topologías no parecen ser una estructura arbórea de forma evidente.

• Exponer la secuencia como la evaluación de una secuencia de determinantes. Se trata de una técnica increíblemente útil; puede contar cuadros y emparejamientos perfectos y todo tipo de locuras, pero los problemas a los que se aplica esta técnica tienen un cierto aire y este ni siquiera se acerca a encajar.

• Usando alguna variante del lema de Burnside o el teorema de Polya. Pero no parece haber ninguna forma útil de interpretar las topologías finitas en términos de una acción de grupo.

Dado que las topologías finitas son una especie de estructura algebraica -un conjunto cerrado bajo dos operaciones-, tal vez quiera pensar en un problema algebraico correspondientemente difícil, que es la enumeración de grupos finitos.

Answer 4

La enciclopedia de Sloane da algunas referencias. Creo que si algo se mueve en esta cuestión, el sitio de Sloane será uno de los primeros en actualizarse...

No estoy seguro de hasta qué punto esto tiene que ver con la Conjetura de los Conjuntos Cerrados por la Unión - esta última es sólo una afirmación del estilo de la combinatoria extrema. No veo cómo utilizarla para una enumeración.

Answer 5

Puede encontrar los últimos resultados aquí: https://arxiv.org/pdf/1503.08359.pdf