Source author record

W. Kinnersley

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

2works

1topics

3close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

A note on the acquaintance time of random graphs

In this short note, we prove the conjecture of Benjamini, Shinkar, and Tsur on the acquaintance time $AC(G)$ of a random graph $G \in G(n,p)$ . It is shown that asymptotically almost surely $AC(G) = O(\log n / p)$ for $G \in G(n,p)$ , provided that $pn > (1+ε) \log n$ for some $ε> 0$ (slightly above the threshold for connectivity). Moreover, we show a matching lower bound for dense random graphs, which also implies that asymptotically almost surely $K_n$ cannot be covered with $o(\log n / p)$ copies of a random graph $G \in G(n,p)$ , provided that $pn > n^{1/2+ε}$ and $p < 1-ε$ for some $ε>0$ . We conclude the paper with a small improvement on the general upper bound showing that for any $n$ -vertex graph $G$ , we have $AC(G) = O(n^2/\log n)$ .

preprint2013arXiv

Toppling numbers of complete and random graphs

We study a two-person game played on graphs based on the widely studied chip-firing game. Players Max and Min alternately place chips on the vertices of a graph. When a vertex accumulates as many chips as its degree, it fires, sending one chip to each neighbour; this may in turn cause other vertices to fire. The game ends when vertices continue firing forever. Min seeks to minimize the number of chips played during the game, while Max seeks to maximize it. When both players play optimally, the length of the game is the {\em toppling number} of a graph $G$ , and is denoted by $\tg(G)$ . By considering strategies for both players and investigating the evolution of the game with differential equations, we provide asymptotic bounds on the toppling number of the complete graph. In particular, we prove that for sufficiently large $n$ $0.596400 n^2 < \tg(K_n) < 0.637152 n^2.$ Using a fractional version of the game, we couple the toppling numbers of complete graphs and the binomial random graph $G(n,p)$ . It is shown that for $pn \ge n^{2/\sqrt{\log n}}$ asymptotically almost surely $t(G(n,p))=(1+o(1))p\tg(K_n)$ .

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.