An intersecting system of type (∃, ∀, k, n) is a collection [ ]={[Fscr ]1, ..., [Fscr ]m} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair [Fscr ]i and [Fscr ]j of distinct members of [ ] there exists an A∈[Fscr ]i that intersects every B∈[Fscr ]j. Let In (∃, ∀, k) denote the maximum possible cardinality of an intersecting system of type (∃, ∀, k, n). Ahlswede, Cai and Zhang conjectured that for every k≥1, there exists an n0(k) so that In (∃, ∀, k)=(n−1/k−1) for all n>n0(k). Here we show that this is true for k≤3, but false for all k≥8. We also prove some related results.

A sharper form of the Szarek–Talagrand ‘isomorphic’ version of the Sauer–Shelah lemma is proved. Also we prove an analogous ‘isomorphic’ version of the Karpovsky–Milman lemma, which is a generalization of that due to Sauer and Shelah.

It is shown that if n>n0(d) then any d-regular graph G=(V, E) on n vertices contains a set of u=[lfloor ]n/2[rfloor ] vertices which is joined by at most (d/2−c√d)u edges to the rest of the graph, where c>0 is some absolute constant. This is tight, up to the value of c.

It is proved that the smallest cardinality among the maximal irredundant sets in an n–vertex graph with maximum degree Δ([ges ]2) is at least 2n/3Δ. This substantially improves a bound by Bollobás and Cockayne [1]. The class of graphs which attain this bound is characterised.

This paper is concerned with the analysis of locally time-synchronized slot systems for broadcast in packet radio networks. Local synchronization has been proposed in practice as less expensive than global synchronization over very wide areas, or over mobile networks. In the case of two locally coordinated groups of stations, under the assumption that the phase shift on the clocks between the two groups is random, it is shown that the probability of no collision is maximized when occupied slots within each group are chosen consecutively, regardless of the number of total slots, or the number of occupied slots in either group.

In this paper we consider the Markov process defined by

P1,1=1, Pn,[lscr ]=(1−λn,[lscr ]) ·Pn−1,[lscr ] +λn,[lscr ]−1 ·Pn−1,[lscr ]−1

for transition probabilities λn,[lscr ]=q[lscr ] and λn,[lscr ]=qn−1. We give closed forms for the distributions and the moments of the underlying random variables. Thereby we observe that the distributions can be easily described in terms of q-Stirling numbers of the second kind. Their occurrence in a purely time dependent Markov process allows a natural approximation for these numbers through the normal distribution. We also show that these Markov processes describe some parameters related to the study of random graphs as well as to the analysis of algorithms.

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

In generalisation of the beta law obtained under the GEM/Poisson–Dirichlet distribution in Hirth [12] we undertake here an analogous construction which results in the Dirichlet law. Our proof makes use of Hoppe's Pólya-like urn model in population genetics.

We explore the ‘Hausdorff dimension at infinity’ for self-affine carpets defined on the square lattice. This notion of dimension (due to Barlow and Taylor), which is the correct notion from a probabilistic perspective, differs for these sets from more ‘naive’ indices of fractal dimension.

Certain convergent search algorithms can be turned into chaotic dynamic systems by renormalisation back to a standard region at each iteration. This allows the machinery of ergodic theory to be used for a new probabilistic analysis of their behaviour. Rates of convergence can be redefined in terms of various entropies and ergodic characteristics (Kolmogorov and Rényi entropies and Lyapunov exponent). A special class of line-search algorithms, which contains the Golden-Section algorithm, is studied in detail. Their associated dynamic systems exhibit a Markov partition property, from which invariant measures and ergodic characteristics can be computed. A case is made that the Rényi entropy is the most appropriate convergence criterion in this environment.

It has been known for several years that the lattice of subspaces of a finite vector space has a decomposition into symmetric chains, i.e. a decomposition into disjoint chains that are symmetric with respect to the rank function of the lattice. This paper gives a positive answer to the long-standing open problem of providing an explicit construction of such a symmetric chain decomposition for a given lattice of subspaces of a finite (dimensional) vector space. The construction is done inductively using Schubert normal forms and results in a bracketing algorithm similar to the well-known algorithm for Boolean lattices.

We prove a generalization of a theorem of Ganter concerning the embedding of partial Steiner systems into Steiner systems. As an application we discuss a further version of the problem of Rosenfeld on embedding graphs into strongly regular graphs.