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.
- 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.
źródło