In this paper we prove that given a finite collection of finite graphs, and the subsets of vertices of a random graph G that induce those graphs, it is almost always possible to uniquely reconstruct a class of graphs equivalent to G.

The perceptron learning algorithm quite naturally yields an algorithm for finding a linearly separable boolean function consistent with a sample of such a function. Using the idea of a specifying sample, we give a simple proof that, in general, this algorithm is not efficient.

A causal set is a countably infinite poset in which every element is above finitely many others; causal sets are exactly the posets that have a linear extension with the order-type of the natural numbers; we call such a linear extension a natural extension. We study probability measures on the set of natural extensions of a causal set, especially those measures having the property of order-invariance: if we condition on the set of the bottom k elements of the natural extension, each feasible ordering among these k elements is equally likely. We give sufficient conditions for the existence and uniqueness of an order-invariant measure on the set of natural extensions of a causal set.

Let C63 be the 3-uniform hypergraph on {1, . . ., 6} with edges 123,345,561, which can be seen as the analogue of the triangle in 3-uniform hypergraphs. For sufficiently large n divisible by 6, we show that every n-vertex 3-uniform hypergraph H with minimum codegree at least n/3 contains a C63-factor, that is, a spanning subhypergraph consisting of vertex-disjoint copies of C63. The minimum codegree condition is best possible. This improves the asymptotic result obtained by Mycroft and answers a question of Rödl and Ruciński exactly.

We consider a variant of the Cops and Robbers game where the robber can move t edges at a time, and show that in this variant, the cop number of a d-regular graph with girth larger than 2t+2 is Ω(dt). By the known upper bounds on the order of cages, this implies that the cop number of a connected n-vertex graph can be as large as Ω(n2/3) if t ≥ 2, and Ω(n4/5) if t ≥ 4. This improves the Ω() lower bound of Frieze, Krivelevich and Loh (Variations on cops and robbers, J. Graph Theory, to appear) when 2 ≤ t ≤ 6. We also conjecture a general upper bound O(nt/t+1) for the cop number in this variant, generalizing Meyniel's conjecture.

Extending an old conjecture of Tutte, Jaeger conjectured in 1988 that for any fixed integer p ≥ 1, the edges of any 4p-edge connected graph can be oriented so that the difference between the outdegree and the indegree of each vertex is divisible by 2p+1. It is known that it suffices to prove this conjecture for (4p+1)-regular, 4p-edge connected graphs. Here we show that there exists a finite p0 such that for every p > p0 the assertion of the conjecture holds for all (4p+1)-regular graphs that satisfy some mild quasi-random properties, namely, the absolute value of each of their non-trivial eigenvalues is at most c1p2/3 and the neighbourhood of each vertex contains at most c2p3/2 edges, where c1, c2 > 0 are two absolute constants. In particular, this implies that for p > p0 the assertion of the conjecture holds asymptotically almost surely for random (4p+1)-regular graphs.

Let ℱ be a family of graphs and let d be large enough. For every d-regular graph G, we study the existence of a spanning ℱ-free subgraph of G with large minimum degree. This problem is well understood if ℱ does not contain bipartite graphs. Here we provide asymptotically tight results for many families of bipartite graphs such as cycles or complete bipartite graphs. To prove these results, we study a locally injective analogue of the question.

In this paper we prove lower and upper bounds for the extinction time of the contact process on random geometric graphs with connection radius tending to infinity. We obtain that for any infection rate λ > 0, the contact process on these graphs survives a time super-exponential in the number of vertices.

As usual, let us write $G_{n,p}$ for a random graph with vertex set $[n]=\{1, 2, \dots , n\}$, in which the edges are chosen independently, with probability $p$. Similarly, $G_{n,m}$ is a random graph on $[n]$ with $m$ edges. For $p=m/({{n}\atop{2}})$, in many respects, the random graphs $G_{n,m}$ and $G_{n,p}$ are practically indistinguishable. (See [4] for an introduction to random graphs.) When in the late 1950s and early 1960s Erdős and Rényi founded the theory of random graphs, one of the most important problems they left open was the determination of the chromatic number of a random graph $G_{n,m}$. The original question concerned the case $m=O(n)$, but when in the 1970s Erdős popularized the problem, he was asking for good estimates on the chromatic number of $G_{n,m}$ for $m \sim n^2/4$ (equivalently, the chromatic number of $G_{{n,1/2}}$).

We prove that the number of multigraphs with vertex set {1, . . ., n} such that every four vertices span at most nine edges is an2+o(n2) where a is transcendental (assuming Schanuel's conjecture from number theory). This is an easy consequence of the solution to a related problem about maximizing the product of the edge multiplicities in certain multigraphs, and appears to be the first explicit (somewhat natural) question in extremal graph theory whose solution is transcendental. These results may shed light on a question of Razborov, who asked whether there are conjectures or theorems in extremal combinatorics which cannot be proved by a certain class of finite methods that include Cauchy–Schwarz arguments.

Our proof involves a novel application of Zykov symmetrization applied to multigraphs, a rather technical progressive induction, and a straightforward use of hypergraph containers.

For any positive integer k and ε > 0, there exist nk,ε, ck, e > 0 with the following property. Given any system of n > nk,ε points in the plane with minimal distance at least 1 and any t1, t2…, tk ≥ 1, the number of those pairs of points whose distance is between ti and for some 1 ≤ i ≤ k, is at most (n2/2) (1 − 1/(k+1)+ε). This bound is asymptotically tight.

Model 1. Consider the complete graph Kn, with vertex set [n] = {1, 2,…, n}, in which each edge e is assigned a length Xe. Colour the k shortest edges incident with each vertex green and the remaining edges blue. The graph made up of the green edges only, will be referred to as the k-th nearest neighbour graph. This graph has been studied in a variety of contexts both computational and statistical.

Multiway trees, also known as m–ary search trees, are data structures generalising binary search trees. A common probability model for analysing the behaviour of these structures is the random permutation model. The probability mass function Q on the set of m–ary search trees under the random permutation model is the distribution induced by sequentially inserting the records of a uniformly random permutation into an initially empty m–ary search tree. We study some basic properties of the functional Q, which serves as a measure of the ‘shape’ of the tree. In particular, we determine exact and asymptotic expressions for the maximum and minimum values of Q and identify and count the trees achieving those values.

A harmonious colouring of a simple graph G is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colours in such a colouring.

For any positive integer m, let Q(m) be the least positive integer k such that ≥ m. We show that for almost all unlabelled, unrooted trees T, h(T) = Q(m), where m is the number of edges of T.

Paul Erdős has conjectured that Menger's theorem extends to infinite graphs in the following way: whenever A, B are two sets of vertices in an infinite graph, there exist a set of disjoint A−B paths and an A−B separator in this graph such that the separator consists of a choice of precisely one vertex from each of the paths. We prove this conjecture for graphs that contain a set of disjoint paths to B from all but countably many vertices of A. In particular, the conjecture is true when A is countable.

A solid diagram of volume n is a packing of n unit cubes into a corner so that the heights of vertical stacks of cubes do not increase in either of two horizontal directions away from the corner. An asymptotic distribution of the dimensions – heights, depths, and widths – of the diagram chosen uniformly at random among all such diagrams is studied. For each k, the planar base of k tallest stacks is shown to be Plancherel distributed in the limit $n\to\infty$.

We study the asymptotic behaviour of the relative entropy (to stationarity) for a commonly used model for riffle shuffling a deck of n cards m times. Our results establish and were motivated by a prediction in a recent numerical study of Trefethen and Trefethen. Loosely speaking, the relative entropy decays approximately linearly (in m) for m < log2n, and approximately exponentially for m > log2n. The deck becomes random in this information-theoretic sense after m = 3/2 log2n shuffles.

A subgraph of a hypergraph H is even if all its degrees are positive even integers, and b-bounded if it has maximum degree at most b. Let fb(n) denote the maximum number of edges in a linearn-vertex 3-uniform hypergraph which does not contain a b-bounded even subgraph. In this paper, we show that if b ≥ 12, then for some absolute constant B, thus establishing fb(n) up to polylogarithmic factors. This leaves open the interesting case b = 2, which is the case of 2-regular subgraphs. We are able to show for some constants c, C > 0 that We conjecture that f2(n) = n1 + o(1) as n → ∞.

A k-uniform hypergraph H = (V, E) is called ℓ-orientable if there is an assignment of each edge e ∈ E to one of its vertices v ∈ e such that no vertex is assigned more than ℓ edges. Let Hn,m,k be a hypergraph, drawn uniformly at random from the set of all k-uniform hypergraphs with n vertices and m edges. In this paper we establish the threshold for the ℓ-orientability of Hn,m,k for all k ⩾ 3 and ℓ ⩾ 2, that is, we determine a critical quantity c*k,ℓ such that with probability 1 − o(1) the graph Hn,cn,k has an ℓ-orientation if c < c*k,ℓ , but fails to do so if c > c*k,ℓ .

Our result has various applications, including sharp load thresholds for cuckoo hashing, load balancing with guaranteed maximum load, and massive parallel access to hard disk arrays.

A perfect matching M in an edge-coloured complete bipartite graph Kn,n is rainbow if no pair of edges in M have the same colour. We obtain asymptotic enumeration results for the number of rainbow perfect matchings in terms of the maximum number of occurrences of each colour. We also consider two natural models of random edge-colourings of Kn,n and show that if the number of colours is at least n, then there is with high probability a rainbow perfect matching. This in particular shows that almost every square matrix of order n in which every entry appears n times has a Latin transversal.