The cover time of the giant component of a random graph

We study the cover time of a random walk on the largest component of the random graph G_n,p. We determine its value up to a factor 1 + o(1) whenever np = c > 1, c = O(lnn). In particular, we show that the cover time is not monotone for c = Θ(lnn). We also determine the cover time of the k‐cores, k ≥ 2. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Rumor spreading on random regular graphs and expanders

Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well‐studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all d ‐regular graphs with n vertices. We show that with probability 1 ‐ o(1) the push model broadcasts the message to all nodes within (1 + o(1))C_d lnn rounds, where Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo‐random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + o(1))Clnn with probability 1 ‐ o(1), where \begin{align*}C = \lim_{d\to\infty}C_d = \frac{1}{\ln2} + 1\end{align*}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Disjoint bases in a polymatroid

Let f : 2^N → ⁺ be a polymatroid (an integer‐valued non‐decreasing submodular set function with f(??) = 0). We call S ? N a base if f(S) = f(N). We consider the problem of finding a maximum number of disjoint bases; we denote by m* be this base packing number. A simple upper bound on m* is given by k* = max{k : Σ_iεNf_A(i) ≥ kf_A(N),?A ? N} where f_A(S) = f(A ∪ S) ‐ f(A). This upper bound is a natural generalization of the bound for matroids where it is known that m* = k*. For polymatroids, we prove that m* ≥ (1 ? o(1))k*/lnf(N) and give a randomized polynomial time algorithm to find (1 ? o(1))k*/lnf(N) disjoint bases, assuming an oracle for f. We also derandomize the algorithm using minwise independent permutations and give a deterministic algorithm that finds (1 ? ε)k*/lnf(N) disjoint bases. The bound we obtain is almost tight because it is known there are polymatroids for which m* < (1 + o(1))k*/lnf(N). Moreover it is known that unless NP ? DTIME(n^{log log n}), for any ε > 0, there is no polynomial time algorithm to obtain a (1 + ε)/lnf(N)‐approximation to m*. Our result generalizes and unifies two results in the literature. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On a generalization of Rubin's theorem

The work is devoted to the calculation of asymptotic value of the choice number of the complete r‐partite graph K_{m* r} = K_{m, …, m} with equal part size m. We obtained the asymptotics in the case lnr = o(lnm). The proof generalizes the classical result of A.L. Rubin for the case r = 2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 226–234, 2011 67: 226‐234, 2011     

Estimates for the Rapid Decay of Concentration Functions of n-Fold Convolutions

We estimate the concentration functions of n-fold convolutions of one-dimensional probability measures. The Kolmogorov–Rogozin inequality implies that for nondegenerate distributions these functions decrease at least as O(n ^–1/2). On the other hand, Esseen⁽³⁾ has shown that this rate is o(n ^–1/2) iff the distribution has an infinite second moment. This statement was sharpened by Morozova.⁽⁹⁾ Theorem 1 of this paper provides an improvement of Morozova's result. Moreover, we present more general estimates which imply the rates o(n ^–1/2).     

Greedy colorings of uniform hypergraphs

We give a very short proof of an Erd?s conjecture that the number of edges in a non‐2‐colorable n‐uniform hypergraph is at least f(n)2ⁿ, where f(n) goes to infinity. Originally it was solved by József Beck in 1977, showing that f(n) at least clog n. With an ingenious recoloring idea he later proved that f(n) ≥ cn^1/3+o(1). Here we prove a weaker bound on f(n), namely f(n) ≥ cn^1/4. Instead of recoloring a random coloring, we take the ground set in random order and use a greedy algorithm to color. The same technique works for getting bounds on k‐colorability. It is also possible to combine this idea with the Lovász Local Lemma, reproving some known results for sparse hypergraphs (e.g., the n‐uniform, n‐regular hypergraphs are 2‐colorable if n ≥ 8). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Poisson approximation for non-backtracking random walks

Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the vertices of a graph. The authors of [3] studied non-backtracking random walks on regular graphs, and showed that their mixing rate may be up to twice as fast as that of the simple random walk. As an application, they showed that the maximal number of visits to a vertex, made by a non-backtracking random walk of length n on a high-girth n-vertex regular expander, is typically (1+o(1)))log n/log log n, as in the case of the balls and bins experiment. They further asked whether one can establish the precise distribution of the visits such a walk makes. In this work, we answer the above question by combining a generalized form of Brun’s sieve with some extensions of the ideas in [3]. Let N _t denote the number of vertices visited precisely t times by a non-backtracking random walk of length n on a regular n-vertex expander of fixed degree and girth g. We prove that if g = ω(1), then for any fixed t, N _t /n is typically 1/et! + o(1). Furthermore, if g = Ω(log log n), then N _t /n is typically 1+o(1)/et! niformly on all t ≤ (1 − o(1)) log n/log log n and 0 for all t ≥ (1 + o(1)) log n/log log n. In particular, we obtain the above result on the typical maximal number of visits to a single vertex, with an improved threshold window. The essence of the proof lies in showing that variables counting the number of visits to a set of sufficiently distant vertices are asymptotically independent Poisson variables.     

Improved random graph isomorphism

Canonical labeling of a graph consists of assigning a unique label to each vertex such that the labels are invariant under isomorphism. Such a labeling can be used to solve the graph isomorphism problem. We give a simple, linear time, high probability algorithm for the canonical labeling of a G(n,p) random graph for p[ω(ln⁴n/nlnlnn),1−ω(ln⁴n/nlnlnn)]. Our result covers a gap in the range of p in which no algorithm was known to work with high probability. Together with a previous result by Bollobás, the random graph isomorphism problem can be solved efficiently for p[Θ(lnn/n),1−Θ(lnn/n)].     

On the genus of a random graph

Let p = p(n) be a function of n with 0<p<1. We consider the random graph model ??(n, p); that is, the probability space of simple graphs with vertex-set {1, 2,…, n}, where two distinct vertices are adjacent with probability p. and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p²(1 ? p²) ?? 8(log n)⁴/n. then the (orientable) genus of a random graph in ??(n, p) is (1 + o(1))pn²/12. We prove that for every integer i ? 1, if n^?i/(i + 1) «p «n^{?(i ? 1)/i}. then the genus of a random graph in ??(n, p) is (1 + o(1))i/4(i + 2) pn². If p = cn^?(i?1)/o, where c is a constant, then the genus of a random graph in ??(n, p) is (1 + o(1))g(i, c, n)pn² for some function g(i, c, n) with 1/12 ? g(i, c, n) ? 1. but for i > 1 we were unable to compute this function.     

Enumeration of Almost-Convex Polygons on the Square Lattice

We classify self-avoiding polygons on the square lattice according to a concavity measure, m, where 2m is the difference between the number of steps in the polygon and the perimeter of the minimal rectangle bounding the polygon. We generate series expansions for the perimeter generating functions S_m(x) for polygons of concavity m. We analyze the series S_m(x) for m = 0 to 3. If N_m,n denotes the number of polygons of perimeter 2n and concavity m, with m = o(n^1/2), we prove that N_m,n ? 2^2n?m?7n^m+1/m!, and that the radius of convergence of the series counting all polygons with m = o(n) is equal to 1/4. Our numerical data leads us to conjecture that in fact for m = o(n^1/2), a result confirmed for m = 0 and 1.     

Size ramsey numbers of stars versus 4‐chromatic graphs

We investigate the asymptotics of the size Ramsey number î(K_1,nF), where K_1,n is the n‐star and F is a fixed graph. The author 11 has recently proved that r?(K_1,n,F)=(1+o(1))n² for any F with chromatic number χ(F)=3. Here we show that r?(K_1,n,F)≤ n²+o(n²), if χ (F) ≥ 4 and conjecture that this is sharp. We prove the case χ(F)=4 of the conjecture, that is, that r?(K_1,n,F)=(4+o(1))n² for any 4‐chromatic graph F. Also, some general lower bounds are obtained. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 220–233, 2003     

On the rate of convergence of a regular martingale related to a branching random walk

Let M _n , n = 1, 2, ..., be a supercritical branching random walk in which the number of direct descendants of an individual may be infinite with positive probability. Assume that the standard martingale W _n related to M _n is regular and W is a limit random variable. Let a(x) be a nonnegative function regularly varying at infinity with index greater than −1. We present sufficient conditions for the almost-sure convergence of the series . We also establish criteria for the finiteness of EW ln⁺ Wa(ln⁺ W) and E ln⁺|Z _∞|a(ln⁺|Z _∞|), where and (M _n , Q _n ) are independent identically distributed random vectors not necessarily related to M _n . __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 3, pp. 326–342, March, 2006.     

Topological characteristics of random triangulated surfaces

We consider the topological characteristics of orientable surfaces generated by randomly gluing n triangles together. Our results are most conveniently expressed in terms of a parameter h = n / 2 + χ, where χ is the Euler characteristic of the surface. Simulations and results for similar models suggest that Ex [h] = log(3n) + γ + o(1) and Var [h] = log(3n) + γ ‐ π² / 6 + o(1). We prove that Ex [h] = log n + O(1) and Var [h] = O(log n). We also derive results concerning a number of other topological invariants and combinatorial characteristics of these random surfaces. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

On the number of edge disjoint cliques in graphs of given size

In this paper, we prove that any graph ofn vertices andt _r–1(n)+m edges, wheret _r–1(n) is the Turán number, contains (1–o(1)m edge disjointK _r'sifm=o(n ²). Furthermore, we determine the maximumm such that every graph ofn vertices andt _r–1(n)+m edges containsm edge disjointK _r's ifn is sufficiently large.Research partially supported by Hungarian National Foundation for Scientific Research Grant no. 1812.     

The phase transition in inhomogeneous random graphs

The “classical” random graph models, in particular G(n,p), are “homogeneous,” in the sense that the degrees (for example) tend to be concentrated around a typical value. Many graphs arising in the real world do not have this property, having, for example, power‐law degree distributions. Thus there has been a lot of recent interest in defining and studying “inhomogeneous” random graph models. One of the most studied properties of these new models is their “robustness”, or, equivalently, the “phase transition” as an edge density parameter is varied. For G(n,p), p = c/n, the phase transition at c = 1 has been a central topic in the study of random graphs for well over 40 years. Many of the new inhomogeneous models are rather complicated; although there are exceptions, in most cases precise questions such as determining exactly the critical point of the phase transition are approachable only when there is independence between the edges. Fortunately, some models studied have this property already, and others can be approximated by models with independence. Here we introduce a very general model of an inhomogeneous random graph with (conditional) independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p = c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real‐world graphs. Our model includes as special cases many models previously studied. We show that, under one very weak assumption (that the expected number of edges is “what it should be”), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is “stable”: for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(n). © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 31, 3–122, 2007     

Asymptotic enumeration ofN-free partial orders

LetN(n) andN ^* (n) denote, respectively, the number of unlabeled and labeledN-free posets withn elements. It is proved thatN(n)=2 ^{n logn+o(n logn)} andN ^*(n)=2^{2n logn+o(n logn)}. This is obtained by considering the class ofN-free interval posets which can be easily counted.     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Monochromatic Matchings in the Shadow Graph of Almost Complete Hypergraphs

Edge colorings of r-uniform hypergraphs naturally define a multicoloring on the 2-shadow, i.e., on the pairs that are covered by hyperedges. We show that in any (r – 1)-coloring of the edges of an r-uniform hypergraph with n vertices and at least (1-e)( *20c nr)(1-\varepsilon)\left( {\begin{array}{*{20}c} n\\ r\\ \end{array}}\right) edges, the 2-shadow has a monochromatic matching covering all but at most o(n) vertices. This result confirms an earlier conjecture and implies that for any fixed r and sufficiently large n, there is a monochromatic Berge-cycle of length (1 – o(1))n in every (r – 1)-coloring of the edges of K^(r)_n{K^{(r)}_{n}}, the complete r-uniform hypergraph on n vertices.     

An approximate version of Sumner?s universal tournament conjecture

Sumner?s universal tournament conjecture states that any tournament on 2n−2 vertices contains a copy of any directed tree on n vertices. We prove an asymptotic version of this conjecture, namely that any tournament on (2+o(1))n vertices contains a copy of any directed tree on n vertices. In addition, we prove an asymptotically best possible result for trees of bounded degree, namely that for any fixed Δ, any tournament on (1+o(1))n vertices contains a copy of any directed tree on n vertices with maximum degree at most Δ.