We consider the problem of selecting sequentially a unimodal subsequence from a sequence of independent identically distributed random variables, and we find that a person doing optimal sequential selection does so within a factor of the square root of two as well as a prophet who knows all of the random observations in advance of any selections. Our analysis applies in fact to selections of subsequences that have d+1 monotone blocks, and, by including the case d=0, our analysis also covers monotone subsequences.

We provide a probabilistic analysis of the output of Quicksort when comparisons can err.

We consider large random graphs with prescribed degrees, as generated by the configuration model. In the regime where the empirical degree distribution approaches a limit μ with finite mean, we establish the systematic convergence of a broad class of graph parameters that includes the independence number, the maximum cut size, the logarithm of the Tutte polynomial, and the free energy of the anti-ferromagnetic Ising and Potts models. Contrary to previous works, our results are not a priori limited to the free energy of some prescribed graphical model. They apply more generally to any additive, Lipschitz and concave graph parameter. In addition, the corresponding limits are shown to be Lipschitz and concave in the degree distribution μ. This considerably extends the applicability of the celebrated interpolation method, introduced in the context of spin glasses, and recently related to the challenging question of right-convergence of sparse graphs.

There is a simple greedy algorithm for seeking large values of a function f defined on the vertices of the binary tree. Modeling f as a random function whose increments along edges are i.i.d., we show that (under a natural assumption) the values found by the greedy algorithm grow linearly in time, with rate specified in terms of a fixed-point identity for distributions.

We study the ‘rank 1 case’ of the inhomogeneous random graph model. In the subcritical case we derive an exact formula for the asymptotic size of the largest connected component scaled to log n. This result complements the corresponding known result in the supercritical case. We provide some examples of applications of the derived formula.

Two-sided bounds are explored for concentration functions and Rényi entropies in the class of discrete log-concave probability distributions. They are used to derive certain variants of the entropy power inequalities.

Given non-negative weights wS on the k-subsets S of a km-element set V, we consider the sum of the products wS1 ⋅⋅⋅ wSm over all partitions V = S1 ∪ ⋅⋅⋅ ∪Sm into pairwise disjoint k-subsets Si. When the weights wS are positive and within a constant factor of each other, fixed in advance, we present a simple polynomial-time algorithm to approximate the sum within a polynomial in m factor. In the process, we obtain higher-dimensional versions of the van der Waerden and Bregman–Minc bounds for permanents. We also discuss applications to counting of perfect and nearly perfect matchings in hypergraphs.

Given a graph G on n vertices with average degree d, form a random subgraph Gp by choosing each edge of G independently with probability p. Strengthening a classical result of Margulis we prove that, if the edge connectivity k(G) satisfies k(G) [Gt ] d/log n, then the connectivity threshold in Gp is sharp. This result is asymptotically tight.

A simple explicit construction is provided of a partition-valued fragmentation process whose distribution on partitions of [n] = 1,. . .,n at time θ ≥ 0 is governed by the Ewens sampling formula with parameter θ. These partition-valued processes are exchangeable and consistent, as n varies. They can be derived by uniform sampling from a corresponding mass fragmentation process defined by cutting a unit interval at the points of a Poisson process with intensity θx−1dx on/mathbbR+, arranged to beintensifying as θ increases.

The sub-Gaussian constant of a graph arises naturally in bounding the moment-generating function of Lipschitz functions on the graph, with a given probability measure on the set of vertices. The closely related spread constant of a graph measures the maximal variance over all Lipschitz functions on the graph. As such they are both useful (as demonstrated in the works of Bobkov, Houdré and Tetali and Alon, Boppana and Spencer) for describing the concentration of measure phenomenon in product graphs. An equivalent formulation of the sub-Gaussian constant using a transportation inequality, introduced by Bobkov and Götze, is investigated here in depth, leading to a new way of bounding the sub-Gaussian constant. A tight concentration result for the discrete torus is given as a concrete application. An infinite family of graphs is also provided here to demonstrate that, typically, the spread and the sub-Gaussian constants differ by an order of magnitude.

Sampling formulas describe probability laws of exchangeable combinatorial structures like partitions and compositions. We give a brief account of two known parametric families of sampling formulas for compositions and add a new family to the list.

A family of subsets of {1,. . .,n} is called intersecting if any two of its sets intersect. A classical result in extremal combinatorics due to Erdős, Ko and Rado determines the maximum size of an intersecting family of k-subsets of {1,. . .,n}. In this paper we study the following problem: How many intersecting families of k-subsets of {1,. . .,n} are there? Improving a result of Balogh, Das, Delcourt, Liu and Sharifzadeh, we determine this quantity asymptotically for n ≥ 2k+2+2$\sqrt{k\log k}$ and k → ∞. Moreover, under the same assumptions we also determine asymptotically the number of non-trivial intersecting families, that is, intersecting families for which the intersection of all sets is empty. We obtain analogous results for pairs of cross-intersecting families.

A perfect Kr-tiling in a graph G is a collection of vertex-disjoint copies of the clique Kr in G covering every vertex of G. The famous Hajnal–Szemerédi theorem determines the minimum degree threshold for forcing a perfect Kr-tiling in a graph G. The notion of discrepancy appears in many branches of mathematics. In the graph setting, one assigns the edges of a graph G labels from {‒1, 1}, and one seeks substructures F of G that have ‘high’ discrepancy (i.e. the sum of the labels of the edges in F is far from 0). In this paper we determine the minimum degree threshold for a graph to contain a perfect Kr-tiling of high discrepancy.

Let σ be a finite relational signature, let be a set of finite complete relational structures of signature σ, and let be the countable homogeneous relational structure of signature σ which does not embed any of the structures in .

When σ consists of at most binary relations and is finite, the vertex partition behaviour of is completely analysed, in the sense that it is shown that a canonical partition exists and the size of this partition in terms of the structures in is determined. If is infinite some results are obtained, but a complete analysis is still missing.

Some general results are presented which are intended to be used in further investigations when σ contains relational symbols of arity larger than two or when the set of bounds is infinite.

The discrete Green's function (without boundary) $\mathbb{G}$ is a pseudo-inverse of the combinatorial Laplace operator of a graph G = (V, E). We reveal the intimate connection between Green's function and the theory of exact stopping rules for random walks on graphs. We give an elementary formula for Green's function in terms of state-to-state hitting times of the underlying graph. Namely,$\mathbb{G}(i,j) = \pi_j \bigl( H(\pi,j) - H(i,j) \bigr),$ where πi is the stationary distribution at vertex i, H(i, j) is the expected hitting time for a random walk starting from vertex i to first reach vertex j, and H(π, j) = ∑k∈V πkH(k, j). This formula also holds for the digraph Laplace operator.

The most important characteristics of a stopping rule are its exit frequencies, which are the expected number of exits of a given vertex before the rule halts the walk. We show that Green's function is, in fact, a matrix of exit frequencies plus a rank one matrix. In the undirected case, we derive spectral formulas for Green's function and for some mixing measures arising from stopping rules. Finally, we further explore the exit frequency matrix point of view, and discuss a natural generalization of Green's function for any distribution τ defined on the vertex set of the graph.

For positive integers n and q and a monotone graph property $\mathcal{A}$ , we consider the two-player, perfect information game WC(n, q, $\mathcal{A}$ ), which is defined as follows. The game proceeds in rounds. In each round, the first player, called Waiter, offers the second player, called Client, q + 1 edges of the complete graph Kn which have not been offered previously. Client then chooses one of these edges which he keeps and the remaining q edges go back to Waiter. If, at the end of the game, the graph which consists of the edges chosen by Client satisfies the property $\mathcal{A}$ , then Waiter is declared the winner; otherwise Client wins the game. In this paper we study such games (also known as Picker–Chooser games) for a variety of natural graph-theoretic parameters, such as the size of a largest component or the length of a longest cycle. In particular, we describe a phase transition type phenomenon which occurs when the parameter q is close to n and is reminiscent of phase transition phenomena in random graphs. Namely, we prove that if q ⩾ (1 + ϵ)n, then Client can avoid components of order cϵ−2 ln n for some absolute constant c > 0, whereas for q ⩽ (1 − ϵ)n, Waiter can force a giant, linearly sized component in Client's graph. In the second part of the paper, we prove that Waiter can force Client's graph to be pancyclic for every q ⩽ cn, where c > 0 is an appropriate constant. Note that this behaviour is in stark contrast to the threshold for pancyclicity and Hamiltonicity of random graphs.

In this paper we prove several point selection theorems concerning objects ‘spanned’ by a finite set of points. For example, we show that for any set $P$ of $n$ points in $\R^2$ and any set $C$ of $m \,{\geq}\, 4n$ distinct pseudo-circles, each passing through a distinct pair of points of $P$, there is a point in $P$ that is covered by (i.e., lies in the interior of) $\Omega(m^2/n^2)$ pseudo-circles of $C$. Similar problems involving point sets in higher dimensions are also studied.

Most of our bounds are asymptotically tight, and they improve and generalize results of Chazelle, Edelsbrunner, Guibas, Hershberger, Seidel and Sharir [8], where weaker bounds for some of these cases were obtained.

We give a minimum degree condition sufficient to ensure the existence of a fractional Kr-decomposition in a balanced r-partite graph (subject to some further simple necessary conditions). This generalizes the non-partite problem studied recently by Barber, Lo, Kühn, Osthus and the author, and the 3-partite fractional K3-decomposition problem studied recently by Bowditch and Dukes. Combining our result with recent work by Barber, Kühn, Lo, Osthus and Taylor, this gives a minimum degree condition sufficient to ensure the existence of a (non-fractional) Kr-decomposition in a balanced r-partite graph (subject to the same simple necessary conditions).

We describe how non-crossing partitions arise in substitution method calculations. By using efficient algorithms for computing non-crossing partitions we are able to substantially reduce the computational effort, which enables us to compute improved bounds on the percolation thresholds for three percolation models. For the Kagomé bond model we improve bounds from 0.5182 ≤ pc ≤ 0.5335 to 0.522197 ≤ pc ≤ 0.526873, improving the range from 0.0153 to 0.004676. For the (3, 122) bond model we improve bounds from 0.7393 ≤ pc ≤ 0.7418 to 0.739773 ≤ pc ≤ 0.741125, improving the range from 0.0025 to 0.001352. We also improve the upper bound for the hexagonal site model, from 0.794717 to 0.743359.

In this note we establish a uniform bound for the distribution of a sum Sn=X1+···+Xn of independent non-homogeneous Bernoulli trials. Specifically, we prove that σn(Sn = j) ≤ η, where σn denotes the standard deviation of Sn, and η is a universal constant. We compute the best possible constant η ~ 0.4688 and we show that the bound also holds for limits of sums and differences of Bernoullis, including the Poisson laws which constitute the worst case and attain the bound. We also investigate the optimal bounds for n and j fixed. An application to estimate the rate of convergence of Mann's fixed-point iterations is presented.