Positional Games and the Second Moment Method

Dedicated to the memory of Paul Erdős We study the fair Maker–Breaker graph Ramsey game MB(n;q). The board is , the players alternately occupy one edge a move, and Maker wants a clique of his own. We show that Maker has a winning strategy in MB(n;q) if , which is exactly the clique number of the random graph on n vertices with edge-probability 1/2. Due to an old theorem of Erdős and Selfridge this is best possible apart from an additive constant. Received March 28, 2000     

An Anti-Ramsey Theorem

Let be the Turán number which gives the maximum size of a graph of order containing no subgraph isomorphic to . In 1973, Erdős, Simonovits and Sós [5] proved the existence of an integer such that for every integer , the minimum number of colours , such that every -colouring of the edges of which uses all the colours produces at least one all whose edges have different colours, is given by . However, no estimation of was given in [5]. In this paper we prove that for . This formula covers all the relevant values of n and p. Received January 27, 1997/Revised March 14, 2000     

On Ordered Semigroups Which are Semilattices of Simple and Regular Semigroups

We characterize the ordered semigroups which are decomposable into simple and regular components. We prove that each ordered semigroup which is both regular and intra-regular is decomposable into simple and regular semigroups, and the converse statement also holds. We also prove that an ordered semigroup S is both regular and intra-regular if and only if every bi-ideal of S is an intra-regular (resp. semisimple) subsemigroup of S. An ordered semigroup S is both regular and intra-regular if and only if the left (resp. right) ideals of S are right (resp. left) quasi-regular subsemigroups of S. We characterize the chains of simple and regular semigroups, and we prove that S is a complete semilattice of simple and regular semigroups if and only if S is a semilattice of simple and regular semigroups. While a semigroup which is both π-regular and intra-regular is a semilattice of simple and regular semigroups, this does not hold in ordered semigroups, in general.     

3g3维半单Hopf代数的结构

设g为素数,k是特征为零的代数闭域,日是k上的3q3维半单Hopf代数．本文证明了日总是半可解的,即H可由群代数或对偶群代数经过扩张得到．     

Real groups transitive on complex flag manifolds

Let be a complex flag manifold. The compact real form of is transitive on . If is a noncompact real form, such transitivity is rare but occasionally happens. Here we work out a complete list of Lie subgroups of transitive on and pick out the cases that are noncompact real forms of .

     

An Algebraic Matching Algorithm

V by V skew-symmetric matrix , called the Tutte matrix, associated with a simple graph G=(V,E). He associates an indeterminate with each , then defines when , and otherwise. The rank of the Tutte matrix is exactly twice the size of a maximum matching of G. Using linear algebra and ideas from the Gallai–Edmonds decomposition, we describe a very simple yet efficient algorithm that replaces the indeterminates with constants without losing rank. Hence, by computing the rank of the resulting matrix, we can efficiently compute the size of a maximum matching of a graph. Received September 4, 1997     

NOTE – Edge-Coloring Cliques with Many Colors on Subcliques

with colors in which the edges of every copy of together receive at least 3 colors. We prove that this construction also has the property that at least colors appear on the edges of every copy of for . Received August 11, 1998