A d-regular graph has largest or first (adjacency matrix) eigenvalue λ₁ = d. In this paper we show the following conjecture of Alon. Fix an integer d > 2 and a real ε > 0. Then for sufficiently large n we have that "most" d-regular graphs on n vertices ...

Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ε n² edges have to be deleted from it to make it H-free. We show that in this case G contains at least f(ε,H) n^h copies of H. This is proved ...

In dynamic stabbing, we operate on a dynamic set of intervals. A stabbing query asks for an interval containing a given point. This basic problem encodes problems such as method look-up in object oriented programming languages and classification in IP ...

This paper provides the first explicit construction of extractors which are simultaneously optimal up to constant factors in both seed length and output length. More precisely, for every n,k, our extractor uses a random seed of length O(log n) to ...

We extend the classic notion of well-separated pair decomposition [10] to the (weighted) unit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unit-disk graph metric of n points ...

In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the result of Bartal who gave a bound of O(log n log log n). ...

We present a new bicriteria approximation algorithm for the degree-bounded minimum-cost spanning tree problem: Given an undirected graph with nonnegative edge weights and degree bounds B_v > 1 for all vertices v, find a spanning tree T of minimum total ...

We improve rapid mixing results for the simple Glauber dynamics designed to generate a random k-coloring of a bounded-degree graph.Let G be a graph with maximum degree Δ = Ω(log n), and girth ≥ 5. We prove that if k > Α Δ, where Α ≈ 1.763 then Glauber ...

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [9] and prove that it produces an asymptotically uniform random regular graph in a ...

We study novel combinatorial properties of graphs that allow us to devise a completely new approach to dynamic all pairs shortest paths problems. Our approach yields a fully dynamic algorithm for general directed graphs with non-negative real-valued ...

We consider Fibonacci heap style integer priority queues supporting insert and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys support delete in O(log log n) time. If the integers are ...

We present a new algorithm for answering short path queries in planar graphs. For any fixed constant k and a given unweighted planar graph G=(V,E) one can build in O(|V|) time a data structure, which allows to check in O(1) time whether two given ...