We describe a deterministic, polynomial time algorithm for finding edge-disjoint paths connecting given pairs of vertices in an expander. Specifically, the input of the algorithm is a sufficiently strong d-regular expander G on n vertices, and a sequence of pairs si, ti(1lesilesr) of vertices, where, r=Theta(nd log d/log n), and no vertex appears more than d/3 times in the list of all endpoints s1, t1,... ,sr,tr. The algorithm outputs edge-disjoint paths Q1,...,Qr, where Qiconnects siand ti. The paths are constructed online, that is, the algorithm produces Qias soon as it gets si,tiand before the next requests in the sequence are revealed. This improves in several respects a long list of previous algorithms for the above problem, whose study is motivated by the investigation of communication networks. An analogous result is established for vertex disjoint paths in blowups of strong expanders.

The expected diameter of a cubic undirected N-vertex graph is no more than lg N + lg lg N + 10. However, the problem of explicitly constructing an infinite family of N-vertex graphs with maximum degree 3 and diameter lg N + o(lg N) is open; the best construction known for graphs on N vertices has diameter 1.47lg N. Here we present an explicit construction of an infinite family ${\cal H}$ of cubic graphs $\Lambda$ with diameter $1.413\lg |V(\Lambda)|+ O(1)$.

We present a simple, explicit construction of an infinite family F of bounded-degree 'unique-neighbor' expanders /spl Gamma/; i.e., there are strictly positive constants /spl alpha/ and /spl epsi/, such that all /spl Gamma/ = (X, E(/spl Gamma/)) /spl isin/ F satisfy the following property. For each subset S of X with no more than /spl alpha/|X| vertices, there are at least /spl epsi/|S| vertices in X/spl bsol/S that are adjacent in /spl Gamma/ to exactly one vertex in S. The construction of F is simple to specify, and each /spl Gamma/ /spl isin/ F is 6-regular. We then extend the technique and present easy to describe explicit infinite families of 4-regular and 3-regular unique-neighbor expanders, as well as explicit families of bipartite graphs with nonequal color classes and similar properties. This has several applications and settles an open problem considered by various researchers.

The main concrete result of this paper is the first explicit construction of constant degree lossless expanders. In these graphs, the expansion factor is almost as large as possible: (1—ε)D, where D is the degree and ε is an arbitrarily small constant. The best previous explicit constructions gave expansion factor D/2, which is too weak for many applications. The D/2 bound was obtained via the eigenvalue method, and is known that that method cannot give better bounds.The main abstract contribution of this paper is the introduction and initial study of randomness conductors, a notion which generalizes extractors, expanders, condensers and other similar objects. In all these functions, certain guarantee on the input "entropy" is converted to a guarantee on the output "entropy". For historical reasons, specific objects used specific guarantees of different flavors. We show that the flexibility afforded by the conductor definition leads to interesting combinations of these objects, and to better constructions such as those above.The main technical tool in these constructions is a natural generalization to conductors of the zig-zag graph product, previously defined for expanders and extractors.

For any positive integers r and n, let H(r,n) denote the family of graphs on n vertices with maximum degree r, and let H(r,n,n) denote the family of bipartite graphs H on 2n vertices with n vertices in each vertex class, and with maximum degree r. On one hand, we note that any H(r,n)-universal graph must have /spl Omega/(n/sup 2-2/r/) edges. On the other hand, for any n/spl ges/n/sub 0/(r), we explicitly construct H(r,n)-universal graphs G and /spl Lambda/ on n and 2n vertices, and with O(n/sup 2-/spl Omega//(1/r log r)) and O(n/sup 2-1/r/ log/sup 1/r/ n) edges, respectively, such that we can efficiently find a copy of any H /spl epsiv/ H (r,n) in G deterministically. We also achieve sparse universal graphs using random constructions. Finally, we show that the bipartite random graph G=G(n,n,p), with p=cn/sup -1/2r/ log/sup 1/2r/ n is fault-tolerant; for a large enough constant c, even after deleting any /spl alpha/-fraction of the edges of G, the resulting graph is still H(r,/spl alpha/(/spl alpha/)n,/spl alpha/(/spl alpha/)n)-universal for some /spl alpha/: [0,1)/spl rarr/(0,1].

Let 3& be the family of N-vertex graphs of maximum degree q, and with a 2-sector function j(z) < z"'.For every constant positive 6, we show via an explicit construction algorithm that there exists an 3iT3(-universal graph r' of size O,(N).This construction is a significant improvement over the best previously known construction of size n(N2-").