a. Show that if G is a 0-regular graph then $k(G)= \\lambda (G)$ b. Show that if

Question

a. Show that if G is a 0-regular graph then $k(G)= lambda (G)$

b. Show that if G is a 1-regular graph then $k(G)= lambda (G)$

c. Show that if G is a 2-regular graph then $k(G)= lambda (G)$

Explanation / Answer

documentclass[10pt]{article} usepackage{amsmath,amsfonts} usepackage{textcomp} ewtheorem{define}{Definition} % ewcommand{Z}{{mathbb{Z}}} %usepackage{psfig} oddsidemargin=0.15in evensidemargin=0.15in opmargin=-.5in extheight=9in extwidth=6.25in egin{document} input{preamble.tex} lecture{18}{April 4, 2008}{Ronitt Rubinfeld, lecture given by Krzysztof Onak}{Curtis Fonger} %%%% body goes in here %%%% %We know the following: section{Review of Current Knowledge} Let USTCONN be the problem of checking if two nodes $s$ and $t$ in an undirected graph $G$ are connected. STCONN is the same problem for all graphs, including directed graphs. egin{enumerate} item ${ m USTCONN} in { m RL}$ (we've already seen this result in class) item ${ m STCONN} in { m NL}$ (non-deterministic log-space) item ${ m NL} subset { m L^2}$ (by Savitch's Theorem) item ${ m RL} subset { m L^{3/2}}$ (Saks & Zhou 1999) item ${ m USTCONN} in { m L}$ (Reingold in STOC 2005, we will see this result today) item There is strong evidence that ${ m L} = { m RL}$ (see Reingold, Trevisan, Vadhan 2006), but this is still an open problem. end{enumerate} egin{definition} We say that a graph is an emph{$(N,D,lambda)$-graph} if it is a $D$-regular graph on $N$ nodes such that the absolute values of all eigenvalues but one are bounded by $lambda$. end{definition} egin{fact} %label{thm1} For all $lambda < 1$, there exists an $epsilon > 0$ such that for all $(N, D, lambda)$-graphs $G$ and $S subset G$ such that $bs{S} 1$ and a graph $H$ such that $H$ is a $(D^4, D, 1/4)$-graph. end{fact} From now on, we assume that $H$ is an arbitrary fixed graph of the above properties. We now describe the algorithm. egin{enumerate} item Reduce the input $(G,s,t)$ to $(G_0, s_0, t_0)$ where $G_0$ is a $D^2$-regular, non-bipartite and $s_0$ and $t_0$ are connected if and only if $s$ and $t$ are connected in $G$. item For each $k = 1,...,L$, where $L = O(log N)$: egin{enumerate} item $G_k = G_{k-1}^2 extcircled{sffamily z} H$ item Let $s_k$ (and $t_k$) be any vertex in the copy of $H$ that replaces $s_{k-1}$ ($t_{k-1}$, respectively) in $G_k$. end{enumerate} item Try all paths in $G_L$ of length $O(log N)$ that start from $s_L$, and accept the input if any visits $t_L$. end{enumerate} oindent To see how the graph operations change the degree and the number of nodes, note that: egin{itemize} item $G_0$ is a $D^2$-regular graph on $N'$ nodes, item $G_0^2$ is a $D^4$-regular graph on $N'$ nodes, item $G_1 = G_0^2 extcircled{sffamily z} H$ is a $D^2$-regular graph on $D^4 cdot N'$ nodes. end{itemize} Hence in general, $G_i$ is a $D^2$-regular graph on $D^{4i} cdot N'$ nodes. The following fact is relatively easy to prove. egin{fact} %label{thm5} For any non-bipartite, undirected graph $G$ with $N$ nodes, we have that [ lambda(G) leq 1 - rac{1}{poly(N)}. ] end{fact} It says that the initial spectral gap of each component of the graph is large enough to be amplified in $O(log N)$ graph operations to at least a constant. Let $C_0$ be any connected component in $G_0$, and then let $C_{i+1}$ be the component corresponding to $C_i$ in $G_{i+1}$. We have [ gamma(C_0) geq rac{1}{poly(N)}.] By the properties of squaring, [ 1-gamma(C_{k-1}^2) leq (1-gamma(C_{k-1}))^2, ] and hence, [ gamma(C_{k-1}^2) geq 2gamma(C_{k-1})left(1-rac{1}{2}gamma(C_{k-1}) ight). ] Finally, egin{align*} gamma(C_k) = gamma(C_{k-1}^2 extcircled{sffamily z} H) &geq gamma(H)^2 cdot gamma(C_{k-1}^2) \ &geq left(rac{3}{4} ight)^2 cdot 2 cdot gamma(C_{k-1})cdotleft(1-rac{1}{2}gamma(C_{k-1}) ight) \ &geq minleft{rac{17}{16}gamma(C_{k-1}), rac{1}{18} ight}. end{align*} We have the last inequality because we have two cases: if $gamma(C_{k-1}) leq rac{1}{18}$, then $gamma(C_k) ge rac{17}{16}gamma(C_{k-1})$, and if $gamma(C_{k-1}) geq rac{1}{18}$, then $gamma(C_k) ge rac{1}{18}$. This implies that after $L=O(log N)$ iterations we must have $gamma(C_L) ge rac{1}{18}$. section{Implementation} Why can this algorithm be implemented in logarithmic space? Because: egin{itemize} item We keep the current path throughout the algorithm. We only need $O(1)$ bits per each step, since $G'$ has bounded degree. Besides, the length of the path is $O(log N)$. item When going back, we can compute the location from scratch. item We can compute $G_0$ in logarithmic space and use it as a subroutine. item We can compute each $G_k$ recursively with $O(1)$ space per recursion level. We omit the details here. end{itemize} section{Open Problem} The following challenging question remains open: ${ m RL} = { m L}$? end{document}

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.