Introduction

Suppose we have a tree with \(n\) vertices, and an integer \(1\le k\le n\). Each edge \(e\) of the tree has weight \(w(e)\in\mathbb R\), and we define the weight of a path as the sum of weight of edges on the path. Now we want to select at most \(k\) edge-disjoint paths on the tree, and maximize the total weight of the selected paths. Another version of the problem asks one to select at most \(k\) vertex-disjoint paths. A simple algorithm is to use dynamic programming: let \(f(x,i,b)\) denote the maximum total weight by choosing \(i\) paths in the subtree of \(x\), where \(b\) denotes whether or not \(x\) itself is contained in one of the paths. However, this dynamic programming runs in time \(O(n^2)\). Another solution is, by observing that the answer is concave with respect to \(k\), one can use alien's trick to optimize the dynamic programming algorithm to \(O(n\log n)\) complexity. The concavity is intuitive: when we are trying to add a new path, our new reward is always getting smaller. However, it's not easy to give a rigorous proof of this claim. As far as I know, this is the first full proof of such claim. (I haven't done much survey, so please email me if you have seen a proof somewhere else!)

Background

The story

So I was reading this lecture note about secretary problems, and I was trying to prove Theorem 24.3 myself. I also obtained an sum representing the probability which is different from the one in the lecture note. However I had some difficulty proving that the two sums are equilvalent (if not given this problem). After a day of suffering, using the summation by parts technique, I found that the sum was in fact a high-order sum of the harmonic series, and that this sum has a pretty simple representation.

Introduction

Let's start with the SAT problem: suppose we are given a boolean SAT formula with \(n\) variables and \(poly(n)\) clauses, and we want to know whether there exists a satisfiying assignment. This problem is known to be NP-complete, thus is generally believed to be hard to solve on a classical computer. The exponential time hypothesis states that satisfiability of SAT cannot be solved in \(2^{o(n)}\) time. However, with Grover's algorithm on a quantum computer, one can determine the existence of satisfying assignment, or even find one, within time \(O\left(2^{\frac n2}\right)\)! In fact, for any search problem with \(N\) candidates and \(M\) solutions, Grover's algorithm can find one solution with \(O\left(\sqrt{\frac NM}\right)\) operations, while a classical algorithm usually takes \(O(\frac NM)\) operations.

Recall the definition of algebraic numbers: \(x\) is an algebraic number iff it is a root of some non-zero polynomial with rational coefficients.

Definition of Algebraic Numbers

Let \(x\in\mathbb C\) be a complex number. We call it an algebraic number iff \(\exists n>0\), \(\exists a_0,\cdots,a_n\in\mathbb Q, a_n\ne0\), s.t. \(\sum_{i=0}^na_nx^n=0\).

Algebraic number is algebraically closed

The algebraic numbers have an intriguing property: it is algebraically closed. That is, the sum, difference, product and quotient of two algebraic numbers is again algebraic. Moreover, the roots of a non-zero polynomial whose coefficients are algebraic numbers is again algebraic.

The idea of the proof is from ¹, page 429-431.

Definition

Spectral Expander

Let \(G\) be an \(n\)-vertex \(d\)-regular undirected graph. Let \(A\) be its random walk matrix, i.e. \(a_{i,j}=\frac 1d |E(i,j)|\). One can see that the largest eigenvalue of \(A\) is \(1\). We define \(\lambda(G)\) as the second-largest eigenvalue of \(H\). If \(\lambda(G)\le\lambda\) for some \(\lambda<1\), then we say \(G\) is an \((n,d,\lambda)\)-spectral-expander.

Edge Expander

Let \(G=(V,E)\) be an \(n\)-vertex \(d\)-regular undirected graph. We call it an \((n,d,\rho)\)-edge-expander iff \[ \forall S\subset V, |S|\le\frac n2\implies E(S,\bar S)\ge\rho d|S| \]

Edge Expansion Implies Spectral Expansion

In fact, we can show that the two expanders are somewhat "equivalent", i.e. spectral expansion implies edge expansion and vice versa. Here we focus on the hard direction: edge expansion implies spectral expansion.

Theorem

An \((n,d,\rho)\)-edge-expander is an \((n,d,1-\frac{\rho^2}2)\)-spectral-expander.

h1 Heading 8-)

h2 Heading

h3 Heading

h4 Heading

h5 Heading

h6 Heading