Source author record

Daniel Poole

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

3works
2topics
1close collaborators

Published work

3 publications

preprint2015arXiv

Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs

Two models of a random digraph on nn vertices, D(n,Prob(arc)=p)D(n,\text{Prob}(\text{arc})=p) and D(n,number of arcs=m)D(n,\text{number of arcs}=m) are studied. In 1990, Karp for D(n,p)D(n,p) and independently T. Łuczak for D(n,m=cn)D(n,m=cn) proved that for c>1c>1, with probability tending to 1, there is an unique strong component of size of order nn. Karp showed, in fact, that the giant component has likely size asymptotic to nθ2nθ^2, where θ=θ(c)θ=θ(c) is the unique positive root of 1−θ=e−cθ1-θ=e^{-c θ}. In this paper we prove that, for both random digraphs, the joint distribution of the number of vertices and number of arcs in the giant strong component is asymptotically Gaussian with the same mean vector nμ(c)n\boldsymbolμ(c), μ(c):=(θ2,cθ2)\boldsymbolμ(c):=(θ^2, cθ^2) and two distinct 2×22\times 2 covariance matrices, nB(c)n\mathbf{B}(c) and n[B(c)+c(μ′(c))T(μ′(c)))]n[\mathbf{B}(c)+c (\boldsymbolμ'(c))^T (\boldsymbolμ'(c)))]. To this end, we introduce and analyze a randomized deletion process which determines the directed (1,1)(1,1)-core, the maximal digraph with minimum in-degree and out-degree at least 1. This (1,1)(1,1)-core contains all non-trivial strong components. However, we show that the likely numbers of peripheral vertices and arcs in the (1,1)(1,1)-core, those outside the largest strong component, are of log-polynomial order, thus dwarfed by anticipated fluctuations, on the scale of n1/2n^{1/2}, of the giant component parameters. By approximating the likely realization of the deletion algorithm with a deterministic trajectory, we obtain our main result via exponential supermartingales and Fourier-based techniques.

preprint2015arXiv

On the strength of connectedness of a random hypergraph

Bollobás and Thomason (1985) proved that for each k=k(n)∈[1,n−1]k=k(n) \in [1, n-1], with high probability, the random graph process, where edges are added to vertex set V=[n]V=[n] uniformly at random one after another, is such that the stopping time of having minimal degree kk is equal to the stopping time of becoming kk-(vertex-)connected. We extend this result to the dd-uniform random hypergraph process, where kk and dd are fixed. Consequently, for m=nd(ln⁡n+(k−1)ln⁡ln⁡n+c)m=\frac{n}{d}(\ln n +(k-1)\ln \ln n +c) and p=(d−1)!ln⁡n+(k−1)ln⁡ln⁡n+cnd−1p=(d-1)! \frac{\ln n + (k-1) \ln \ln n +c}{n^{d-1}}, the probability that the random hypergraph models Hd(n,m)H_d(n, m) and Hd(n,p)H_d(n, p) are kk-connected tends to e−e−c/(k−1)!.e^{-e^{-c}/(k-1)!}.

preprint2014arXiv

On Weak Hamiltonicity of a Random Hypergraph

A {\it weak (Berge) cycle} is an alternating sequence of vertices and (hyper)edges C=(v0,e1,v1,...,vℓ−1,eℓ,vℓ=v0)C=(v_0, e_1, v_1, ..., v_{\ell-1}, e_\ell, v_{\ell}=v_0) such that the vertices v0,...,vℓ−1v_0, ..., v_{\ell-1} are distinct with vk,vk+1∈ekv_k, v_{k+1} \in e_{k} for each kk, but the edges e1,...,eℓe_1, ..., e_\ell are not necessarily distinct. We prove that the main barrier to the random dd-uniform hypergraph Hd(n,p),H_d(n,p), where each of the potential edges of cardinality dd is present with probability pp, developing a weak Hamilton cycle is the presence of isolated vertices. In particular, for d≥3d \geq 3 fixed and p=(d−1)!ln⁡n+cnd−1p=(d-1)! \frac{\ln n + c}{n^{d-1}}, the probability that Hd(n,p)H_d(n, p) has a weak Hamilton cycle tends to e−e−ce^{-e^{-c}}, which is also the limiting probability that Hd(n,p)H_d(n,p) has no isolated vertices. As a consequence, the probability that the random hypergraph Hd(n,m=n(ln⁡n+c)d),H_d(n, m=\frac{n(\ln n + c)}{d}), where mm potential edges are chosen uniformly at random to be present, is weak Hamiltonian also tends to e−e−ce^{-e^{-c}}.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.