Vorhandensein langer induzierter Pfade in Expandergraphen

Angenommen, eine Graphenfamilie hat lange induzierte Pfade, wenn es eine Konstante , sodass jeder Graph in einen induzierten Pfad auf Ecken. Ich interessiere mich für Eigenschaften von Graphenfamilien, die die Existenz langer induzierter Pfade sicherstellen. Insbesondere frage ich mich derzeit, ob Expander mit konstantem Grad lange induzierte Wege haben. Hier ist was ich weiß. ϵ > 0 G F | V ( G ) | $\mathcal{F}$$\epsilon > 0$$G$$\mathcal{F}$$|V(G)|^{\epsilon}$

• Zufällige Graphen mit konstantem Durchschnittsgrad (im Erdős-Rényi-Modell) weisen lange (auch linear große) induzierte Pfade mit hoher Wahrscheinlichkeit auf. siehe zum Beispiel Suens Artikel .
• Unique-Neighbor-Expander-Graphen (wie von Alon und Copalbo definiert ) weisen große induzierte Bäume auf . Tatsächlich ist jeder maximal induzierte Baum in solchen Graphen groß.

Angesichts dieser beiden Tatsachen würde ich erwarten, dass Expander mit höherem Grad lange induzierte Wege haben. Konkrete Ergebnisse konnte ich jedoch nicht finden. Erkenntnisse werden sehr geschätzt.

Die Antwort sollte positiv sein, wenn Ihr Diagramm mit begrenztem Grad sowohl die Eigenschaft einer konstanten Ausdehnung als auch des Umfangs von . Das Argument wäre: Beginne an einem Scheitelpunkt, dann mache für n ϵ Schritte einen Spaziergang, bei dem jeder Schritt nach dem Zufallsprinzip aus denjenigen ausgewählt wird, die uns nicht dorthin zurückbringen, wo wir vorher waren. (Wenn das Diagramm also d- regulär ist, haben wir bei jedem Schritt d - 1 zufällige Auswahlmöglichkeiten.)$\Omega( \log n)$$n^\epsilon$$d$$d-1$

Nun behaupte ich, dass für jedes und j , wenn ich die Schritte i und j des Laufs betrachte, die Wahrscheinlichkeit, dass es eine Kante zwischen dem Scheitelpunkt in Schritt i und dem Scheitelpunkt in Schritt gibt, . Wenn dann ausreichend klein gewählt wird, zeigt eine Vereinigungsgrenze, dass die Wanderung einen Pfad mit der Wahrscheinlichkeit induziert . $i$$j$$i$$j$$i$n - Ω ( 1 ) ≤ 1 - o ( 1 $j$$n^{-\Omega(1)}$$\epsilon$$1-o(1)$

Wenn ist kleiner als der Umfang, dann ist die Wahrscheinlichkeit einer Kante zwischen i und j gleich Null. Wenn j > i + Ω ( log n ) ist , sollte die Erweiterung des Graphen ausreichen, um zu argumentieren, dass die Existenz der Kante ( i , j ) mit der Wahrscheinlichkeit n - Ω ( 1 ) auftritt . Dies liegt daran, dass für einen festen Startscheitelpunkt v die Verteilung des Laufs nach einer Anzahl von Schritten, die gleich dem Umfang sind, über einen Satz von Größen gleichmäßig ist$|i-j|$$i$$j$$j> i+ \Omega(\log n)$$(i,j)$$n^{-\Omega(1)}$$v$ und damit die Kollisionswahrscheinlichkeit n - Ω ( 1 ) ; Jeder nachfolgende Schritt sollte nur die Kollisionswahrscheinlichkeit verringern (dies gilt für einen tatsächlichen Zufallsrundgang, aber auch für diesen nicht rückverfolgenden Rundgang), und daher bleibt die Kollisionswahrscheinlichkeit und damit die Minientropie der Verteilung erhalten n - Ω ( 1 ) , und die Wahrscheinlichkeit, einen der O ( 1 ) -Nachbarn von v zu treffen,beträgt ebenfalls n - Ω ( 1 ) .$n^{\Omega(1)}$$n^{-\Omega(1)}$$n^{-\Omega(1)}$$O(1)$$v$$n^{-\Omega(1)}$