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 study monotone cellular automata (also known as U-bootstrap percolation) in Zd with random initial configurations. Confirming a conjecture of Balister, Bollobás, Przykucki and Smith, who proved the corresponding result in two dimensions, we show that the critical probability is non-zero for all subcritical models.
We study the class of monotone, two-state, deterministic cellular automata, in which sites are activated (or 'infected') by certain configurations of nearby infected sites. These models have close connections to statistical physics, and several specific examples have been extensively studied in recent years by both mathematicians and physicists. This general setting was first studied only recently, however, by Bollobás, Smith and Uzzell, who showed that the family of all such 'bootstrap percolation' models on Z2 can be naturally partitioned into three classes, which they termed subcritical, critical and supercritical. In this paper we determine the order of the threshold for percolation (complete occupation) for every critical bootstrap percolation model in two dimensions. This 'universality' theorem includes as special cases results of Aizenman and Lebowitz, Gravner and Griffeath, Mountford, and van Enter and Hulshof, significantly strengthens bounds of Bollobás, Smith and Uzzell, and complements recent work of Balister, Bollobás, Przykucki and Smith on subcritical models.
For a graph G, let f(G) be the largest integer k for which there exist two vertex-disjoint induced subgraphs of G each on k vertices, both inducing the same number of edges. We prove that f(G)≥n/2−o(n) for every graph G on n vertices. This answers a question of Caro and Yuster.
We consider the problem of maximising the largest eigenvalue of subgraphs of the hypercube Qd of a given order. We believe that in most cases, Hamming balls are maximisers, and our results support this belief. We show that the Hamming balls of radius o(d) have largest eigenvalue that is within 1+o(1) of the maximum value. We also prove that Hamming balls with fixed radius maximise the largest eigenvalue exactly, rather than asymptotically, when d is sufficiently large. Our proofs rely on the method of compressions.
In this paper we study in complete generality the family of two-state, deterministic, monotone, local, homogeneous cellular automata in Zd with random initial configurations. Formally, we are given a set U={X1,…,Xm} of finite subsets of Zd∖{0}, and an initial set A0⊂Zd of `infected' sites, which we take to be random according to the product measure with density p. At time t∈N, the set of infected sites At is the union of At−1 and the set of all x∈Zd such that x+X∈At−1 for some X∈U. Our model may alternatively be thought of as bootstrap percolation on Zd with arbitrary update rules, and for this reason we call it U-bootstrap percolation. In two dimensions, we give a classification of U-bootstrap percolation models into three classes -- supercritical, critical and subcritical -- and we prove results about the phase transitions of all models belonging to the first two of these classes. More precisely, we show that the critical probability for percolation on (Z/nZ)2 is (logn)−Θ(1) for all models in the critical class, and that it is n−Θ(1) for all models in the supercritical class. The results in this paper are the first of any kind on bootstrap percolation considered in this level of generality, and in particular they are the first that make no assumptions of symmetry. It is the hope of the authors that this work will initiate a new, unified theory of bootstrap percolation on Zd.
Delete the edges of a Kneser graph independently of each other with some probability: for what probabilities is the independence number of this random graph equal to the independence number of the Kneser graph itself? We prove a sharp threshold result for this question in certain regimes. Since an independent set in the Kneser graph is the same as a uniform intersecting family, this gives us a random analogue of the Erdős-Ko-Rado theorem.
We determine to within a constant factor the threshold for the property that two random k-uniform hypergraphs with edge probability p have an edge-disjoint packing into the same vertex set. More generally, we allow the hypergraphs to have different densities. In the graph case, we prove a stronger result, on packing a random graph with a fixed graph.
The independence density of a finite hypergraph is the probability that a subset of vertices, chosen uniformly at random contains no hyperedges. Independence densities can be generalized to countable hypergraphs using limits. We show that, in fact, every positive independence density of a countably infinite hypergraph with hyperedges of bounded size is equal to the independence density of some finite hypergraph whose hyperedges are no larger than those in the infinite hypergraph. This answers a question of Bonato, Brown, Kemkes, and Prałat about independence densities of graphs. Furthermore, we show that for any k, the set of independence densities of hypergraphs with hyperedges of size at most k is closed and contains no infinite increasing sequences.
Consider a random sequence of N integers, each chosen uniformly and independently from the set {1,…,x}. Motivated by applications to factorisation algorithms such as Dixon's algorithm, the quadratic sieve, and the number field sieve, Pomerance in 1994 posed the following problem: how large should N be so that, with high probability, this sequence contains a subsequence, the product of whose elements is a perfect square? Pomerance determined asymptotically the logarithm of the threshold for this event, and conjectured that it in fact exhibits a sharp threshold in N. More recently, Croot, Granville, Pemantle and Tetali determined the threshold up to a factor of 4/π+o(1) as x→∞, and made a conjecture regarding the location of the sharp threshold. In this paper we prove both of these conjectures, by determining the sharp threshold for making squares. Our proof combines techniques from combinatorics, probability and analytic number theory; in particular, we use the so-called method of self-correcting martingales in order to control the size of the 2-core of the random hypergraph that encodes the prime factors of our random numbers. Our method also gives a new (and completely different) proof of the upper bound in the main theorem of Croot, Granville, Pemantle and Tetali.
The class of critical bootstrap percolation models in two dimensions was recently introduced by Bollobás, Smith and Uzzell, and the critical threshold for percolation was determined up to a constant factor for all such models by the authors of this paper. Here we develop and refine the techniques introduced in that paper in order to determine a sharp threshold for the Duarte model. This resolves a question of Mountford from 1995, and is the first result of its type for a model with drift.
For natural numbers n,r∈N with n≥r, the Kneser graph K(n,r) is the graph on the family of r-element subsets of {1,…,n} in which two sets are adjacent if and only if they are disjoint. Delete the edges of K(n,r) with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? We answer this question affirmatively as long as r/n is bounded away from 1/2, even when the probability of retaining an edge of the Kneser graph is quite small. This gives us a random analogue of the Erdős-Ko-Rado theorem since an independent set in the Kneser graph is the same as a uniform intersecting family. To prove our main result, we give some new estimates for the number of disjoint pairs in a family in terms of its distance from an intersecting family, these might be of independent interest.
Given a hereditary graph property P, consider distributions of random orderings of vertices of graphs G∈P that are preserved under isomorphisms and under taking induced subgraphs. We show that for many properties P the only such random orderings are uniform, and give some examples of non-uniform orderings when they exist.
In 1990 Bender, Canfield and McKay gave an asymptotic formula for the number of connected graphs on [n] with m edges, whenever n and the nullity m−n+1 tend to infinity. Asymptotic formulae for the number of connected r-uniform hypergraphs on [n] with m edges and so nullity t=(r−1)m−n+1 were proved by Karoński and Łuczak for the case t=o(logn/loglogn), and Behrisch, Coja-Oghlan and Kang for t=Θ(n). Here we prove such a formula for any r≥3 fixed, and any t=t(n) satisfying t=o(n) and t→∞ as n→∞. This leaves open only the (much simpler) case t/n→∞, which we will consider in future work. ( arXiv:1511.04739 ) Our approach is probabilistic. Let Hn,pr denote the random r-uniform hypergraph on [n] in which each edge is present independently with probability p. Let L1 and M1 be the numbers of vertices and edges in the largest component of Hn,pr. We prove a local limit theorem giving an asymptotic formula for the probability that L1 and M1 take any given pair of values within the `typical' range, for any p=p(n) in the supercritical regime, i.e., when p=p(n)=(1+ε(n))(r−2)!n−r+1 where ε3n→∞ and ε→0; our enumerative result then follows easily. Taking as a starting point the recent joint central limit theorem for L1 and M1, we use smoothing techniques to show that `nearby' pairs of values arise with about the same probability, leading to the local limit theorem. Behrisch et al used similar ideas in a very different way, that does not seem to work in our setting. Independently, Sato and Wormald have recently proved the special case r=3, with an additional restriction on t. They use complementary, more enumerative methods, which seem to have a more limited scope, but to give additional information when they do work.
The k-limited packing number, Lk(G), of a graph G, introduced by Gallant, Gunther, Hartnell, and Rall, is the maximum cardinality of a set X of vertices of G such that every vertex of G has at most k elements of X in its closed neighbourhood. The main aim in this paper is to prove the best-possible result that if G is a cubic graph, then L2(G)≥∣V(G)∣/3, improving the previous lower bound given by Gallant, \emph{et al.} In addition, we construct an infinite family of graphs to show that lower bounds given by Gagarin and Zverovich are asymptotically best-possible, up to a constant factor, when k is fixed and Δ(G) tends to infinity. For Δ(G) tending to infinity and k tending to infinity sufficiently quickly, we give an asymptotically best-possible lower bound for Lk(G), improving previous bounds.
Given a countable dense subset S of a finite-dimensional normed space X, and 0<p<1, we form a random graph on S by joining, independently and with probability p, each pair of points at distance less than 1. We say that S is `Rado' if any two such random graphs are (almost surely) isomorphic. Bonato and Janssen showed that in l∞d almost all S are Rado. Our main aim in this paper is to show that l∞d is the unique normed space with this property: indeed, in every other space almost all sets S are non-Rado. We also determine which spaces admit some Rado set: this turns out to be the spaces that have an l∞ direct summand. These results answer questions of Bonato and Janssen. A key role is played by the determination of which finite-dimensional normed spaces have the property that every bijective step-isometry (meaning that the integer part of distances is preserved) is in fact an isometry. This result may be of independent interest.
We consider the following question. Suppose that d≥2 and n are fixed, and that θ1,θ2,…,θn are n specified angles. How many points do we need to place in Rd to realise all of these angles? A simple degrees of freedom argument shows that m points in R2 cannot realise more than 2m−4 general angles. We give a construction to show that this bound is sharp when m≥5. In d dimensions the degrees of freedom argument gives an upper bound of dm−(2d+1)−1 general angles. However, the above result does not generalise to this case; surprisingly, the bound of 2m−4 from two dimensions cannot be improved at all. Indeed, our main result is that there are sets of 2m−3 of angles that cannot be realised by m points in any dimension.
We study the distribution of the percolation time T of two-neighbour bootstrap percolation on [n]2 with initial set A∼Bin([n]2,p). We determine T with high probability up to a constant factor for all p above the critical probability for percolation, and to within a 1+o(1) factor for a large range of p.
In 1991 Aizenman and Grimmett claimed that any `essential enhancement' of site or bond percolation on a lattice lowers the critical probability, an important result with many implications, such as strict inequalities between critical probabilities on suitable pairs of lattices. Their proof has two parts, one probabilistic and one combinatorial. In this paper we point out that a key combinatorial lemma, for which they provide only a figure as proof, is false. We prove an alternative form of the lemma, and thus the enhancement result, in the special cases of site percolation on the square, triangular and cubic lattices, and for bond percolation on Zd, d≥2. The general case remains open, even for site percolation on Zd, d≥4.
Given two weighted k-uniform hypergraphs G, H of order n, how much (or little) can we make them overlap by placing them on the same vertex set? If we place them at random, how concentrated is the distribution of the intersection? The aim of this paper is to investigate these questions.
We prove that there exist natural generalizations of the classical bootstrap percolation model on Z2 that have non-trivial critical probabilities, and moreover we characterize all homogeneous, local, monotone models with this property. Van Enter (in the case d=r=2) and Schonmann (for all d≥r≥2) proved that r-neighbour bootstrap percolation models have trivial critical probabilities on Zd for every choice of the parameters d≥r≥2: that is, an initial set of density p almost surely percolates Zd for every p>0. These results effectively ended the study of bootstrap percolation on infinite lattices. Recently Bollobás, Smith and Uzzell introduced a broad class of percolation models called U-bootstrap percolation, which includes r-neighbour bootstrap percolation as a special case. They divided two-dimensional U-bootstrap percolation models into three classes -- subcritical, critical and supercritical -- and they proved that, like classical 2-neighbour bootstrap percolation, critical and supercritical U-bootstrap percolation models have trivial critical probabilities on Z2. They left open the question as to what happens in the case of subcritical families. In this paper we answer that question: we show that every subcritical U-bootstrap percolation model has a non-trivial critical probability on Z2. This is new except for a certain `degenerate' subclass of symmetric models that can be coupled from below with oriented site percolation. Our results re-open the study of critical probabilities in bootstrap percolation on infinite lattices, and they allow one to ask many questions of subcritical bootstrap percolation models that are typically asked of site or bond percolation.
Bootstrap percolation is a type of cellular automaton which has been used to model various physical phenomena, such as ferromagnetism. For each natural number r, the r-neighbour bootstrap process is an update rule for vertices of a graph in one of two states: `infected' or `healthy'. In consecutive rounds, each healthy vertex with at least r infected neighbours becomes itself infected. Percolation is said to occur if every vertex is eventually infected. Usually, the starting set of infected vertices is chosen at random, with all vertices initially infected independently with probability p. In that case, given a graph G and infection threshold r, a quantity of interest is the critical probability, pc(G,r), at which percolation becomes likely to occur. In this paper, we look at infinite trees and, answering a problem posed by Balogh, Peres and Pete, we show that for any b≥r and for any ε>0 there exists a tree T with branching number $\br(T) = b$ and critical probability pc(T,r)<ε. However, this is false if we limit ourselves to the well-studied family of Galton--Watson trees. We show that for every r≥2 there exists a constant cr>0 such that if T is a Galton--Watson tree with branching number $\br(T) = b \geq r$ then p_c(T,r) > \frac{c_r}{b} e^{-\frac{b}{r-1}}. We also show that this bound is sharp up to a factor of O(b) by giving an explicit family of Galton--Watson trees with critical probability bounded from above by Cre−r−1b for some constant Cr>0.
Let q be an odd prime power and let f(r) be the minimum size of the symmetric difference of r lines in the Desarguesian projective plane PG(2,q). We prove some results about the function f(r), in particular showing that there exists a constant C>0 such that f(r)=O(q) for Cq^{3/2}<r<q^2 - Cq^{3/2}.
We study the percolation time of the r-neighbour bootstrap percolation model on the discrete torus (Z/nZ)d. For t at most a polylog function of n and initial infection probabilities within certain ranges depending on t, we prove that the percolation time of a random subset of the torus is exactly equal to t with high probability as n tends to infinity. Our proof rests crucially on three new extremal theorems that together establish an almost complete understanding of the geometric behaviour of the r-neighbour bootstrap process in the dense setting. The special case d−r=0 of our result was proved recently by Bollobás, Holmgren, Smith and Uzzell.
A colouring of a hypergraph's vertices is polychromatic if every hyperedge contains at least one vertex of each colour; the polychromatic number is the maximum number of colours in such a colouring. Its dual, the cover-decomposition number, is the maximum number of disjoint hyperedge-covers. In geometric hypergraphs, there is extensive work on lower-bounding these numbers in terms of their trivial upper bounds (minimum hyperedge size and degree); our goal here is to broaden the study beyond geometric settings. We obtain algorithms yielding near-tight bounds for three families of hypergraphs: bounded hyperedge size, paths in trees, and bounded VC-dimension. This reveals that discrepancy theory and iterated linear program relaxation are useful for cover-decomposition. Finally, we discuss the generalization of cover-decomposition to sensor cover.
Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollobás in 1968, and is defined as follows. Given a graph H, and a set G⊂E(Kn) of initially `infected' edges, we infect, at each time step, a new edge e if there is a copy of H in Kn such that e is the only not-yet infected edge of H. We say that G percolates in the H-bootstrap process if eventually every edge of Kn is infected. The extremal questions for this model, when H is the complete graph Kr, were solved (independently) by Alon, Kalai and Frankl almost thirty years ago. In this paper we study the random questions, and determine the critical probability pc(n,Kr) for the Kr-process up to a poly-logarithmic factor. In the case r=4 we prove a stronger result, and determine the threshold for pc(n,K4).
We prove that, in the Gilbert model for a random geometric graph, almost every graph becomes Hamiltonian exactly when it first becomes 2-connected. This answers a question of Penrose. We also show that in the k-nearest neighbor model, there is a constant κ such that almost every κ-connected graph has a Hamilton cycle.
In $\HH$-bootstrap percolation, a set $A \subset V(\HH)$ of initially 'infected' vertices spreads by infecting vertices which are the only uninfected vertex in an edge of the hypergraph $\HH$. A particular case of this is the H-bootstrap process, in which $\HH$ encodes copies of H in a graph G. We find the minimum size of a set A that leads to complete infection when G and H are powers of complete graphs and $\HH$ encodes induced copies of H in G. The proof uses linear algebra, a technique that is new in bootstrap percolation, although standard in the study of weakly saturated graphs, which are equivalent to (edge) H-bootstrap percolation on a complete graph.
In r-neighbour bootstrap percolation on the vertex set of a graph G, vertices are initially infected independently with some probability p. At each time step, the infected set expands by infecting all uninfected vertices that have at least r infected neighbours. We study the distribution of the time t at which all vertices become infected. Given t = t(n) = o(log n/log log n), we prove a sharp threshold result for the probability that percolation occurs by time t in d-neighbour bootstrap percolation on the d-dimensional discrete torus T_n^d. Moreover, we show that for certain ranges of p = p(n), the time at which percolation occurs is concentrated either on a single value or on two consecutive values. We also prove corresponding results for the modified d-neighbour rule.
We specify a small set, consisting of O(d(loglogd)2) points, that intersects the basins under Newton's method of \emph{all} roots of \emph{all} (suitably normalized) complex polynomials of fixed degrees d, with arbitrarily high probability. This set is an efficient and universal \emph{probabilistic} set of starting points to find all roots of polynomials of degree d using Newton's method; the best known \emph{deterministic} set of starting points consists of ⌈1.1d(logd)2⌉ points.
The problem of designing policies for in-network function computation with minimum energy consumption subject to a latency constraint is considered. The scaling behavior of the energy consumption under the latency constraint is analyzed for random networks, where the nodes are uniformly placed in growing regions and the number of nodes goes to infinity. The special case of sum function computation and its delivery to a designated root node is considered first. A policy which achieves order-optimal average energy consumption in random networks subject to the given latency constraint is proposed. The scaling behavior of the optimal energy consumption depends on the path-loss exponent of wireless transmissions and the dimension of the Euclidean region where the nodes are placed. The policy is then extended to computation of a general class of functions which decompose according to maximal cliques of a proximity graph such as the k-nearest neighbor graph or the geometric random graph. The modified policy achieves order-optimal energy consumption albeit for a limited range of latency constraints.
Several emerging classes of applications that run over wireless networks have a need for mathematical models and tools to systematically characterize the reliability of the network. We propose two metrics for measuring the reliability of wireless mesh routing topologies, one for flooding and one for unicast routing. The Flooding Path Probability (FPP) metric measures the end-to-end packet delivery probability when each node broadcasts a packet after hearing from all its upstream neighbors. The Unicast Retransmission Flow (URF) metric measures the end-to-end packet delivery probability when a relay node retransmits a unicast packet on its outgoing links until it receives an acknowledgement or it tries all the links. Both metrics rely on specific packet forwarding models, rather than heuristics, to derive explicit expressions of the end-to-end packet delivery probability from individual link probabilities and the underlying connectivity graph. We also propose a distributed, greedy algorithm that uses the URF metric to construct a reliable routing topology. This algorithm constructs a Directed Acyclic Graph (DAG) from a weighted, undirected connectivity graph, where each link is weighted by its success probability. The algorithm uses a vector of decreasing reliability thresholds to coordinate when nodes can join the routing topology. Simulations demonstrate that, on average, this algorithm constructs a more reliable topology than the usual minimum hop DAG.
Isoperimetric inequalities have been studied since antiquity, and in recent decades they have been studied extensively on discrete objects, such as the hypercube. An important special case of this problem involves bounding the size of the shadow of a set system, and the basic question was solved by Kruskal (in 1963) and Katona (in 1968). In this paper we introduce the concept of the shadow \d\G of a collection \G of ordered graphs, and prove the following, simple-sounding statement: if n \in \N is sufficiently large, |V(G)| = n for each G \in \G, and |\G| < n, then |\d \G| \ge |\G|. As a consequence, we substantially strengthen a result of Balogh, Bollobás and Morris on hereditary properties of ordered graphs: we show that if ¶is such a property, and |¶_k| < k for some sufficiently large k \in \N, then |¶_n| is decreasing for k \le n < \infty.
In r-neighbour bootstrap percolation on a graph G, a (typically random) set A of initially 'infected' vertices spreads by infecting (at each time step) vertices with at least r already-infected neighbours. This process may be viewed as a monotone version of the Glauber dynamics of the Ising model, and has been extensively studied on the d-dimensional grid [n]d. The elements of the set A are usually chosen independently, with some density p, and the main question is to determine pc([n]d,r), the density at which percolation (infection of the entire vertex set) becomes likely. In this paper we prove, for every pair d≥r≥2, that there is a constant L(d,r) such that pc([n]d,r)=[(L(d,r)+o(1))/log(r−1)(n)]d−r+1 as n→∞, where logr denotes an r-times iterated logarithm. We thus prove the existence of a sharp threshold for percolation in any (fixed) number of dimensions. Moreover, we determine L(d,r) for every pair (d,r).
In this paper we determine the percolation threshold for an arbitrary sequence of dense graphs (Gn). Let λn be the largest eigenvalue of the adjacency matrix of Gn, and let Gn(pn) be the random subgraph of Gn obtained by keeping each edge independently with probability pn. We show that the appearance of a giant component in Gn(pn) has a sharp threshold at pn=1/λn. In fact, we prove much more: if (Gn) converges to an irreducible limit, then the density of the largest component of Gn(c/n) tends to the survival probability of a multi-type branching process defined in terms of this limit. Here the notions of convergence and limit are those of Borgs, Chayes, Lovász, Sós and Vesztergombi. In addition to using basic properties of convergence, we make heavy use of the methods of Bollobás, Janson and Riordan, who used multi-type branching processes to study the emergence of a giant component in a very broad family of sparse inhomogeneous random graphs.
We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form (x or y), chosen uniformly at random from among all 2-clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n --> alpha, the problem is known to have a phase transition at alpha_c = 1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite-size scaling about this transition, namely the scaling of the maximal window W(n,delta) = (alpha_-(n,delta),alpha_+(n,delta)) such that the probability of satisfiability is greater than 1-delta for alpha < alpha_- and is less than delta for alpha > alpha_+. We show that W(n,delta)=(1-Theta(n^{-1/3}),1+Theta(n^{-1/3})), where the constants implicit in Theta depend on delta. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+epsilon)n, where epsilon may depend on n as long as |epsilon| is sufficiently small and |epsilon|*n^(1/3) is sufficiently large, we show that the probability of satisfiability decays like exp(-Theta(n*epsilon^3)) above the window, and goes to one like 1-Theta(1/(n*|epsilon|^3)) below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2-SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2-SAT are identical to those of the random graph.
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.