18.317 Combinatorics, Probability, and Computations on Groups October 29, 2001

Lecture 0

Lecturer: Igor Pak Scribe: M. Alekhnovich

Mixing time & long paths in graphs

Let Γ be a Cayley graph of group G: Γ = Caley(G, S), |S| = D, |Γ| = n. Recall the following notation from the previous lectures: {x_{t}^{v}} - random walk on Γ starting at v ∈ Γ. Q_{v}^{t}(g) = P r(x_{t}^{v} = g) τ_{4} = min\{t : ||Q_{v}^{t} − u|| < \frac{1}{4} ∀v ∈ Γ\} In this lecture we will prove the following result: Theorem 1 Let Γ be a D-regular graph with τ_{4} ≤ k s.t. D > 8k^{2}. Then Γ contains a (self-avoiding) path of length greater than \frac{|Γ|}{16k}. This theorem holds for an arbitrary D-regular graph as well but in this lecture we will confine ourselves only to Cayley graphs. Definition 2 Let α_{v}(A) = P r (x_{t}^{v} ∉ A, ∀ t ∈ [1..k]), β_{v}(A) = 1 − α_{v}(A). Clearly, β_{v}(A) ≤ ∑_{t=1}^{k} P r(x_{t}^{v} ∈ A) = ∑_{t=1}^{k} Q_{v}^{t}(A). Proposition 3 FOr any A ⊆ G, we have: ∑_{v∈Γ} β_{v}(A) ≤ k|A|. Proof:

∑_{v∈Γ} β_{v}(A) ≤ ∑_{v∈Γ} ∑_{t=1}^{k} Q_{v}^{t}(A) = ∑_{t=1}^{k} ∑_{z∈A} ∑_{v∈Γ} Q_{v}^{t}(z) = k|A|

Lemma 4 For any A ⊆ G and any β > 0 we have:

#\{v ∈ Γ : β_{v}(A) < β\} ≥ n − \frac{k|A|}{β}

Proof: Let m = #\{v ∈ Γ : β_{v}(A) ≥ β\}. Since mβ ≤ ∑_{v∈Γ} β_{v}(A) ≤ k|A| we have m ≤ \frac{k|A|}{β} and

#\{v ∈ Γ : β_{v}(A) < β\} = n − m ≥ n − \frac{k|A|}{β}.

Lemma 5 Let

ρ := min ; \begin{matrix}|B| = k \\ v ∉ B \end{matrix} P r(x_{1}^{v}, ..., x_{k}^{v} ∉ B ∧ [all x_{i}^{v} are distinct])

δ := 1 − ρ

Then ρ > 1 − \frac{2k^{2}}{D}; δ < \frac{2k^{2}}{D} . Proof:

ρ ≥ (1 − \frac{|B| + 1}{D}) · ... · (1 − \frac{|B| + k}{D} ) > (1 − \frac{2k}{D} )^{k} > 1 − \frac{2k^{2}}{D}

Lemma 6 Let

ξ_{v}(A) = min ; \begin{matrix}B ⊂ G, |B| = k \\ v ∉ A ∪ B \end{matrix} α_{v}(A ∪ B)

Z(A, β) = \{v ∈ Γ : ξ_{v}(A) > 1 − β − \frac{2k^{2}}{D} \}

Then ∀A ⊂ Γ |Z(A, β)| > n − \frac{k|A|}{β}. Proof:

ξ_{v}(A) ≥ 1 − β_{v}(A) − δ >^{(Lemma 5)} 1 − β − \frac{2k^{2}}{D}

if β_{v}(A) < β. Hence, by Lemma 4

ξ_{v}(A) > 1 − β − \frac{2k^{2}}{D}

for more than n − \frac{k|A|}{β} points. Definition 7 (failure probability) Assume that v and A are given. The random walk starting in v is successful iff all x_{i} i ∈ [1..k] are distinct and don’t belong to A. Let the failure probability be

fp(v, A) = 1 − P r(x_{1}^{v}, ..., x_{k}^{v} ∉ A ∧ [all x_{i}^{v} are distinct]).

Clearly ||A_{v}^{k} − U|| ≥ \frac{|Z|}{|Γ|} − Q_{v}^{k}(Z). By the statement of the theorem ||A_{v}^{k} − U|| < \frac{1}{4}. Thus Q_{v}^{k}(Z) > \frac{|Z|}{n} − \frac{1}{4} for any Z ⊆ Γ. Proof (of the Theorem): Fix γ := \frac{1}{2}; β := γ − \frac{2k^{2}}{D} ≤ \frac{1}{2} − \frac{1}{4} = \frac{1}{4}. Let A be some set s.t. ∃v ∉ A for which failure probability is less or equal than γ. Let us denote

p = P r(x_{1}^{v}, ..., x_{k}^{v} ∉ A ∧ [all x_{i} are distinct] ∧ fp(x_{k}^{v}, A ∪ {x_{1}^{v}, ..., x_{k−1}^{v}}) < γ).

Then

p ≥ P r(x_{k}^{v} ∈ Z(A, β)) − γ ≥ (\frac{|Z(A, β)|}{|Γ|} − \frac{1}{4}) − γ > 1 − \frac{k|A|}{βn} − \frac{1}{4} − \frac{1}{2} = \frac{1}{4} − \frac{k|A|}{\frac{1}{4}n},

which is greater than 0 as long as |A| < \frac{n}{16k} .

Let us set A = ∅ at the start. By Lemma 5, ∃v fp(v, A) < γ. Since p > 0 we can choose at least one self-avoiding path with “good” end-point. We can continue the process of constructing the path as long as p > 0 which is equivalent to |A| < \frac{n}{16k}. Thus there exists a path of length greater or equal \frac{n}{16k}.

At the end, I would like to mention about the following conjecture of Lovász:

Every Cayley graph has a Hamiltonian path.

The main Theorem shows that it is not very easy to produce a counterexample to this conjecture in class of groups with small mixing time.

Also, we proved Theorem 1 in a non-constructive way, but in fact using these ideas one can find a long path in polynomial time. For this, it is sufficient to test x_{k}^{v} ∈ Z efficiently.