Let $T$ denote a real function defined on random subsets of a given family of finite sets. The random variable $T$ is decomposed into the sum of the linear, the quadratic, the cubic etc. parts which are mutually uncorrelated. Applications of this decomposition to the asymptotics of the probability distribution of $T$ (as the sizes of random subsets and of finite sets increase) are discussed.

In a 1947 paper [6], M. Kac derived the eigenvalues and eigenvectors of the probability transition matrix associated with the Ehrenfest urn model with $n$ balls, in which a ball is selected at random and moved to the other urn. The connection (see, for instance, [1, p. 19]) between the Markov chain defined by the Ehrenfest model and the nearest-neighbour uniform random walk on the abelian group $\Z^n_2$ prompted M. Kac to ask when a Markov chain may be lifted to a random walk on a group. More specifically, given a Markov chain $\{X_m\}_{m \geq 0}$ with state space $S = \{1, 2, \ldots, n \}$ and probability transition matrix ${\mbox{\bf $P$}} = [p_{ij}] (\mbox{here } p_{ij}:= P(X_{r + 1} = j | X_r = i) \mbox{ for all } r \geq 0)$, we say that the Markov chain $\{X_m\}_{m \geq 0}$ or equivalently ${\mbox{\bf $P$}}$lifts to a random walk on a finite group $G$ if there exists a probability measure $\mu$ on $G$ and a surjective map $L:G \rightarrow S$ such that, for all $i, j \in S$, and for each $g \in L^{-1}(i)$, $$ p_{ij} = \sum_{h \in L^{-1}(j)} \!\! \mu (g^{-1}h).$$

A detachment of a graph $G$ is formed by splitting each vertex into one or more subvertices, and sharing the incident edges arbitrarily among the subvertices. In this paper we consider the question of whether a graph $H$ is a detachment of some complete graph $K_n$. When $H$ is large and restricted to belong to certain classes of graphs, for example bounded degree planar triangle-free graphs, we obtain necessary and sufficient conditions which give a complete characterization.

A harmonious colouring of a simple graph $G$ is a proper vertex colouring such that each pair of colours appears together on at most one edge. The harmonious chromatic number$h(G)$ is the least number of colours in such a colouring. The results on detachments of complete graphs give exact results on harmonious chromatic number for many classes of graphs, as well as algorithmic results.

A stable set $I$ of a graph $G$ is called $k$-extendable, $k \,{\ge}\, 1$, if there exists a stable set $X \,{\subseteq}\,V(G) {\setminus} I$ such that $|X| \,{\le}\, k$ and $|N(X) \,{\cap}\, I| \,{<}\, |X|$. A graph $G$ is called $k$-extendable if every stable set in $G$, which is not maximum, is $k$-extendable. Let us denote by ${\rm E}(k)$ the class of all $k$-extendable graphs.

We present a finite forbidden induced subgraph characterization of the maximal hereditary subclass ${\rm PE}(k)$ in ${\rm E}(k)$ for every $k \,{\ge}\,1$.

Thus, we define a hierarchy ${\rm PE}(1) \,{\subset}\, {\rm PE}(2) \,{\subset}\,{\cdots}\,{ \subset}\, {\rm PE}(k) \,{\subset}\,{ \cdots}\,$ of hereditary classes of graphs, in each of which a maximum stable set can be found in polynomial time. The hierarchy covers all graphs, and all its classes can be recognized in polynomial time.

We derive a generalization of a theorem of Raimi proving there is a partition of natural numbers with given densities of classes which meet structured translates of any other class of a partition of natural numbers.

We prove that for all $\alpha,c>0$ and for all bipartite graphs $H$, all but at most $\alpha n$ vertices of every $cn$-regular graph $G$ whose order $n$ is sufficiently large can be covered by vertex-disjoint copies of $H$. If the vertex classes of $H$ have different size, then even all but a constant number of vertices of $G$ can be covered. This implies that for all $c>0$ and all $r\geq 4$ there exists a constant $C$ such that, in every $cn$-regular graph $G$, all but at most $C$ vertices can be covered by vertex-disjoint subdivisions of $K_r$. We also show that for $r=4,5$ one can take $C=0$.

In a one-parameter model for evolution of random trees, which also includes the Barabási–Albert random graph [1], the law of large numbers and the central limit theorem are proved for the maximal degree. In the proofs martingale methods are applied.

In 1978 Erdős, Faudree, Rousseau and Schelp conjectured that \[ r ( C_{p},K_{r} ) = ( p-1 ) (r-1) +1 \] for every $p\,{\geq}\,r\,{\geq}\,3$, except for $p\,{=}\,q\,{=}\,3$. This has been proved for $r\,{\leq}\,6$, and for \[ p \geq r^{2}-2r\].

In this note we prove the conjecture for $p\,{\geq}\,4r+2$.

Many applications of Szemerédi's Regularity Lemma for graphs are based on the following counting result. If ${\mathcal G}$ is an $s$-partite graph with partition $V({\mathcal G}) =\bigcup_{i=1}^{s} V_i$, $\vert V_i\vert =m$ for all $i\in [s]$, and all pairs $(V_i, V_j)$, $1\leq i < j\leq s$, are $\epsilon$-regular of density $d$, then $\mathcal{G}$ contains $(1\pm f(\epsilon))d^{({s\atop 2})}m^s$ cliques $K_{s}$, provided $\epsilon<\epsilon(d)$, where $f(\epsilon)$ tends to 0 as $\epsilon$ tends to 0.

Guided by the regularity lemma for 3-uniform hypergraphs established earlier by Frankl and Rödl, Nagle and Rödl proved a corresponding counting lemma. Their proof is rather technical, mostly due to the fact that the ‘quasi-random’ hypergraph arising after application of Frankl and Rödl's regularity lemma is ‘sparse’, and consequently difficult to handle.

When the ‘quasi-random’ hypergraph is ‘dense’ Kohayakawa, Rödl and Skokan (J. Combin. Theory Ser. A97 307–352) found a simpler proof of the counting lemma. Their result applies even to $k$-uniform hypergraphs for arbitrary $k$. While the Frankl–Rödl regularity lemma will not render the dense case, in this paper, for $k=3$, we are nevertheless able to reduce the harder, sparse case to the dense case.

Namely, we prove that a ‘dense substructure’ randomly chosen from the ‘sparse $\delta$-regular structure’ is $\delta$-regular as well. This allows us to count the number of cliques (and other subhypergraphs) using the Kohayakawa–Rödl–Skokan result, and provides an alternative proof of the counting lemma in the sparse case. Since the counting lemma in the dense case applies to $k$-uniform hypergraphs for arbitrary $k$, there is a possibility that the approach of this paper can be adopted to the general case as well.

The lamplighter group over $\Z$ is the wreath product $\Z_q \wr \Z$. With respect to a natural generating set, its Cayley graph is the Diestel–Leader graph $\mbox{\sl DL}(q,q)$. We study harmonic functions for the ‘simple’ Laplacian on this graph and, more generally, for a class of random walks on $\mbox{\sl DL}(q,r)$, where $q,r \geq 2$. The $\mbox{\sl DL}$-graphs are horocyclic products of two trees, and we give a full description of all positive harmonic functions in terms of the boundaries of these two trees. In particular, we determine the minimal Martin boundary, that is, the set of minimal positive harmonic functions.

Hadwiger's well known conjecture (see the survey of Toft [9]) states that any graph $G$ has a $K_{\chi(G)}$ minor, where $\chi(G)$ is the chromatic number of $G$. Let $\alpha(G)$ denote the independence (or stability) number of $G$, namely the maximum number of pairwise nonadjacent vertices in $G$. It was observed in [1], [4], [10] that via the inequality $\chi(G)\ge {|V(G)|\over \alpha(G)}$, Hadwiger's conjecture implies

Conjecture 1.1.Any graph G on n vertices contains a$K_{\lceil {n\over \alpha(G)}\rceil}$as a minor.