In 2011, shortly after his untimely passing, several colleagues and I wrote an obituary for Philippe Flajolet [5] that includes the following:

For a fixed permutation τ, let $\mathcal{S}_N(\tau)$ be the set of permutations on N elements that avoid the pattern τ. Madras and Liu (2010) conjectured that $\lim_{N\rightarrow\infty}\frac{|\mathcal{S}_{N+1}(\tau)|}{ |\mathcal{S}_N(\tau)|}$ exists; if it does, it must equal the Stanley–Wilf limit. We prove the conjecture for every permutation τ of length 5 or less, as well as for some longer cases (including 704 of the 720 permutations of length 6). We also consider permutations drawn at random from $\mathcal{S}_N(\tau)$, and we investigate properties of their graphs (viewing permutations as functions on {1,. . .,N}) scaled down to the unit square [0,1]2. We prove exact large deviation results for these graphs when τ has length 3; it follows, for example, that it is exponentially unlikely for a random 312-avoiding permutation to have points above the diagonal strip |y−x| < ε, but not unlikely to have points below the strip. For general τ, we show that some neighbourhood of the upper left corner of [0,1]2 is exponentially unlikely to contain a point of the graph if and only if τ starts with its largest element. For patterns such as τ=4231 we establish that this neighbourhood can be extended along the sides of [0,1]2 to come arbitrarily close to the corner points (0,0) and (1,1), as simulations had suggested.

The spread of a connected graph G was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions f on V(G) of the variance of f(X) when X is uniformly distributed on V(G). We investigate the spread for certain models of sparse random graph, in particular for random regular graphs G(n,d), for Erdős–Rényi random graphs Gn,p in the supercritical range p>1/n, and for a ‘small world’ model. For supercritical Gn,p, we show that if p=c/n with c>1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when p=(1+o(1))/n. Further, we show that for d large, with high probability the spread of G(n,d) becomes arbitrarily close to that of the complete graph $\mathsf{K}_n$.

We explore the asymptotic distributions of sequences of integer-valued additive functions defined on the symmetric group endowed with the Ewens probability measure as the order of the group increases. Applying the method of factorial moments, we establish necessary and sufficient conditions for the weak convergence of distributions to discrete laws. More attention is paid to the Poisson limit distribution. The particular case of the number-of-cycles function is analysed in more detail. The results can be applied to statistics defined on random permutation matrices.

For any c ≥ 2, a c-strong colouring of the hypergraph G is an assignment of colours to the vertices of G such that, for every edge e of G, the vertices of e are coloured by at least min{c,|e|} distinct colours. The hypergraph G is t-intersecting if every two edges of G have at least t vertices in common.

A natural variant of a question of Erdős and Lovász is: For fixed c ≥ 2 and t ≥ 1, what is the minimum number of colours that is sufficient to c-strong colour any t-intersecting hypergraphs? The purpose of this note is to describe some open problems related to this question.

Let ${\mathcal H}$ denote a collection of subsets of {1,2,. . .,n}, and assign independent random variables uniformly distributed over [0,1] to the n elements. Declare an element p-present if its corresponding value is at most p. In this paper, we quantify how much the observation of the r-present (r>p) set of elements affects the probability that the set of p-present elements is contained in ${\mathcal H}$. In the context of percolation, we find that this question is closely linked to the near-critical regime. As a consequence, we show that for every r>1/2, bond percolation on the subgraph of the square lattice given by the set of r-present edges is almost surely noise sensitive at criticality, thus generalizing a result due to Benjamini, Kalai and Schramm.

We study the mixing properties of permutations obtained as a product of two uniformly random permutations of fixed cycle types. For instance, we give an exact formula for the probability that elements 1,2,. . .,k are in distinct cycles of the random permutation of {1,2,. . .,n} obtained as a product of two uniformly random n-cycles.

Starting from an n-by-n matrix of zeros, choose uniformly random zero entries and change them to ones, one at a time, until the matrix becomes invertible. We show that with probability tending to one as n → ∞, this occurs at the very moment the last zero row or zero column disappears. We prove a related result for random symmetric Bernoulli matrices, and give quantitative bounds for some related problems. These results extend earlier work by Costello and Vu [10].

We consider the problem of enumerating d-irreducible maps, i.e., planar maps all of whose cycles have length at least d, and such that any cycle of length d is the boundary of a face of degree d. We develop two approaches in parallel: the natural approach via substitution, where these maps are obtained from general maps by a replacement of all d-cycles by elementary faces, and a bijective approach via slice decomposition, which consists in cutting the maps along shortest paths. Both lead to explicit expressions for the generating functions of d-irreducible maps with controlled face degrees, summarized in some elegant ‘pointing formula’. We provide an equivalent description of d-irreducible slices in terms of so-called d-oriented trees. We finally show that irreducible maps give rise to a hierarchy of discrete integrable equations which include equations encountered previously in the context of naturally embedded trees.

We prove several results from different areas of extremal combinatorics, giving complete or partial solutions to a number of open problems. These results, coming from areas such as extremal graph theory, Ramsey theory and additive combinatorics, have been collected together because in each case the relevant proofs are quite short.

Bounded-size rules (BSRs) are dynamic random graph processes which incorporate limited choice along with randomness in the evolution of the system. Typically one starts with the empty graph and at each stage two edges are chosen uniformly at random. One of the two edges is then placed into the system according to a decision rule based on the sizes of the components containing the four vertices. For bounded-size rules, all components of size greater than some fixed K ≥ 1 are accorded the same treatment. Writing BSR(t) for the state of the system with ⌊nt/2⌋ edges, Spencer and Wormald [26] proved that for such rules, there exists a (rule-dependent) critical time tc such that when t < tc the size of the largest component is of order log n, while for t > tc, the size of the largest component is of order n. In this work we obtain upper bounds (that hold with high probability) of order n2γ log4n, on the size of the largest component, at time instants tn = tc−n−γ, where γ ∈ (0,1/4). This result for the barely subcritical regime forms a key ingredient in the study undertaken in [4], of the asymptotic dynamic behaviour of the process describing the vector of component sizes and associated complexity of the components for such random graph models in the critical scaling window. The proof uses a coupling of BSR processes with a certain family of inhomogeneous random graphs with vertices in the type space $\mathbb{R}_+\times \mathcal{D}([0,\infty):\mathbb{N}_0)$, where $\mathcal{D}([0,\infty):\mathbb{N}_0)$ is the Skorokhod D-space of functions that are right continuous and have left limits, with values in the space of non-negative integers $\mathbb{N}_0$, equipped with the usual Skorokhod topology. The coupling construction also gives an alternative characterization (from the usual explosion time of the susceptibility function) of the critical time tc for the emergence of the giant component in terms of the operator norm of integral operators on certain L2 spaces.

Let Hd(n,p) signify a random d-uniform hypergraph with n vertices in which each of the $\binom{n}{d}$ possible edges is present with probability p=p(n) independently, and let Hd(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. We derive local limit theorems for the joint distribution of the number of vertices and the number of edges in the largest component of Hd(n,p) and Hd(n,m) in the regime $(d-1)\binom{n-1}{d-1}p>1+\varepsilon$, resp. d(d−1)m/n>1+ϵ, where ϵ>0 is arbitrarily small but fixed as n → ∞. The proofs are based on a purely probabilistic approach.

We model the transmission of a message on the complete graph with n vertices and limited resources. The vertices of the graph represent servers that may broadcast the message at random. Each server has a random emission capital that decreases at each emission. Quantities of interest are the number of servers that receive the information before the capital of all the informed servers is exhausted and the exhaustion time. We establish limit theorems (law of large numbers, central limit theorem and large deviation principle), as n → ∞, for the proportion of informed vertices before exhaustion and for the total duration. The analysis relies on a construction of the transmission procedure as a dynamical selection of successful nodes in a Galton–Watson tree with respect to the success epochs of the coupon collector problem.

We consider samples of n geometric random variables with parameter 0 < p < 1, and study the largest missing value, that is, the highest value of such a random variable, less than the maximum, that does not appear in the sample. Asymptotic expressions for the mean and variance for this quantity are presented. We also consider samples with the property that the largest missing value and the largest value which does appear differ by exactly one, and call this the LMV property. We find the probability that a sample of n variables has the LMV property, as well as the mean for the average largest value in samples with this property. The simpler special case of p = 1/2 has previously been studied, and verifying that the results of the present paper coincide with those previously found for p = 1/2 leads to some interesting identities.

Let G be a triangle-free graph with n vertices and average degree t. We show that G contains at least

${\exp\biggl({1-n^{-1/12})\frac{1}{2}\frac{n}{t}\ln t} \biggl(\frac{1}{2}\ln t-1\biggr)\biggr)}$

${e^{(c_1-o(1)) \sqrt{n} \ln n}}$

$c_1 = \sqrt{\ln 2}/4 = 0.208138 \ldots$

${e^{(c_2+o(1))\sqrt{n}\ln n}}$

$c_2 = 2\sqrt{\ln 2} = 1.665109 \ldots$

Let H be a (k+1)-uniform linear hypergraph with n vertices and average degree t. We also show that there exists a constant ck such that the number of independent sets in H is at least

${\exp\biggl({c_{k} \frac{n}{t^{1/k}}\ln^{1+1/k}{t}\biggr})}.$

$\Omega\biggl(\frac{n}{t^{1/k}} \ln^{1/k}t\biggr).$

For d ≥ 2, let Hd(n,p) denote a random d-uniform hypergraph with n vertices in which each of the $\binom{n}{d}$ possible edges is present with probability p=p(n) independently, and let Hd(n,m) denote a uniformly distributed d-uniform hypergraph with n vertices and m edges. Let either H=Hd(n,m) or H=Hd(n,p), where m/n and $\binom{n-1}{d-1}p$ need to be bounded away from (d−1)−1 and 0 respectively. We determine the asymptotic probability that H is connected. This yields the asymptotic number of connected d-uniform hypergraphs with given numbers of vertices and edges. We also derive a local limit theorem for the number of edges in Hd(n,p), conditioned on Hd(n,p) being connected.

In the index coding problem, introduced by Birk and Kol (INFOCOM, 1998), the goal is to broadcast an n-bit word to n receivers (one bit per receiver), where the receivers have side information represented by a graph G. The objective is to minimize the length of a codeword sent to all receivers which allows each receiver to learn its bit. For linear index coding, the minimum possible length is known to be equal to a graph parameter called minrank (Bar-Yossef, Birk, Jayram and Kol, IEEE Trans. Inform. Theory, 2011).

We show a polynomial-time algorithm that, given an n-vertex graph G with minrank k, finds a linear index code for G of length Õ(nf(k)), where f(k) depends only on k. For example, for k = 3 we obtain f(3) ≈ 0.2574. Our algorithm employs a semidefinite program (SDP) introduced by Karger, Motwani and Sudan for graph colouring (J. Assoc. Comput. Mach., 1998) and its refined analysis due to Arora, Chlamtac and Charikar (STOC, 2006). Since the SDP we use is not a relaxation of the minimization problem we consider, a crucial component of our analysis is an upper bound on the objective value of the SDP in terms of the minrank.

At the heart of our analysis lies a combinatorial result which may be of independent interest. Namely, we show an exact expression for the maximum possible value of the Lovász ϑ-function of a graph with minrank k. This yields a tight gap between two classical upper bounds on the Shannon capacity of a graph.

We are given a graph G with n vertices, where a random subset of k vertices has been made into a clique, and the remaining edges are chosen independently with probability $\frac12$. This random graph model is denoted $G(n,\frac12,k)$. The hidden clique problem is to design an algorithm that finds the k-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov [3] uses spectral techniques to find the hidden clique with high probability when $k = c \sqrt{n}$ for a sufficiently large constant c > 0. Recently, an algorithm that solves the same problem was proposed by Feige and Ron [12]. It has the advantages of being simpler and more intuitive, and of an improved running time of O(n2). However, the analysis in [12] gives a success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in time O(n2) (that is, linear in the size of the input) and has a failure probability that tends to 0 as n tends to ∞. We develop this algorithm in the more general setting where the clique is replaced by a dense random graph.

For 1 < α < 2 we derive the asymptotic distribution of the total length of external branches of a Beta(2 − α, α)-coalescent as the number n of leaves becomes large. It turns out that the fluctuations of the external branch length follow those of τn2−α over the entire parameter regime, where τn denotes the random number of coalescences that bring the n lineages down to one. This is in contrast to the fluctuation behaviour of the total branch length, which exhibits a transition at $\alpha_0 = (1+\sqrt 5)/2$ ([18]).

We prove the existence of a function $f :\mathbb{N} \to \mathbb{N}$ such that the vertices of every planar graph with maximum degree Δ can be 3-coloured in such a way that each monochromatic component has at most f(Δ) vertices. This is best possible (the number of colours cannot be reduced and the dependence on the maximum degree cannot be avoided) and answers a question raised by Kleinberg, Motwani, Raghavan and Venkatasubramanian in 1997. Our result extends to graphs of bounded genus.