BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Simon Griffiths

Simon Griffiths appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRmath.NTmath.GR

Catalog footprint

What is connected

19works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

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.

Published work

19 published item(s)

preprint2020arXiv

Moderate deviations of subgraph counts in the Erdős-Rényi random graphs $G(n,m)$ and $G(n,p)$

The main contribution of this article is an asymptotic expression for the rate associated with moderate deviations of subgraph counts in the Erdős-Rényi random graph $G(n,m)$. Our approach is based on applying Freedman's inequalities for the probability of deviations of martingales to a martingale representation of subgraph count deviations. In addition, we prove that subgraph count deviations of different subgraphs are all linked, via the deviations of two specific graphs, the path of length two and the triangle. We also deduce new bounds for the related $G(n,p)$ model.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Chromatic thresholds in dense random graphs

The chromatic threshold $δ_χ(H,p)$ of a graph $H$ with respect to the random graph $G(n,p)$ is the infimum over $d > 0$ such that the following holds with high probability: the family of $H$-free graphs $G \subset G(n,p)$ with minimum degree $δ(G) \ge dpn$ has bounded chromatic number. The study of the parameter $δ_χ(H) := δ_χ(H,1)$ was initiated in 1973 by Erdős and Simonovits, and was recently determined for all graphs $H$. In this paper we show that $δ_χ(H,p) = δ_χ(H)$ for all fixed $p \in (0,1)$, but that typically $δ_χ(H,p) \ne δ_χ(H)$ if $p = o(1)$. We also make significant progress towards determining $δ_χ(H,p)$ for all graphs $H$ in the range $p = n^{-o(1)}$. In sparser random graphs the problem is somewhat more complicated, and is studied in a separate paper.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Chromatic thresholds in sparse random graphs

The chromatic threshold $δ_χ(H,p)$ of a graph $H$ with respect to the random graph $G(n,p)$ is the infimum over $d > 0$ such that the following holds with high probability: the family of $H$-free graphs $G \subset G(n,p)$ with minimum degree $δ(G) \ge dpn$ has bounded chromatic number. The study of $δ_χ(H) :=δ_χ(H,1)$ was initiated in 1973 by Erdős and Simonovits. Recently $δ_χ(H)$ was determined for all graphs $H$. It is known that $δ_χ(H,p) =δ_χ(H)$ for all fixed $p \in (0,1)$, but that typically $δ_χ(H,p) \ne δ_χ(H)$ if $p = o(1)$. Here we study the problem for sparse random graphs. We determine $δ_χ(H,p)$ for most functions $p = p(n)$ when $H\in\{K_3,C_5\}$, and also for all graphs $H$ with $χ(H) \not\in \{3,4\}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quenched Voronoi percolation

We prove that the probability of crossing a large square in quenched Voronoi percolation converges to 1/2 at criticality, confirming a conjecture of Benjamini, Kalai and Schramm from 1999. The main new tools are a quenched version of the box-crossing property for Voronoi percolation at criticality, and an Efron-Stein type bound on the variance of the probability of the crossing event in terms of the sum of the squares of the influences. As a corollary of the proof, we moreover obtain that the quenched crossing event at criticality is almost surely noise sensitive.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Explosion and linear transit times in infinite trees

Let $T$ be an infinite rooted tree with weights $w_e$ assigned to its edges. Denote by $m_n(T)$ the minimum weight of a path from the root to a node of the $n$th generation. We consider the possible behaviour of $m_n(T)$ with focus on the two following cases: we say $T$ is explosive if \[ \lim_{n\to \infty}m_n(T) < \infty, \] and say that $T$ exhibits linear growth if \[ \liminf_{n\to \infty} \frac{m_n(T)}{n} > 0. \] We consider a class of infinite randomly weighted trees related to the Poisson-weighted infinite tree, and determine precisely which trees in this class have linear growth almost surely. We then apply this characterization to obtain new results concerning the event of explosion in infinite randomly weighted spherically-symmetric trees, answering a question of Pemantle and Peres. As a further application, we consider the random real tree generated by attaching sticks of deterministic decreasing lengths, and determine for which sequences of lengths the tree has finite height almost surely.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Noise Sensitivity in Continuum Percolation

We prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality. This is the first such result for a Continuum Percolation model, and the first for which the critical probability p_c \ne 1/2. Our proof uses a version of the Benjamini-Kalai-Schramm Theorem for biased product measures. A quantitative version of this result was recently proved by Keller and Kindler. We give a simple deduction of the non-quantitative result from the unbiased version. We also develop a quite general method of approximating Continuum Percolation models by discrete models with p_c bounded away from zero; this method is based on an extremal result on non-uniform hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On explosions in heavy-tailed branching random walks

Consider a branching random walk on $\mathbb{R}$, with offspring distribution Z and nonnegative displacement distribution W. We say that explosion occurs if an infinite number of particles may be found within a finite distance of the origin. In this paper, we investigate this phenomenon when the offspring distribution Z is heavy-tailed. Under an appropriate condition, we are able to characterize the pairs (Z, W) for which explosion occurs, by demonstrating the equivalence of explosion with a seemingly much weaker event: that the sum over generations of the minimum displacement in each generation is finite. Furthermore, we demonstrate that our condition on the tail is best possible for this equivalence to occur. We also investigate, under additional smoothness assumptions, the behavior of $M_n$, the position of the particle in generation n closest to the origin, when explosion does not occur (and hence $\lim_{n\rightarrow\infty}M_n=\infty$).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On the Ramsey number of the triangle and the cube

The Ramsey number r(K_3,Q_n) is the smallest integer N such that every red-blue colouring of the edges of the complete graph K_N contains either a red n-dimensional hypercube, or a blue triangle. Almost thirty years ago, Burr and Erdős conjectured that r(K_3,Q_n) = 2^{n+1} - 1 for every n \in \N, but the first non-trivial upper bound was obtained only recently, by Conlon, Fox, Lee and Sudakov, who proved that r(K_3,Q_n) \le 7000 \cdot 2^n. Here we show that r(K_3,Q_n) = (1 + o(1)) 2^{n+1} as n \to \infty.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

(k+1)-sums versus k-sums

A $k$-sum of a set $A\subseteq \mathbb{Z}$ is an integer that may be expressed as a sum of $k$ distinct elements of $A$. How large can the ratio of the number of $(k+1)$-sums to the number of $k$-sums be? Writing $k\wedge A$ for the set of $k$-sums of $A$ we prove that \[ \frac{|(k+1)\wedge A|}{|k\wedge A|}\, \le \, \frac{|A|-k}{k+1} \] whenever $|A|\ge (k^{2}+7k)/2$. The inequality is tight -- the above ratio being attained when $A$ is a geometric progression. This answers a question of Ruzsa.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Invasion percolation on the Poisson-weighted infinite tree

We study invasion percolation on Aldous' Poisson-weighted infinite tree, and derive two distinct Markovian representations of the resulting process. One of these is the $σ\to\infty$ limit of a representation discovered by Angel et al. [Ann. Appl. Probab. 36 (2008) 420-466]. We also introduce an exploration process of a randomly weighted Poisson incipient infinite cluster. The dynamics of the new process are much more straightforward to describe than those of invasion percolation, but it turns out that the two processes have extremely similar behavior. Finally, we introduce two new "stationary" representations of the Poisson incipient infinite cluster as random graphs on $\mathbb {Z}$ which are, in particular, factors of a homogeneous Poisson point process on the upper half-plane $\mathbb {R}\times[0,\infty)$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

k-Sums in abelian groups

Given a finite subset A of an abelian group G, we study the set k \wedge A of all sums of k distinct elements of A. In this paper, we prove that |k \wedge A| >= |A| for all k in {2,...,|A|-2}, unless k is in {2,|A|-2} and A is a coset of an elementary 2-subgroup of G. Furthermore, we characterize those finite subsets A of G for which |k \wedge A| = |A| for some k in {2,...,|A|-2}. This result answers a question of Diderrich. Our proof relies on an elementary property of proper edge-colourings of the complete graph.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tight inequalities among set hitting times in Markov chains

Given an irreducible discrete-time Markov chain on a finite state space, we consider the largest expected hitting time $T(α)$ of a set of stationary measure at least $α$ for $α\in(0,1)$. We obtain tight inequalities among the values of $T(α)$ for different choices of $α$. One consequence is that $T(α) \le T(1/2)/α$ for all $α< 1/2$. As a corollary we have that, if the chain is lazy in a certain sense as well as reversible, then $T(1/2)$ is equivalent to the chain's mixing time, answering a question of Peres. We furthermore demonstrate that the inequalities we establish give an almost everywhere pointwise limiting characterisation of possible hitting time functions $T(α)$ over the domain $α\in(0,1/2]$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Quasi-random oriented graphs

We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham and Wilson in the case of unoriented graphs, and by Chung and Graham in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G the main result of Chung and Graham which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four-cycle can be used for a quasi-randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Subset sums in abelian groups

Denoting by Sigma(S) the set of subset sums of a subset S of a finite abelian group G, we prove that |Sigma(S)| >= |S|(|S|+2)/4-1 whenever S is symmetric, |G| is odd and Sigma(S) is aperiodic. Up to an additive constant of 2 this result is best possible, and we obtain the stronger (exact best possible) bound in almost all cases. We prove similar results in the case |G| is even. Our proof requires us to extend a theorem of Olson on the number of subset sums of anti-symmetric subsets S from the case of Z_p to the case of a general finite abelian group. To do so, we adapt Olson's method using a generalisation of Vosper's Theorem proved by Hamidoune and Plagne.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The chromatic thresholds of graphs

The chromatic threshold delta_chi(H) of a graph H is the infimum of d>0 such that there exists C=C(H,d) for which every H-free graph G with minimum degree at least d|G| satisfies chi(G)<C. We prove that delta_chi(H) \in {(r-3)/(r-2), (2r-5)/(2r-3), (r-2)/(r-1)} for every graph H with chi(H)=r>2. We moreover characterise the graphs H with a given chromatic threshold, and thus determine delta_chi(H) for every graph H. This answers a question of Erdős and Simonovits [Discrete Math. 5 (1973), 323-334], and confirms a conjecture of Łuczak and Thomassé [preprint (2010), 18pp].

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The spectrum of random lifts

For a fixed d-regular graph H, a random n-lift is obtained by replacing each vertex v of H by a "fibre" containing n vertices, then placing a uniformly random matching between fibres corresponding to adjacent vertices of H. We show that with extremely high probability, all eigenvalues of the lift that are not eigenvalues of H, have order O(sqrt(d)). In particular, if H is Ramanujan then its n-lift is with high probability nearly Ramanujan. We also show that any exceptionally large eigenvalues of the n-lift that are not eigenvalues of H, are overwhelmingly likely to have been caused by a dense subgraph of size O(|E(H)|).

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Subgraphs of weakly quasi-random oriented graphs

It is an intriguing question to see what kind of information on the structure of an oriented graph $D$ one can obtain if $D$ does not contain a fixed oriented graph $H$ as a subgraph. The related question in the unoriented case has been an active area of research, and is relatively well-understood in the theory of quasi-random graphs and extremal combinatorics. In this paper, we consider the simplest cases of such a general question for oriented graphs, and provide some results on the global behavior of the orientation of $D$. For the case that $H$ is an oriented four-cycle we prove: in every $H$-free oriented graph $D$, there is a pair $A,B\ssq V(D)$ such that $e(A,B)\ge e(D)^{2}/32|D|^{2}$ and $e(B,A)\le e(A,B)/2$. We give a random construction which shows that this bound on $e(A,B)$ is best possible (up to the constant). In addition, we prove a similar result for the case $H$ is an oriented six-cycle, and a more precise result in the case $D$ is dense and $H$ is arbitrary. We also consider the related extremal question in which no condition is put on the oriented graph $D$, and provide an answer that is best possible up to a multiplicative constant. Finally, we raise a number of related questions and conjectures.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Asymptotically tight bounds on subset sums

For a subset A of a finite abelian group G we define Sigma(A)={sum_{a\in B}a:B\subset A}. In the case that Sigma(A) has trivial stabiliser, one may deduce that the size of Sigma(A) is at least quadratic in |A|; the bound |Sigma(A)|>= |A|^{2}/64 has recently been obtained by De Vos, Goddyn, Mohar and Samal. We improve this bound to the asymptotically best possible result |Sigma(A)|>= (1/4-o(1))|A|^{2}. We also study a related problem in which A is any subset of Z_{n} with all elements of A coprime to n; it has recently been shown, by Vu, that if such a set A has the property Sigma(A) is not Z_{n} then |A|=O(sqrt{n}). This bound was improved to |A|<= 8sqrt{n} by De Vos, Goddyn, Mohar and Samal, we further improve the bound to the asymptotically best possible result |A|<= (2+o(1))sqrt{n}.

0 citations0 reviewsNo code linkedOpen access