Let G(n,d) be the random d-regular graph on n vertices. For any integer k exceeding a certain constant k_0 we identify a number d_ k-col such that G(n,d) is k-colorable w.h.p. if d d_ k-col .
With respect to random regular graphs @math , Frieze and @cite_20 proved a result akin to 's @cite_14 for @math . In fact, Cooper, Frieze, Reed and Riordan @cite_5 extended this result to the regime @math for any fixed @math , and Krivelevich, Sudakov, Vu and Wormald @cite_33 further still to @math . For @math fixed as @math , the bounds from @cite_20 were improved by the aforementioned contributions @cite_18 @cite_17 .
@cite_18 @cite_14 @cite_33 @cite_5 @cite_20 @cite_17
2610630562 1798337851 2000931246 2949304946
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 [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n1 3−e), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd2). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. Let λλ be the second largest eigenvalue in absolute value of a uniform random dd-regular graph on nn vertices. It was famously conjectured by Alon and proved by Friedman that if dd is fixed independent of nn, then λ=2d−1−−−−√+o(1)λ=2d−1+o(1) with high probability. In the present work, we show that λ=O(d−−√)λ=O(d) continues to hold with high probability as long as d=O(n2 3)d=O(n2 3), making progress toward a conjecture of Vu that the bound holds for all 1≤d≤n 21≤d≤n 2. Prior to this work the best result was obtained by Broder, Frieze, Suen and Upfal (1999) using the configuration model, which hits a barrier at d=o(n1 2)d=o(n1 2). We are able to go beyond this barrier by proving concentration of measure results directly for the uniform distribution on dd-regular graphs. These come as consequences of advances we make in the theory of concentration by size biased couplings. Specifically, we obtain Bennett-type tail estimates for random variables admitting certain unbounded size biased couplings. Let f be a random Boolean formula that is an instance of 3-SAT. We consider the problem of computing the least real number k such that if the ratio of the number of clauses over the number of variables of f strictly exceeds k , then f is almost certainly unsatisfiable. By a well-known and more or less straightforward argument, it can be shown that kF5.191. This upper bound was improved by to 4.758 by first providing new improved bounds for the occupancy problem. There is strong experimental evidence that the value of k is around 4.2. In this work, we define, in terms of the random formula f, a decreasing sequence of random variables such that, if the expected value of any one of them converges to zero, then f is almost certainly unsatisfiable. By letting the expected value of the first term of the sequence converge to zero, we obtain, by simple and elementary computations, an upper bound for k equal to 4.667. From the expected value of the second term of the sequence, we get the value 4.601q . In general, by letting the U This work was performed while the first author was visiting the School of Computer Science, Carleton Ž University, and was partially supported by NSERC Natural Sciences and Engineering Research Council . of Canada , and by a grant from the University of Patras for sabbatical leaves. The second and third Ž authors were supported in part by grants from NSERC Natural Sciences and Engineering Research . Council of Canada . During the last stages of this research, the first and last authors were also partially Ž . supported by EU ESPRIT Long-Term Research Project ALCOM-IT Project No. 20244 . †An extended abstract of this paper was published in the Proceedings of the Fourth Annual European Ž Symposium on Algorithms, ESA’96, September 25]27, 1996, Barcelona, Spain Springer-Verlag, LNCS, . pp. 27]38 . That extended abstract was coauthored by the first three authors of the present paper. Correspondence to: L. M. Kirousis Q 1998 John Wiley & Sons, Inc. CCC 1042-9832r98r030253-17 253 Given a discrete random walk on a finite graph @math , the vacant set and vacant net are, respectively, the sets of vertices and edges which remain unvisited by the walk at a given step @math . These sets induce subgraphs of the underlying graph. Let @math be the subgraph of @math induced by the vacant set of the walk at step @math . Similarly, let @math be the subgraph of @math induced by the edges of the vacant net. For random @math -regular graphs @math , it was previously established that for a simple random walk, the graph @math of the vacant set undergoes a phase transition in the sense of the phase transition on Erd os -Renyi graphs @math . Thus, for @math there is an explicit value @math of the walk, such that for @math , @math has a unique giant component, plus components of size @math , whereas for @math all the components of @math are of size @math . We establish the threshold value @math for a phase transition in the graph @math of the vacant net of a simple random walk on a random @math -regular graph. We obtain the corresponding threshold results for the vacant set and vacant net of two modified random walks. These are a non-backtracking random walk, and, for @math even, a random walk which chooses unvisited edges whenever available. This allows a direct comparison of thresholds between simple and modified walks on random @math -regular graphs. The main findings are the following: As @math increases the threshold for the vacant set converges to @math in all three walks. For the vacant net, the threshold converges to @math for both the simple random walk and non-backtracking random walk. When @math is even, the threshold for the vacant net of the unvisited edge process converges to @math , which is also the vertex cover time of the process.