Consider the minimal weights of paths between two points in a complete graph Kn with random weights on the edges, the weights being, for instance, uniformly distributed. It is shown that, asymptotically, this is log n/n for two given points, that the maximum if one point is fixed and the other varies is 2 log n/n, and that the maximum over all pairs of points is 3 log n/n.

Some further related results are given as well, including results on asymptotic distributions and moments, and on the number of edges in the minimal weight paths.

For a graph H and an integer n, the Turán number is the maximum possible number of edges in a simple graph on n vertices that contains no copy of H. H is r-degenerate if every one of its subgraphs contains a vertex of degree at most r. We prove that, for any fixed bipartite graph H in which all degrees in one colour class are at most r, . This is tight for all values of r and can also be derived from an earlier result of Füredi. We also show that there is an absolute positive constant c such that, for every fixed bipartite r-degenerate graph H, This is motivated by a conjecture of Erdős that asserts that, for every such H,

For two graphs G and H, the Ramsey number is the minimum number n such that, in any colouring of the edges of the complete graph on n vertices by red and blue, there is either a red copy of G or a blue copy of H. Erdős conjectured that there is an absolute constant c such that, for any graph G with m edges, . Here we prove this conjecture for bipartite graphs G, and prove that for general graphs G with m edges, for some absolute positive constant c.

These results and some related ones are derived from a simple and yet surprisingly powerful lemma, proved, using probabilistic techniques, at the beginning of the paper. This lemma is a refined version of earlier results proved and applied by various researchers including Rödl, Kostochka, Gowers and Sudakov.

We prove the following conjecture of J. van den Berg and H. Kesten. For any events [Ascr ] and [Bscr ] in a product probability space, Prob([Ascr ]□[Bscr ]) [les ] Prob([Ascr ])Prob([Bscr ]), where [Ascr ]□[Bscr ] is the event that [Ascr ] and [Bscr ] occur ‘disjointly’.

One of our results: let X be a finite set on the plane, 0 < ε < 1, then there exists a set F (a weak ε-net) of size at most 7/ε2 such that every convex set containing at least ε|X| elements of X intersects F. Note that the size of F is independent of the size of X.

The asymptotic distribution of the number of Hamilton cycles in a random regular graph is determined. The limit distribution is of an unusual type; it is the distribution of a variable whose logarithm can be written as an infinite linear combination of independent Poisson variables, and thus the logarithm has an infinitely divisible distribution with a certain discrete Lévy measure. Similar results are found for some related problems. These limit results imply that some different models of random regular graphs are contiguous, which means that they are qualitatively asymptotically equivalent. For example, if r > 3, then the usual (uniformly distributed) random r-regular graph is contiguous to the one constructed by taking the union of r perfect matchings on the same vertex set (assumed to be of even cardinality), conditioned on there being no multiple edges. Some consequences of contiguity for asymptotic distributions are discussed.

A graph G is m-choosable with impropriety d, or simply (m, d)*-choosable, if for every list assignment L, where [mid ]L(v)[mid ][ges ]m for every v∈V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We show that every planar graph is (3, 2)*-choosable and every outerplanar graph is (2, 2)*-choosable. We also propose some interesting problems about this colouring.

This paper has two parts. In the first part we consider a simple Markov chain for d-regular graphs on n vertices, where d = d(n) may grow with n. We show that the mixing time of this Markov chain is bounded above by a polynomial in n and d. In the second part of the paper, a related Markov chain for d-regular graphs on a varying number of vertices is introduced, for even constant d. This is a model for a certain peer-to-peer network. We prove that the related chain has mixing time which is bounded above by a polynomial in N, the expected number of vertices, provided certain assumptions are met about the rate of arrival and departure of vertices.

In a one-parameter model for evolution of random trees, which also includes the Barabási–Albert random graph [1], the law of large numbers and the central limit theorem are proved for the maximal degree. In the proofs martingale methods are applied.

Recent inapproximability results of Sly (2010), together with an approximation algorithm presented by Weitz (2006), establish a beautiful picture of the computational complexity of approximating the partition function of the hard-core model. Let λc($\mathbb{T}_{\Delta}$) denote the critical activity for the hard-model on the infinite Δ-regular tree. Weitz presented an FPTAS for the partition function when λ < λc($\mathbb{T}_{\Delta}$) for graphs with constant maximum degree Δ. In contrast, Sly showed that for all Δ ⩾ 3, there exists εΔ > 0 such that (unless RP = NP) there is no FPRAS for approximating the partition function on graphs of maximum degree Δ for activities λ satisfying λc($\mathbb{T}_{\Delta}$) < λ < λc($\mathbb{T}_{\Delta}$) + εΔ.

We prove that a similar phenomenon holds for the antiferromagnetic Ising model. Sinclair, Srivastava and Thurley (2014) extended Weitz's approach to the antiferromagnetic Ising model, yielding an FPTAS for the partition function for all graphs of constant maximum degree Δ when the parameters of the model lie in the uniqueness region of the infinite Δ-regular tree. We prove the complementary result for the antiferromagnetic Ising model without external field, namely, that unless RP = NP, for all Δ ⩾ 3, there is no FPRAS for approximating the partition function on graphs of maximum degree Δ when the inverse temperature lies in the non-uniqueness region of the infinite tree $\mathbb{T}_{\Delta}$. Our proof works by relating certain second moment calculations for random Δ-regular bipartite graphs to the tree recursions used to establish the critical points on the infinite tree.

I show that the zeros of the chromatic polynomials $P_G(q)$ for the generalized theta graphs $\Theta^{(s,p)}$ are, taken together, dense in the whole complex plane with the possible exception of the disc $|q-1| < 1$. The same holds for their dichromatic polynomials (alias Tutte polynomials, alias Potts-model partition functions) $Z_G(q,v)$ outside the disc $|q+v| < |v|$. An immediate corollary is that the chromatic roots of not-necessarily-planar graphs are dense in the whole complex plane. The main technical tool in the proof of these results is the Beraha–Kahane–Weiss theorem on the limit sets of zeros for certain sequences of analytic functions, for which I give a new and simpler proof.

We apply an idea of Székely to prove a general upper bound on the number of incidences between a set of m points and a set of n ‘well-behaved’ curves in the plane.

In this paper we study the use of spectral techniques for graph partitioning. Let G = (V, E) be a graph whose vertex set has a ‘latent’ partition V1,. . ., Vk. Moreover, consider a ‘density matrix’ Ɛ = (Ɛvw)v, sw∈V such that, for v ∈ Vi and w ∈ Vj, the entry Ɛvw is the fraction of all possible Vi−Vj-edges that are actually present in G. We show that on input (G, k) the partition V1,. . ., Vk can (very nearly) be recovered in polynomial time via spectral methods, provided that the following holds: Ɛ approximates the adjacency matrix of G in the operator norm, for vertices v ∈ Vi, w ∈ Vj ≠ Vi the corresponding column vectors Ɛv, Ɛw are separated, and G is sufficiently ‘regular’ with respect to the matrix Ɛ. This result in particular applies to sparse graphs with bounded average degree as n = #V → ∞, and it has various consequences on partitioning random graphs.

It is proved that any plane graph may be represented by a triangle contact system, that is a collection of triangular disks which are disjoint except at contact points, each contact point being a node of exactly one triangle. Representations using contacts of T-or Y-shaped objects follow. Moreover, there is a one-to-one mapping between all the triangular contact representations of a maximal plane graph and all its partitions into three Schnyder trees.

Let ex(n, K3,3) denote the maximum number of edges of a K3,3-free graph on n vertices. Improving earlier results of Kővári, T. Sós and Turán on Zarankiewicz' problem, we obtain that Brown's example for a maximal K3,3-free graph is asymptotically optimal. Hence .

This paper introduces a split-and-merge transformation of interval partitions which combines some features of one model studied by Gnedin and Kerov [12, 11] and another studied by Tsilevich [30, 31] and Mayer-Wolf, Zeitouni and Zerner [21]. The invariance under this split-and-merge transformation of the interval partition generated by a suitable Poisson process yields a simple proof of the recent result of [21] that a Poisson–Dirichlet distribution is invariant for a closely related fragmentation–coagulation process. Uniqueness and convergence to the invariant measure are established for the split-and-merge transformation of interval partitions, but the corresponding problems for the fragmentation–coagulation process remain open.

More than forty years ago, Erdős conjectured that for any , every k-uniform hypergraph on n vertices without t disjoint edges has at most max edges. Although this appears to be a basic instance of the hypergraph Turán problem (with a t-edge matching as the excluded hypergraph), progress on this question has remained elusive. In this paper, we verify this conjecture for all . This improves upon the best previously known range , which dates back to the 1970s.

Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability $p$, independently of each other, and a deterministic spreading rule with a fixed parameter $k$: if a vacant site has at least $k$ occupied neighbours at a certain time step, then it becomes occupied in the next step. This process is well studied on ${\mathbb Z}^d$; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of $p$ for which the process achieves complete occupation with positive probability. On trees we find the following discontinuity: if the branching number of a tree is strictly smaller than $k$, then the critical probability is 1, while it is $1-1/k$ on the $k$-ary tree. A related result is that in any rooted tree $T$ there is a way of erasing $k$ children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree $T'$ has branching number $\mbox{\rm br}(T')\leq \max\{\mbox{\rm br}(T)-k,\,0\}$. We also prove that on any $2k$-regular non-amenable graph, the critical probability for the $k$-rule is strictly positive.

A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemerédi theorem: for every positive integer r, every graph with maximum degree at most r has an equitable colouring with r+1 colours. The proof yields a polynomial time algorithm for such colourings.

Let G = (G, +) be an additive group. The sumset theory of Plünnecke and Ruzsa gives several relations between the size of sumsets A + B of finite sets A, B, and related objects such as iterated sumsets kA and difference sets A − B, while the inverse sumset theory of Freiman, Ruzsa, and others characterizes those finite sets A for which A + A is small. In this paper we establish analogous results in which the finite set A ⊂ G is replaced by a discrete random variable X taking values in G, and the cardinality |A| is replaced by the Shannon entropy H(X). In particular, we classify those random variables X which have small doubling in the sense that H(X1 + X2) = H(X) + O(1) when X1, X2 are independent copies of X, by showing that they factorize as X = U + Z, where U is uniformly distributed on a coset progression of bounded rank, and H(Z) = O(1).

When G is torsion-free, we also establish the sharp lower bound , where o(1) goes to zero as H(X) → ∞.

We show that the number of independent sets in an N-vertex, d-regular graph is at most (2d+1 − 1)N/2d, where the bound is sharp for a disjoint union of complete d-regular bipartite graphs. This settles a conjecture of Alon in 1991 and Kahn in 2001. Kahn proved the bound when the graph is assumed to be bipartite. We give a short proof that reduces the general case to the bipartite case. Our method also works for a weighted generalization, i.e., an upper bound for the independence polynomial of a regular graph.