Search

In previous papers the authors showed that almost all d-regular graphs for d≤3 are hamiltonian. In the present paper this result is generalized so that a set of j oriented root edges have been randomly specified for the cycle to contain. The Hamilton cycle must be orientable to agree with all of the orientations on the j root edges. It is shown that the requisite Hamilton cycle almost surely exists if and the limiting probability distribution at the threshold is determined when d=3. It is a corollary (in view of results elsewhere) that almost all claw-free cubic graphs are hamiltonian. There is a variation in which an additional cyclic ordering on the root edges is imposed which must also agree with their ordering on the Hamilton cycle. In this case, the required Hamilton cycle almost surely exists if j=o(n2/5). The method of analysis is small subgraph conditioning. This gives results on contiguity and the distribution of the number of Hamilton cycles which imply the facts above. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 128–147, 2001

The Lovasz local lemma is a sieve method to prove the existence of certain structures with certain prescribed properties. In most of its applications the Lovasz local lemma does not supply a polynomial-time algorithm for finding these structures. Beck was the first who gave a method of converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. He applied his technique to the symmetric form of the Lovasz local lemma and, in particular, to the problem of 2-coloring uniform hypergraphs. In this paper we investigate the general form of the Lovasz local lemma. Our main result is a randomized algorithm for 2-coloring nonuniform hypergraphs that runs in expected linear time. Even for uniform hypergraphs no algorithm with such a runtime bound was previously known, and no polynomial-time algorithm was known at all for the class of nonuniform hypergraphs we will consider in this paper. Our algorithm and its analysis provide a novel approach to the general Lovasz local lemma that may be of independent interest. We also show how to extend our result to the c-coloring problem. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 17: 213–237, 2000

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 Kamath et al. 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

One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability which permits routing, both for the hypercube and for the $d-$dimensional mesh. We use tools from percolation theory to show that in the $d-$dimensional mesh, once a giant component appears -- efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location then that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph $G_{n,p}$.

We close a gap in the proof of Theorem 4.1 in our paper "The complexity of counting graph homomorphisms" [Random Structures Algorithms 17 (2000), 260-289].

In his seminal result, Beck gave the first algorithmic version of the Lovasz Local Lemma by giving polynomial time algorithms for 2-coloring and partitioning uniform hypergraphs. His work was later generalized by Alon, and Molloy and Reed. Recently, Czumaj and Scheideler gave an efficient algorithm for 2-coloring nonuniform hypergraphs. But the partitioning algorithm obtained based on their second paper only applies to a more limited range of hypergraphs, so much so that their work doesn't imply the result of Beck for the uniform case. Here we give an algorithmic version of the general form of the Local Lemma which captures (almost) all applications of the results of Beck and Czumaj and Scheideler, with an overall simpler proof. In particular, if H is a nonuniform hypergraph in which every edge ei intersects at most |ei|2αk other edges of size at most k, for some small constant α, then we can find a partitioning of H in expected linear time. This result implies the result of Beck for uniform hypergraphs along with a speedup in his running time.

Iteratively computing and discarding a set of convex hulls creates a structure known as an "onion." In this paper, we show that the expected number of layers of a convex hull onion for n uniformly and independently distributed points in a disk is Θ(n2/3). Additionally, we show that in general the bound is Θ(n2/(d+1)) for points distributed in a d-dimensional ball. Further, we show that this bound holds more generally for any fixed, bounded, full-dimensional shape with a nonempty interior.

The goal of this paper is to present a novel application of a recent and useful martingale inequality. As an illustration, we prove an essentially sharp bound for the probability that a random graph contains significantly more triangles than expected.

We study the asymptotic distribution of the fill-up level in a binary trie built over n independent strings generated by a biased memoryless source. The fill-up level is the number of full levels in a tree. A level is full if it contains the maximum allowable number of nodes (e.g., in a binary tree level k can have up to 2k nodes). The fill-up level finds many interesting applications, e.g., in the internet IP lookup problem and in the analysis of level compressed tries (LC tries). In this paper, we present a complete asymptotic characterization of the fill-up distribution. In particular, we prove that this distribution concentrates on one or two points around the most probably value k = ⌊log1/qn - log log log n + 1 + log log(p/q)⌋, where p > q = 1 - p is the probability of generating the more likely symbol (while q = 1 - p is the probability of the less likely symbol). We derive our results by analytic methods such as generating functions, Mellin transform, the saddle point method, and analytic depoissonization. We also present some numerical verification of our results.

Let ℋk(n, p) be the random k-uniform hypergraph on V = [n] with edge probability p. Motivated by a theorem of Erdős and Renyi 7 regarding when a random graph G(n, p) = ℋ2(n, p) has a perfect matching, the following conjecture may be raised. (See J. Schmidt and E. Shamir 16 for a weaker version.) Conjecture. Let k|n for fixed k ≥ 3, and the expected degree d(n, p) = p(). Then (Erdős and Renyi 7 proved this for G(n, p).) Assuming d(n, p)/n1/2 ∞, Schmidt and Shamir 16 were able to prove that ℋk(n, p) contains a perfect matching with probability 1 − o(1). Frieze and Janson 8 showed that a weaker condition d(n, p)/n1/3 ∞ was enough. In this paper, we further weaken the condition to A condition for a similar problem about a perfect triangle packing of G(n, p) is also obtained. A perfect triangle packing of a graph is a collection of vertex disjoint triangles whose union is the entire vertex set. Improving a condition p ≥ cn−2/3+1/15 of Krivelevich 12, it is shown that if 3|n and p ≫ n−2/3+1/18, then © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 111–132, 2003

The cover time is the expected time it takes a random walk to cover all vertices of a graph. Despite the fact that it can be approximated with arbitrary precision by a simple polynomial time Monte-Carlo algorithm which simulates the random walk, it is not known whether the cover time of a graph can be computed in deterministic polynomial time. In the present paper we establish a deterministic polynomial time algorithm that, for any graph and any starting vertex, approximates the cover time within polylogarithmic factors. More generally, our algorithm approximates the cover time for arbitrary reversible Markov chains. The new aspect of our algorithm is that the starting vertex of the random walk may be arbitrary and is given as part of the input, whereas previous deterministic approximation algorithms for the cover time assume that the walk starts at the worst possible vertex. In passing, we show that the starting vertex can make a difference of up to a multiplicative factor of Θ(n3/2/√log n) in the cover time of an n-vertex graph.

This paper gives a new upper bound for the average length l(n) of the shortest disjunctive normal form for a random Boolean function of n arguments, as well as new proofs of two old results related to this quantity. We consider a random Boolean function of n arguments to be uniformly distributed over all 22n such functions. (This is equivalent to considering each entry in the truth-table to be 0 or 1 independently and with equal probabilities.) We measure the length of a disjunctive normal form by the number of terms. (Measuring it by the number of literals would simply introduce a factor of n into all our asymptotic results.) We give a short proof using martingales of Nigmatullin's result that almost all Boolean functions have the length of their shortest disjunctive normal form asymptotic to the average length l(n). We also give a short information-theoretic proof of Kuznetsov's lower bound l(n) ≥ (1 + o(1)) 2n/log n log log n. (Here log denotes the logarithm to base 2.) Our main result is a new upper bound l(n) ≤ (1 + o(1)) H(n) 2n/log n log log n, where H(n) is a function that oscillates between 1.38826... and 1.54169 .... The best previous upper bound, due to Korshunov, had a similar form, but with a function oscillating between 1.581411... and 2.621132 .... The main ideas in our new bound are (1) the use of Rodl's "nibble" technique for solving packing and covering problems, (2) the use of correlation inequalities due to Harris and Janson to bound the effects of weakly dependent random variables, and (3) the solution of an optimization problem that determines the sizes of "nibbles" and larger "bites" to be taken at various stages of the construction.

This paper investigates the number of random edges required to add to an arbitrary dense graph in order to make the resulting graph Hamiltonian with high probability. Adding Θ(n) random edges is both necessary and sufficient to ensure this for all such dense graphs. If, however, the original graph contains no large independent set, then many fewer random edges are required. We prove a similar result for directed graphs.

A "dyadic rectangle" is a set of the form R = [a2-s,(a + 1)2-s] × [b2-t,(b + 1)2-t], where s and t are nonnegative integers. A dyadic tiling is a tiling of the unit square with dyadic rectangles. In this paper we study n-tilings, which consist of 2n nonoverlapping dyadic rectangles, each of area 2-n, whose union is the unit square. We discuss some of the underlying combinatorial structures, provide some efficient methods for uniformly sampling from the set of n-tilings, and study some limiting properties of random tilings.

This paper studies the symmetry of random regular graphs and random graphs. Our main result shows that for all 3 ≤ d ≤ n - 4 the random d-regular graph on n vertices almost surely has no nontrivial automorphisms. This answers an open question of N. Wormald [13].

The decycling number φ(G) of a graph G is the smallest number of vertices which can be removed from G so that the resultant graph contains no cycles. In this paper, we study the decycling numbers of random regular graphs. For a random cubic graph G of order n, we prove that φ(G) = ⌈n/4 + 1/2⌉ holds asymptotically almost surely. This is the result of executing a greedy algorithm for decycling G making use of a randomly chosen Hamilton cycle. For a general random d-regular graph G of order n, where d ≥ 4, we prove that φ(G)/n can be bounded below and above asymptotically almost surely by certain constants b(d) and B(d), depending solely on d, which are determined by solving, respectively, an algebraic equation and a system of differential equations.

A sequence a = a1a2. . . . an is said to be nonrepetitive if no two adjacent blocks of a are exactly the same. For instance, the sequence 1232321 contains a repetition 2323, while 123132123213 is nonrepetitive. A theorem of Thue asserts that, using only three symbols, one can produce arbitrarily long nonrepetitive sequences. In this paper we consider a natural generalization of Thue's sequences for colorings of graphs. A coloring of the set of edges of a given graph G is nonrepetitive if the sequence of colors on any path in G is nonrepetitive. We call the minimal number of colors needed for such a coloring the Thue number of G and denote it by π(G). The main problem we consider is the relation between the numbers π(G) and Δ(G). We show, by an application of the Lovasz Local Lemma, that the Thue number stays bounded for graphs with bounded maximum degree, in particular, π(G) ≤ cΔ(G)2 for some absolute constant c. For certain special classes of graphs we obtain linear upper bounds on π(G), by giving explicit colorings. For instance, the Thue number of the complete graph Kn is at most 2n - 3, and π(T) ≤ 4(Δ(T - 1) for any tree T with at least two edges. We conclude by discussing some generalizations and proposing several problems and conjectures.

The Horton-Strahler number naturally arose from problems in various fields, e.g., geology, molecular biology and computer science. Consequently, detailed investigations of related parameters for different classes of binary tree structures are of interest. This paper shows one possibility of how to perform a mathematical analysis for parameters related to the Horton-Strahler number in a unified way such that only a single analysis is needed to obtain results for many different classes of trees. The method is explained by the examples of the expected Horton-Strahler number and the related rth moments, the average number of critical nodes, and the expected distance between critical nodes.

Let H be a fixed bipartite graph with δ(H) = 1. It is shown that if G is any graph with n vertices and minimum degree at least n/2(1 + on(1)) and e(H) divides e(G), then G can be decomposed into e(G)/e(H) edge-disjoint copies of H. This is best possible and significantly extends the result of an earlier paper by the author [8] which deals with the case where H is a tree.

Many NP-hard languages can be "decided" in subexponential time if the definition of "decide" is relaxed only slightly. Rubinfeld and Sudan introduced the notion of property testers, probabilistic algorithms that can decide, with high probability, if a function has a certain property or if it is far from any function having this property. Goldreich, Goldwasser, and Ron constructed property testers with constant query complexity for dense instances of a large class of graph problems. Since many graph problems can be viewed as special cases of the Constraint Satisfaction Problem on Boolean domains, it is natural to try to construct property testers for more general cases of the Constraint Satisfaction Problem. In this paper, we give explicit constructions of property testers using a constant number of queries for dense instances of Constraint Satisfaction Problems where the constraints have constant arity and the variables assume values in some domain of finite size.

Strong concentration results play a fundamental role in probabilistic combinatorics and theoretical computer science. In this paper, we present several new concentration results developed recently by the author and collaborators. To illustrate the power of these new results, we discuss applications in many different areas of mathematics, from combinatorial number theory to the theory of random graphs.

Let Γ be a finite index set and k ≥ 1 a given integer. Let further S ⊆ [Γ]≤k be an arbitrary family of k element subsets of Γ. Consider a (binomial) random subset Γp of Γ, where p = (pt : i ∈ Γ) and a random variable X counting the elements of S that are contained in this random subset. In this paper we survey techniques of obtaining upper bounds on the upper tail probabilities P(X ≥ λ + t) for t > 0. Seven techniques, ranging from Azuma's inequality to the purely combinatorial deletion method, are described, illustrated, and compared against each other for a couple of typical applications. As one application, we obtain essentially optimal bounds for the upper tails for the numbers of subgraphs isomorphic to K4 or C4 in a random graph G(n, p), for certain ranges of p.

The creation and growth of components of a given complexity in a random graph process are studied. In particular, the expected number and total size of all such components is found. It follows that the largest '-component during the process is Op(n 2/3 ) for any given '. The results also yield a new proof of the asymptotic behaviour of Wright's coecients. between the two processes is that in {G(n,m)}, the edges are added at the fixed times 1,2,..., so at time m we have the random graph G(n,m) with m edges, while in {G(n,t)} the edges are added at random times in such a way that at time t = p, we have the random graph G(n,p). ({G(n,t)} may be constructed by letting each edge e in the complete graph Kn appear at a random time Te, with Te independent and uniformly distributed on (0,1), and letting G(n,t) contain the edges that have appeared before t.) In this paper, we will study random variables that depend on the order the edges appear in the process, but not on the time scale. All such variables will thus have the same distribution for both processes (not only asymptotically, but also for each finite n). Hence all results below are valid for both processes. We define the complexity of a connected graph to be its number of edges minus its number of vertices. A component of a graph of complexity ' is called an '-component. Here ' 1; a ( 1)-component is a tree, a 0-component is unicyclic, and '-components with ' 1 are known as complex components. In the beginning of the random graph process, there are no edges at all, and thus n components of order 1 and complexity 1; at the end, we have the complete graph, with a single component of complexity n 2 n. Several authors have studied what happens in between, see e.g. (4, 9, 6, 7, 11, 8). We will here add some results obtained by studying, as in (6), the ways '-components are created. Each time a new edge is added, there are two possibilities

We consider the mixing properties of the widely used Swendsen–Wang process for the Markov chain Monte Carlo estimation of the partition function of the ferromagnetic Q-state Potts model, for certain classes of graphs. In the paper “The Swendsen–Wang Process Does Not Always Mix Rapidly,” V. Gore and M. Jerrum obtained results for the mixing properties of the Swendsen–Wang process on the complete graph Kn. Our main results for graphs with n vertices are the following: For graphs with small maximum degree, the mixing time is polynomial in n for small enough values of the coupling constant β. For trees, the mixing time is O(n) for any β. For cycles, the mixing time is O(n log n) for any β. For random graphs Gn, p, p=Ω(n−1/3), there are values of the coupling constant β for which whp the Swendsen–Wang process does not mix rapidly. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 242–261, 1999

It is proved that the internal path length of a d-dimensional quad tree after normalization converges in distribution. The limiting distribution is characterized as a fixed point of a random affine operator. We obtain convergence of all moments and of the Laplace transforms. The moments of the limiting distribution can be evaluated from the recursion and lead to first order asymptotics for the moments of the internal path lengths. The analysis is based on the contraction method. In the final part of the paper we state similar results for general split tree models if the expectation of the path length has a similar expansion as in the case of quad trees. This applies in particular to the m-ary search trees. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 5: 25–41, 1999

This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are based on the rapidly mixing properties of random walks on expander graphs. In the static version of the problem an algorithm is required to route a path between each of K pairs of vertices so that no edge is used by more than g paths. A natural approach to this problem is through a multicommodity flow reduction. However, we show that the random walk approach leads to significantly stronger-results than those recently obtained by Leighton w x and Rao Proc. of 9th International Parallel Processing Symposium, 1995 using the multicommodity flow setup. In the dynamic version of the problem connection requests are Ž continuously injected into the network. Once a connection is established it utilizes a path a . virtual circuit for a certain time until the communication terminates and the path is deleted. Again each edge in the network should not be used by more than g paths at once. The dynamic version is a better model for the practical use of communication networks. Our random walk approach gives a simple and fully distributed solution for this problem. We show that if the injection to the network and the duration of connection are both controlled by Poisson processes then our algorithm achieves a steady state utilization of the network which is similar to the utilization achieved in the static case situation. Q 1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 87]109, 1999 Correspondence to: A. Frieze *Supported in part by NSF Grants CCR-9225008 and CCR-9530974. Q 1999 John Wiley & Sons, Inc. CCC 1042-9832r99r010087-23 87 BRODER, FRIEZE, AND UPFAL 88

We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph G(n, 1/2), and then choose randomly a subset Q of vertices of size k and force it to be a clique by joining every pair of vertices of Q by an edge. The problem is to give a polynomial time algorithm for finding this hidden clique almost surely for various values of k. This question was posed independently, in various variants, by Jerrum and by Kucera. In this paper we present an efficient algorithm for all k>cn0.5, for any fixed c>0, thus improving the trivial case k>cn0.5(log n)0.5. The algorithm is based on the spectral properties of the graph. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13: 457–466, 1998

Recently we developed a new method in graph theory based on the regularity lemma. The method is applied to find certain spanning subgraphs in dense graphs. The other main general tool of the method, besides the regularity lemma, is the so-called blow-up lemma (Komlos, Sarkozy, and Szemeredi [Combinatorica,17, 109–123 (1997)]. This lemma helps to find bounded degree spanning subgraphs in e-regular graphs. Our original proof of the lemma is not algorithmic, it applies probabilistic methods. In this paper we provide an algorithmic version of the blow-up lemma. The desired subgraph, for an n-vertex graph, can be found in time O(nM(n)), where M(n)=O(n2.376) is the time needed to multiply two n by n matrices with 0, 1 entires over the integers. We show that the algorithm can be parallelized and implemented in NC5. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 297–312, 1998

In this paper typical properties of large random Boolean AND/OR formulas are investigated. Such formulas with n variables are viewed as rooted binary trees chosen from the uniform distribution of all rooted binary trees with m leaves, where n is fixed and m tends to infinity. The leaves are labeled by literals and the inner nodes by the connectives AND/OR, both uniformly at random. In extending the investigation to infinite trees, we obtain a close relation between the formula size complexity of an arbitrary Boolean function f and the probability of its occurrence under this distribution, i.e., the negative logarithm of this probability differs from the formula size complexity of f only by a polynomial factor.

The theory of random graphs has been mainly concerned with structural properties, in particular the most likely values of various graph invariants – see Bollobas [21]. There has been increasing interest in using random graphs as models for the average case analysis of graph algorithms. In this paper we survey some of the results in this area.

Wojciech S:r,pankowskit Dept. Computer Science Purdue University W. Lafayette, IN 47907 U.S.A. vVe present an analytical method of analyzing a class of "splitting algorilhms" that include probabilistic counting, selecting the leader, estimating the number of questions necessary to identify distinct objects, searching algorithms based on digital tries, approximate counting, ,mel so forth. In our disCl1ssion we concentrate on the analysis of a generalized probabilistic counting algorithm. Our techniquc belongs to lhe toolkit of the a.nalytical analysis of algorithms, and it involves solutions offunctional equations, analytical poissoniJr.ation and depoissorllzation, Mellin transform, etc. In particular, we deal with a functional equation of lhe form g(z) = fJa(z)g(z/2) + b(z) where a(z) and b(z) are given funclions, and fJ < 1 is a constant. With respect to our generalized probabilistic counting algorithm, we obtain asymptotic expansions of the first two moments of an estimatc of the cardinality of a set that is computed by the algorithm. We also derive the asymptotic distribution of tIllS cstimate, and observe that it actually flucluales, leading to a conclusion that its limiting distribution docs not exist . •A preliminary version of parts of tilis paper was presented ill }CALP 92, Vienna [26]. This work w~ supported by NSF Grants INT-8912631 and CCH.-9201078. lThis author was additionally was supported by NSF Grants NSF Gra.nts NCH.-!l206315 and NCH9115191, and in part by NATO Collaborative Grant CRG.!l50060.

This paper provides logspace and small circuit depth analogs of the result of Valiant and Vazirani, which is a randomized (or nonuniform) reduction from $NP$ to its arithmetic analog $\plusminus P$. We show a similar randomized reduction between the Boolean classes $NL$ and semiunbounded fan-in Boolean circuits and their arithmetic counterparts. These reductions are based on the Isolation Lemma of Mulmuley, Vazirani and Vazirani. Combinatorically our results can be viewed as simple (logspace) transformations of existential quantifiers into counting quantifiers in graphs and shallow circuits.

In 1962 Posa conjectured that any graph G of order n and minimum degree at least ⅔ n contains the square of a Hamiltonian cycle. In this paper we prove this conjecture for sufficiently large n. © 1996 John Wiley & Sons, Inc.

Let Gmn denote the set of simple graphs with n vertices and m edges, t(G) the number of spanning trees of a graph G, and F ≥ H if t(Ks\E(F)) ≥ t(Ks\E(H)) for every s ≥ max{v(F), v(H)}. We give a complete characterization of ≥-maximal (maximum) graphs in Gmn subject to m ≤ n. This result contains, in particular, a complete characterization of those graphs in Gkn that have the maximum number of spanning trees among all graphs in Gkn subject to n(n − 1)/2 − n ≤ k ≤ n(n − 1)/2. We discuss and use properties of the Laplacian polynomial L(λ, G) of a graph G [8]. Because of relation t(Ks\E(Gn)) = ss-n-2L(s, Gn) [8], the main result of the paper can also be interpreted as a characterisation of those graphs in Gmn, m ≤ n, having the maximum. Laplacian polynomial for every integer λ ≥ n. We also give an overview of some known approaches and results on this problem. © 1996 John Wiley & Sons, Inc.

In this paper, we apply some recent eigenvalue bounds based on heat kernel estimates to provide polynomial bounds on Markov chain approaches to a number of sampling problems. In particular, for the space S of m by n contingency tables (which are arrays of non-negative integers having fixed row and column sums), we give the first bounds on the mixing time for the natural walk on S which is polynomial in m, n and the row and column sums, provided the minimum row and column sums are large enough.

Let H be an r-uniform hypergraph satisfying deg(x) = D(1 + o(1)) for each vertex xϵ V(H) and deg(x, y) = o(D) for each pair of vertices x, y ϵ V(H), where D infinity. Recently, J. Spencer [5] showed, using a branching process approach, that almost surely the random greedy algorithm finds a packing of size at least n/r(1 − o(1)) for this class of hypergraphs. In this paper, we show an alternative proof of this via “nibbles.” Further, let Tα be the number of edges that the random greedy algorithm has to consider before yielding a packing of size [n/r · (1 − α)]. We show that almost surely Tα ∼ (1/α)r−1 · n/r(r − 1) as α 0+ holds. © 1996 John Wiley & Sons, Inc.

Raghavan's paper on derandomized approximation algorithms for 0–1 packing integer programs raised two challenging problems [11]: 1. Are there more examples of NP-hard combinatorial optimization problems for which derandomization yields constant factor approximations in polynomial-time ? 2. The pessimistic estimator technique shows an O(mn)-time implementation of the conditional probability method on the RAM model of computation in case of m large deviation events associated to m unweighted sums of n indepependent Bernoulli trials. Is there a fast algorithm also in case of rational weighted sums of Bernoulli trials ?

In this paper we prove improved lower and upper bounds on the size of sample spaces which which are required to be independent on specified neighborhoods. Our new constructions yield sample spaces whose size is smaller than previous constructions due to Schulman. Our lower bounds generalize the known lower bounds of Alon et al. and Chor et al. In obtaining these bounds we examine the possibilities and limitations of amplifying limited independence by fixed functions. We show that in general independence cannot be amplified from k-wise independence to (k + 1)-wise independence. Finally, we enumerate all possible logical consequences of pairwise independence random bits, i.e., events whose probabilities are a consequence of pairwise independence.

This paper is an investigation of the structural properties of random plane-oriented recursive trees and their branches. We begin by an enumeration of these trees and some general properties related to the outdegrees of nodes. Using generalized Polya urn models we study the exact and limiting distributions of the size and the number of leaves in the branches of the tree. The exact distribution for the leaves in the branches is given by formulas involving second-order Eulerian numbers. A martingale central limit theorem for a linear combination of the number of leaves and the number of internal nodes is derived. The distribution of that linear combination is a mixture of normals with a beta distribution as its mixing density. The martingale central limit theorem allows easy determination of the limit laws governing the leaves in the branches. Furthermore, the asymptotic joint distribution of the number of nodes of outdegree 0, 1 and 2 is shown to be trivariate normal. © 1993 John Wiley & Sons, Inc.