Source author record

Bela Bollobas

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

ResearcherUnclaimed source record

math.CO math.PR math.NT

Catalog footprint

Research overview

26works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

A strengthening of Freiman's 3k-4 theorem

In its usual form, Freiman's 3k-4 theorem states that if A and B are subsets of the integers of size k with small sumset (of size close to 2k) then they are very close to arithmetic progressions. Our aim in this paper is to strengthen this by allowing only a bounded number of possible summands from one of the sets. We show that if A and B are subsets of the integers of size k such that for any four-element subset X of B the sumset A+X has size not much more than 2k then already this implies that A and B are very close to arithmetic progressions.

preprint2022arXiv

Large sumsets from medium-sized subsets

The classical Cauchy--Davenport inequality gives a lower bound for the size of the sum of two subsets of ${\mathbb Z}_p$ , where $p$ is a prime. Our main aim in this paper is to prove a considerable strengthening of this inequality, where we take only a small number of points from each of the two subsets when forming the sum. One of our results is that there is an absolute constant $c>0$ such that if $A$ and $B$ are subsets of ${\mathbb Z}_p$ with $|A|=|B|=n\le p/3$ then there are subsets $A'\subset A$ and $B'\subset B$ with $|A'|=|B'|\le c \sqrt{n}$ such that $|A'+B'|\ge 2n-1$ . In fact, we show that one may take any sizes one likes: as long as $c_1$ and $c_2$ satisfy $c_1c_2 \ge cn$ then we may choose $|A'|=c_1$ and $|B'|=c_2$ . We prove related results for general abelian groups.

preprint2022arXiv

Large sumsets from small subsets

In this paper we start to investigate a new body of questions in additive combinatorics. The fundamental Cauchy--Davenport theorem gives a lower bound on the size of a sumset A+B for subsets of the cyclic group Zp of order p (p prime), and this is just one example of a large family of results. Our aim in this paper is to investigate what happens if we restrict the number of elements of one set that we may use to form the sums. Here is the question we set out to answer: given two subsets, A and B, does B have a subset C of bounded size such that A+C is large, perhaps even comparable to the size of A+B? In particular, can we get close to the lower bound of the Cauchy--Davenport theorem? Our main results show that, rather surprisingly, in many circumstances it is possible to obtain not merely an asymptotic version of the usual sumset bound, but even the exact bound itself.

preprint2020arXiv

Counting independent sets in regular hypergraphs

Amongst $d$ -regular $r$ -uniform hypergraphs on $n$ vertices, which ones have the largest number of independent sets? While the analogous problem for graphs (originally raised by Granville) is now well-understood, it is not even clear what the correct general conjecture ought to be; our goal here is propose such a generalisation. Lending credence to our conjecture, we verify it within the class of `quasi-bipartite' hypergraphs (a generalisation of bipartite graphs that seems natural in this context) by adopting the entropic approach of Kahn.

preprint2016arXiv

On a problem of Erdos and Moser

A set $A$ of vertices in an $r$ -uniform hypergraph $\mathcal H$ is covered in $\mathcal H$ if there is some vertex $u\not\in A$ such that, for every $(r-1)$ -set $B\subset A$ , the set $\{u\}\cup B$ is in $\mathcal H$ . Erdos and Moser (1970) determined the minimum number of edges in a graph on $n$ vertices such that every $k$ -set is covered. We extend this result to $r$ -uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs.

preprint2015arXiv

An old approach to the giant component problem

In 1998, Molloy and Reed showed that, under suitable conditions, if a sequence of degree sequences converges to a probability distribution $D$ , then the size of the largest component in corresponding $n$ -vertex random graph is asymptotically $ρ(D)n$ , where $ρ(D)$ is a constant defined by the solution to certain equations that can be interpreted as the survival probability of a branching process associated to $D$ . There have been a number of papers strengthening this result in various ways; here we prove a strong form of the result (with exponential bounds on the probability of large deviations) under minimal conditions.

preprint2014arXiv

A coding problem for pairs of subsets

Let $X$ be an $n$ --element finite set, $0<k\leq n/2$ an integer. Suppose that $\{A_1,A_2\}$ and $\{B_1,B_2\}$ are pairs of disjoint $k$ -element subsets of $X$ (that is, $|A_1|=|A_2|=|B_1|=|B_2|=k$ , $A_1\cap A_2=\emptyset$ , $B_1\cap B_2=\emptyset$ ). Define the distance of these pairs by $d(\{A_1,A_2\} ,\{B_1,B_2\})=\min \{|A_1-B_1|+|A_2-B_2|, |A_1-B_2|+|A_2-B_1|\}$ . This is the minimum number of elements of $A_1\cup A_2$ one has to move to obtain the other pair $\{B_1,B_2\}$ . Let $C(n,k,d)$ be the maximum size of a family of pairs of disjoint subsets, such that the distance of any two pairs is at least $d$ . Here we establish a conjecture of Brightwell and Katona concerning an asymptotic formula for $C(n,k,d)$ for $k,d$ are fixed and $n\to \infty$ . Also, we find the exact value of $C(n,k,d)$ in an infinite number of cases, by using special difference sets of integers. Finally, the questions discussed above are put into a more general context and a number of coding theory type problems are proposed.

preprint2012arXiv

A simple branching process approach to the phase transition in $G_{n,p}$

It is well known that the branching process approach to the study of the random graph $G_{n,p}$ gives a very simple way of understanding the size of the giant component when it is fairly large (of order $Θ(n)$ ). Here we show that a variant of this approach works all the way down to the phase transition: we use branching process arguments to give a simple new derivation of the asymptotic size of the largest component whenever $(np-1)^3n\to\infty$ .

preprint2012arXiv

Covering numbers for graphs and hypergraphs

This paper has been withdrawn, as it has been merged into arXiv:1009.6144

preprint2011arXiv

Asymptotic normality of the size of the giant component in a random hypergraph

Recently, we adapted random walk arguments based on work of Nachmias and Peres, Martin-Löf, Karp and Aldous to give a simple proof of the asymptotic normality of the size of the giant component in the random graph $G(n,p)$ above the phase transition. Here we show that the same method applies to the analogous model of random $k$ -uniform hypergraphs, establishing asymptotic normality throughout the (sparse) supercritical regime. Previously, asymptotic normality was known only towards the two ends of this regime.

preprint2011arXiv

Asymptotic normality of the size of the giant component via a random walk

In this paper we give a simple new proof of a result of Pittel and Wormald concerning the asymptotic value and (suitably rescaled) limiting distribution of the number of vertices in the giant component of $G(n,p)$ above the scaling window of the phase transition. Nachmias and Peres used martingale arguments to study Karp's exploration process, obtaining a simple proof of a weak form of this result. We use slightly different martingale arguments to obtain a much sharper result with little extra work.

preprint2011arXiv

Daisies and Other Turan Problems

We make some conjectures about extremal densities of daisy-free families, where a `daisy' is a certain hypergraph. These questions turn out to be related to some Turan problems in the hypercube, but they are also natural in their own right.

preprint2011arXiv

Monotone graph limits and quasimonotone graphs

The recent theory of graph limits gives a powerful framework for understanding the properties of suitable (convergent) sequences $(G_n)$ of graphs in terms of a limiting object which may be represented by a symmetric function $W$ on $[0,1]$ , i.e., a kernel or graphon. In this context it is natural to wish to relate specific properties of the sequence to specific properties of the kernel. Here we show that the kernel is monotone (i.e., increasing in both variables) if and only if the sequence satisfies a `quasi-monotonicity' property defined by a certain functional tending to zero. As a tool we prove an inequality relating the cut and $L^1$ norms of kernels of the form $W_1-W_2$ with $W_1$ and $W_2$ monotone that may be of interest in its own right; no such inequality holds for general kernels.

preprint2010arXiv

Bootstrap percolation in high dimensions

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A \subset V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]^d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t -> infinity. The main question is to determine the critical probability p_c([n]^d,r) at which percolation becomes likely, and to give bounds on the size of the critical window. In this paper we study this problem when r = 2, for all functions n and d satisfying d \gg log n. The bootstrap process has been extensively studied on [n]^d when d is a fixed constant and 2 \leq r \leq d, and in these cases p_c([n]^d,r) has recently been determined up to a factor of 1 + o(1) as n -> infinity. At the other end of the scale, Balogh and Bollobas determined p_c([2]^d,2) up to a constant factor, and Balogh, Bollobas and Morris determined p_c([n]^d,d) asymptotically if d > (log log n)^{2+\eps}, and gave much sharper bounds for the hypercube. Here we prove the following result: let λbe the smallest positive root of the equation \sum_{k=0}^\infty (-1)^k λ^k / (2^{k^2-k} k!) = 0, so λ\approx 1.166. Then (16λ/ d^2) (1 + (log d / \sqrt{d})) 2^{-2\sqrt{d}} < p_c([2]^d,2) < (16λ/ d^2) (1 + (5(log d)^2 / \sqrt{d})) 2^{-2\sqrt{d}} if d is sufficiently large, and moreover we determine a sharp threshold for the critical probability p_c([n]^d,2) for every function n = n(d) with d \gg log n.

preprint2010arXiv

Large joints in graphs

We show that if G is a graph of sufficiently large order n containing as many r-cliques as the r-partite Turan graph of order n; then for some C>0 G has more than Cn^(r-1) (r+1)-cliques sharing a common edge unless G is isomorphic to the the r-partite Turan graph of order n. This structural result generalizes a previous result that has been useful in extremal graph theory.

preprint2010arXiv

On covering by translates of a set

In this paper we study the minimal number of translates of an arbitrary subset $S$ of a group $G$ needed to cover the group, and related notions of the efficiency of such coverings. We focus mainly on finite subsets in discrete groups, reviewing the classical results in this area, and generalizing them to a much broader context. For example, we show that while the worst-case efficiency when $S$ has $k$ elements is of order $1/\log k$ , for $k$ fixed and $n$ large, almost every $k$ -subset of any given $n$ -element group covers $G$ with close to optimal efficiency.

preprint2010arXiv

Percolation on self-dual polygon configurations

Recently, Scullard and Ziff noticed that a broad class of planar percolation models are self-dual under a simple condition that, in a parametrized version of such a model, reduces to a single equation. They state that the solution of the resulting equation gives the critical point. However, just as in the classical case of bond percolation on the square lattice, self-duality is simply the starting point: the mathematical difficulty is precisely showing that self-duality implies criticality. Here we do so for a generalization of the models considered by Scullard and Ziff. In these models, the states of the bonds need not be independent; furthermore, increasing events need not be positively correlated, so new techniques are needed in the analysis. The main new ingredients are a generalization of Harris's Lemma to products of partially ordered sets, and a new proof of a type of Russo-Seymour-Welsh Lemma with minimal symmetry assumptions.

preprint2010arXiv

Sparse graphs: metrics and random models

Recently, Bollobás, Janson and Riordan introduced a family of random graph models producing inhomogeneous graphs with $n$ vertices and $Θ(n)$ edges whose distribution is characterized by a kernel, i.e., a symmetric measurable function $\ka:[0,1]^2 \to [0,\infty)$. To understand these models, we should like to know when different kernels $\ka$ give rise to `similar' graphs, and, given a real-world network, how `similar' is it to a typical graph $G(n,\ka)$ derived from a given kernel $\ka$. The analogous questions for dense graphs, with $Θ(n^2)$ edges, are answered by recent results of Borgs, Chayes, Lovász, Sós, Szegedy and Vesztergombi, who showed that several natural metrics on graphs are equivalent, and moreover that any sequence of graphs converges in each metric to a graphon, i.e., a kernel taking values in $[0,1]$ . Possible generalizations of these results to graphs with $o(n^2)$ but $ω(n)$ edges are discussed in a companion paper [arXiv:0708.1919]; here we focus only on graphs with $Θ(n)$ edges, which turn out to be much harder to handle. Many new phenomena occur, and there are a host of plausible metrics to consider; many of these metrics suggest new random graph models, and vice versa.

preprint2010arXiv

The cut metric, random graphs, and branching processes

In this paper we study the component structure of random graphs with independence between the edges. Under mild assumptions, we determine whether there is a giant component, and find its asymptotic size when it exists. We assume that the sequence of matrices of edge probabilities converges to an appropriate limit object (a kernel), but only in a very weak sense, namely in the cut metric. Our results thus generalize previous results on the phase transition in the already very general inhomogeneous random graph model we introduced recently, as well as related results of Bollobás, Borgs, Chayes and Riordan, all of which involve considerably stronger assumptions. We also prove corresponding results for random hypergraphs; these generalize our results on the phase transition in inhomogeneous random graphs with clustering.

preprint2010arXiv

The number of graphs with large forbidden subgraphs

In this note, extending some results of Erdos, Frankl, Rodl, Alexeev, Bollobas and Thomason we determine asymptotically the number of graphs which do not contain certain large subgraphs. In particular, if H_1,...,H_n,... are graphs with chromatic numbers r_1,...,r_n,... and order o(log n), we dermine asymptotically the number of graphs of order n not containing H_n as a subgraph. We also give similar results for induced subgraphs.

preprint2010arXiv

Walks and Paths in Trees

Recently Csikvári \cite{csik} proved a conjecture of Nikiforov concerning the number of closed walks on trees. Our aim is to extend his theorem to all walks. In addition, we give a simpler proof of Csikvári's result and answer one of his questions in the negative. Finally we consider an analogous question for paths rather than walks.

preprint2009arXiv

Erratum: Percolation on random Johnson-Mehl tessellations and related models

We correct a simple error in Percolation on random Johnson-Mehl tessellations and related models, Probability Theory and Related Fields 140 (2008), 417-468. (See also arXiv:math/0610716)

preprint2009arXiv

Sparse random graphs with clustering

In 2007 we introduced a general model of sparse random graphs with independence between the edges. The aim of this paper is to present an extension of this model in which the edges are far from independent, and to prove several results about this extension. The basic idea is to construct the random graph by adding not only edges but also other small graphs. In other words, we first construct an inhomogeneous random hypergraph with independent hyperedges, and then replace each hyperedge by a (perhaps complete) graph. Although flexible enough to produce graphs with significant dependence between edges, this model is nonetheless mathematically tractable. Indeed, we find the critical point where a giant component emerges in full generality, in terms of the norm of a certain integral operator, and relate the size of the giant component to the survival probability of a certain (non-Poisson) multi-type branching process. While our main focus is the phase transition, we also study the degree distribution and the numbers of small subgraphs. We illustrate the model with a simple special case that produces graphs with power-law degree sequences with a wide range of degree exponents and clustering coefficients.

preprint2008arXiv

Clique percolation

Derenyi, Palla and Vicsek introduced the following dependent percolation model, in the context of finding communities in networks. Starting with a random graph $G$ generated by some rule, form an auxiliary graph $G'$ whose vertices are the $k$ -cliques of $G$ , in which two vertices are joined if the corresponding cliques share $k-1$ vertices. They considered in particular the case where $G=G(n,p)$ , and found heuristically the threshold for a giant component to appear in $G'$ . Here we give a rigorous proof of this result, as well as many extensions. The model turns out to be very interesting due to the essential global dependence present in $G'$ .

preprint2007arXiv

Percolation on random Johnson-Mehl tessellations and related models

We make use of the recent proof that the critical probability for percolation on random Voronoi tessellations is 1/2 to prove the corresponding result for random Johnson-Mehl tessellations, as well as for two-dimensional slices of higher dimensional Voronoi tessellations. Surprisingly, the proof is a little simpler for these more complicated models.

preprint2006arXiv

The phase transition in inhomogeneous random graphs

We introduce a very general model of an inhomogenous random graph with independence between the edges, which scales so that the number of edges is linear in the number of vertices. This scaling corresponds to the p=c/n scaling for G(n,p) used to study the phase transition; also, it seems to be a property of many large real-world graphs. Our model includes as special cases many models previously studied. We show that under one very weak assumption (that the expected number of edges is `what it should be'), many properties of the model can be determined, in particular the critical point of the phase transition, and the size of the giant component above the transition. We do this by relating our random graphs to branching processes, which are much easier to analyze. We also consider other properties of the model, showing, for example, that when there is a giant component, it is `stable': for a typical random graph, no matter how we add or delete o(n) edges, the size of the giant component does not change by more than o(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.

Bela Bollobas

Research overview

Is this your work?

26 publications

A strengthening of Freiman's 3k-4 theorem

Large sumsets from medium-sized subsets

Large sumsets from small subsets

Counting independent sets in regular hypergraphs

On a problem of Erdos and Moser

An old approach to the giant component problem

A coding problem for pairs of subsets

A simple branching process approach to the phase transition in $G_{n,p}$

Covering numbers for graphs and hypergraphs

Asymptotic normality of the size of the giant component in a random hypergraph

Asymptotic normality of the size of the giant component via a random walk

Daisies and Other Turan Problems

Monotone graph limits and quasimonotone graphs

Bootstrap percolation in high dimensions

Large joints in graphs

On covering by translates of a set

Percolation on self-dual polygon configurations

Sparse graphs: metrics and random models

The cut metric, random graphs, and branching processes

The number of graphs with large forbidden subgraphs

Walks and Paths in Trees

Erratum: Percolation on random Johnson-Mehl tessellations and related models

Sparse random graphs with clustering

Clique percolation

Percolation on random Johnson-Mehl tessellations and related models

The phase transition in inhomogeneous random graphs

See the researcher in context

Building this map preview

Bela Bollobas

Research overview

Is this your work?

26 publications

A strengthening of Freiman's 3k-4 theorem

Large sumsets from medium-sized subsets

Large sumsets from small subsets

Counting independent sets in regular hypergraphs

On a problem of Erdos and Moser

An old approach to the giant component problem

A coding problem for pairs of subsets

A simple branching process approach to the phase transition in Gn,pG_{n,p}Gn,p​

Covering numbers for graphs and hypergraphs

Asymptotic normality of the size of the giant component in a random hypergraph

Asymptotic normality of the size of the giant component via a random walk

Daisies and Other Turan Problems

Monotone graph limits and quasimonotone graphs

Bootstrap percolation in high dimensions

Large joints in graphs

On covering by translates of a set

Percolation on self-dual polygon configurations

Sparse graphs: metrics and random models

The cut metric, random graphs, and branching processes

The number of graphs with large forbidden subgraphs

Walks and Paths in Trees

Erratum: Percolation on random Johnson-Mehl tessellations and related models

Sparse random graphs with clustering

Clique percolation

Percolation on random Johnson-Mehl tessellations and related models

The phase transition in inhomogeneous random graphs

See the researcher in context

Building this map preview

A simple branching process approach to the phase transition in $G_{n,p}$