Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time. Issue 1 (27th June 2013)

• Record Type: Journal Article
• Authors: Berenbrink, Petra; Cooper, Colin; Friedetzky, Tom
• Is Part Of: Random structures & algorithms. Volume 46:Issue 1(2015)
• Page Start: 36
• Page End: 54
• Publication Date: 2013-06-27
• Subjects: Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20504
• Languages: English
• ISSNs: 1042-9832

Abstract

<abstract abstract-type="main"> <title>Abstract</title> <p>Let <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcvb0" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0001" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>G</mml:mi><mml:mo>=</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>V</mml:mi><mml:mo>, </mml:mo><mml:mi>E</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> be a connected graph with <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcvcj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0002" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>|</mml:mo><mml:mi>V</mml:mi><mml:mo>|</mml:mo><mml:mo>=</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:math></alternatives></inline-formula> vertices. A simple random walk on the vertex set of <italic>G</italic> is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random.</p> <p>We consider a modified walk which, whenever possible, chooses an unvisited edge for the next transition; and makes a simple random walk otherwise. We call such a walk an <italic>edge‐process</italic> (or <italic>E</italic>‐process). The rule used to choose among unvisited edges at any step has no effect on our analysis. One possible method is to choose an unvisited edge uniformly at random, but we impose no such restriction.</p> <p>For the class of connected even degree graphs of constant maximum degree, we bound the vertex cover time of the <italic>E</italic>‐process in terms of the edge expansion rate of the graph <italic>G</italic>, as measured by eigenvalue gap <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcv8w" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0003" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msub><mml:mo>λ</mml:mo><mml:mrow><mml:mi>max</mml:mi></mml:mrow></mml:msub></mml:mrow></mml:math></alternatives></inline-formula> of the transition matrix of a simple random walk on <italic>G</italic>.</p> <p>A vertex <italic>v</italic> is <italic>ℓ</italic>‐good, if any even degree subgraph containing all edges incident with <italic>v</italic> contains at least <italic>ℓ</italic> vertices. A graph <italic>G</italic> is <italic>ℓ</italic>‐good, if every vertex has the <italic>ℓ</italic>‐good property. Let <italic>G</italic> be an even degree <italic>ℓ</italic>‐good expander of bounded maximum degree. Any <italic>E</italic>‐process on <italic>G</italic> has vertex cover time <disp-formula content-type="mathematics" id="rsa20504-disp-0001"><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcv9f" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="block" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0004" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:msub><mml:mi>C</mml:mi><mml:mi>V</mml:mi></mml:msub><mml:mo stretchy="false">(</mml:mo><mml:mi>E</mml:mi><mml:mo>−</mml:mo><mml:mtext>process</mml:mtext><mml:mo stretchy="false">)</mml:mo><mml:mo>=</mml:mo><mml:mi>O</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mrow><mml:mi>n</mml:mi><mml:mo>+</mml:mo><mml:mfrac><mml:mrow><mml:mi>n</mml:mi><mml:mi>log</mml:mi><mml:mi>n</mml:mi></mml:mrow><mml:mo>ℓ</mml:mo></mml:mfrac></mml:mrow><mml:mo>)</mml:mo></mml:mrow><mml:mo>.</mml:mo></mml:mrow></mml:math></alternatives></disp-formula> This is to be compared with the <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcv57" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0005" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Ω</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula> lower bound on the cover time of any connected graph by a weighted random walk. Our result is independent of the rule used to select the order of the unvisited edges, which could, for example, be chosen on‐line by an adversary.</p> <p>As no walk based process can cover an <italic>n</italic> vertex graph in less than <italic>n</italic> – 1 steps, the cover time of the <italic>E</italic>‐process is of optimal order when <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcv6s" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0006" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>=</mml:mo><mml:mo>Θ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. With high probability random <italic>r</italic>‐regular graphs, <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcv34" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0007" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>r</mml:mi><mml:mo>≥</mml:mo><mml:mn>4</mml:mn></mml:mrow></mml:math></alternatives></inline-formula> even, have <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcv4p" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0008" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>ℓ</mml:mo><mml:mo>=</mml:mo><mml:mo>Ω</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>log</mml:mi><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. Thus the vertex cover time of the <italic>E</italic>‐process on such graphs is <inline-formula><alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh2d2rcv2k" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" /><mml:math display="inline" altimg="urn:x-wiley:10429832:media:rsa20504:rsa20504-math-0009" overflow="scroll" xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>Θ</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mi>n</mml:mi><mml:mo stretchy="false">)</mml:mo></mml:mrow></mml:math></alternatives></inline-formula>. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 36–54, 2015</p> </abstract>