Let TBin(N, n, q) be the game on the complete graph KN in which two players, the Breaker and the Maker, alternately claim one and q edges, respectively. The Maker's aim is to build a binary tree on n<N vertices in n−1 turns while the Breaker tries to prevent him from doing so. It is shown that, for every constant ε>0, there exists n0 such that, for every n[ges ]n0, the Breaker has a winning strategy in TBin(N, n, q) if q>(1+ε)N/logn, while, for q<(1−ε)N/logn, the game TBin(N, n, q) can be won by the Maker provided that n=o(N).

Stacks which allow elements to be pushed into any of the top r positions and popped from any of the top s positions are studied. An asymptotic formula for the number un of permutations of length n sortable by such a stack is found in the cases r=1 or s=1. This formula is found from the generating function of un. The sortable permutations are characterized if r=1 or s=1 or r=s=2 by a forbidden subsequence condition.

Consider the complete n-graph with independent exponential (mean n) edge-weights. Let M(c, n) be the maximal size of subtree for which the average edge-weight is at most c. It is shown that M(c, n) makes the transition from o(n) to Ω(n) around some critical value c(0), which can be specified in terms of a fixed point of a mapping on probability distributions.

In this paper we will give all Ramsey numbers r(K3, G) for connected graphs G of order 7 and 8. For smaller orders and non-connected graphs of order up to 8, the number of graphs with given Ramsey number is listed for all possible values.

We give a characterization for isoperimetric invariants, including the Cheeger constant and the isoperimetric number of a graph. This leads to an isoperimetric inequality for the Cartesian products of graphs.

To bound the probability of a union of n events from a single set of events, Bonferroni inequalities are sometimes used. There are sharper bounds which are called Sobel–Uppuluri–Galambos inequalities. When two (or more) sets of events are involved, bounds are considered on the probability of intersection of several such unions, one union from each set. We present a method for unified treatment of bivariate lower and upper bounds in this note. The lower bounds obtained are new and at least as good as lower bounds appearing in the literature so far. The upper bounds coincide with existing bivariate Sobel–Uppuluri–Galambos type upper bounds derived by the method of indicator functions. A numerical example is given to illustrate that the new lower bounds can be strictly better than existing ones.

Let a, b and n be integers with 2[les ]a[les ]b and n[ges ]a+b. Suppose that [Ascr ]⊂([n]a) and [Bscr ]⊂([n]b) are nontrivial cross-intersecting families. Then [mid ][Ascr ][mid ]+[mid ][Bscr ][mid ][les ]2+(nb) −2(n−ab)+ (n−2ab). This result is best possible.

Consider first-passage percolation on the square lattice. Welsh, who together with Hammersley introduced the subject in 1963, has formulated a problem about mean first-passage times, which, although seemingly simple, has not been proved in any non-trivial case. In this paper we give a general proof of Welsh's problem.

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

Let k be a positive integer and G a finite abelian group of order n, where n[ges ]k2−4k+8. Then every sequence of 2n−¼k2+k−2 elements in G assuming k distinct values has an n-subsequence with sum zero. This settles a conjecture of Bialostocki and Lotspeich.

Let T be a semicomplete digraph on n vertices. Let ak(T) denote the minimum number of arcs whose addition to T results in a k-connected semicomplete digraph and let rk(T) denote the minimum number of arcs whose reversal in T results in a k-connected semicomplete digraph. We prove that if n[ges ]3k−1, then ak(T)=rk(T). We also show that this bound on n is best possible.

Let f(n, k, l) be the expected length of a longest common subsequence of l sequences of length n over an alphabet of size k. It is known that there are constants γ(l)k such that f(n, k, l)→ γ(l)kn as n→∞, and we show that γ(l)k= Θ(k1/l−1) as k→∞. Bounds for the corresponding constants for the expected length of a shortest common supersequence are also presented.

For any integer k, we prove the existence of a uniquely k-colourable graph of girth at least g on at most k12(g+1) vertices whose maximal degree is at most 5k13. From this we deduce that, unless NP=RP, no polynomial time algorithm for k-Colourability on graphs G of girth g(G)[ges ]log[mid ]G[mid ]/13logk and maximum degree Δ(G)[les ]6k13 can exist. We also study several related problems.

We show that if S1 is a strongly complete sum-free set of positive integers, and if S0 is a finite sum-free set, then, with positive probability, a random sum-free set U contains S0 and is contained in S0∪S1. As a corollary we show that, with positive probability, 2 is the only even element of a random sum-free set.

The cover time, C, for a simple random walk on a realization, GN, of [Gscr ](N, p), the random graph on N vertices where each two vertices have an edge between them with probability p independently, is studied. The parameter p is allowed to decrease with N and p is written on the form f(N)/N, where it is assumed that f(N)[ges ]c log N for some c>1 to asymptotically ensure connectedness of the graph. It is shown that if f(N) is of higher order than log N, then, with probability 1−o(1), (1−ε)N log N[les ]E[C[mid ]GN] [les ](1+ε)N log N for any fixed ε>0, whereas if f(N)=O(log N), there exists a constant a>0 such that, with probability 1−o(1), E[C[mid ]GN] [ges ](1+a)N log N. It is furthermore shown that if f(N) is of higher order than (log N)3 then Var(C[mid ]GN)= o((N log N)2) with probability 1−o(1), so that with probability 1−o(1), the stronger statement that (1−ε)N log N[les ]C[les ](1+ε)N log N holds.

Let M be a loopless matroid with rank r and c components. Let P(M, t) be the characteristic polynomial of M. We shall show that (−1)rP(M, t)[ges ](1−t)r for t∈(−∞, 1), that the multiplicity of the zeros of P(M, t) at t=1 is equal to c, and that (−1)r+cP(M, t)[ges ](t−1)r for t∈(1, 32/27]. Using a result of C. Thomassen we deduce that the maximal zero-free intervals for characteristic polynomials of loopless matroids are precisely (−∞, 1) and (1, 32/27].

A 2×2 table of nonnegative integers is subdivided additively into n 2×2 subtables of nonnegative integers in an arbitrary way. The first case of Simpson's Paradox (SP) occurs when the determinant of the original table is less than zero, but the determinant of each of the n 2×2 subtables is greater than or equal to zero. The second case of SP occurs when the previous inequalities hold with ‘less than’ and ‘greater than or equal’ replaced by ‘greater than’ and ‘less than or equal’, respectively. For the case n=2, this paper calculates the asymptotic proportion of the subdivisions of the original 2×2 table such that SP occurs. It is shown that this asymptotic proportion is bounded above by 1/12.

Deuber's theorem states that, given any m, p, c, r in IN, there exist n, q, μ in IN such that, whenever an (n, q, cμ)-set is r-coloured, there is a monochrome (m, p, c)-set. This theorem has been used in conjunction with the algebraic structure of the Stone–Čech compactification βIN of IN to derive several strengthenings of itself. We present here an algebraic proof of the main results in βIN and derive Deuber's theorem as a consequence.

The natural relations for sets are those definable in terms of the emptiness of the subsets corresponding to Boolean combinations of the sets. For pairs of sets, there are just five natural relations of interest, namely, strict inclusion in each direction, disjointness, intersection with the universe being covered, or not. Let N denote {1, 2, …, n} and (N2) denote {(i, j)[mid ]i, j∈N and i<j}. A function μ on (N2) specifies one of these relations for each pair of indices. Then μ is said to be consistent on M⊆N if and only if there exists a collection of sets corresponding to indices in M such that the relations specified by μ hold between each associated pair of the sets. Firstly, it is proved that if μ is consistent on all subsets of N of size three then μ is consistent on N. Secondly, explicit conditions that make μ consistent on a subset of size three are given as generalized transitivity laws. Finally, it is shown that the result concerning binary natural relations can be generalized to r-ary natural relations for arbitrary r[ges ]2.

It is shown that every partially ordered set with n elements admits an endomorphism with an image of a size at least n1/7 but smaller than n. We also prove that there exists a partially ordered set with n elements such that each of its non-trivial endomorphisms has an image of size O((n log n)1/3).