The lifetime of a player is defined to be the time where he gets his b-th hit, where a hit will occur with probability p. We consider the maximum statistics of N independent players. For b≠1 this is significantly more difficult than the known instance b=1. The expected value of the maximum lifetime of N players is given by logQN+(b−1)logQ logQN+ smaller order terms, where Q=1/(1−p).

Mauduit and Sárközy introduced and studied certain numerical parameters associated to finite binary sequences $E_N\in\{-1,1\}^N$ in order to measure their ‘level of randomness’. Two of these parameters are the normality measure$\cal{N}(E_N)$ and the correlation measure$C_k(E_N)$of order k, which focus on different combinatorial aspects of $E_N$. In their work, amongst others, Mauduit and Sárközy investigated the minimal possible value of these parameters.

In this paper, we continue the work in this direction and prove a lower bound for the correlation measure $C_k(E_N)$ (k even) for arbitrary sequences $E_N$, establishing one of their conjectures. We also give an algebraic construction for a sequence $E_N$ with small normality measure $\cal{N}(E_N)$.

In 1978 Erdős, Faudree, Rousseau and Schelp conjectured that \[ r ( C_{p},K_{r} ) = ( p-1 ) (r-1) +1 \] for every $p\,{\geq}\,r\,{\geq}\,3$, except for $p\,{=}\,q\,{=}\,3$. This has been proved for $r\,{\leq}\,6$, and for \[ p \geq r^{2}-2r\].

In this note we prove the conjecture for $p\,{\geq}\,4r+2$.

For a graph G and an integer t we let mcct(G) be the smallest m such that there exists a colouring of the vertices of G by t colours with no monochromatic connected subgraph having more than m vertices. Let be any non-trivial minor-closed family of graphs. We show that mcc2(G) = O(n2/3) for any n-vertex graph G ∈ . This bound is asymptotically optimal and it is attained for planar graphs. More generally, for every such , and every fixed t we show that mcct(G)=O(n2/(t+1)). On the other hand, we have examples of graphs G with no Kt+3 minor and with mcct(G)=Ω(n2/(2t−1)).

It is also interesting to consider graphs of bounded degrees. Haxell, Szabó and Tardos proved mcc2(G) ≤ 20000 for every graph G of maximum degree 5. We show that there are n-vertex 7-regular graphs G with mcc2(G)=Ω(n), and more sharply, for every ϵ > 0 there exists cϵ > 0 and n-vertex graphs of maximum degree 7, average degree at most 6 + ϵ for all subgraphs, and with mcc2(G) ≥ cϵn. For 6-regular graphs it is known only that the maximum order of magnitude of mcc2 is between and n.

We also offer a Ramsey-theoretic perspective of the quantity mcct(G).

Thinking of a deterministic function s: ℤ → ℕ as ‘scenery’ on the integers, a simple random walk on ℤ generates a random record of scenery ‘observed’ along the walk. We address this question: If t:ℤ → ℕ is another scenery on the integers and we are handed a random scenery record obtained from either s or t, under what circumstances can the source be distinguished? We allow ourselves to use information about s and t together with information contained in the scenery record. It has been conjectured that it is sufficient for t to be neither a translate of s nor a translate of the reflection of s. We show that this condition is sufficient to ensure distinguishability if s−1(δ) is finite and non-empty for some δ ∈ℕ.

The notion of the influence of a variable on a Boolean function on a product space has attracted much attention in combinatorics, computer science and other fields. Two of the basic papers dealing with this notion are by Kahn, Kalai and Linial (KKL) and Bourgain, Kahn, Kalai, Katznelson and Linial (BKKKL).

In this paper we survey the results in those papers and offer some simpler proofs, corrections, and extensions of the theorems presented there. We present several related open problems.

A famous result of Freĭman describes the sets A, of integers, for which |A+A| ≤ K|A|. In this short note we address the analogous question for subsets of vector spaces over . Specifically we show that if A is a subset of a vector space over with |A+A| ≤ K|A| then A is contained in a coset of size at most 2O(K3/2 log K)|A|, which improves upon the previous best, due to Green and Ruzsa, of 2O(K2)|A|. A simple example shows that the size may need to be at least 2Ω(K)|A|.

We show that for each α>0 every sufficiently large oriented graph G with δ+(G), δ−(G)≥3|G|/8+α|G| contains a Hamilton cycle. This gives an approximate solution to a problem of Thomassen [21]. In fact, we prove the stronger result that G is still Hamiltonian if δ(G)+δ+(G)+δ−(G)≥3|G|/2 + α|G|. Up to the term α|G|, this confirms a conjecture of Häggkvist [10]. We also prove an Ore-type theorem for oriented graphs.

Consider the following one-player game. Starting with the empty graph on n vertices, in every step a new edge is drawn uniformly at random and inserted into the current graph. This edge has to be coloured immediately with one of r available colours. The player's goal is to avoid creating a monochromatic copy of some fixed graph F for as long as possible. We prove a lower bound of nβ(F,r) on the typical duration of this game, where β(F,r) is a function that is strictly increasing in r and satisfies limr→∞ β(F,r) = 2 − 1/m2(F), where n2−1/m2(F) is the threshold of the corresponding offline colouring problem.

Consider a uniform random rooted labelled tree on n vertices. We imagine that each node of the tree has space for a single car to park. A number m ≤ n of cars arrive one by one, each at a node chosen independently and uniformly at random. If a car arrives at a space which is already occupied, it follows the unique path towards the root until it encounters an empty space, in which case it parks there; if there is no empty space, it leaves the tree. Consider m = ⌊α n⌋ and let An,α denote the event that all ⌊α n⌋ cars find spaces in the tree. Lackner and Panholzer proved (via analytic combinatorics methods) that there is a phase transition in this model. Then if α ≤ 1/2, we have $\mathbb{P}({A_{n,\alpha}}) \to {\sqrt{1-2\alpha}}/{(1-\alpha})$, whereas if α > 1/2 we have $\mathbb{P}({A_{n,\alpha}}) \to 0$. We give a probabilistic explanation for this phenomenon, and an alternative proof via the objective method. Along the way, we consider the following variant of the problem: take the tree to be the family tree of a Galton–Watson branching process with Poisson(1) offspring distribution, and let an independent Poisson(α) number of cars arrive at each vertex. Let X be the number of cars which visit the root of the tree. We show that $\mathbb{E}{[X]}$ undergoes a discontinuous phase transition, which turns out to be a generic phenomenon for arbitrary offspring distributions of mean at least 1 for the tree and arbitrary arrival distributions.

We prove results about the Lp-almost-periodicity of convolutions. One of these follows from a simple but rather general lemma about approximating a sum of functions in Lp, and gives a very short proof of a theorem of Green that if A and B are subsets of {1,. . .,N} of sizes αN and βN then A+B contains an arithmetic progression of length at least

\begin{equation} \exp ( c (\alpha \beta \log N)^{1/2} - \log\log N). \end{equation}

\begin{equation} \exp\biggl( c \biggl(\frac{\alpha \log N}{\log^3 2\beta^{-1}} \biggr)^{1/2} - \log( \beta^{-1} \log N) \biggr). \end{equation}

A graph G is called an H-type graph for some graph H if there is a mapping from V(G) to V(H) preserving edges. In this paper, we shall prove that: (1) every triangle-free graph G of order n with χ(G)[les ]3 and δ(G)>n/3 is of Fd-type for some d[ges ]1, where Fd is a certain d-regular triangle-free Hamiltonian Cayley graph of order 3d−1, (2) every triangle-free graph G of order n with χ(G)[ges ]4 and δ(G)>n/3 contains the Mycielski graph (see Figure 2) as a subgraph.

We prove that a bipartite uniquely Hamiltonian graph has a vertex of degree 2 in each color class. As consequences, every bipartite Hamiltonian graph of minimum degree d has at least 21−dd! Hamiltonian cycles, and every bipartite Hamiltonian graph of minimum degree at least 4 and girth g has at least (3/2)g/8 Hamiltonian cycles. We indicate how the existence of more than one Hamiltonian cycle may lead to a general reduction method for Hamiltonian graphs.

It has been shown [2] that if n is odd and m1,…,mt are integers with mi[ges ]3 and [sum ]i=1tmi=|E(Kn)| then Kn can be decomposed as an edge-disjoint union of closed trails of lengths m1,…,mt. This result was later generalized [3] to all sufficiently dense Eulerian graphs G in place of Kn. In this article we consider the corresponding questions for directed graphs. We show that the complete directed graph <?TeX \displaystyle{\mathop{K}^{\raise-2pt\hbox{$\scriptstyle\leftrightarrow$}}}_{n}?> can be decomposed as an edge-disjoint union of directed closed trails of lengths m1,…,mt whenever mi[ges ]2 and <?TeX \sum_{i=1}^t m_{i}=\vert E({\leftrightarrow}_{n})\vert ?>, except for the single case when n=6 and all mi=3. We also show that sufficiently dense Eulerian digraphs can be decomposed in a similar manner, and we prove corresponding results for (undirected) complete multigraphs.

We prove that there exists a constant c such that, for any integer Δ, the Ramsey number of a bipartite graph on n vertices with maximum degree Δ is less than 2cΔn. A probabilistic argument due to Graham, Rödl and Ruciński implies that this result is essentially sharp, up to the constant c in the exponent. Our proof hinges upon a quantitative form of a hypergraph packing result of Rödl, Ruciński and Taraz.

We show that symmetry, represented by a graph's automorphism group, can be used to greatly reduce the computational work for the substitution method. This allows application of the substitution method over larger regions of the problem lattices, resulting in tighter bounds on the percolation threshold $p_c$. We demonstrate the symmetry reduction technique using bond percolation on the $(3,12^2)$ lattice, where we improve the bounds on $p_c$ from (0.738598,0.744900) to (0.739399,0.741757), a reduction of more than 62% in width, from 0.006302 to 0.002358.

A graph G is m-choosable with impropriety d, or simply (m, d)*-choosable, if, for every list assignment L, where [mid ]L(v)[mid ][ges ]m for every v∈V(G), there exists an L-colouring of G such that each vertex of G has at most d neighbours coloured with the same colour as itself. We prove a Grötzsch-type theorem for list colourings with impropriety one, that is, the (3, 1)*-choosability for triangle-free planar graphs; in the proof the method of extending a precolouring of a 4- or 5-cycle is used.

We provide an alternative, simpler and more general derivation of the Clarkson–Shor probabilistic technique [7] and use it to obtain several extensions and new combinatorial bounds.

The notion of conductance introduced by Jerrum and Sinclair [8] has been widely used to prove rapid mixing of Markov chains. Here we introduce a bound that extends this in two directions. First, instead of measuring the conductance of the worst subset of states, we bound the mixing time by a formula that can be thought of as a weighted average of the Jerrum–Sinclair bound (where the average is taken over subsets of states with different sizes). Furthermore, instead of just the conductance, which in graph theory terms measures edge expansion, we also take into account node expansion. Our bound is related to the logarithmic Sobolev inequalities, but it appears to be more flexible and easier to compute.

In the case of random walks in convex bodies, we show that this new bound is better than the known bounds for the worst case. This saves a factor of $O(n)$ in the mixing time bound, which is incurred in all proofs as a ‘penalty’ for a ‘bad start’. We show that in a convex body in $\mathbb{R}^n$, with diameter $D$, random walk with steps in a ball with radius $\delta$ mixes in $O^*(nD^2/\delta^2)$ time (if idle steps at the boundary are not counted). This gives an $O^*(n^3)$ sampling algorithm after appropriate preprocessing, improving the previous bound of $O^*(n^4)$.

The application of the general conductance bound in the geometric setting depends on an improved isoperimetric inequality for convex bodies.

We prove that every connected graph of order n ≥ 2 has an induced subgraph with all degrees odd of order at least cn/log n, where cis a constant. We also give a bound in terms of chromatic number, and resolve the analogous problem for random graphs.