Given two functions f,g : {0,1}n → {0,1}, a mapping ψ : {0,1}n → {0,1}n is said to be a mapping from f to g if it is a bijection and f(z) = g(ψ(z)) for every z ∈ {0,1}n. In this paper we study Lipschitz mappings between Boolean functions.

Our first result gives a construction of a C-Lipschitz mapping from the Majority function to the Dictator function for some universal constant C. On the other hand, there is no n/2-Lipschitz mapping in the other direction, namely from the Dictator function to the Majority function. This answers an open problem posed by Daniel Varga in the paper of Benjamini, Cohen and Shinkar (FOCS 2014 [1]).

We also show a mapping from Dictator to XOR that is 3-local, 2-Lipschitz, and its inverse is O(log(n))-Lipschitz, where by L-local mapping we mean that each output bit of the mapping depends on at most L input bits.

Next, we consider the problem of finding functions such that any mapping between them must have large average stretch, where the average stretch of a mapping φ is defined as

$${\sf avgstretch}(\phi) = {\mathbb E}_{x,i}[{\sf dist}(\phi(x),\phi(x+e_i)].$$

$\sqrt{n}$

Finally, we show that for a random balanced function f: {0,1}n → {0,1}n, with high probability there is a mapping φ from Dictator to f such that both φ and φ−1 have constant average stretch. In particular, this implies that one cannot obtain lower bounds on average stretch by taking uniformly random functions.

Due to a calculation error, the constant in the main theorem is not $80 \sqrt{k\log k}$ but $80\sqrt{k} \log k$. The error was discovered by Xizhi Liu.

For a new discussion on the limit of the method used in this paper see the revised arXiv version of the paper.

We consider the behaviour of minimax recursions defined on random trees. Such recursions give the value of a general class of two-player combinatorial games. We examine in particular the case where the tree is given by a Galton–Watson branching process, truncated at some depth 2n, and the terminal values of the level 2n nodes are drawn independently from some common distribution. The case of a regular tree was previously considered by Pearl, who showed that as n → ∞ the value of the game converges to a constant, and by Ali Khan, Devroye and Neininger, who obtained a distributional limit under a suitable rescaling.

For a general offspring distribution, there is a surprisingly rich variety of behaviour: the (unrescaled) value of the game may converge to a constant, or to a discrete limit with several atoms, or to a continuous distribution. We also give distributional limits under suitable rescalings in various cases.

We also address questions of endogeny. Suppose the game is played on a tree with many levels, so that the terminal values are far from the root. To be confident of playing a good first move, do we need to see the whole tree and its terminal values, or can we play close to optimally by inspecting just the first few levels of the tree? The answers again depend in an interesting way on the offspring distribution.

We also mention several open questions.

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.

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.

Assume that the edges of the complete graph Kn are given independent uniform [0, 1] weights. We consider the expected minimum total weight μk of k ⩽ 2 edge-disjoint spanning trees. When k is large we show that μk ≈ k2. Most of the paper is concerned with the case k = 2. We show that m2 tends to an explicitly defined constant and that μ2 ≈ 4.1704288. . . .

We study structural properties of graphs with bounded clique number and high minimum degree. In particular, we show that there exists a function L = L(r,ɛ) such that every Kr-free graph G on n vertices with minimum degree at least ((2r–5)/(2r–3)+ɛ)n is homomorphic to a Kr-free graph on at most L vertices. It is known that the required minimum degree condition is approximately best possible for this result.

For r = 3 this result was obtained by Łuczak (2006) and, more recently, Goddard and Lyle (2011) deduced the general case from Łuczak’s result. Łuczak’s proof was based on an application of Szemerédi’s regularity lemma and, as a consequence, it only gave rise to a tower-type bound on L(3, ɛ). The proof presented here replaces the application of the regularity lemma by a probabilistic argument, which yields a bound for L(r, ɛ) that is doubly exponential in poly(ɛ).

Magnant and Martin conjectured that the vertex set of any d-regular graph G on n vertices can be partitioned into $n / (d+1)$ paths (there exists a simple construction showing that this bound would be best possible). We prove this conjecture when $d = \Omega(n)$ , improving a result of Han, who showed that in this range almost all vertices of G can be covered by $n / (d+1) + 1$ vertex-disjoint paths. In fact our proof gives a partition of V(G) into cycles. We also show that, if $d = \Omega(n)$ and G is bipartite, then V(G) can be partitioned into n/(2d) paths (this bound is tight for bipartite graphs).

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.

In this paper, we study asymmetric Ramsey properties of the random graph $G_{n,p}$ . Let $r \in \mathbb{N}$ and $H_1, \ldots, H_r$ be graphs. We write $G_{n,p} \to (H_1, \ldots, H_r)$ to denote the property that whenever we colour the edges of $G_{n,p}$ with colours from the set $[r] \,{:\!=}\, \{1, \ldots, r\}$ there exists $i \in [r]$ and a copy of $H_i$ in $G_{n,p}$ monochromatic in colour $i$ . There has been much interest in determining the asymptotic threshold function for this property. In several papers, Rödl and Ruciński determined a threshold function for the general symmetric case; that is, when $H_1 = \cdots = H_r$ . A conjecture of Kohayakawa and Kreuter from 1997, if true, would fully resolve the asymmetric problem. Recently, the $1$ -statement of this conjecture was confirmed by Mousset, Nenadov and Samotij.

Building on work of Marciniszyn, Skokan, Spöhel and Steger from 2009, we reduce the $0$ -statement of Kohayakawa and Kreuter’s conjecture to a certain deterministic subproblem. To demonstrate the potential of this approach, we show this subproblem can be resolved for almost all pairs of regular graphs. This therefore resolves the $0$ -statement for all such pairs of graphs.

There was an incorrect argument in the proof of the main theorem in ‘On percolation and the bunkbed conjecture’, in Combin. Probab. Comput. (2011) 20 103–117 doi: 10.1017/S0963548309990666. I thus no longer claim to have a proof for the bunkbed conjecture for outerplanar graphs.

We show that recognizing the K3-freeness and K4-freeness of graphs is hard, respectively, for two-player nondeterministic communication protocols using exponentially many partitions and for nondeterministic syntactic read-r times branching programs.

The key ingredient is a generalization of a colouring lemma, due to Papadimitriou and Sipser, which says that for every balanced red—blue colouring of the edges of the complete n-vertex graph there is a set of εn2 triangles, none of which is monochromatic, such that no triangle can be formed by picking edges from different triangles. We extend this lemma to exponentially many colourings and to partial colourings.

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.

We introduce the path resistance method for lower bounds on the smallest nontrivial eigenvalue of the Laplacian matrix of a graph. The method is based on viewing the graph in terms of electrical circuits: it uses clique embeddings to produce lower bounds on λ2 and star embeddings to produce lower bounds on the smallest Rayleigh quotient when there is a zero Dirichlet boundary condition. The method assigns priorities to the paths in the embedding; we show that, for an unweighted tree T, using uniform priorities for a clique embedding produces a lower bound on λ2 that is off by at most an O(log diameter(T)) factor. We show that the best bounds this method can produce for clique embeddings are the same as for a related method that uses clique embeddings and edge lengths to produce bounds.

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.

Let $P=(X,\le)$ be a finite partially ordered set. That is, $X$ is a finite ground set and $\le$ is a partial ordering on $X$ (a reflexive, transitive, and weakly antisymmetric relation). An $x\in X$ is an immediate predecessor of a $y\in X$ if $x<y$ and there is no $z\in X$ with $x<z<y$ (where $x<y$ means that $x\le y$ and $x\ne y$). The Hasse diagram$H(P)$ is the undirected graph with vertex set $X$ and with $\{x,y\}$ forming an edge if $x$ is an immediate predecessor of $y$ or if $y$ is an immediate predecessor of $x$. We denote bya $\alpha(H(P))$ the independence number of the Hasse diagram, that is, the maximum possible size of a subset $I\subseteq X$ such that no element of $I$ is an immediate predecessor (in $P$) of another element of $I$. This quantity should not be confused with the maximum size of an antichain in $P$, which is sometimes denoted by $\alpha(P)$.

Denote by ${\mathcal H}_k$(n, p) the random k-graph in which each k-subset of {1,. . .,n} is present with probability p, independent of other choices. More or less answering a question of Balogh, Bohman and Mubayi, we show: there is a fixed ε > 0 such that if n = 2k + 1 and p > 1 - ε, then w.h.p. (that is, with probability tending to 1 as k → ∞), ${\mathcal H}_k$(n, p) has the ‘Erdős–Ko–Rado property’. We also mention a similar random version of Sperner's theorem.

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:

We investigate decompositions of a graph into a small number of low-diameter subgraphs. Let P(n, ε, d) be the smallest k such that every graph G = (V, E) on n vertices has an edge partition E = E0 ∪ E1 ∪ ⋅⋅⋅ ∪ Ek such that |E0| ≤ εn2, and for all 1 ≤ i ≤ k the diameter of the subgraph spanned by Ei is at most d. Using Szemerédi's regularity lemma, Polcyn and Ruciński showed that P(n, ε, 4) is bounded above by a constant depending only on ε. This shows that every dense graph can be partitioned into a small number of ‘small worlds’ provided that a few edges can be ignored. Improving on their result, we determine P(n, ε, d) within an absolute constant factor, showing that P(n, ε, 2) = Θ(n) is unbounded for ε < 1/4, P(n, ε, 3) = Θ(1/ε2) for ε > n−1/2 and P(n, ε, 4) = Θ(1/ε) for ε > n−1. We also prove that if G has large minimum degree, all the edges of G can be covered by a small number of low-diameter subgraphs. Finally, we extend some of these results to hypergraphs, improving earlier work of Polcyn, Rödl, Ruciński and Szemerédi.

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?