Let G be a graph on vertex set [n], and for X ⊆ [n] let N(X) be the union of X and its neighbourhood in G. A family of sets [Fscr ] ⊆ 2[n] is G-intersecting if N(X) ∩ Y ≠ [empty ] for all X, Y ∈ [Fscr ]. In this paper we study the cardinality and structure of the largest k-uniform G-intersecting families on a fixed graph G.

The expectation of the descent number of a random Young tableau of a fixed shape is given, and concentration around the mean is shown. This result is generalized to the major index and to other descent functions. The proof combines probabilistic arguments together with combinatorial character theory. Connections with Hecke algebras are mentioned.

The number of excluded minors for the class of graphs with path-width at most two is very large. To give a practical characterization of the obstructions, we introduce some operations which preserve path-width at most two. We give a list of ten graphs such that any graph with path-width more than two can be reduced – by taking minors and applying our operations – to one of the graphs on our list. We think that our operations and excluded substructures give a far more transparent description of the class of graphs with path-width at most two than Kinnersley and Langston's characterization by 110 excluded minors (see [4]).

We present versions of concentration inequalities for products of Markov kernels and graph products. We also present discussions of a variety of consequences such as sharp upper bounds, in terms of the diameter of the state space, on the spectral gap.

We shall pack circuits of arbitrary lengths into the complete graph KN. More precisely, if N is odd and [sum ]ti=1mi = (N2), mi [ges ] 3, then the edges of KN can be written as an edge-disjoint union of circuits of lengths m1,…,mt. Since the degrees of the vertices in any such packing must be even, this result cannot hold for even N. For N even, we prove that if [sum ]ti=1mi [les ] (N2) − N−2 then we can write some subgraph of KN as an edge-disjoint union of circuits of lengths m1,…,mt. In particular, KN minus a 1-factor can be written as a union of such circuits when [sum ]ti=1mi = (N2) − N−2. We shall also show that these results are best possible.

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.

Simulated annealing is a very successful heuristic for various problems in combinatorial optimization. In this paper an application of simulated annealing to the 3-colouring problem is considered. In contrast to many good empirical results we will show for a certain class of graphs that the expected first hitting time of a proper colouring, given an arbitrary cooling scheme, is of exponential size.

These results are complementary to those in [13], where we prove the convergence of simulated annealing to an optimal solution in exponential time.

Let X1, …, Xn be a sequence of r.v.s produced by a stationary Markov chain with state space an alphabet Ω = {ω1, …, ωq}, q [ges ] 2. We consider a set of words {A1, …, Ar}, r [ges ] 2, with letters from the alphabet Ω. We allow the words to have self-overlaps as well as overlaps between them. Let [Escr ] denote the event of the appearance of a word from the set {A1, …, Ar} at a given position. Moreover, define by N the number of non-overlapping (competing renewal) appearances of [Escr ] in the sequence X1, …, Xn. We derive a bound on the total variation distance between the distribution of N and a Poisson distribution with parameter [ ]N. The Stein–Chen method and combinatorial arguments concerning the structure of words are employed. As a corollary, we obtain an analogous result for the i.i.d. case. Furthermore, we prove that, under quite general conditions, the r.v. N converges in distribution to a Poisson r.v. A numerical example is presented to illustrate the performance of the bound in the Markov case.

A graph Γ with diameter d is strongly distance-regular if Γ is distance-regular and its distance-d graph Γd is strongly regular. Some known examples of such graphs are the connected strongly regular graphs, with distance-d graph Γd = Γ (the complement of Γ), and the antipodal distance-regular graphs. Here we study some spectral conditions for a (regular or distance-regular) graph to be strongly distance-regular. In particular, for the case d = 3 the following characterization is proved. A regular (connected) graph Γ, with distinct eigenvalues λ0 > λ1 > λ2 > λ3, is strongly distance-regular if and only if λ2 = −1, and Γ3 is k-regular with degree k satisfying an expression which depends only on the order and the different eigenvalues of Γ.

Hurwitz's extension of Abel's binomial theorem defines a probability distribution on the set of integers from 0 to n. This is the distribution of the number of non-root vertices of a fringe subtree of a suitably defined random tree with n + 2 vertices. The asymptotic behaviour of this distribution is described in a limiting regime in which the fringe subtree converges in distribution to a Galton–Watson tree with a mixed Poisson offspring distribution.

We strengthen the Cohen–Körner–Simonyi upper bound on counting ‘very different sequences’.

A random interval graph of order n is generated by picking 2n numbers X1,…,X2n independently from the uniform distribution on [0,1] and considering the collection of n intervals with endpoints X2i−1 and X2i for i ∈ {1,…,n}. The graph vertices correspond to intervals. Two vertices are connected if the corresponding intervals intersect. This paper characterizes the fluctuations of the independence number in random interval graphs. This characterization is obtained through the analysis of the greedy algorithm. We actually prove limit theorems (central limit theorem and large deviation principle) on the number of phases of this greedy algorithm. The proof relies on the analysis of first-passage times through a random level.

Fix q and let Mn be an n × n matrix with entries drawn independently from the finite field Fq according to some distribution μn. It is shown that, except in certain pathological cases, the probability that Mn is nonsingular is asymptotically the same as for uniform entries; that is,

[Formula here]

In this paper we prove the following almost optimal theorem. For any δ > 0, there exist constants c and n0 such that, if n [ges ] n0, T is a tree of order n and maximum degree at most cn/log n, and G is a graph of order n and minimum degree at least (1/2 + δ)n, then T is a subgraph of G.

Algorithmic aspects of a chip-firing game on a graph introduced by Biggs are studied. This variant of the chip-firing game, called the dollar game, has the properties that every starting configuration leads to a so-called critical configuration. The set of critical configurations has many interesting properties. In this paper it is proved that the number of steps needed to reach a critical configuration is polynomial in the number of edges of the graph and the number of chips in the starting configuration, but not necessarily in the size of the input. An alternative algorithm is also described and analysed.

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 there exist universal constants C(r) < ∞ such that, for all loopless graphs G of maximum degree [les ] r, the zeros (real or complex) of the chromatic polynomial PG(q) lie in the disc [mid ]q[mid ] < C(r). Furthermore, C(r) [les ] 7.963907r. This result is a corollary of a more general result on the zeros of the Potts-model partition function ZG(q, {ve}) in the complex antiferromagnetic regime [mid ]1 + ve[mid ] [les ] 1. The proof is based on a transformation of the Whitney–Tutte–Fortuin–Kasteleyn representation of ZG(q, {ve}) to a polymer gas, followed by verification of the Dobrushin–Kotecký–Preiss condition for nonvanishing of a polymer-model partition function. We also show that, for all loopless graphs G of second-largest degree [les ] r, the zeros of PG(q) lie in the disc [mid ]q[mid ] < C(r) + 1. Along the way, I give a simple proof of a generalized (multivariate) Brown–Colbourn conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.

Let (Xn) be a residual allocation model with i.i.d. residual fractions Un: For W a random variable with values in [0; 1] and independent of (Xn), we define another sequence (Yn) by setting

(formula here)

Under minor regularity assumptions we show that (Xn) and (Yn) have the same probability law if and only if this law is a GEM distribution. In this case, the distribution of W and the Uns is Beta(1; θ) for some θ > 0.

We introduce a notion of the derivative with respect to a function, not necessarily related to a probability distribution, which generalizes the concept of derivative as proposed by Lebesgue [14]. The differential calculus required to solve linear differential equations using this notion of the derivative is included in the paper. The definition given here may also be considered as the inverse operator of a modified notion of the Riemann–Stieltjes integral. Both this unified approach and the results of differential calculus allow us to characterize distributions in terms of three different types of conditional expectations. In applying these results, a test of goodness of fit is also indicated. Finally, two characterizations of a general Poisson process are included. Specifically, a useful result for the homogeneous Poisson process is generalized.

Let [Mscr ] be the class of simple matroids which do not contain the 5-point line U2,5, the Fano plane F7, the non-Fano plane F−7, or the matroid P7 as minors. Let h(n) be the maximum number of points in a rank-n matroid in [Mscr ]. We show that h(2) = 4, h(3) = 7, and h(n) = (n+12) for n [ges ] 4, and we also find all the maximum-sized matroids for each rank.