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
Let F be an antichain of finite subsets of N. How quickly can the quantities ∣F∩2[n]∣ grow as n→∞? We show that for any sequence (fn)n≥n0 of positive integers satisfying ∑n=n0∞fn/2n≤1/4, fn0=1 and fn≤fn+1≤2fn, there exists an infinite antichain F of finite subsets of N such that ∣F∩2[n]∣≥fn for all n≥n0. It follows that for any ε>0 there exists an antichain F⊆2N such that liminfn→∞∣F∩2[n]∣⋅(nlog1+εn2n)−1>0. This resolves a problem of Sudakov, Tomon and Wagner in a strong form, and is essentially tight.
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.
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.
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.
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.
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.
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}.
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.
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.