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

12

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.Fϵ>0solfa|V.(sol)|ϵ

  • 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.

Bart Jansen
źródło

Odpowiedzi:

10

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).Ω(logn)nϵrere-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 ) . jajotjajotjajotn-Ω(1)ϵ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|ja-jot|jajotjot>ja+Ω(logn)(ja,jot)n-Ω(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Ω(1)n-Ω(1)n-Ω(1)O(1)vn-Ω(1)

Luca Trevisan
źródło
1
Ω(logn)