Comprensión de varias definiciones de TREE( $n$ ) en la forma finita de Friedman del teorema del árbol de Kruskal.

Question

Estaba leyendo el artículo de Wikipedia sobre la forma finita de Friedman del teorema del árbol de Kruskal y estoy interesado en los grandes números TREE(n). Me gustaría verificar TREE(2)=3 yo mismo, pero encuentro definiciones contradictorias de las condiciones de los árboles/embeddings en varios sitios web. ¿Qué propiedades tienen los árboles y qué tienen que satisfacer las incrustaciones correspondientes?

Editar:

Por ejemplo, una búsqueda de información llevó a esta antigua publicación (en adelante, "ese post") que enlaza con dos páginas que afirman que TREE(2)=2, y sugiere que son un error. El post utiliza las palabras "secuencia de árboles enraizados etiquetados con vértices", lo que da una pista sobre el significado de TREE(n). El post también contiene un posible ejemplo que puede demostrar que TREE(2)≥3.

Por otro lado, Wikipedia dice " árboles etiquetados sin orden entre hermanos, parametrizando en el tamaño del conjunto de etiquetas en lugar de en el tamaño del primer árbol de la secuencia (y la incrustación homeomórfica, ≤, siendo ahora inf- y preservadora de etiquetas): Para cada n, hay un m tan grande que si T ₁ ,...,T _m es una secuencia finita de árboles con vértices etiquetados a partir de un conjunto de n etiquetas, donde cada Ti tiene como máximo i vértices, entonces Ti ≤ Tj para algún i<j". Esto dice árboles etiquetados pero no menciona que estén enraizados (excepto quizás implícitamente a través de "inf-preservación"; no estoy seguro de lo que significa esa parte). También trae a colación la palabra "homeomórfico", que si la tomo literalmente como aplicable a una incrustación planar de los árboles, parece una noción muy impar para usar ya que partes del árbol pueden ser contraídas (¿posiblemente saltando vértices?) en un homeomorfismo.

Además, creo recordar haber encontrado una fuente que parecía implicar que los árboles tenían que ser "completos", y decía que eso significaba algo así como "el árbol tiene raíces y, en cada nivel, el número de hijos de cada vértice es el mismo", pero ahora no puedo encontrar esa fuente.

Por último, la otra cosa que mis búsquedas sacaron fue una vieja pregunta de intercambio de pilas (http://math.stackexchange.com/questions/116478/quickest-way-to-understand-kruskals-tree-theorem) en la que un usuario llamado "Bruce" hace referencia a un artículo: Jean H. Gallier, "¿Qué tiene de especial el teorema de Kruskal y el ordinal Γ0? A survey of some results in proof theory". Ann. Pure Appl. Logic 53 (1991), no. 3, 199-260. Resumiré lo que parecen ser las partes relevantes.

El resumen comienza aquí

En ese documento, el teorema relevante parece deberse a Friedman:

Teorema 5.2

Sea Σ un conjunto finito. Para cada número entero k≥2, existe algún número entero n≥2 tan grande que, para cualquier secuencia finita <t ₁ , t _n > de árboles en T _Σ con |t _m |≤m para todo m, 1≤m≤n, existen algunos enteros i ₁ , ,i _k tal que 1≤i ₁ < <i _k ≤n y t _{i 1} ≼ ≼t _{i k} .

Para desentrañar esta afirmación, primero debemos entender qué significa |t| para un árbol t, qué es T _Σ es, y quizás lo más importante, lo que significa "≼". Las definiciones pertinentes aparecen al principio de la sección 4. Definen (4.1) que un "dominio de árbol" es un tipo especial de conjunto de cadenas de naturales positivos (donde los números parecen representar qué hijo de un nodo se selecciona en cada paso), y dado un conjunto Σ de etiquetas, un Σ-árbol (4.2) es una función desde un dominio de árbol a Σ. (Esto etiqueta los nodos de un árbol cuya estructura viene dada por el dominio del árbol). T _Σ es el conjunto de todos los árboles Σ finitos. Si t es un árbol, |t| es el tamaño de su dominio (el número de nodos).

Por último, el comienzo de la sección 5 sugiere que "≼" es "el preorden de incrustación de la definición 4.11", pero eso también requiere más definiciones. La definición 4.3 explica que para una etiqueta f, f también puede utilizarse para representar el árbol de un nodo ""↦f". Continúa explicando que si t ₁ , ,t _k son árboles, y f es una etiqueta, entonces f(t ₁ , ,t _k ) denota el árbol con raíz f donde el t _i se adjuntan a continuación. (La redacción original es formal; puedo aclararla si es necesario).

El preorden ≼ de 4.11 se define entonces inductivamente en T _Σ satisfaciendo dos condiciones: 1. Si s y t son árboles, entonces s≼t⇒s≼f( ,t, ). y 2. si 0≤m≤n y hay m enteros j _i tal que 1≤j ₁ < <j _m ≤n y s ₁ ≼t _{j 1} , ,s _m ≼t _{j m} entonces f(s ₁ , ,s _m )≼f(t ₁ , ,t _n ).

En palabras incómodas (usando "subárbol inmediato" para significar "un subárbol completo que comienza en un hijo de la raíz"): 1. Si un árbol "cabe dentro" de un subárbol inmediato de otro árbol, entonces cabe dentro de todo el árbol. y 2. Si dos árboles tienen la misma raíz, y los subárboles inmediatos encajan cada uno dentro de diferentes subárboles inmediatos correspondientes del segundo, entonces el primer árbol encaja dentro del segundo.

El resumen termina aquí

Suponiendo que esas definiciones/afirmaciones de ese documento sean correctas, entonces parece que el número entero n que se nos garantiza que existe por Thm 5.2 depende tanto de k como del tamaño del conjunto de etiquetas Σ. Parece que el "k" de Gallier se ha establecido igual a 2 en Wikipedia, el "tamaño de Σ" de Gallier se ha llamado "n" en Wikipedia, el índice ficticio "m" de Gallier se ha llamado "i" en Wikipedia, y el "n" de Gallier se llama "m" o "TREE(n)" en Wikipedia. Teniendo esto en cuenta, parece que el ejemplo de esa publicación muestra realmente que TREE(2)≥3.

Entonces me pregunto si TREE(2) podría ser mayor que 3. Sin embargo, parece que un solo nodo de una etiqueta dada impide que esa etiqueta se utilice de nuevo, de modo que los dos primeros árboles se ven obligados a un ordenamiento de las etiquetas; utilizando negrita para denotar la cabeza, son " 2 " y " 1 --1". El tercer árbol no puede utilizar la etiqueta 2, por lo que debe ser " 1 --1--1" o "1-- 1 --1" o " 1 --1" o " 1 ". Las tres primeras opciones contienen " 1 --1" en la forma pertinente, para que los ejemplos en ese puesto sean realmente los mejores posibles.

Preguntas pendientes:

¿Hay algún error en mi cálculo de que TREE(2)=3? ¿Qué significan las partes de la definición de Wikipedia, si es que efectivamente es equivalente a la del artículo de Gallier? (¿O es no equivalente).

Answer 1

TREE(2) = 3

re: su pregunta específica

Su cálculo de TREE(2) = 3 es correcto, y es esencialmente el mismo que me llevó a hacer la antiguo puesto de trabajo que usted cita. No tengo ninguna explicación de por qué Friedman habría escrito (en al menos dos lugares) que TREE(2) = 2, excepto quizás como algún tipo de descuido y/o error tipográfico. Hay algunas discusiones relevantes en la página de discusión del artículo de WP que mencionas, que también enlaza con otros artículos sobre la función TREE. También puedes echar un vistazo a los comentarios y respuestas a esta pregunta no tan antigua del modus operandi sobre TREE(3).

La función TREE

re: definiciones contrastadas

La función TREE de Friedman se refiere a la función finita árboles como posets que tienen una sola raíz, están etiquetados con vértices y no están ordenados. Desordenado significa aquí que no hay orden entre los hermanos (es decir, vértices que tienen un padre común); además, no se asume ningún orden ni cuasi-orden para el conjunto finito de etiquetas - aunque utiliza las etiquetas 1,2,3,..., $k$ , donde $k$ es el argumento de TREE( $k$ ). Lo anterior establece el contexto para La definición de Friedman de la función TREE :

ÁRBOL( $k$ ) es la longitud $n$ de la secuencia más larga de árboles $T_1,...,T_n$ con vértices etiquetados de {1,...,k}, donde cada $T_i$ tiene como máximo $i$ vértices, y no $T_i$ es infravalorado y etiquetado incrustado en un posterior $T_j$ .

Obsérvese que, además de TREE, las variaciones sobre etiquetado/sin etiqueta, hermanos ordenados/sin orden, etiquetas cuasi-ordenadas/sin orden, incrustaciones con/sin condición de hueco, etc. etc., han dado lugar a una plétora de funciones similares pero diferentes de rápido crecimiento en la literatura sobre este tema. La función Fr del artículo que mencionas, de Gallier, es una de estas variaciones no equivalentes; más concretamente, el argumento de Fr es el longitud de una cadena de incrustaciones, en lugar del tamaño del alfabeto de etiquetas como en TREE (que sólo se refiere a una incrustación, no a una cadena).