BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We provide a new lower bound on the length of the longest cycle of the binomial random graph G(n,(1+ε)/n) that holds w.h.p. for all ε=ε(n) such that ε3n→∞. In the case ε≤ε0 for some sufficiently small constant ε0, this bound is equal to 1.581ε2n which improves upon the current best lower bound of 4ε2n/3 due to Luczak.
We discuss the length Lc,n of the longest directed cycle in the sparse random digraph Dn,p,p=c/n, c constant. We show that for large c there exists a function f(c) such that Lc,n/n→f(c) a.s. The function f(c)=1−∑k=1∞pk(c)e−kc where pk is a polynomial in c. We are only able to explicitly give the values p1,p2, although we could in principle compute any pk.
We discuss the length of the longest cycle in a sparse random graph Gn,p,p=c/n. c constant. We show that for large c there is a function f(c) such that Ln(c)/n→f(c) a.s. The function f(c)=1−∑k=1∞pk(c)e−kc where pk is a polynomial in k. We are only able to explicitly give the values p1,p2, although we could in principle compute any pk. We see immediately that the length of the longest path is also asymptotic to f(c)n w.h.p.
In this paper we consider the existence of Hamilton cycles in the random graph G=Gn,mδ≥3. This a random graph chosen uniformly from the set of graphs with vertex set [n], m edges and minimum degree at least 3. Our ultimate goal is to prove that if m=cn and c>3/2 is constant then G is Hamiltonian w.h.p. In an earlier paper the second author showed that c≥10 is sufficient for this and in this paper we reduce the lower bound to c>2.662.... This new lower bound is the same lower bound found in Frieze and Pittel \cite{FP} for the expansion of so-called Pósa sets.
Let G be a graph with edge set (e1,e2,...eN). We independently associate to each edge ei of G a cost xi that is drawn from a Uniform [0, 1] distribution. Suppose F is a set of targeted structures that consists of subgraphs of G. We would like to buy a subset of F at small cost, however we do not know a priori the values of the random variables x1,...,xN. Instead, we inspect the random variables xi one at a time. As soon as we inspect the random variable associated with the cost of an edge we have to decide whether we want to buy that edge or reject it for ever. In the present paper we consider the case where G is the complete graph on n vertices and F is the set of all C4 -cycles on 4 vertices- out of which we want to buy one.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.