Existencia de largos caminos inducidos en gráficos expansores

Supongamos que una familia de gráficos tiene rutas inducidas largas si hay una constante modo que cada gráfico en contenga una ruta inducida en vértices. Estoy interesado en las propiedades de las familias de gráficos que aseguran la existencia de rutas inducidas largas. En particular, actualmente me pregunto si los expansores de grado constante tienen largos caminos inducidos. Aquí está lo que sé.$\mathcal{F}$$\epsilon > 0$$G$$\mathcal{F}$$|V(G)|^{\epsilon}$

• Los gráficos aleatorios con grado promedio constante (en el modelo Erdős-Rényi) tienen trayectorias inducidas largas (incluso de tamaño lineal) con alta probabilidad; ver por ejemplo el artículo de Suen .
• Los gráficos expansores de vecinos únicos (según lo definido por Alon y Copalbo ) tienen grandes árboles inducidos . De hecho, cualquier árbol inducido máximo es grande en tales gráficos.

Teniendo en cuenta estos dos hechos, esperaría que los expansores de grado contante tengan largas rutas inducidas. Sin embargo, no pude encontrar ningún resultado concreto. Cualquier idea es muy apreciada.

La respuesta debería ser positiva si su gráfico de grado acotado tiene la propiedad de tener una expansión constante y una circunferencia . El argumento sería: comenzar en un vértice, luego, para pasos, dar un paseo en el que cada paso se elige al azar entre aquellos que no nos llevan de vuelta a donde estábamos antes. (Entonces, si el gráfico es regular tenemos opciones aleatorias en cada paso).$\Omega( \log n)$$n^\epsilon$$d$$d-1$

Ahora afirmo que, para cada y , si miro pasos y de la caminata, la probabilidad de que existe una arista entre los vértices en el paso y el vértice en el paso es . Entonces, si se elige lo suficientemente pequeño, un enlace de unión mostrará que la caminata inducirá un camino con probabilidad . $i$$j$$i$$j$$i$$j$$n^{-\Omega(1)}$$\epsilon$$1-o(1)$

Sies menor que la circunferencia, entonces la probabilidad de un borde entre y es solo cero. Si , entonces la expansión del gráfico debería ser suficiente para argumentar que la existencia del borde ocurre con probabilidad . Esto se debe a que, para un vértice de inicio fijo , la distribución de la caminata después de un número de pasos igual a la circunferencia es uniforme sobre un conjunto de tamaño , y también tiene una probabilidad de colisión$|i-j|$$i$$j$$j> i+ \Omega(\log n)$$(i,j)$ v n Ω ( 1 ) n - Ω ( 1 ) n - Ω ( 1 ) O ( 1 ) v n - Ω ( 1 $n^{-\Omega(1)}$$v$$n^{\Omega(1)}$$n^{-\Omega(1)}$; cada paso posterior solo debería disminuir la probabilidad de colisión (esto es cierto para una caminata aleatoria real, pero también debería ser cierto para esta caminata sin retroceso), y así la probabilidad de colisión, y por lo tanto la min-entropía, de la distribución permanece , y la probabilidad de golpear a uno de los vecinos de también es .$n^{-\Omega(1)}$$O(1)$$v$$n^{-\Omega(1)}$