The theorems of Hindman and van der Waerden belong to the classical theorems of partition Ramsey Theory. The Central Sets Theorem is a strong simultaneous extension of both theorems that applies to general commutative semigroups. We give a common extension of the Central Sets Theorem and Ramsey's theorem.

We derive identities for the probability that at least a1 and at least a2, and for the probability that exactly a1 and exactly a2, out of n and N events occur (1 ≤ a1 ≤ n, 1 ≤ a2 ≤ N). From this, we produce multivariate permutation hybrid upper bounds, and a multivariate Bonferroni-type upper bound which includes Galambos and Xu's [2] optimal result. The methodology generalizes that of Hoppe and Seneta [3, §5]. A numerical example is given.

We call a graph H Ramsey-unsaturated if there is an edge in the complement of H such that the Ramsey number r(H) of H does not change upon adding it to H. This notion was introduced by Balister, Lehel and Schelp in [J. Graph Theory51 (2006), pp. 22–32], where it is shown that cycles (except for C4) are Ramsey-unsaturated, and conjectured that, moreover, one may add any chord without changing the Ramsey number of the cycle Cn, unless n is even and adding the chord creates an odd cycle.

We prove this conjecture for large cycles by showing a stronger statement. If a graph H is obtained by adding a linear number of chords to a cycle Cn, then r(H)=r(Cn), as long as the maximum degree of H is bounded, H is either bipartite (for even n) or almost bipartite (for odd n), and n is large.

This motivates us to call cycles strongly Ramsey-unsaturated. Our proof uses the regularity method.

A Steiner quadruple system SQS(v) of order v is a family ℬ of 4-element subsets of a v-element set V such that each 3-element subset of V is contained in precisely one B ∈ ℬ. We prove that if T ∩ B ≠ ø for all B ∈ ℬ (i.e., if T is a transversal), then |T| ≥ v/2, and if T is a transversal of cardinality exactly v/2, then V \ T is a transversal as well (i.e., T is a blocking set). Also, in respect of the so-called ‘doubling construction’ that produces SQS(2v) from two copies of SQS(v), we give a necessary and sufficient condition for this operation to yield a Steiner quadruple system with blocking sets.

Let G=(V, E) be a simple connected graph of order [mid ]V[mid ]=n[ges ]2 and minimum degree δ, and let 2[les ]s[les ]n. We define two parameters, the s-average distance μs(G) and the s-average nearest neighbour distance Λs(G), with respect to each of which V contains an extremal subset X of order s with vertices ‘as spread out as possible’ in G. We compute the exact values of both parameters when G is the cycle Cn, and show how to obtain the corresponding optimal arrangements of X. Sharp upper and lower bounds are then established for Λs(G), as functions of s, n and δ, and the extremal graphs described.

We consider unlabelled flowgraphs for a model of binary logic without the constraints of structured programming. The number of such flowgraphs is asymptotic to (3.4n)n/2, where n is the number of nodes in the flowgraph. This is to be compared with bounds of between (8.8)n/2 and of (9.8)n/2 for unlabelled structured flowgraphs of the Böhm and Jacopini type. Of the space of flowgraphs we study, 41% are prime, that is contain no proper sub-flowgraphs. The main obstructions to primality being the Dijkstra-structures, which are based on If_Then_Else and Do_While constructs.

We show that, for every positive integer c*, there is an integer n such that, if M is a matroid whose largest cocircuit has size c*, then E(M) can be partitioned into two sets E1 and E2 such that every connected component of each of M[mid ]E1 and M[mid ]E2 has at most n elements.

A transformation that increases the blocking probability of the channel graphs arising in interconnection networks is developed. This provides the basis for eminently computing a bound on the blocking probability by applying the transformation to reduce an arbitrary four-stage channel graph to a threshold channel graph. The four-stage channel graph that is most likely to block, given links that are equally likely to block, is characterized. Partial results are proved concerning the threshold channel graphs that are least likely to block.

We investigate the asymptotic version of the Erdős–Ko–Rado theorem for the random k-uniform hypergraph $\mathcal{H}$k(n, p). For 2⩽k(n) ⩽ n/2, let $N=\binom{n}k$ and $D=\binom{n-k}k$. We show that with probability tending to 1 as n → ∞, the largest intersecting subhypergraph of $\mathcal{H}$ has size

$$(1+o(1))p\ffrac kn N$$

$$p\gg \ffrac nk\ln^2\biggl(\ffrac nk\biggr)D^{-1}.$$

A different behaviour occurs when k = o(n). In this case, the lower bound on p is almost optimal. Further, for the small interval D−1 ≪ p ⩽ (n/k)1−ϵD−1, the largest intersecting subhypergraph of $\mathcal{H}$k(n, p) has size Θ(ln(pD)ND−1), provided that $k \gg \sqrt{n \ln n}$.

Together with previous work of Balogh, Bohman and Mubayi, these results settle the asymptotic size of the largest intersecting family in $\mathcal{H}$k, for essentially all values of p and k.

A family of subsets of an n-set is k-locally thin if, for every k-tuple of its members, the ground set has at least one element contained in exactly one of them. For k = 5 we derive a new exponential upper bound for the maximum size of these families. This implies the same bound for all odd values of k > 3. Our proof uses the graph entropy bounding technique to exploit a self-similarity in the structure of the hypergraph associated with such set families.

We show that if G is a simple outerplanar graph and H is a graph with the same Tutte polynomial as G, then H is also outerplanar. Examples show that the condition of G being simple cannot be omitted.

We analyse the behaviour of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field $\mathbb{F}_{q}$ of q elements when the highest degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f that are relatively prime with g and for the average degree of $\gcd(g,f)$ . We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.

We consider redundant binary joint digital expansions of integer vectors. The redundancy is used to minimize the Hamming weight, i.e., the number of non-zero digit vectors. This leads to efficient linear combination algorithms in abelian groups, which are used in elliptic curve cryptography, for instance.

If the digit set is a set of contiguous integers containing zero, a special syntactical condition is known to minimize the weight. We analyse the optimal weight of all non-negative integer vectors with maximum entry less than N. The expectation and the variance are given with a main term and a periodic fluctuation in the second-order term. Finally, we prove asymptotic normality.

We consider the asymptotics of the difference between the empirical measures of the β-Hermite tridiagonal matrix and its minor. We prove that this difference has a deterministic limit and Gaussian fluctuations. Through a correspondence between measures and continual Young diagrams, this deterministic limit is identified with the Vershik–Kerov–Logan–Shepp curve. Moreover, the Gaussian fluctuations are identified with a sectional derivative of the Gaussian free field.

The discrete cube {0, 1}d is a fundamental combinatorial structure. A subcube of {0, 1}d is a subset of 2k of its points formed by fixing k coordinates and allowing the remaining d − k to vary freely. This paper is concerned with patterns of intersections among subcubes of the discrete cube. Two sample questions along these lines are as follows: given a family of subcubes in which no r + 1 of them have non-empty intersection, how many pairwise intersections can we have? How many subcubes can we have if among them there are no k which have non-empty intersection and no l which are pairwise disjoint?

These questions are naturally expressed using intersection graphs. The intersection graph of a family of sets has one vertex for each set in the family with two vertices being adjacent if the corresponding subsets intersect. Let $\I(n,d)$ be the set of all n vertex graphs which can be represented as the intersection graphs of subcubes in {0, 1}d. With this notation our first question above asks for the largest number of edges in a Kr+1-free graph in $\I(n,d)$. As such it is a Turán-type problem. We answer this question asymptotically for some ranges of r and d. More precisely we show that if $(k+1)2^{\lfloor\frac{d}{k+1}\rfloor}<n\leq k2^{\lfloor\frac{d}{k}\rfloor}$ for some integer k ≥ 2 then the maximum edge density is $\bigl(1-\frac{1}{k}-o(1)\bigr)$ provided that n is not too close to the lower limit of the range.

The second question can be thought of as a Ramsey-type problem. The maximum such n can be defined in the same way as the usual Ramsey number but only considering graphs which are in $\I(n,d)$. We give bounds for this maximum n mainly concentrating on the case that l is fixed, and make some comparisons with the usual Ramsey number.

We prove that if a unimodular random graph is almost surely planar and has finite expected degree, then it has a combinatorial embedding into the plane which is also unimodular. This implies the claim in the title immediately by a theorem of Angel, Hutchcroft, Nachmias and Ray [2]. Our unimodular embedding also implies that all the dichotomy results of [2] about unimodular maps extend in the one-ended case to unimodular random planar graphs.

A set A is called universal sum-free if, for every finite 0–1 sequence χ = (e1, …, en), either

(i) there exist i, j, where 1[les ]j<i[les ]n, such that ei = ej = 1 and i − j∈A, or

(ii) there exists t∈N such that, for 1[les ]i[les ]n, we have t + i∈A if and only if ei = 1.

It is proved that the density of each universal sum-free set is zero, which settles a problem of Cameron.

A definition is adopted for convexity of a set of directed lines in the plane. Following this, the duals of a number of standard problems of geometric probability are formulated. Problems considered in detail are the duals of Sylvester's problem, chord length distributions and Ambartzumian's combinatorial geometry. The paper suggests some questions for further work.

Let $${{\mathcal G}_{n,r,s}}$$ denote a uniformly random r-regular s-uniform hypergraph on the vertex set {1, 2, … , n}. We establish a threshold result for the existence of a spanning tree in $${{\mathcal G}_{n,r,s}}$$, restricting to n satisfying the necessary divisibility conditions. Specifically, we show that when s ≥ 5, there is a positive constant ρ(s) such that for any r ≥ 2, the probability that $${{\mathcal G}_{n,r,s}}$$ contains a spanning tree tends to 1 if r > ρ(s), and otherwise this probability tends to zero. The threshold value ρ(s) grows exponentially with s. As $${{\mathcal G}_{n,r,s}}$$ is connected with probability that tends to 1, this implies that when r ≤ ρ(s), most r-regular s-uniform hypergraphs are connected but have no spanning tree. When s = 3, 4 we prove that $${{\mathcal G}_{n,r,s}}$$ contains a spanning tree with probability that tends to 1, for any r ≥ 2. Our proof also provides the asymptotic distribution of the number of spanning trees in $${{\mathcal G}_{n,r,s}}$$ for all fixed integers r, s ≥ 2. Previously, this asymptotic distribution was only known in the trivial case of 2-regular graphs, or for cubic graphs.