It is known that any k-uniform family with covering number t has at most ktt-covers. In this paper, we deal with intersecting families and give better upper bounds for the number of t-covers. Let pt(k) be the maximum number of t-covers in any k-uniform intersecting families with covering number t. We prove that, for a fixed t,

formula here

In the cases of t=4 and 5, we also prove that the coefficient of kt−1 in pt(k) is exactly (t2).

We study the concept of list total colourings and prove that every multigraph of maximum degree 3 is 5-total-choosable. We also show that the total choice number of a graph of maximum degree 2 is equal to its total chromatic number.

Given a sequence of nonnegative real numbers λ0, λ1, … that sum to 1, we consider a random graph having approximately λin vertices of degree i. In [12] the authors essentially show that if [sum ]i(i−2)λi>0 then the graph a.s. has a giant component, while if [sum ]i(i−2)λi<0 then a.s. all components in the graph are small. In this paper we analyse the size of the giant component in the former case, and the structure of the graph formed by deleting that component. We determine ε, λ′0, λ′1 … such that a.s. the giant component, C, has εn+o(n) vertices, and the structure of the graph remaining after deleting C is basically that of a random graph with n′=n−[mid ]C[mid ] vertices, and with λ′in′ of them of degree i.

We consider continuous time random walks on a product graph G×H, where G is arbitrary and H consists of two vertices x and y linked by an edge. For any t>0 and any a, b∈V(G), we show that the random walk starting at (a, x) is more likely to have hit (b, x) than (b, y) by time t. This contrasts with the discrete time case and proves a conjecture of Bollobás and Brightwell. We also generalize the result to cases where H is either a complete graph on n vertices or a cycle on n vertices.

It is known that evaluating the Tutte polynomial, T(G; x, y), of a graph, G, is #P-hard at all but eight specific points and one specific curve of the (x, y)-plane. In contrast we show that if k is a fixed constant then for graphs of tree-width at most k there is an algorithm that will evaluate the polynomial at any point using only a linear number of multiplications and additions.

Let G be an abelian group of order n and let μ be a sequence of elements of G with length 2n−k+1 taking k distinct values. Assuming that no value occurs n−k+3 times, we prove that the sums of the n-subsequences of μ must include a non-null subgroup. As a corollary we show that if G is cyclic then μ has an n-subsequence summing to 0. This last result, conjectured by Bialostocki, reduces to the Erdos–Ginzburg–Ziv theorem for k=2.

Often when analysing randomized algorithms, especially parallel or distributed algorithms, one is called upon to show that some function of many independent choices is tightly concentrated about its expected value. For example, the algorithm might colour the vertices of a given graph with two colours and one would wish to show that, with high probability, very nearly half of all edges are monochromatic.

The classic result of Chernoff [3] gives such a large deviation result when the function is a sum of independent indicator random variables. The results of Hoeffding [5] and Azuma [2] give similar results for functions which can be expressed as martingales with a bounded difference property. Roughly speaking, this means that each individual choice has a bounded effect on the value of the function. McDiarmid [9] nicely summarized these results and gave a host of applications. Expressed a little differently, his main result is as follows.

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 consider the function χ(Gk), defined to be the smallest number of colours that can colour a graph G in such a way that no vertices of distance at most k receive the same colour. In particular we shall look at how small a value this function can take in terms of the order and diameter of G. We get general bounds for this and tight bounds for the cases k=2 and k=3.

Let X be a vertex-transitive graph and let S be an arbitrary finite subset of its vertices. Denote by @∂S the set of vertices adjacent to S but not in S. Babai and Szegedy proved that for an infinite, connected, locally finite X with subexponential growth we have

formula here

where d(S) is the diameter of S. The aim of this note is to provide a slightly better, tight lower bound on this quantity. We prove that

formula here

under the same conditions.

We consider the problem of fault diagnosis in multiprocessor systems. Processors perform tests on one another: fault-free testers correctly identify the fault status of tested processors, while faulty testers can give arbitrary test results. Processors fail independently with constant probability p<1/2 and the goal is to identify correctly the status of all processors, based on the set of test results. For 0<q<1, q-diagnosis is a fault diagnosis algorithm whose probability of error does not exceed q. We show that the minimum number of tests to perform q-diagnosis for n processors is Θ(n log 1/q) in the nonadaptive case and n+Θ( log 1/q) in the adaptive case. We also investigate q-diagnosis algorithms that minimize the maximum number of tests performed by, and performed on, processors in the system, constructing testing schemes in which each processor is involved in very few tests. Our results demonstrate that the flexibility yielded by adaptive testing permits a significant saving in the number of tests for the same reliability of diagnosis.

A collection H of integers is called an affine d-cube if there exist d+1 positive integers x0,x1,…, xd so that

formula here

We address both density and Ramsey-type questions for affine d-cubes. Regarding density results, upper bounds are found for the size of the largest subset of {1,2,…,n} not containing an affine d-cube. In 1892 Hilbert published the first Ramsey-type result for affine d-cubes by showing that, for any positive integers r and d, there exists a least number n=h(d,r) so that, for any r-colouring of {1,2,…,n}, there is a monochromatic affine d-cube. Improvements for upper and lower bounds on h(d,r) are given for d>2.

For an undirected graph G=(V, E), let σ(L(G)) be the size of the maximum cut of the line graph L(G). Let dv denote the degree of the vertex v in G. Then we have the following results.

(a) If G=(V, E) is Eulerian, then

formula here

(b) If G is not Eulerian, then

formula here

Let S be a generating subset of a cyclic group G such that 0=∉S and [mid ]S[mid ][ges ]5. We show that the number of sums of the subsets of S is at least min([mid ]G[mid ], 2[mid ]S[mid ]). Our bound is best possible. We obtain similar results for abelian groups and mention the generalization to nonabelian groups.

It was conjectured by Bartels and Welsh [1] that removing an edge from an n-vertex graph G will not increase the average number of colours in the proper colourings of G if k=n colours are available. This paper shows that for all n>3, and for each k∈{3, 4, …, [lfloor ](3n−6)/2[rfloor ]}, there is a graph on n vertices with an edge whose removal increases the average number of colours in the k-colourings, thus disproving the conjecture.

We prove that there exists n0, such that, for every n[ges ]n0 and every 2-colouring of the edges of the complete graph Kn, one can find two vertex-disjoint monochromatic cycles of different colours which cover all vertices of Kn.

Given a class of combinatorial structures [Cscr ], we consider the quantity N(n, m), the number of multiset constructions [Pscr ] (of [Cscr ]) of size n having exactly m [Cscr ]-components. Under general analytic conditions on the generating function of [Cscr ], we derive precise asymptotic estimates for N(n, m), as n→∞ and m varies through all possible values (in general 1[les ]m[les ]n). In particular, we show that the number of [Cscr ]-components in a random (assuming a uniform probability measure) [Pscr ]-structure of size n obeys asymptotically a convolution law of the Poisson and the geometric distributions. Applications of the results include random mapping patterns, polynomials in finite fields, parameters in additive arithmetical semigroups, etc. This work develops the ‘additive’ counterpart of our previous work on the distribution of the number of prime factors of an integer [20].

We determine the asymptotic behaviour of the number of Eulerian circuits in a complete graph of odd order. One corollary of our result is the following. If a maximum random walk, constrained to use each edge at most once, is taken on Kn, then the probability that all the edges are eventually used is asymptotic to e3/4n−½. Some similar results are obtained about Eulerian circuits and spanning trees in random regular tournaments. We also give exact values for up to 21 nodes.

Let kp(G) denote the number of complete subgraphs of order p in the graph G. Bollobás proved that any real linear combination of the form [sum ]apkp(G) attains its maximum on a complete multipartite graph. We show that the same is true for a linear combination of the form [sum ]apkp(G) +bpkp(G¯), provided bp[ges ]0 for every p.

We consider probability spaces which contain a family {EA[ratio ]A⊆{1, 2, …, n}, [mid ]A[mid ]=k} of events indexed by the k-element subsets of {1, 2, …, n}. A pair (A, B) of k-element subsets of {1, 2, …, n} is called a shift pair if the largest k−1 elements of A coincide with the smallest k−1 elements of B. For a shift pair (A, B), Pr[AB¯] is the probability that event EA is true and EB is false. We investigate how large the minimum value of Pr[AB¯], taken over all shift pairs, can be. As n→∞, this value converges to a number λk, with ½−1/2k+2[les ]λk[les ] ½−1/4k+2. We show that λk is a strictly increasing function of k, with λ1=¼ and λ2=1/3.

For k=1, our results have the following natural interpretation. If a fair coin is tossed repeatedly, and event Ei is true when the ith toss is heads, then for all i and j with i<j, Pr[EiĒj]=¼. Furthermore, as we show in this paper, for any ε>0, there is an n such that for any sequence E1, E2, …, En of events in an arbitrary probability space, there are indices i<j with Pr[EiĒj]<¼+ε. The results and techniques we develop in this research, together with further applications of Ramsey theory, are then used to show that the supremum of fractional dimensions of interval orders is exactly 4, answering a question of Brightwell and Scheinerman.

Generalizing the ¼+ε result to random variables X1, X2, …, Xn with values in an m-element set, we obtain a finite version of de Finetti's theorem without the exchangeability hypothesis: for any fixed m, k and ε, every sufficiently long sequence of such random variables has a length-k subsequence at variation distance less than ε from an i.i.d. mix.