In this paper we consider j-tuple-connected components in random k-uniform hypergraphs (the j-tuple-connectedness relation can be defined by letting two j-sets be connected if they lie in a common edge and considering the transitive closure; the case j = 1 corresponds to the common notion of vertex-connectedness). We show that the existence of a j-tuple-connected component containing Θ(nj) j-sets undergoes a phase transition and show that the threshold occurs at edge probability

$$\frac{(k-j)!}{\binom{k}{j}-1}n^{j-k}.$$

Our main original contribution is a bounded degree lemma, which controls the structure of the component grown in the search process.

Cops and robbers is a turn-based pursuit game played on a graph G. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number c(G) denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points x1, . . ., xn ∈ ℝ2, and r ∈ ℝ+, the vertex set of the geometric graph G(x1, . . ., xn; r) is the graph on these n points, with xi, xj adjacent when ∥xi − xj∥ ≤ r. We prove that c(G) ≤ 9 for any connected geometric graph G in ℝ2 and we give an example of a connected geometric graph with c(G) = 3. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let (n,r) denote the probability space of geometric graphs with n vertices chosen uniformly and independently from [0,1]2. For G ∈ (n,r), we show that with high probability (w.h.p.), if r ≥ K1 (log n/n)1/4 then c(G) ≤ 2, and if r ≥ K2(log n/n)1/5 then c(G) = 1, where K1, K2 > 0 are absolute constants. Finally, we provide a lower bound near the connectivity regime of (n,r): if r ≤ K3 log n/ then c(G) > 1 w.h.p., where K3 > 0 is an absolute constant.

In this paper we consider the following problem, given a graph H, what is the structure of a typical, i.e. random, H-free graph? We completely solve this problem for all graphs H containing a critical vertex. While this result subsumes a sequence of known results, its short proof is self contained.

Every node of an undirected connected graph is coloured white or black. Adjacent nodes can be compared and the outcome of each comparison is either 0 (same colour) or 1 (different colours). The aim is to discover a node of the majority colour, or to conclude that there is the same number of black and white nodes. We consider randomized algorithms for this task and establish upper and lower bounds on their expected running time. Our main contribution are lower bounds showing that some simple and natural algorithms for this problem cannot be improved in general.

We prove that if the edge probability p(n) satisfies n−1/4+ε [les ] p(n) [les ] 3/4, where 0 < ε < 1/4 is a constant, then the choice number and the chromatic number of the random graph G(n, p) are almost surely asymptotically equal.

We prove a joint local limit law for the distribution of the r largest components of decomposable logarithmic combinatorial structures, including assemblies, multisets and selections. Our method is entirely probabilistic, and requires only weak conditions that may readily be verified in practice.

We show that for 0<α<1 and θ>−α, the Poisson–Dirichlet distribution with parameter (α, θ) is the unique reversible distribution of a rather natural fragmentation–coalescence process. This completes earlier results in the literature for certain split-and-merge transformations and the parameter α = 0.

We give a very general sufficient condition for a one-parameter family of curves not to have n members with ‘too many’ (i.e., a near-quadratic number of) triple points of intersections. As a special case, a combinatorial distinction between straight lines and unit circles will be shown. (Actually, this is more than just a simple application; originally this motivated our results.)

We generalize and unify results on parametrized and coloured Tutte polynomials of graphs and matroids due to Zaslavsky, and Bollobás and Riordan. We give a generalized Zaslavsky–Bollobás–Riordan theorem that characterizes parametrized contraction–deletion functions on minor-closed classes of matroids, as well as the modifications necessary to apply the discussion to classes of graphs. In general, these parametrized Tutte polynomials do not satisfy analogues of all the familiar properties of the classical Tutte polynomial. We give conditions under which they do satisfy corank-nullity formulas, and also conditions under which they reflect the structure of series-parallel connections.

In a set of even cardinality n, each member ranks all the others in order of preference. A stable matching is a partition of the set into n/2 pairs, with the property that no two unpaired members both prefer each other to their partners under matching. It is known that for some problem instances no stable matching exists. In 1985, Irving found an O(n2) two-phase algorithm that would determine, for any instance, whether a stable matching exists, and if so, would find such a matching. Recently, Tan proved that Irving's algorithm, with a modified second phase, always finds a stable cyclic partition of the members set, which is a stable matching when each cycle has length two. In this paper we study a likely behavior of the algorithm under the assumption that an instance of the ranking system is chosen uniformly at random. We prove that the likely number of basic steps, i.e. the individual proposals in the first phase and the rotation eliminations, involving subsets of members in the second phase, is O(n log n), and that the likely size of a rotation is O((n log n)1/2). We establish a ‘hyperbola law’ analogous to our past result on stable marriages. It states that at every step of the second phase, the product of the rank of proposers and the rank of proposal holders is asymptotic, in probability, to n3. We show that every stable cyclic partition is likely to be almost a stable matching, in the sense that at most O((n log n)1/2) members can be involved in the cycles of length three or more.

A graph G is threshold if there exists a ‘weight’ function w: V(G) → R such that the total weight of any stable set of G is less than the total weight of any non-stable set of G. Let n denote the set of threshold graphs with n vertices. A graph is called n-universal if it contains every threshold graph with n vertices as an induced subgraph. n-universal threshold graphs are of special interest, since they are precisely those n-universal graphs that do not contain any non-threshold induced subgraph.

In this paper we shall study minimumn-universal (threshold) graphs, i.e.n-universal (threshold) graphs having the minimum number of vertices.

It is shown that for any n ≥ 3 there exist minimum n-universal graphs, which are themselves threshold, and others which are not.

Two extremal minimum n-universal graphs having respectively the minimum and the maximum number of edges are described, it is proved that they are unique, and that they are threshold graphs.

The set of all minimum n-universal threshold graphs is then described constructively; it is shown that it forms a lattice isomorphic to the n − 1 dimensional Boolean cube, and that the minimum and the maximum elements of this lattice are the two extremal graphs introduced above.

The proofs provide a (polynomial) recursive procedure that determines for any threshold graph G with n vertices and for any minimum n-universal threshold graph T, an induced subgraph G' of T isomorphic to G.

We consider three aspects of homomorphisms of graphs and hypergraphs which are related to the structure of colour classes: (1) density, (2) the fractal property and (3) the generation of colour classes. In particular, we prove a density theorem for hypergraphs and show that, for connected oriented graphs, all jumps are balanced (and give an example to show that connectivity is needed here). We also show that a Hajós-type theorem holds for any colour class of undirected graphs, thus providing further evidence of the well-known ‘non-effective’ character of Hajós' theorem.

Let kp(G) denote the number of complete subgraphs of order p in the graph G. Bollobás proved that any real linear combination of the form [sum ]apkp(G) attains its maximum on a complete multipartite graph. We show that the same is true for a linear combination of the form [sum ]apkp(G) +bpkp(G¯), provided bp[ges ]0 for every p.

We study a restricted form of list colouring, for which every pair of lists that correspond to adjacent vertices may not share more than one colour. The optimal list size such that a proper list colouring is always possible given this restriction, we call separation choosability. We show for bipartite graphs that separation choosability increases with (the logarithm of) the minimum degree. This strengthens results of Molloy and Thron and, partially, of Alon. One attempt to drop the bipartiteness assumption precipitates a natural class of Ramsey-type questions, of independent interest. For example, does every triangle-free graph of minimum degree d contain a bipartite induced subgraph of minimum degree Ω(log d) as d→∞?

For fixed graphs F1,…,Fr, we prove an upper bound on the threshold function for the property that G(n, p) → (F1,…,Fr). This establishes the 1-statement of a conjecture of Kohayakawa and Kreuter.

We show that if a graph contains few copies of a given graph, then its edges are distributed rather unevenly.

In particular, for all $\varepsilon > 0$ and $r\geq2$, there exist $\xi =\xi (\varepsilon,r) > 0$ and $k=k (\varepsilon,r)$ such that, if $n$ is sufficiently large and $G=G(n)$ is a graph with fewer than $\xi n^{r}$$r$-cliques, then there exists a partition $V(G) =\cup_{i=0}^{k}V_{i}$ such that \[ \vert V_{i}\vert =\lfloor n/k\rfloor \quad \text{and} \quad e(W_{i}) <\varepsilon\vert V_{i}\vert ^{2}\] for every $i\in [k]$.

We deduce the following slightly stronger form of a conjecture of Erdős.

For all $c>0$ and $r\geq3$, there exist $\xi=\xi (c,r) >0$ and $\beta=\beta(c,r)>0$ such that, if $n$ is sufficiently large and $G=G(n,\lceil cn^{2} \rceil)$ is a graph with fewer than $\xi n^{r}$$r$-cliques, then there exists a partition $V(G) =V_{1}\cup V_{2}$ with $ \vert V_{1} \vert = \lfloor n/2 \rfloor $ and $\vert V_{2} \vert = \lceil n/2 \rceil $ such that \[ e(V_{1},V_{2}) > (1/2+\beta) e (G).\]

Notions of deletion and contraction for the class of set functions from finite sets into the integers are defined. An operation on a subclass of such set functions is a function from the subclass into itself that preserves ground sets and respects isomorphism. The operations on set functions that interchange deletion and contraction are characterised, as are those with the further property of being involutary. Similar results are given for polymatroids. There is a unique involutary operation on the class of k-polymatroids that interchanges deletion and contraction. The results generalise those of Kung [3].

Let (Xn) be a residual allocation model with i.i.d. residual fractions Un: For W a random variable with values in [0; 1] and independent of (Xn), we define another sequence (Yn) by setting

(formula here)

Under minor regularity assumptions we show that (Xn) and (Yn) have the same probability law if and only if this law is a GEM distribution. In this case, the distribution of W and the Uns is Beta(1; θ) for some θ > 0.

Let $s$ and $t$ be integers satisfying $s \geq 2$ and $t \geq 2$. Let $S$ be a tree of size $s$, and let $P_t$ be the path of length $t$. We show in this paper that, for every edge-colouring of the complete graph on $n$ vertices, where $n=224(s-1)^2t$, there is either a monochromatic copy of $S$ or a rainbow copy of $P_t$. So, in particular, the number of vertices needed grows only linearly in $t$.

A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph H as a minor has the so-called Erdős–Pósa property; namely, there exists a function f depending only on H such that, for every graph G and every positive integer k, the graph G has k vertex-disjoint subgraphs each containing H as a minor, or there exists a subset X of vertices of G with |X| ≤ f(k) such that G − X has no H-minor (see Robertson and Seymour, J. Combin. Theory Ser. B41 (1986) 92–114). While the best function f currently known is exponential in k, a O(k log k) bound is known in the special case where H is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function f can be taken to be linear when H is a forest. This is best possible in the sense that no linear bound is possible if H has a cycle.