Search

Let $X_1,..., X_n$ be independent, uniformly random points from $[0,1]^2$. We prove that if we add edges between these points one by one by order of increasing edge length then, with probability tending to 1 as the number of points $n$ tends to $\infty$, the resulting graph gets its first Hamilton cycle at exactly the same time it loses its last vertex of degree less than two. This answers an open question of Penrose and provides an analogue for the random geometric graph of a celebrated result of Ajtai, Koml\'os and Szemer\'edi and independently of Bollob\'as on the usual random graph. We are also able to deduce very precise information on the limiting probability that the random geometric graph is Hamiltonian analogous to a result of Koml\'os and Szemer{\'e}di on the usual random graph. The proof generalizes to uniform random points on the $d$-dimensional hypercube where the edge-lengths are measured using the $l_p$-norm for some $1

We prove that, in the Gilbert model for a random geometric graph, almost every graph becomes Hamiltonian exactly when it first becomes 2-connected. This answers a question of Penrose. We also show that in the k-nearest neighbor model, there is a constant \kappa\ such that almost every \kappa-connected graph has a Hamilton cycle., Comment: Published in at http://dx.doi.org/10.1214/10-AAP718 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

We prove that there is an absolute constant $C>0$ so that for every natural $n$ there exists a triangle-free \emph{regular} graph with no independent set of size at least $C\sqrt{n\log n}$., Comment: 5 pages

An old problem of Erd\H{o}s, Fajtlowicz and Staton asks for the order of a largest induced regular subgraph that can be found in every graph on n vertices. Motivated by this problem, we consider the order of such a subgraph in a typical graph on n vertices, i.e., in a binomial random graph G(n,1/2). We prove that with high probability a largest induced regular subgraph of G(n,1/2) has about n^{2/3} vertices.

In this work we suggest a new model for generating random satisfiable k-CNF formulas. To generate such formulas -- randomly permute all 2^k\binom{n}{k} possible clauses over the variables x_1, ..., x_n, and starting from the empty formula, go over the clauses one by one, including each new clause as you go along if after its addition the formula remains satisfiable. We study the evolution of this process, namely the distribution over formulas obtained after scanning through the first m clauses (in the random permutation's order). Random processes with conditioning on a certain property being respected are widely studied in the context of graph properties. This study was pioneered by Ruci\'nski and Wormald in 1992 for graphs with a fixed degree sequence, and also by Erd\H{o}s, Suen, and Winkler in 1995 for triangle-free and bipartite graphs. Since then many other graph properties were studied such as planarity and H-freeness. Thus our model is a natural extension of this approach to the satisfiability setting. Our main contribution is as follows. For m \geq cn, c=c(k) a sufficiently large constant, we are able to characterize the structure of the solution space of a typical formula in this distribution. Specifically, we show that typically all satisfying assignments are essentially clustered in one cluster, and all but e^{-\Omega(m/n)} n of the variables take the same value in all satisfying assignments. We also describe a polynomial time algorithm that finds with high probability a satisfying assignment for such formulas.

In numerous positional games the identity of the winner is easily determined. In this case one of the more interesting questions is not {\em who} wins but rather {\em how fast} can one win. These type of problems were studied earlier for Maker-Breaker games; here we initiate their study for unbiased Avoider-Enforcer games played on the edge set of the complete graph $K_n$ on $n$ vertices. For several games that are known to be an Enforcer's win, we estimate quite precisely the minimum number of moves Enforcer has to play in order to win. We consider the non-planarity game, the connectivity game and the non-bipartite game.

In this paper we analyze the appearance of a Hamilton cycle in the following random process. The process starts with an empty graph on n labeled vertices. At each round we are presented with K=K(n) edges, chosen uniformly at random from the missing ones, and are asked to add one of them to the current graph. The goal is to create a Hamilton cycle as soon as possible. We show that this problem has three regimes, depending on the value of K. For K=o(\log n), the threshold for Hamiltonicity is (1+o(1))n\log n /(2K), i.e., typically we can construct a Hamilton cycle K times faster that in the usual random graph process. When K=\omega(\log n) we can essentially waste almost no edges, and create a Hamilton cycle in n+o(n) rounds with high probability. Finally, in the intermediate regime where K=\Theta(\log n), the threshold has order n and we obtain upper and lower bounds that differ by a multiplicative factor of 3., Comment: 23 pages

We say that a graph $G=(V,E)$ on $n$ vertices is a $\beta$-expander for some constant $\beta>0$ if every $U\subseteq V$ of cardinality $|U|\leq \frac{n}{2}$ satisfies $|N_G(U)|\geq \beta|U|$ where $N_G(U)$ denotes the neighborhood of $U$. In this work we explore the process of deleting vertices of a $\beta$-expander independently at random with probability $n^{-\alpha}$ for some constant $\alpha>0$, and study the properties of the resulting graph. Our main result states that as $n$ tends to infinity, the deletion process performed on a $\beta$-expander graph of bounded degree will result with high probability in a graph composed of a giant component containing $n-o(n)$ vertices that is in itself an expander graph, and constant size components. We proceed by applying the main result to expander graphs with a positive spectral gap. In the particular case of $(n,d,\lambda)$-graphs, that are such expanders, we compute the values of $\alpha$, under additional constraints on the graph, for which with high probability the resulting graph will stay connected, or will be composed of a giant component and isolated vertices. As a graph sampled from the uniform probability space of $d$-regular graphs with high probability is an expander and meets the additional constraints, this result strengthens a recent result due to Greenhill, Holt and Wormald about vertex percolation on random $d$-regular graphs. We conclude by showing that performing the above described deletion process on graphs that expand sub-linear sets by an unbounded expansion ratio, with high probability results in a connected expander graph., Comment: 13 pages

For a real c \geq 1 and an integer n, let f(n,c) denote the maximum integer f so that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at most c times the minimum degree. Thus, in particular, every graph on n vertices contains a regular induced subgraph on at least f(n,1) vertices. The problem of estimating $(n,1) was posed long time ago by Erdos, Fajtlowicz and Staton. In this note we obtain the following upper and lower bounds for the asymptotic behavior of f(n,c): (i) For fixed c>2.1, n^{1-O(1/c)} \leq f(n,c) \leq O(cn/\log n). (ii) For fixed c=1+\epsilon with epsilon>0 sufficiently small, f(n,c) \geq n^{\Omega(\epsilon^2/ \ln (1/\epsilon))}. (iii) \Omega (\ln n) \leq f(n,1) \leq O(n^{1/2} \ln^{3/4} n). An analogous problem for not necessarily induced subgraphs is briefly considered as well.

For a fixed integer r, consider the following random process. At each round, one is presented with r random edges from the edge set of the complete graph on n vertices, and is asked to choose one of them. The selected edges are collected into a graph, which thus grows at the rate of one edge per round. This is a natural generalization of what is known in the literature as an Achlioptas process (the original version has r=2), which has been studied by many researchers, mainly in the context of delaying or accelerating the appearance of the giant component. In this paper, we investigate the small subgraph problem for Achlioptas processes. That is, given a fixed graph H, we study whether there is an online algorithm that substantially delays or accelerates a typical appearance of H, compared to its threshold of appearance in the random graph G(n, M). It is easy to see that one cannot accelerate the appearance of any fixed graph by more than the constant factor r, so we concentrate on the task of avoiding H. We determine thresholds for the avoidance of all cycles C_t, cliques K_t, and complete bipartite graphs K_{t,t}, in every Achlioptas process with parameter r >= 2., Comment: 43 pages; reorganized and shortened

The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we improve known parameterized algorithms and combinatorial bounds on the number of leaves in out-branchings. We show that \begin{itemize} \item every strongly connected digraph $D$ of order $n$ with minimum in-degree at least 3 has an out-branching with at least $(n/4)^{1/3}-1$ leaves; \item if a strongly connected digraph $D$ does not contain an out-branching with $k$ leaves, then the pathwidth of its underlying graph is $O(k\log k)$; \item it can be decided in time $2^{O(k\log^2 k)}\cdot n^{O(1)}$ whether a strongly connected digraph on $n$ vertices has an out-branching with at least $k$ leaves. \end{itemize} All improvements use properties of extremal structures obtained after applying local search and of some out-branching decompositions.

Extending several previous results we obtained nearly tight estimates on the maximum size of a clique-minor in various classes of expanding graphs. These results can be used to show that graphs without short cycles and other H-free graphs contain large clique-minors, resolving some open questions in this area.

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d\geq 2 and 0<\epsilon<1, there exists a constant c=c(d,\epsilon) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-\epsilon)n vertices with maximum degree at most d. We also prove that if an (n,D,\lambda)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most \lambda in their absolute values) has large enough spectral gap D/\lambda as a function of d and \epsilon, then G has a copy of every tree T as above.

We prove that finding a rooted subtree with at least $k$ leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in digraphs from a wide family $\cal L$ that includes all strong and acyclic digraphs. This settles completely an open question of Fellows and solves another one for digraphs in $\cal L$. Our algorithms are based on the following combinatorial result which can be viewed as a generalization of many results for a `spanning tree with many leaves' in the undirected case, and which is interesting on its own: If a digraph $D\in \cal L$ of order $n$ with minimum in-degree at least 3 contains a rooted spanning tree, then $D$ contains one with at least $(n/2)^{1/5}-1$ leaves.

In this paper we prove a sufficient condition for the existence of a Hamilton cycle, which is applicable to a wide variety of graphs, including relatively sparse graphs. In contrast to previous criteria, ours is based on only two properties: one requiring expansion of ``small'' sets, the other ensuring the existence of an edge between any two disjoint ``large'' sets. We also discuss applications in positional games, random graphs and extremal graph theory., Comment: 19 pages

Let $K_{n,n}$ be the complete bipartite graph with $n$ vertices in each side. For each vertex draw uniformly at random a list of size $k$ from a base set $S$ of size $s=s(n)$. In this paper we estimate the asymptotic probability of the existence of a proper colouring from the random lists for all fixed values of $k$ and growing $n$. We show that this property exhibits a sharp threshold for $k\geq 2$ and the location of the threshold is precisely $s(n)=2n$ for $k=2$, and approximately $s(n)=\frac{n}{2^{k-1}\ln 2}$ for $k\geq 3$., Comment: 14 pages. To appear in Random Structures and Algorithms

Let $C_n^k$ be the $k$-th power of a cycle on $n$ vertices (i.e. the vertices of $C_n^k$ are those of the $n$-cycle, and two vertices are connected by an edge if their distance along the cycle is at most $k$). For each vertex draw uniformly at random a subset of size $c$ from a base set $S$ of size $s=s(n)$. In this paper we solve the problem of determining the asymptotic probability of the existence of a proper colouring from the lists for all fixed values of $c,k$, and growing $n$., Comment: 7 pages

In this work we show that with high probability the chromatic number of a graph sampled from the random regular graph model $\Gnd$ for $d=o(n^{1/5})$ is concentrated in two consecutive values, thus extending a previous result of Achlioptas and Moore. This concentration phenomena is very similar to that of the binomial random graph model $\Gnp$ with $p=\frac{d}{n}$. Our proof is largely based on ideas of Alon and Krivelevich who proved this two-point concentration result for $\Gnp$ for $p=n^{-\delta}$ where $\delta>1/2$. The main tool used to derive such a result is a careful analysis of the distribution of edges in $\Gnd$, relying both on the switching technique and on bounding the probability of exponentially small events in the configuration model., Comment: 18 pages

The isoperimetric constant of a graph $G$ on $n$ vertices, $i(G)$, is the minimum of $\frac{|\partial S|}{|S|}$, taken over all nonempty subsets $S\subset V(G)$ of size at most $n/2$, where $\partial S$ denotes the set of edges with precisely one end in $S$. A random graph process on $n$ vertices, $\widetilde{G}(t)$, is a sequence of $\binom{n}{2}$ graphs, where $\widetilde{G}(0)$ is the edgeless graph on $n$ vertices, and $\widetilde{G}(t)$ is the result of adding an edge to $\widetilde{G}(t-1)$, uniformly distributed over all the missing edges. We show that in almost every graph process $i(\widetilde{G}(t))$ equals the minimal degree of $\widetilde{G}(t)$ as long as the minimal degree is $o(\log n)$. Furthermore, we show that this result is essentially best possible, by demonstrating that along the period in which the minimum degree is typically $\Theta(\log n)$, the ratio between the isoperimetric constant and the minimum degree falls from 1 to 1/2, its final value.

Random graphs have proven to be one of the most important and fruitful concepts in modern Combinatorics and Theoretical Computer Science. Besides being a fascinating study subject for their own sake, they serve as essential instruments in proving an enormous number of combinatorial statements, making their role quite hard to overestimate. Their tremendous success serves as a natural motivation for the following very general and deep informal questions: what are the essential properties of random graphs? How can one tell when a given graph behaves like a random graph? How to create deterministically graphs that look random-like? This leads us to a concept of pseudo-random graphs and the aim of this survey is to provide a systematic treatment of this concept., Comment: 50 pages

We calculate the asymptotic value of the choice number of complete multi-partite graphs., Comment: 16 pages

Using graph-theoretic methods we give a new proof that for all sufficiently large $n$, there exist sphere packings in $\R^n$ of density at least $cn2^{-n}$, exceeding the classical Minkowski bound by a factor linear in $n$. This matches up to a constant the best known lower bounds on the density of sphere packings due to Rogers, Davenport-Rogers, and Ball. The suggested method makes it possible to describe the points of such a packing with complexity $\exp(n\log n)$, which is significantly lower than in the other approaches., Comment: 6 pages, 2 postscript figures

We prove that for all values of the edge probability p(n) the largest eigenvalue of a random graph G(n,p) satisfies almost surely: \lambda_1(G)=(1+o(1))max{\sqrt{\Delta},np}, where \Delta is a maximal degree of G, and the o(1) term tends to zero as max{\sqrt{\Delta},np} tends to infinity.

We prove that few largest (and most important) eigenvalues of random symmetric matrices of various kinds are very strongly concentrated. This strong concentration enables us to compute the means of these eigenvalues with high precision. Our approach uses Talagrand's inequality and is very different from standard approaches.