Häggkvist and Scott asked whether one can find a quadratic function q(k) such that, if G is a graph of minimum degree at least q(k), then G contains vertex-disjoint cycles of k consecutive even lengths. In this paper, it is shown that if G is a graph of average degree at least k2+19k+10 with sufficiently many vertices, then G contains vertex-disjoint cycles of k consecutive even lengths, answering the above question in the affirmative. The coefficient of k2 cannot be decreased and, in this sense, this result is best possible.

Let G denote a finite abelian group of order n and Davenport constant D, and put m = n + D − 1. Let x = (x1,. . .,xm) ∈ Gm. Gao's theorem states that there is a reordering (xj1, . . ., xjm) of x such that

Let w = (x1, . . ., wm) ∈ ℤm. As a corollary of the main result, we show that there are reorderings (xj1, . . ., xjm) of x and (wk1, . . ., wkm) of w, such that where xj1 is the most repeated value in x. For w = (1, . . ., 1), this result reduces to Gao's theorem.

A set of n triangles sharing a common edge is called a book with n pages and is denoted by $B_{n}$. It is known that the Ramsey number $r ( B_{n} ) $ satisfies $r ( B_{n} ) = ( 4+o ( 1 ) ) n.$ We show that every red–blue edge colouring of $K_{ \lfloor ( 4-\varepsilon ) n \rfloor }$ with no monochromatic $B_{n}$ exhibits quasi-random properties when $\varepsilon$ tends to 0. This implies that there is a constant $c>0$ such that for every red–blue edge colouring of $K_{r ( B_{n} ) }$ there is a monochromatic $B_{n}$ whose vertices span at least $ \lfloor cn^{2} \rfloor $ edges of the same colour as the book.

As an application we find the Ramsey number for a class of graphs.

Given a pair of graphs G and H, the Ramsey number R(G, H) is the smallest N such that every red–blue colouring of the edges of the complete graph KN contains a red copy of G or a blue copy of H. If a graph G is connected, it is well known and easy to show that R(G, H) ≥ (|G|−1)(χ(H)−1)+σ(H), where χ(H) is the chromatic number of H and σ(H) is the size of the smallest colour class in a χ(H)-colouring of H. A graph G is called H-good if R(G, H) = (|G|−1)(χ(H)−1)+σ(H). The notion of Ramsey goodness was introduced by Burr and Erdős in 1983 and has been extensively studied since then.

In this paper we show that if n≥ Ω(|H| log4 |H|) then every n-vertex bounded degree tree T is H-good. The dependency between n and |H| is tight up to log factors. This substantially improves a result of Erdős, Faudree, Rousseau, and Schelp from 1985, who proved that n-vertex bounded degree trees are H-good when n ≥ Ω(|H|4).

Let m,n and t be positive integers. Consider [m]n as the set of sequences of length n on an m-letter alphabet. We say that two subsets A⊂[m]n and B⊂[m]n cross t-intersect if any two sequences a∈A and b∈B match in at least t positions. In this case it is shown that if $m > (1-\frac 1{\sqrt[t]2})^{-1}$ then |A||B|≤(mn−t)2. We derive this result from a weighted version of the Erdős–Ko–Rado theorem concerning cross t-intersecting families of subsets, and we also include the corresponding stability statement. One of our main tools is the eigenvalue method for intersection matrices due to Friedgut [10].

We introduce and study the model of simply generated non-crossing partitions, which are, roughly speaking, chosen at random according to a sequence of weights. This framework encompasses the particular case of uniform non-crossing partitions with constraints on their block sizes. Our main tool is a bijection between non-crossing partitions and plane trees, which maps such simply generated non-crossing partitions into simply generated trees so that blocks of size k are in correspondence with vertices of out-degree k. This allows us to obtain limit theorems concerning the block structure of simply generated non-crossing partitions. We apply our results in free probability by giving a simple formula relating the maximum of the support of a compactly supported probability measure on the real line in terms of its free cumulants.

We show that the list chromatic number of a simple d-regular r-uniform hypergraph is at least (1/2r log(2r2) + o(1)) log d if d is large.

The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge. We say that a subset of vertices is j-independent if its intersection with any edge has size strictly less than j. The Kruskal–Katona theorem implies that in an r-uniform hypergraph with a fixed size and order, the hypergraph with the most r-independent sets is the lexicographic hypergraph. In this paper, we use a hypergraph regularity lemma, along with a technique developed by Loh, Pikhurko and Sudakov, to give an asymptotically best possible upper bound on the number of j-independent sets in an r-uniform hypergraph.

We show distributional results for the length of the longest matching consecutive subsequence between two independent sequences A1, A2, …, Am and B1, B2, …, Bn whose letters are taken from a finite alphabet. We assume that A1, A2, … are i.i.d. with distribution μ and B1, B2, … are i.i.d. with distribution ν. It is known that if μ and v are not too different, the Chen–Stein method for Poisson approximation can be used to establish distributional results. We extend these results beyond the region where the Chen–Stein method was previously successful. We use a combination of ‘matching by patterns’ results obtained by Arratia and Waterman [1], and the Chen–Stein method to show that the Poisson approximation can be extended. Our method explains how the matching is achieved. This provides an explanation for the formulas in Arratia and Waterman [1] and thus answers one of the questions posed in comment F19 in Aldous [2]. Furthermore, in the case where the alphabet consists of only two letters, the phase transition observed by Arratia and Waterman [1] for the strong law of large numbers extends to the distributional result. We conjecture that this phase transition on the distributional level holds for any finite alphabet.

In this work we give a study of generalizations of Stirling permutations, a restricted class of permutations of multisets introduced by Gessel and Stanley [15]. First we give several bijections between such generalized Stirling permutations and various families of increasing trees extending the known correspondences of [20, 21]. Then we consider several permutation statistics of interest for generalized Stirling permutations as the number of left-to-right minima, the number of left-to-right maxima, the number of blocks of specified sizes, the distance between occurrences of elements, and the number of inversions. For all these quantities we give a distributional study, where the established connections to increasing trees turn out to be very useful. To obtain the exact and limiting distribution results we use several techniques ranging from generating functions, connections to urn models, martingales and Stein's method.

Hadwiger's well known conjecture (see the survey of Toft [9]) states that any graph $G$ has a $K_{\chi(G)}$ minor, where $\chi(G)$ is the chromatic number of $G$. Let $\alpha(G)$ denote the independence (or stability) number of $G$, namely the maximum number of pairwise nonadjacent vertices in $G$. It was observed in [1], [4], [10] that via the inequality $\chi(G)\ge {|V(G)|\over \alpha(G)}$, Hadwiger's conjecture implies

Conjecture 1.1.Any graph G on n vertices contains a$K_{\lceil {n\over \alpha(G)}\rceil}$as a minor.

A cocircuit C* in a matroid M is said to be non-separating if and only if M[setmn ]C*, the deletion of C* from M, is connected. A vertex-triad in a matroid is a three-element non-separating cocircuit. Non-separating cocircuits in binary matroids correspond to vertices in graphs. Let C be a circuit of a 3-connected binary matroid M such that [mid ]E(M)[mid ][ges ]4 and, for all elements x of C, the deletion of x from M is not 3-connected. We prove that C meets at least two vertex-triads of M. This gives direct binary matroid generalizations of certain graph results of Halin, Lemos, and Mader. For binary matroids, it also generalizes a result of Oxley. We also prove that a minimally 3-connected binary matroid M which has at least four elements has at least ½r*(M)+1 vertex-triads, where r*(M) is the corank of the matroid M. An immediate consequence of this result is the following result of Halin: a minimally 3-connected graph with n vertices has at least 2n+6/5 vertices of degree three. We also generalize Tutte's Triangle Lemma for general matroids.

It has been conjectured by Alspach [2] that given integers n and m1, …, mt with 3 [les ] mi [les ] n and [sum ]ti=1mi = (n2) (n odd) or [sum ]ti=1mi = (n2) − n/2 (n even), then one can pack Kn (n odd) or Kn minus a 1-factor (n even) with cycles of lengths m1, …, mt. In this paper we show that if the cycle lengths mi are bounded by some linear function of n and n is sufficiently large then this conjecture is true.

A rational polyhedron$P\subseteq {\mathbb{R^n}}$ is a finite union of simplexes in ${\mathbb{R^n}}$ with rational vertices. P is said to be $\mathbb Z$-homeomorphic to the rational polyhedron $Q\subseteq {\mathbb{R^{\it m}}}$ if there is a piecewise linear homeomorphism η of P onto Q such that each linear piece of η and η−1 has integer coefficients. When n=m, $\mathbb Z$-homeomorphism amounts to continuous $\mathcal{G}_n$-equidissectability, where $\mathcal{G}_n=GL(n,\mathbb Z) \ltimes \mathbb Z^{n}$ is the affine group over the integers, i.e., the group of all affinities on $\mathbb{R^{n}}$ that leave the lattice $\mathbb Z^{n}$ invariant. $\mathcal{G}_n$ yields a geometry on the set of rational polyhedra. For each d=0,1,2,. . ., we define a rational measure λd on the set of rational polyhedra, and show that any two $\mathbb Z$-homeomorphic rational polyhedra $$P\subseteq {\mathbb{R^n}}$$ and $Q\subseteq {\mathbb{R^{\it m}}}$ satisfy $\lambda_d(P)=\lambda_d(Q)$. $\lambda_n(P)$ coincides with the n-dimensional Lebesgue measure of P. If 0 ≤ dim P=d < n then λd(P)>0. For rational d-simplexes T lying in the same d-dimensional affine subspace of ${\mathbb{R^{\it n}}, $\lambda_d(T)$$ is proportional to the d-dimensional Hausdorff measure of T. We characterize λd among all unimodular invariant valuations.

We study three quantities that can each be viewed as the time needed for a finite irreducible Markov chain to ‘forget’ where it started. One of these is the mixing time, the minimum mean length of a stopping rule that yields the stationary distribution from the worst starting state. A second is the forget time, the minimum mean length of any stopping rule that yields the same distribution from any starting state. The third is the reset time, the minimum expected time between independent samples from the stationary distribution.

Our main results state that the mixing time of a chain is equal to the mixing time of the time-reversed chain, while the forget time of a chain is equal to the reset time of the reverse chain. In particular, the forget time and the reset time of a time-reversible chain are equal. Moreover, the mixing time lies between absolute constant multiples of the sum of the forget time and the reset time.

We also derive an explicit formula for the forget time, in terms of the 'access times' introduced in [11]. This enables us to relate the forget and reset times to other mixing measures of the chain.

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.

Let G be a connected graph that is 2-cell embedded in a surface S, and let G* be its topological dual graph. We will define and discuss several matroids whose element set is E(G), for S homeomorphic to the plane, projective plane, or torus. We will also state and prove old and new results of the type that the dual matroid of G is the matroid of the topological dual G*.

A class of completely symmetric simple Venn diagrams for seven sets is constructed and displayed.

Given a digraph D, let δ0(D) := min{δ+(D), δ−(D)} be the minimum semi-degree of D. We show that every sufficiently large digraph D with δ0(D)≥n/2 + l −1 is l-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis [17]. We also determine the smallest minimum semi-degree which ensures that a sufficiently large digraph D is k-ordered, i.e., that for every sequence s1, . . ., sk of distinct vertices of D there is a directed cycle which encounters s1, . . ., sk in this order. This result will be used in [16].

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).