Keberadaan jalur panjang yang diinduksi dalam grafik expander

Katakanlah keluarga grafik memiliki jalur yang diinduksi panjang jika ada konstanta ϵ > 0 sehingga setiap grafik G dalam F berisi jalur yang diinduksi pada | V ( G ) | ϵ simpul. Saya tertarik pada properti keluarga grafik yang memastikan keberadaan jalur yang panjang. Secara khusus, saya saat ini bertanya-tanya apakah ekspander derajat konstan telah lama diinduksi jalur. Inilah yang saya tahu.$\mathcal{F}$$\epsilon > 0$$G$$\mathcal{F}$$|V(G)|^{\epsilon}$

• Grafik acak dengan derajat rata-rata konstan (dalam model Erd-Rényi) memiliki jalur panjang yang diinduksi (bahkan linier) dengan probabilitas tinggi; lihat misalnya artikel Suen .
• Grafik expander unik-tetangga (seperti yang didefinisikan oleh Alon dan Copalbo ) memiliki pohon besar yang diinduksi . Faktanya, setiap pohon maksimal yang diinduksi besar dalam grafik tersebut.

Dengan adanya dua fakta ini, saya berharap bahwa ekspander tingkat kontestan telah menempuh jalan yang panjang. Namun, saya tidak dapat menemukan hasil yang konkret. Wawasan apa pun sangat dihargai.

Jawabannya harus positif jika grafik derajat terbatas Anda memiliki sifat memiliki ekspansi konstan dan ketebalan. Argumennya adalah: mulai dari titik, kemudian untuk n ϵ langkah berjalan di mana setiap langkah dipilih secara acak di antara mereka yang tidak membawa kita kembali ke tempat kita sebelumnya. (Jadi jika grafiknya d- reguler, kita memiliki d - 1 pilihan acak pada setiap langkah.)$\Omega( \log n)$$n^\epsilon$$d$$d-1$

$i$$j$$i$$j$$i$$j$$n^{-\Omega(1)}$$\epsilon$$1-o(1)$

$|i-j|$$i$$j$$j> i+ \Omega(\log n)$$(i,j)$$n^{-\Omega(1)}$$v$$n^{\Omega(1)}$$n^{-\Omega(1)}$$n^{-\Omega(1)}$$O(1)$$v$$n^{-\Omega(1)}$