Existence de longs trajets induits dans les graphiques d'expansion

Disons qu'une famille de graphes a de longs chemins induits s'il y a une constante telle que chaque graphe dans contient un chemin induit sur sommets. Je m'intéresse aux propriétés des familles de graphes qui assurent l'existence de longs trajets induits. En particulier, je me demande actuellement si les expanseurs à degré constant ont de longs trajets induits. Voici ce que je sais.$\mathcal{F}$$\epsilon > 0$$G$$\mathcal{F}$$|V(G)|^{\epsilon}$

• Les graphiques aléatoires à degré moyen constant (dans le modèle Erdős – Rényi) ont de longs trajets induits (même de taille linéaire) avec une probabilité élevée; voir par exemple l'article de Suen .
• Les graphiques d'extensions à voisin unique (tels que définis par Alon et Copalbo ) ont de grands arbres induits . En fait, tout arbre maximal induit est grand dans ces graphiques.

Compte tenu de ces deux faits, je m'attendrais à ce que les expanseurs à degré contant aient de longs chemins induits. Cependant, je n'ai pas pu trouver de résultats concrets. Toutes les idées sont très appréciées.

La réponse doit être positive si votre graphique à degrés bornés a à la fois la propriété d'avoir une expansion constante et une circonférence . L'argument serait: commencer à un sommet, puis pour faire un pas dans lequel chaque pas est choisi au hasard parmi ceux qui ne nous ramènent pas à l'endroit où nous étions avant. (Donc, si le graphique est régulier, nous avons choix aléatoires à chaque étape.)$\Omega( \log n)$$n^\epsilon$$d$$d-1$

Maintenant, je prétends que, pour chaque et , si je regarde les étapes et de la marche, la probabilité qu'il y ait un bord entre le sommet à l'étape et le sommet à l'étape est . Ensuite, si est choisi suffisamment petit, une borne d'union montrera que la marche induira un chemin de probabilité . $i$$j$$i$$j$$i$$j$$n^{-\Omega(1)}$$\epsilon$$1-o(1)$

Siest inférieure à la circonférence, alors la probabilité d'un bord entre et est juste nulle. Si , alors l'expansion du graphique devrait être suffisante pour soutenir que l'existence de l'arête se produit avec la probabilité . En effet, pour un sommet de départ fixe , la distribution de la marche après un nombre de pas égal à la circonférence est uniforme sur un ensemble de taille , de même que la probabilité de collision$|i-j|$$i$$j$$j> i+ \Omega(\log n)$$(i,j)$$n^{-\Omega(1)}$$v$$n^{\Omega(1)}$$n^{-\Omega(1)}$; chaque étape suivante ne devrait que diminuer la probabilité de collision (cela est vrai pour une marche aléatoire réelle, mais cela devrait également être vrai pour cette marche sans retour en arrière), et donc la probabilité de collision, et donc l'entropie minimale, de la distribution reste , et la probabilité de toucher l'un des voisins de est également .$n^{-\Omega(1)}$$O(1)$$v$$n^{-\Omega(1)}$