Istnienie długo indukowanych ścieżek na wykresach ekspanderów

Powiedzmy, że rodzina grafów ma długo indukowane ścieżki, jeśli istnieje stała ϵ > 0, tak że każdy wykres G w F zawiera ścieżkę indukowaną na | V ( G ) | ϵ wierzchołki. Interesują mnie właściwości rodzin grafów, które zapewniają istnienie długo indukowanych ścieżek. W szczególności zastanawiam się obecnie, czy ekspandery o stałym stopniu mają długo indukowane ścieżki. Oto co wiem.$\mathcal{F}$$\epsilon > 0$$G$$\mathcal{F}$$|V(G)|^{\epsilon}$

• Losowe wykresy o stałym średnim stopniu (w modelu Erdősa – Rényi) mają długie ścieżki (nawet o rozmiarach liniowych) z dużym prawdopodobieństwem; patrz na przykład artykuł Suen .
• Wykresy ekspanderów unikalnych sąsiadów (zgodnie z definicją Alona i Copalbo ) mają duże drzewa indukowane . W rzeczywistości każde maksymalne indukowane drzewo jest duże na takich wykresach.

Biorąc pod uwagę te dwa fakty, spodziewałbym się, że ekspandery o stopniu ciągłości mają długo indukowane ścieżki. Nie udało mi się jednak znaleźć żadnych konkretnych rezultatów. Wszelkie spostrzeżenia są bardzo mile widziane.

Odpowiedź powinna być pozytywna, jeśli wykres ograniczonego stopnia ma zarówno właściwość ciągłego rozszerzania, jak i obwód . Argument byłby następujący: zacznij od wierzchołka, a następnie n ϵ kroków wybierz spacer, w którym każdy krok jest wybierany losowo spośród tych, które nie zabierają nas z powrotem do miejsca, w którym byliśmy krok wcześniej. (Więc jeśli wykres jest d- nieregularny, mamy d - 1 losowych wyborów na każdym kroku).$\Omega( \log n)$$n^\epsilon$$d$$d-1$

Teraz twierdzę, że dla każdego i j , jeśli spojrzę na kroki i i j przejścia, prawdopodobieństwo, że istnieje krawędź między wierzchołkiem w kroku i a wierzchołkiem w kroku j wynosi n - Ω ( 1 ) . Następnie, jeśli ϵ zostanie wybrane wystarczająco małe, granica unii pokaże, że marsz indukuje ścieżkę z prawdopodobieństwem 1 - o ( 1 ) . $i$$j$$i$$j$$i$$j$$n^{-\Omega(1)}$$\epsilon$$1-o(1)$

Jeśli jest mniejszy niż obwód, wówczas prawdopodobieństwo krawędzi między i i j wynosi tylko zero. Jeśli j > i + Ω ( log n ) , wówczas rozwinięcie wykresu powinno wystarczyć, aby argumentować, że istnienie zbocza ( i , j ) dzieje się z prawdopodobieństwem n - Ω ( 1 ) . Wynika to z tego, że dla ustalonego wierzchołka początkowego v rozkład przejścia po liczbie kroków równych obwodowi jest równomierny w zestawie wielkości$|i-j|$$i$$j$$j> i+ \Omega(\log n)$$(i,j)$$n^{-\Omega(1)}$$v$ , a zatem ma prawdopodobieństwo kolizji n - Ω ( 1 ) ; każdy kolejny krok powinien tylko zmniejszać prawdopodobieństwo kolizji (dotyczy to faktycznego marszu losowego, ale powinien być również prawdziwy dla tego chodzenia bez cofania się), a zatem prawdopodobieństwo kolizji, a tym samym min-entropii rozkładu, pozostaje n - Ω ( 1 ) , a prawdopodobieństwo trafienia jednego zsąsiadów O ( 1 ) v również wynosi n - Ω ( 1 ) .$n^{\Omega(1)}$$n^{-\Omega(1)}$$n^{-\Omega(1)}$$O(1)$$v$$n^{-\Omega(1)}$