Número de topologías sobre un conjunto finito de n elementos

Question

He oído que el problema de contar topologías es duro, pero yo realmente no podía encontrar nada al respecto en el resto de internet. Este problema ha sido resuelto? Si no, ¿hay alguna característica que lo hace bastante intratable?

Answer 1

Voy a ampliar un poco más de Harrison respuesta. Hay varias técnicas de combinatoria algebraica que permita exacto de la enumeración de desordenada de las estructuras, que incluyen

• La escritura de la generación de la función en términos de funciones elementales. Esto generalmente requiere que su estructura tiene algo que ver con la estructura de $e^x$ de los conjuntos, la estructura de $\frac{1}{1 - x}$ lineal de órdenes, o estructuras relacionadas. Importante maneras de combinar estructuras incluyen la suma, producto, composición, y derivados, todos los que han conocido la combinatoria de los significados. Pero, en la superficie, parece ser que no hay manera de codificar la estructura de una topología de esta manera.

• La escritura de la funcional de la ecuación de la generación de la función satisface. Esto es muy útil con las estructuras en árbol, ya que la naturaleza recursiva de su definición se refleja en determinadas las ecuaciones funcionales. Por ejemplo, la generación de la función $f$ de etiquetado de los árboles famoso satisface $f = xe^f$, y junto con Lagrange inversión que pueda obtener fácilmente la fórmula de Cayley. Pero topologías no parecen ser una estructura de árbol de una manera obvia.

• Exhibiendo la secuencia como en la evaluación de una secuencia de los determinantes. Esta es una increíblemente útil técnica; puede contar de cuadros y perfecto elecciones y todo tipo de cosas locas, pero los problemas a los que esta técnica se aplica tienen un cierto aspecto a ellos y esto no se acercan siquiera a la colocación de la factura.

• Utilizando alguna variante de Burnside del lexema o Polya del teorema. Pero no parece haber ninguna manera útil para interpretar finito topologías en términos de un grupo de acción.

Desde finito topologías son una expresión algebraica de la estructura de clases - un conjunto cerrado bajo dos operaciones - se podría pensar en un correspondientemente difícil algebraicas problema, que es la enumeración de grupos finitos.

Answer 2

El mejor resultado lo que sé es encontrar en el artículo Del número finito de topologías, por D. Kleitman y B. Rothschild, donde afirman que el logaritmo en base 2 del número de distintas topologías en un conjunto de $n$ elementos es asintótica a $n^2/4$.

Answer 3

Es wiiiiiiide abierto para calcular exactamente. Que yo sepa la "característica que le hace intratable" es que no hay una característica que lo hace manejable. En términos generales, si usted desea contar las maneras en que un tipo genérico de la estructura se puede poner en un n-elemento de conjunto, no hay manera eficiente de hacer esto, básicamente, tendrá que enumerar las estructuras de uno en uno. Este es, esencialmente, porque "da una descripción de un tipo de estructura y $n$, contar el número de estructuras en un n-element set" es un muy amplio problema, lo que termina reduciendo a montones y montones de diferentes contar y de los problemas de decisión. Alternativamente, 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 sobre la persona que afirma que un eficiente algoritmo de conteo debe de existir. (Si usted cree que algunas cosas locas acerca de la teoría de la complejidad, como P = PSPACE, esto empieza a ser menos cierto, ya que los tipos de estructura de difícil enumerar normalmente será difícil de describir. Pero si usted cree que usted es una causa perdida en cualquier caso :P) Es todavía razonable preguntar para mayor justificación, aunque. Me gustaría intento de dar algo, pero he estado despierto durante más de 30 horas y sería aún más handwavey que los anteriores. La versión corta: Si usted hace bastante combinatoria enumerativa, empiezas a ver que bonito fórmulas para enumerar las estructuras surgen de una de las pocas situaciones. Algunos realmente grandes son:

1. La capacidad para obtener un suficientemente agradable de la recurrencia de la relación. Este es un lugar nebuloso de la propiedad, y algunas sorprendentes tipos de estructura han lindo de relaciones de recurrencia. Realmente no puedo decirle a usted una buena y sólida razón por la que el número finito de topologías de no admitir una buena relación de recurrencia; si se trabaja con él un rato, simplemente no se siente como lo hace.
2. Una clasificación teorema de tales de que las estructuras en cada clase de niza fórmulas. A veces, estos son profundos, y a veces no lo son. Uno no profunda ejemplo está en la costumbre (no-lineales en álgebra) prueba de Cayley de la fórmula en el número de árboles. Punto-establecer la topología es raro, y es bastante raro, incluso en el caso finito. Esto es fuera de la cuestión.
3. Si el conjunto de estructuras en un conjunto de n elementos es muy rígido, no puede ser un "algebraica" manera de contarlas. De nuevo, el punto de establecer la topología es demasiado raro para que esto patada en.

Así que mi respuesta se reduce a: Es intratable 'causa que es. No es un motivo especial de satisfacción, pero a veces esa es la manera en la combinatoria de las obras. Lo siento si has leído todo el post, se me fue la intención de ser más corto y tiene más contenido, pero terminó como la mayoría de los cuentos contados por idiotas. Pero espero que hayas aprendido algo, o al menos la diversión con ella?

Answer 4

Sloane enciclopedia da algunas referencias. Creo que si algo se mueve en esta pregunta, entonces Sloane del sitio será uno de los primeros en actualizarse...

No estoy seguro de en qué medida esta que tiene que hacer la Unión-Conjuntos Cerrados Conjetura que este último es sólo un extremal-combinatoria estilo afirmación. No veo cómo usarlo para una enumeración.

Answer 5

Esta cuestión está estrechamente relacionada con la de la Unión-Conjuntos Cerrados Conjetura de que es una pregunta abierta propuesto en 1979.