Infinitely Long Walks on Two Colored Graphs

Peter S. Gemmell

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-92-719

, 1992

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/CSD-92-719.pdf

Suppose we have a undirected graph G = (V,E) where V is the set of vertices and E is the set of edges. Suppose E consists of red colored edges and blue colored edges. Suppose we have an infinite sequence S of characters R and B. We take a random walk starting at vertex v on G based on the sequence S as follows: At the ith step, if S has an R at position i the walk traverses a random red edge out of the current vertex (chosen uniformly from the outgoing edges). If S has a B the walk traverses a random blue edge out of the current vertex. We say S covers G starting at vertex v when a random walk using S starting at v covers every vertex of G. Theorem 1 If G is a red-blue colored undirected graph which is connected in red and connected in blue and there exists an RB-sequence S such that starting at some vertex v, Pr[S covers G] < 1, then G contains a proper subgraph H such that H's vertices can be divided into two sets: U and W where there are no red edges between U and V - W and no blue edges between U and V - U.

BibTeX citation:

@techreport{Gemmell:CSD-92-719,
    Author= {Gemmell, Peter S.},
    Title= {Infinitely Long Walks on Two Colored Graphs},
    Year= {1992},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6015.html},
    Number= {UCB/CSD-92-719},
    Abstract= {Suppose we have a undirected graph <i>G</i> = (<i>V</i>,<i>E</i>) where <i>V</i> is the set of vertices and <i>E</i> is the set of edges. Suppose <i>E</i> consists of red colored edges and blue colored edges. Suppose we have an infinite sequence <i>S</i> of characters <i>R</i> and <i>B</i>. <p>We take a random walk starting at vertex <i>v</i> on <i>G</i> based on the sequence <i>S</i> as follows:   <p>At the <i>i</i>th step, if <i>S</i> has an <i>R</i> at position <i>i</i> the walk traverses a random red edge out of the current vertex (chosen uniformly from the outgoing edges). If <i>S</i> has a <i>B</i> the walk traverses a random blue edge out of the current vertex. <p>We say <i>S</i> covers <i>G</i> starting at vertex <i>v</i> when a random walk using <i>S</i> starting at <i>v</i> covers every vertex of <i>G</i>.   <p><strong>Theorem 1</strong> If <i>G</i> is a red-blue colored undirected graph which is connected in red and connected in blue and there exists an <i>RB</i>-sequence <i>S</i>  such that starting at some vertex <i>v</i>, <i>Pr</i>[<i>S</i> covers <i>G</i>] < 1, then <i>G</i> contains a proper subgraph <i>H</i> such that <i>H</i>'s vertices can be divided into two sets: <i>U</i> and <i>W</i> where there are no red edges between <i>U</i> and <i>V</i> - <i>W</i> and no blue edges between <i>U</i> and <i>V</i> - <i>U</i>.},
}

EndNote citation:

%0 Report
%A Gemmell, Peter S. 
%T Infinitely Long Walks on Two Colored Graphs
%I EECS Department, University of California, Berkeley
%D 1992
%@ UCB/CSD-92-719
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1992/6015.html
%F Gemmell:CSD-92-719