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.
Title
Infinitely Long Walks on Two Colored Graphs
Published
1992-12-14
Full Collection Name
Electrical Engineering & Computer Sciences Technical Reports
Other Identifiers
CSD-92-719
Type
Text
Extent
7 p
Archive
The Engineering Library
Usage Statement
Researchers may make free and open use of the UC Berkeley Library’s digitized public domain materials. However, some materials in our online collections may be protected by U.S. copyright law (Title 17, U.S.C.). Use or reproduction of materials protected by copyright beyond that allowed by fair use (Title 17, U.S.C. § 107) requires permission from the copyright owners. The use or reproduction of some materials may also be restricted by terms of University of California gift or purchase agreements, privacy and publicity rights, or trademark law. Responsibility for determining rights status and permissibility of any use or reproduction rests exclusively with the researcher. To learn more or make inquiries, please see our permissions policies (https://www.lib.berkeley.edu/about/permissions-policies).
