Given partially ordered sets (posets) $(P, \leq _P\!)$ and $(P^{\prime}, \leq _{P^{\prime}}\!)$ , we say that $P^{\prime}$ contains a copy of $P$ if for some injective function $f\,:\, P\rightarrow P^{\prime}$ and for any $X, Y\in P$ , $X\leq _P Y$ if and only if $f(X)\leq _{P^{\prime}} f(Y)$ . For any posets $P$ and $Q$ , the poset Ramsey number $R(P,Q)$ is the least positive integer $N$ such that no matter how the elements of an $N$ -dimensional Boolean lattice are coloured in blue and red, there is either a copy of $P$ with all blue elements or a copy of $Q$ with all red elements. We focus on a poset Ramsey number $R(P, Q_n)$ for a fixed poset $P$ and an $n$ -dimensional Boolean lattice $Q_n$ , as $n$ grows large. We show a sharp jump in behaviour of this number as a function of $n$ depending on whether or not $P$ contains a copy of either a poset $V$ , that is a poset on elements $A, B, C$ such that $B\gt C$ , $A\gt C$ , and $A$ and $B$ incomparable, or a poset $\Lambda$ , its symmetric counterpart. Specifically, we prove that if $P$ contains a copy of $V$ or $\Lambda$ then $R(P, Q_n) \geq n +\frac{1}{15} \frac{n}{\log n}$ . Otherwise $R(P, Q_n) \leq n + c(P)$ for a constant $c(P)$ . This gives the first non-marginal improvement of a lower bound on poset Ramsey numbers and as a consequence gives $R(Q_2, Q_n) = n + \Theta \left(\frac{n}{\log n}\right)$ .

Monotonic surfaces spanning finite regions of ℤd arise in many contexts, including DNA-based self-assembly, card-shuffling and lozenge tilings. One method that has been used to uniformly generate these surfaces is a Markov chain that iteratively adds or removes a single cube below the surface during a step. We consider a biased version of the chain, where we are more likely to add a cube than to remove it, thereby favouring surfaces that are ‘higher’ or have more cubes below it. We prove that the chain is rapidly mixing for any uniform bias in ℤ2 and for bias λ > d in ℤd when d > 2. In ℤ2 we match the optimal mixing time achieved by Benjamini, Berger, Hoffman and Mossel in the context of biased card shuffling [2], but using much simpler arguments. The proofs use a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile. We show that the chain continues to be rapidly mixing if the biases are close to uniform, but that the chain can converge exponentially slowly in the general setting.

We consider networks in which both the nodes and the links may fail. We represent the network by an undirected graph G. Vertices of the graph fail with probability p and edges of the graph fail with probability q, where all failures are assumed independent. We shall be concerned with minimising the probability P(G) that G is disconnected for graphs with given numbers of vertices and edges. We show how to construct these optimal graphs in many cases when p and q are ‘small’.

Let G be a minimally n-edge-connected finite simple graph with vertex number |G| ≥ 2n + 2 + [3/n] and let n ≥ 3 be odd. It is proved that the number of vertices of degree n in G is at least ((n − 1 − ∈n)/(2n + 1))|G| + 2 + 2∈n, where ∈n = (3n + 3)/(2n2 − 3n − 3), and that for every n ≡ 3 (mod 4) this lower bound is attained by infinitely many minimally n-edge-connected finite simple graphs.

We consider the oriented binary tree and the oriented hypercube. The tree edges are oriented from the root to the leaves, while the orientation of the cube edges is induced by the direction from 0 to 1 in the coordinatewise form. The problem is to embed such a tree with l levels into the oriented n-cube as an oriented subgraph, for minimal possible n. A new approach to such problems is presented, which improves the known upper bound n/l ≤ 3/2 given by Havel [1] to n/l ≤ 4/3 + o(1) as l → ∞.

In 1964 Dirac conjectured that every graph with n vertices and at least 3n − 5 edges contains a subdivision of K5 We prove a weakened version with 7/2;n − 7 instead of 3n − 5. We prove that, for any prescribed vertex νo, the subdivision can be found such that νo is not one of the five branch vertices. This variant of Dirac's problem, which was suggested by the present author in 1973, is best possible in the sense that 7/2;n − 7 cannot be replaced by 7/2;n − 15/2;.

Given graphs G and H, a family of vertex-disjoint copies of H in G is called an H-tiling. Conlon, Gowers, Samotij and Schacht showed that for a given graph H and a constant γ>0, there exists C>0 such that if $p \ge C{n^{ - 1/{m_2}(H)}}$ , then asymptotically almost surely every spanning subgraph G of the random graph 𝒢(n, p) with minimum degree at least

$\delta (G) \ge (1 - \frac{1}{{{\chi _{{\rm{cr}}}}(H)}} + \gamma )np$

$\gamma {(C/p)^{{m_2}(H)}}$

$p \ge C{n^{ - 1/{m_2}(H)}}$

Erdős, Gyárfás and Pyber showed that every r-edge-coloured complete graph Kn can be covered by 25 r2 log r vertex-disjoint monochromatic cycles (independent of n). Here we extend their result to the setting of binomial random graphs. That is, we show that if $p = p(n) = \Omega(n^{-1/(2r)})$ , then with high probability any r-edge-coloured G(n, p) can be covered by at most 1000r4 log r vertex-disjoint monochromatic cycles. This answers a question of Korándi, Mousset, Nenadov, Škorić and Sudakov.

The clustered chromatic number of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$ -colourable with monochromatic components of size at most $c$ . We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on the clustered chromatic number of any minor-closed class with bounded pathwidth. As a consequence, we determine the fractional clustered chromatic number of every minor-closed class.

There has been substantial interest in estimating the value of a graph parameter, i.e. of a real-valued function defined on the set of finite graphs, by querying a randomly sampled substructure whose size is independent of the size of the input. Graph parameters that may be successfully estimated in this way are said to be testable or estimable, and the sample complexity qz = qz(ε) of an estimable parameter z is the size of a random sample of a graph G required to ensure that the value of z(G) may be estimated within an error of ε with probability at least 2/3. In this paper, for any fixed monotone graph property $\mathcal{P}= \text{Forb}\!(\mathcal{F}),$ we study the sample complexity of estimating a bounded graph parameter z that, for an input graph G, counts the number of spanning subgraphs of G that satisfy$\mathcal{P}$. To improve upon previous upper bounds on the sample complexity, we show that the vertex set of any graph that satisfies a monotone property $\mathcal{P}$ may be partitioned equitably into a constant number of classes in such a way that the cluster graph induced by the partition is not far from satisfying a natural weighted graph generalization of $\mathcal{P}$. Properties for which this holds are said to be recoverable, and the study of recoverable properties may be of independent interest.

We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two independent uniform random neighbours. We prove that this allows the controller to significantly accelerate the hitting and cover times in several natural graph classes. In particular, we show that the cover time becomes linear in the number n of vertices on discrete tori and bounded degree trees, of order $${\mathcal O}(n\log \log n)$$ on bounded degree expanders, and of order $${\mathcal O}(n{(\log \log n)^2})$$ on the Erdős–Rényi random graph in a certain sparsely connected regime. We also consider the algorithmic question of computing an optimal strategy and prove a dichotomy in efficiency between computing strategies for hitting and cover times.

We introduce a non-increasing tree growth process $((T_n,{\sigma}_n),\, n\ge 1)$ , where Tn is a rooted labelled tree on n vertices and σn is a permutation of the vertex labels. The construction of (Tn, σn) from (Tn−1, σn−1) involves rewiring a random (possibly empty) subset of edges in Tn−1 towards the newly added vertex; as a consequence Tn−1 ⊄ Tn with positive probability. The key feature of the process is that the shape of Tn has the same law as that of a random recursive tree, while the degree distribution of any given vertex is not monotone in the process.

We present two applications. First, while couplings between Kingman’s coalescent and random recursive trees were known for any fixed n, this new process provides a non-standard coupling of all finite Kingman’s coalescents. Second, we use the new process and the Chen–Stein method to extend the well-understood properties of degree distribution of random recursive trees to extremal-range cases. Namely, we obtain convergence rates on the number of vertices with degree at least $c\ln n$ , c ∈ (1, 2), in trees with n vertices. Further avenues of research are discussed.

We prove that the roots of the chromatic polynomials of planar graphs are dense in the interval between 32/27 and 4, except possibly in a small interval around τ + 2 where τ is the golden ratio. This interval arises due to a classical result of Tutte, which states that the chromatic polynomial of every planar graph takes a positive value at τ + 2. Our results lead us to conjecture that τ + 2 is the only such number less than 4.

How ‘tightly’ can we pack a given number of $r$-sets of an $n$-set? To be a little more precise, let $X=[n]=\{ 1,\ldots,n \}$, and let $X^r=\{ A\subset X : |A|=r \}$. For a set system $\mathcal{A}\subset X^r $, the neighbourhood of $\mathcal{A}$ is $N(\mathcal{A})=\{ B \in X^r: |B \bigtriangleup A|\le 2 \hbox{ for some }A \in \mathcal{A} \}$. In other words, $N(\mathcal{A})$ consists of those $r$-sets that are either in $\mathcal{A}$ or are ‘adjacent’ to it, in the sense that they are at minimal Hamming distance (i.e., distance 2) from some point of it. Given $|\mathcal{A}|$, how small can $|N(\mathcal{A})|$ be?

An n × n partial Latin square P is called α-dense if each row and column has at most αn non-empty cells and each symbol occurs at most αn times in P. An n × n array A where each cell contains a subset of {1,…, n} is a (βn, βn, βn)-array if each symbol occurs at most βn times in each row and column and each cell contains a set of size at most βn. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants α, β > 0 such that, for every positive integer n, if P is an α-dense n × n partial Latin square, A is an n × n (βn, βn, βn)-array, and no cell of P contains a symbol that appears in the corresponding cell of A, then there is a completion of P that avoids A; that is, there is a Latin square L that agrees with P on every non-empty cell of P, and, for each i, j satisfying 1 ≤ i, j ≤ n, the symbol in position (i, j) in L does not appear in the corresponding cell of A.

Let Ωn be the nn-element set consisting of all functions that have {1, 2, 3, . . ., n} as both domain and codomain. Let T(f) be the order of f, i.e., the period of the sequence f, f(2), f(3), f(4) . . . of compositional iterates. A closely related number, B(f) = the product of the lengths of the cycles of f, has previously been used as an approximation for T. This paper proves that the average values of these two quantities are quite different. The expected value of T is where k0 is a complicated but explicitly defined constant that is approximately 3.36. The expected value of B is much larger:

A long-standing conjecture of Richter and Thomassen states that the total number of intersection points between any n simple closed Jordan curves in the plane, so that any pair of them intersect and no three curves pass through the same point, is at least (1−o(1))n 2.

We confirm the above conjecture in several important cases, including the case (1) when all curves are convex, and (2) when the family of curves can be partitioned into two equal classes such that each curve from the first class touches every curve from the second class. (Two closed or open curves are said to be touching if they have precisely one point in common and at this point the two curves do not properly cross.)

An important ingredient of our proofs is the following statement. Let S be a family of n open curves in ℝ2, so that each curve is the graph of a continuous real function defined on ℝ, and no three of them pass through the same point. If there are nt pairs of touching curves in S, then the number of crossing points is $\Omega(nt\sqrt{\log t/\log\log t})$ .

For two graphs S and T, the constrained Ramsey number f(S, T) is the minimum n such that every edge colouring of the complete graph on n vertices (with any number of colours) has a monochromatic subgraph isomorphic to S or a rainbow subgraph isomorphic to T. Here, a subgraph is said to be rainbow if all of its edges have different colours. It is an immediate consequence of the Erdős–Rado Canonical Ramsey Theorem that f(S, T) exists if and only if S is a star or T is acyclic. Much work has been done to determine the rate of growth of f(S, T) for various types of parameters. When S and T are both trees having s and t edges respectively, Jamison, Jiang and Ling showed that f(S, T) ≤ O(st2) and conjectured that it is always at most O(st). They also mentioned that one of the most interesting open special cases is when T is a path. In this paper, we study this case and show that f(S, Pt) = O(st log t), which differs only by a logarithmic factor from the conjecture. This substantially improves the previous bounds for most values of s and t.

Consider a finite alphabet Ω and patterns which consist of characters from Ω. For a given pattern w, let cor(w) denote its autocorrelation, which can be seen as a measure of the amount of overlap in w. Letting aw(n) denote the number of strings over Ω of length n which do not contain w as a substring, the main result of this paper is: If cor(w) > cor(w′) then aw(n)−aw′(n) > (|Ω|−1)(aw(n−1)−aw′(n−1)) for n [ges ] N, and the value of N is given. This result confirms a conjecture by Eriksson [2], which was previously proved to be true by Cakir, Chryssaphinou and Månsson [1] when |Ω| [ges ] 3.

Suppose a binary string x = x1 . . . xn is being broadcast repeatedly over a faulty communication channel. Each time, the channel delivers a fixed number m of the digits (m < n) with the lost digits chosen uniformly at random and the order of the surviving digits preserved. How large does m have to be to reconstruct the message?