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 pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time – the expected time required to visit every node in a graph at least once – and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s–t connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

Extending an old conjecture of Tutte, Jaeger conjectured in 1988 that for any fixed integer p ≥ 1, the edges of any 4p-edge connected graph can be oriented so that the difference between the outdegree and the indegree of each vertex is divisible by 2p+1. It is known that it suffices to prove this conjecture for (4p+1)-regular, 4p-edge connected graphs. Here we show that there exists a finite p0 such that for every p > p0 the assertion of the conjecture holds for all (4p+1)-regular graphs that satisfy some mild quasi-random properties, namely, the absolute value of each of their non-trivial eigenvalues is at most c1p2/3 and the neighbourhood of each vertex contains at most c2p3/2 edges, where c1, c2 > 0 are two absolute constants. In particular, this implies that for p > p0 the assertion of the conjecture holds asymptotically almost surely for random (4p+1)-regular graphs.

We say that α ∈ [0, 1) is a jump for an integer r ≥ 2 if there exists c(α) > 0 such that for all ϵ > 0 and all t ≥ 1, any r-graph with n ≥ n0(α, ϵ, t) vertices and density at least α + ϵ contains a subgraph on t vertices of density at least α + c.

The Erdős–Stone–Simonovits theorem [4, 5] implies that for r = 2, every α ∈ [0, 1) is a jump. Erdős [3] showed that for all r ≥ 3, every α ∈ [0, r!/rr) is a jump. Moreover he made his famous ‘jumping constant conjecture’, that for all r ≥ 3, every α ∈ [0, 1) is a jump. Frankl and Rödl [7] disproved this conjecture by giving a sequence of values of non-jumps for all r ≥ 3.

We use Razborov's flag algebra method [9] to show that jumps exist for r = 3 in the interval [2/9, 1). These are the first examples of jumps for any r ≥ 3 in the interval [r!/rr, 1). To be precise, we show that for r = 3 every α ∈ [0.2299, 0.2316) is a jump.

We also give an improved upper bound for the Turán density of K4− = {123, 124, 134}: π(K4−) ≤ 0.2871. This in turn implies that for r = 3 every α ∈ [0.2871, 8/27) is a jump.

Consider a randomly oriented graph G = (V, E) and let a, s and b be three distinct vertices in V. We study the correlation between the events {a → s} and {s → b}. We show that, counter-intuitively, when G is the complete graph Kn, n ≥ 5, then the correlation is positive. (It is negative for n = 3 and zero for n = 4.) We briefly discuss and pose problems for the same question on other graphs.

Yahya ould Hamidoune passed away in Paris on 11 March 2011 after a brief illness, leaving insufficient time for his friends and colleagues to express their indebtedness to him for his kindness and generosity, both in mathematics and in everyday life. Yahya was a discreet individual, always looking for the essential rather than the superficial, and certainly did not receive the recognition he deserved. May this modest testimony render justice to this singular man.

The cover time of a graph is a celebrated example of a parameter that is easy to approximate using a randomized algorithm, but for which no constant factor deterministic polynomial time approximation is known. A breakthrough due to Kahn, Kim, Lovász and Vu [25] yielded a (log logn)2 polynomial time approximation. We refine the upper bound of [25], and show that the resulting bound is sharp and explicitly computable in random graphs. Cooper and Frieze showed that the cover time of the largest component of the Erdős–Rényi random graph G(n, c/n) in the supercritical regime with c > 1 fixed, is asymptotic to ϕ(c)nlog2n, where ϕ(c) → 1 as c ↓ 1. However, our new bound implies that the cover time for the critical Erdős–Rényi random graph G(n, 1/n) has order n, and shows how the cover time evolves from the critical window to the supercritical phase. Our general estimate also yields the order of the cover time for a variety of other concrete graphs, including critical percolation clusters on the Hamming hypercube {0, 1}n, on high-girth expanders, and on tori ℤdn for fixed large d. This approach also gives a simpler proof of a result of Aldous [2] that the cover time of a uniform labelled tree on k vertices is of order k3/2. For the graphs we consider, our results show that the blanket time, introduced by Winkler and Zuckerman [45], is within a constant factor of the cover time. Finally, we prove that for any connected graph, adding an edge can increase the cover time by at most a factor of 4.

For an increasing monotone graph property the local resilience of a graph G with respect to is the minimal r for which there exists a subgraph H ⊆ G with all degrees at most r, such that the removal of the edges of H from G creates a graph that does not possess . This notion, which was implicitly studied for some ad hoc properties, was recently treated in a more systematic way in a paper by Sudakov and Vu. Most research conducted with respect to this distance notion focused on the binomial random graph model (n, p) and some families of pseudo-random graphs with respect to several graph properties, such as containing a perfect matching and being Hamiltonian, to name a few. In this paper we continue to explore the local resilience notion, but turn our attention to random and pseudo-random regular graphs of constant degree. We investigate the local resilience of the typical random d-regular graph with respect to edge and vertex connectivity, containing a perfect matching, and being Hamiltonian. In particular, we prove that for every positive ϵ and large enough values of d, with high probability, the local resilience of the random d-regular graph, n, d, with respect to being Hamiltonian, is at least (1−ϵ)d/6. We also prove that for the binomial random graph model (n, p), for every positive ϵ > 0 and large enough values of K, if p > then, with high probability, the local resilience of (n, p) with respect to being Hamiltonian is at least (1−ϵ)np/6. Finally, we apply similar techniques to positional games, and prove that if d is large enough then, with high probability, a typical random d-regular graph G is such that, in the unbiased Maker–Breaker game played on the edges of G, Maker has a winning strategy to create a Hamilton cycle.

Let P be a set of n points in ℝ3, and let k ≤ n be an integer. A sphere σ is k-rich with respect to P if |σ ∩ P| ≥ k, and is η-non-degenerate, for a fixed fraction 0 < η < 1, if no circle γ ⊂ σ contains more than η|σ ∩ P| points of P.

We improve the previous bound given in [1] on the number of k-rich η-non-degenerate spheres in 3-space with respect to any set of n points in ℝ3, from O(n4/k5 + n3/k3), which holds for all 0 < η < 1/2, to O*(n4/k11/2 + n2/k2), which holds for all 0 < η < 1 (in both bounds, the constants of proportionality depend on η). The new bound implies the improved upper bound O*(n58/27) ≈ O(n2.1482) on the number of mutually similar triangles spanned by n points in ℝ3; the previous bound was O(n13/6) ≈ O(n2.1667) [1].

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.

The line graph G of a directed graph G has a vertex for every edge of G and an edge for every path of length 2 in G. In 1967, Knuth used the Matrix Tree Theorem to prove a formula for the number of spanning trees of G, and he asked for a bijective proof [6]. In this paper, we give a bijective proof of Knuth's formula. As a result of this proof, we find a bijection between binary de Bruijn sequences of degree n and binary sequences of length 2n−1. Finally, we determine the critical groups of all the Kautz graphs and de Bruijn graphs, generalizing a result of Levine [7].

Philippe Flajolet, mathematician and computer scientist extraordinaire, the father of analytic combinatorics, suddenly passed away on 22 March 2011, at the prime of his career. He is celebrated for opening new lines of research in the analysis of algorithms, developing powerful new methods, and solving difficult open problems. His research contributions will have an impact for generations, and his approach to research, based on curiosity, discriminating taste, broad knowledge and interests, intellectual integrity, and a genuine sense of camaraderie, will serve as an inspiration to those who knew him, for years to come.

We develop lower bounds on the Hadwiger number h(G) of graphs G with high chromatic number. In particular, if G has n vertices and chromatic number k then h(G) ≥ (4k − n)/3.

The Turán number of a graph H, ex(n, H), is the maximum number of edges in any graph on n vertices which does not contain H as a subgraph. Let Pl denote a path on l vertices, and let k ⋅ Pl denote k vertex-disjoint copies of Pl. We determine ex(n, k ⋅ P3) for n appropriately large, answering in the positive a conjecture of Gorgol. Further, we determine ex(n, k ⋅ Pl) for arbitrary l, and n appropriately large relative to k and l. We provide some background on the famous Erdős–Sós conjecture, and conditional on its truth we determine ex(n, H) when H is an equibipartite forest, for appropriately large n.

Consider the barycentric subdivision which cuts a given triangle along its medians to produce six new triangles. Uniformly choosing one of them and iterating this procedure gives rise to a Markov chain. We show that, almost surely, the triangles forming this chain become flatter and flatter in the sense that their isoperimetric values go to infinity with time. Nevertheless, if the triangles are renormalized through a similitude to have their longest edge equal to [0, 1] ⊂ ℂ (with 0 also adjacent to the shortest edge), their aspect does not converge and we identify the limit set of the opposite vertex with the segment [0, 1/2]. In addition we prove that the largest angle converges to π in probability. Our approach is probabilistic, and these results are deduced from the investigation of a limit iterated random function Markov chain living on the segment [0, 1/2]. The stationary distribution of this limit chain is particularly important in our study.

Dubhashi, Jonasson and Ranjan Dubhashi, Jonasson and Ranjan (2007) study the negative dependence properties of Srinivasan's sampling processes (SSPs), random processes which sample sets of a fixed size with prescribed marginals. In particular they prove that linear SSPs have conditional negative association, by using the Feder–Mihail theorem and a coupling argument. We consider a broader class of SSPs that we call tournament SSPs (TSSPs). These have a tree-like structure and we prove that they have conditional negative association. Our approach is completely different from that of Dubhashi, Jonasson and Ranjan. We give an abstract characterization of TSSPs, and use this to deduce that certain conditioned TSSPs are themselves TSSPs. We show that TSSPs have negative association, and hence conditional negative association. We also give an example of an SSP that does not have negative association.

We offer a unified approach to the theory of concave majorants of random walks, by providing a path transformation for a walk of finite length that leaves the law of the walk unchanged whilst providing complete information about the concave majorant. This leads to a description of a walk of random geometric length as a Poisson point process of excursions away from its concave majorant, which is then used to find a complete description of the concave majorant of a walk of infinite length. In the case where subsets of increments may have the same arithmetic mean, we investigate three nested compositions that naturally arise from our construction of the concave majorant.

Let I be an independent set drawn from the discrete d-dimensional hypercube Qd = {0, 1}d according to the hard-core distribution with parameter λ > 0 (that is, the distribution in which each independent set I is chosen with probability proportional to λ|I|). We show a sharp transition around λ = 1 in the appearance of I: for λ > 1, min{|I ∩ Ɛ|, |I ∩ |} = 0 asymptotically almost surely, where Ɛ and are the bipartition classes of Qd, whereas for λ < 1, min{|I ∩ Ɛ|, |I ∩ |} is asymptotically almost surely exponential in d. The transition occurs in an interval whose length is of order 1/d.

A key step in the proof is an estimation of Zλ(Qd), the sum over independent sets in Qd with each set I given weight λ|I| (a.k.a. the hard-core partition function). We obtain the asymptotics of Zλ(Qd) for , and nearly matching upper and lower bounds for , extending work of Korshunov and Sapozhenko. These bounds allow us to read off some very specific information about the structure of an independent set drawn according to the hard-core distribution.

We also derive a long-range influence result. For all fixed λ > 0, if I is chosen from the independent sets of Qd according to the hard-core distribution with parameter λ, conditioned on a particular v ∈ Ɛ being in I, then the probability that another vertex w is in I is o(1) for w ∈ but Ω(1) for w ∈ Ɛ.

We show that a set A ⊂ {0, 1}n with edge-boundary of size at most can be made into a subcube by at most (2ε/log2(1/ε))|A| additions and deletions, provided ε is less than an absolute constant.

We deduce that if A ⊂ {0, 1}n has size 2t for some t ∈ ℕ, and cannot be made into a subcube by fewer than δ|A| additions and deletions, then its edge-boundary has size at least provided δ is less than an absolute constant. This is sharp whenever δ = 1/2j for some j ∈ {1, 2, . . ., t}.

The asymptotics of 2-colour Ramsey numbers of loose and tight cycles in 3-uniform hypergraphs were recently determined [16, 17]. We address the same problem for Berge cycles and for 3 colours. Our main result is that the 3-colour Ramsey number of a 3-uniform Berge cycle of length n is asymptotic to . The result is proved with the Regularity Lemma via the existence of a monochromatic connected matching covering asymptotically 4n/5 vertices in the multicoloured 2-shadow graph induced by the colouring of Kn(3).