Gráficos mínimos con un número prescrito de árboles de distribución

Question

Como hace tiempo que murió Erdos y MathOverflow es la segunda mejor alternativa a él (para discutir problemas personales), me gustaría iniciar una fructífera discusión sobre el siguiente problema que me parece muy interesante.

Dejemos que $n \geq 3$ sea un número entero y que $\alpha(n)$ denotan el menor entero $k$ tal que existe una en $k$ vértices que tienen precisamente $n$ árboles de expansión. ¿Cuál es el comportamiento asintótico de $\alpha$ ?

Motivación. Se me planteó la cuestión a través de este Correo electrónico: en el blog de Dick Lipton. Resulta que la cuestión fue planteada ya en 1970 por el teórico de grafos checo J. Sedlacek (On the minimal graph with a given number of spanning trees, Canad. Math. Bull. 13 (1970) 515-517)

¿Qué se sabe?

Sedlacek pudo demostrar que para cada (no tan) grande $n$

$ \alpha(n) \leq \frac{n+6}{3}$ si $n \equiv 0 \pmod{3} $ y $\alpha(n) \leq \frac{n+4}{3}$ si $n \equiv 2 \pmod{3}. $

A continuación, un resumen de lo que he podido averiguar.

Dado que la ecuación $n = ab+ac+bc$ es solucionable para números enteros $1 \leq a < b < c$ para todos los números enteros excepto un número finito $n$ (ver este post) se puede deducir (considerando el gráfico $\theta_{a,b,c}$ que tiene $ab+ac+bc$ árboles de extensión) que para un tamaño suficientemente grande $n \not \equiv 2 \pmod{3}$

$$\alpha(n) \leq \frac{n+9}{4}.$$

Además, los únicos puntos fijos de $\alpha$ son 3, 4, 5, 6, 7, 10, 13 y 22.

Al generalizar el enfoque y considerar los gráficos $\theta_{x_1,\ldots,x_k}$ se podría intentar bajar la constante de la fracción de la desigualdad en una cantidad arbitraria. Como resulta no se sabe si todos los grandes $n$ es entonces expresable como $n = x_1\cdots x_k(\frac{1}{x_1} + \cdots + \frac{1}{x_k})$ para números enteros adecuados $1 \leq x_1 < \cdots < x_k.$

Incluso si ese método funcionara, lo más probable es que el límite siguiera siendo subóptimo. Según el gráfico (creado generando aleatoriamente grafos y calculando el número de sus árboles de extensión) parece razonable conjeturar que

Conjetura.

$$\alpha(n) = o(\log{n})$$

texto alternativo http://shrani.si/f/1G/lc/2yL7fZJd/graf.png

La conjetura es claramente justificable para los números altamente compuestos $n$ (considere el gráfico obtenido tras identificar un vértice común de los ciclos $C_{x_1},\ldots,C_{x_k}$ para los factores Impares adecuados $x_1, \ldots,x_k$ de $n$ ) pero falla para $n$ que son primos.

Es evidente para mí que carezco de las herramientas necesarias para atacar esta conjetura, así que cualquier tipo de sugerencias (dónde buscar una posible respuesta, qué tipo de herramientas debería aprender ) relacionadas con ella son muy bienvenidas.

Editar. Si alguien está dispuesto a trabajar en este problema, estaré encantado de colaborar ya que me beneficiaría mucho.

Answer 1

No hay respuesta, pero sí una pregunta relacionada: El número $n$ de árboles de extensión en un grafo con $k+1$ vértices es el determinante de un $k\times k$ con entradas enteras entre $-1$ y $k$ .

Para un determinado $n$ ¿Cuál es el menor $k=\beta(n)$ tal que $n$ es el determinante de dicha matriz?

Por supuesto, $\alpha(n)\ge \beta(n)+1$ . Las variaciones de este problema podrían restringirse a matrices simétricas, o diagonalmente dominantes, o por otro lado permitir entradas entre $-k$ y $k$ .

¿Se sabe algo sobre esta cuestión?

Adiciones (incorporando el comentario de Will Sawin): Por ejemplo, $$\left| \begin {matrix} 4&7&1&3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10 \end {matrix} \right| = 4713.$$ De este modo, con $k$ como base en lugar de 10, se obtienen todos los números hasta $k^k$ (y un poco más). El límite superior del determinante de la desigualdad de Hadamard es $k^{3k/2}$ . Con el límite inferior $-1$ en las entradas, este límite probablemente puede ser mejorado, ya que los vectores de fila de la matriz no pueden ser simultáneamente "largos" y cercanos a la ortogonalidad.

Uno puede trabajar este determinante en el número de dirigido árboles de distribución de un multigraph : $$\left| \begin {matrix} 4&-7&-1&-3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10 \end {matrix} \right| = 4000-713=3287.$$ Añadamos una quinta columna para que las sumas de las columnas sean cero: $$ \begin {pmatrix} 4&-7&-1&-3\cr -1&10&0&0 \cr 0&-1&10&0\cr 0&0&-1&10\cr -3& -2&-8&-7 \end {pmatrix} $$ Los dígitos del determinante están ahora en la última fila. Este número 3287 es igual al número de árboles orientados (arborescencias) en un multigrafo dirigido $G$ en 5 vértices que están orientados fuera del nodo raíz 5. El gráfico $G$ se obtiene tomando las entradas negativas fuera de la diagonal como multiplicidades de las aristas. (Los arcos que entran en el nodo 5, que sería la quinta columna, son obviamente irrelevantes). También se puede averiguar directamente que es el número de arborescencias, clasificándolas en aquellas 3000 que utilizan el arco $(5,1)$ y los 287 restantes que no lo hacen.

En el caso de los grafos dirigidos, se pueden eliminar las aristas múltiples subdividiéndolas. El nuevo vértice intermedio de una arista debe tener exactamente un arco entrante en cada árbol, y como el indegree es 1 este arco es fijo, y el número de arborescencias que se extienden es como en el grafo original. Además, todas las aristas múltiples salen del vértice 1 o del vértice $k+1=5$ . Varias aristas que parten de un vértice y se dirigen a vértices diferentes pueden compartir el vértice de subdivisión intermedio. Por lo tanto, sólo necesitamos en total $2(k-2)$ vértices adicionales para eliminar los arcos múltiples, $k-2$ del vértice 1 y $k-2$ del vértice $k+1$ para un total de $3k-3$ . (No he resuelto cómo queda este argumento traducido a términos matriciales).

Cada número entero hasta $k^k$ se puede realizar como el número de spanning arborescencias con una raíz fija en un dígrafo en $3k-3$ vértices sin arcos múltiples.

En otras palabras, $\alpha(n)$ para los dígrafos está limitada por $O(\log n/\log\log n)$ . Mucho mejor que lo que se conoce para los grafos no dirigidos, resolviendo la conjetura al menos para los grafos dirigidos.

El siguiente reto pendiente es investigar $\beta(n)$ para matrices simétricas .

Answer 2

Mientras que la construcción theta (trayectorias de longitudes $a,b$ y $c$ con puntos finales comunes) no es óptimo, ¿qué tan malo puede ser? Pues el mejor podría ser con números reales en lugar de enteros es $a+b+c=\sqrt{3}\sqrt{n}.$ Supongo, basándome en pruebas limitadas, que utilizando la construcción theta siempre se puede obtener $\alpha(p) \lt 2\sqrt{p}$ (digamos para $p \gt 1000$ ) En otras palabras, $\frac{(a+b+c)^2}{p} \lt 4$

He mirado los conjuntos $\{a,b,c\}$ con miembros de menos de $101$ y co-prima por pares (ya que estaba apuntando a los primos). Los únicos primos bajo $12500$ que no conseguí fueron $13,37,9463.$ Para $n=9463$ hay $a,b,c=35,41,108$ con $\frac{(a+b+c)^2}{p} \approx 3.51.$ Hay $1324$ primos $(1000 \lt p \lt 12500.)$ Hay trece primas en esta gama con $\frac{(a+b+c)^2}{p} \gt 3.5.$ Los otros doce son

$\small [1657, {3, 31, 46}, 3.862], [2293, {11, 23, 60}, 3.853], [4093, {11, 38, 75}, 3.757], [1093, {5, 21, 38}, 3.747],$$ | [4513, {17, 32, 81}, 3.745], [1777, {6, 31, 43}, 3.602], [1297, {6, 25, 37}, 3.565], [1153, {11, 15, 38}, 3.552], $$\small [1549, {7, 27, 40}, 3.535], [4657, {22, 31, 75}, 3.518], [7129, {24, 43, 91}, 3.502], [3457, {19, 27, 64}, 3.500]$

Hay otros doce con la proporción en $(3.4,3.5).$ Y $894$ de estos primos (algo más de $2/3$ ) tienen la relación bajo $3.1.$

Answer 3

Como la imagen de la pregunta original no funciona, y de todos modos no sé hasta dónde se extendía, comparto esta imagen que muestra cómo el valor exacto de $\alpha(n)$ crece hasta $n=6\,000\,000$ . La curva es, de hecho, una media móvil sobre 100 puntos consecutivos (de lo contrario, es demasiado oscilante para verla).

Esto se calculó por fuerza bruta inspeccionando todos los gráficos de como máximo $11$ vértices y el recuento de sus árboles de extensión con el teorema del árbol matriz de Kirchoff. Hay oscilaciones interesantes, pero el crecimiento aproximado parece logarítmico.