Search

A t-design λ; t-d-n is a system of subsets of size d (called blocks) from an n-set S, such that each t-subset from S is contained in precisely λ blocks. A Steiner system S(l, m, n) is a t-design with parameters 1; l-m-n. Two Steiner systems (or t-designs) are disjoint if they share no blocks. A search has been conducted which resulted in discovering 9 mutually disjoint S(5, 8, 24)'s, 24 mutually disjoint S(4, 7, 23)'s, 60 mutually disjoint S(3, 6, 22)'s, and 197 mutually disjoint S(2, 5, 21)'s. Taking unions of several mutually disjoint Steiner systems will then produce t-designs (with varying λ's) on 21, 22, 23, and 24 points.

Let H \mathcal {H} be a separable Hilbert space, B ( H ) \mathcal {B}(\mathcal {H}) the bounded operators on H , K \mathcal {H},\mathcal {K} the ideal of compact operators, and π \pi the natural map from B ( H ) \mathcal {B}(\mathcal {H}) onto the Calkin algebra B ( H ) / K \mathcal {B}(\mathcal {H})/\mathcal {K} . Suppose X is a compact metric space and Φ : C ( X ) × [ 0 , 1 ] → B ( H ) / K \Phi :C(X) \times [0,1] \to \mathcal {B}(\mathcal {H})/\mathcal {K} is a continuous function such that Φ ( ⋅ , t ) \Phi ( \cdot ,t) is a ∗ \ast -isomorphism for each t and such that there is a ∗ \ast -isomorphism ψ : C ( X ) → B ( H ) \psi :C(X) \to \mathcal {B}(\mathcal {H}) with π ψ ( ⋅ ) = Φ ( ⋅ , 0 ) \pi \psi ( \cdot ) = \Phi ( \cdot ,0) . It is shown in this paper that if X is a simple Jordan curve, a simple closed Jordan curve, or a totally disconnected metric space then there is a continuous map Ψ : C ( X ) × [ 0 , 1 ] → B ( H ) \Psi :C(X) \times [0,1] \to \mathcal {B}(\mathcal {H}) such that π Ψ = Φ \pi \Psi = \Phi and Ψ ( ⋅ , 0 ) = ψ ( ⋅ ) \Psi ( \cdot ,0) = \psi ( \cdot ) . Furthermore if X is the disjoint union of two spaces that both have this property, then X itself has this property.

6XK-equivalence. For M and JVe^n[G], if there is an (w + 1) -dimensional compact G-manifold L with dL = M-\-N, the disjoint union of M and N, then they are called G-cobordant and L is called a G-cobordism between them, This cobordism relation defines the cobordism group Nn[G} of ndimensional closed G-manifolds. If a G-cobordism L between M and N admits a nonzero G-vector field which is inward normal on M and outward normal on N9 then, following Reinhart [8], M and N are called Reinhart G-cobordant, and L a Reinhart G-cobordism between them. The set of cobordism classes by this cobordism relation in ^ ra[G] forms a semigroup with disjoint union + as its group operation. Denote by N^[G-] the Grothendieck group of the semigroup,, From the author [4] we obtain a necessary and sufficient condition for M and N^Jtn{G] to represent the same class in N?[_G] in terms of JVn[G] and the Euler characteristics of the fixed point sets of M and

In this note we study some properties of E-m semigroups, recently defined by Nordahl in [3]. In particular we study connections with power joined and strongly reversible semigroups. We prove, among other things, that an E-m semigroup is a disjoint union of power joined semigroups.

We consider only completely regular, Hausdorff spaces. Responding to a question of R. Levy and R. H. McDowell [Proc. Amer. Math. Soc. 49 (1975), 426-430] we show that for ω ⩽ γ ⩽ 2 2 ω \omega \leqslant \gamma \leqslant {2^{{2^\omega }}} there is a separable space equal to the (appropriately topologized) disjoint union of γ \gamma copies of the “Stone-Čech remainder” β N ∖ N \beta N\backslash N . More generally, denoting density character by d and weight by w, we prove this Theorem. The following statements about infinite cardinal numbers γ \gamma and α \alpha are equivalent: (a) 2 α ⩽ 2 γ {2^\alpha } \leqslant {2^\gamma } and γ ⩽ 2 2 α \gamma \leqslant {2^{{2^\alpha }}} ; (b) For every family { X ξ : ξ > γ } \{ {X_\xi }:\xi > \gamma \} of spaces, with w ( X ξ ) ⩽ 2 α w({X_\xi }) \leqslant {2^\alpha } for all ξ > γ \xi > \gamma , the set-theoretic disjoint union X = ∪ ξ > γ X ξ X = { \cup _{\xi > \gamma }}{X_\xi } admits a topology such that d ( X ) ⩽ α d(X) \leqslant \alpha and each X ξ {X_\xi } is a topological subspace of X. The following observation (a special case of Theorem 3.1) suggests that it may be difficult to achieve a stronger result: If α ⩾ ω \alpha \geqslant \omega and X 0 {X_0} and X 1 {X_1} denote copies of the discrete space of cardinality α + {\alpha ^ + } , then the disjoint union X = X 0 ∪ X 1 X = {X_0} \cup {X_1} admits a topology (making each X i {X_i} a topological subspace) such that d ( X ) ⩽ α d(X) \leqslant \alpha .

One proves easily (1) If K =f-‘(K’) c K1 for some compact K1 with K1 n c?M = 0, then d(f, K’) = f*(%). (2) d(f, K’) = d(g, K’), if there exists a homotopy H: M x I + X such that: H( *, 0) = f, H(*, 1) = g, II-’ is compact and H-‘(K’) n(3M x I) = 0. (3) If U E M is some open subset containing K = f -‘(K’), then d(f, K’) = d(f[ CJ, K’). (4) If M = Ml ir M, (disjoint union),_& =flMi (i = 1, 2), then d(f, K’) = d(f,, K’) +

Let S be a monoid such that every left S-operand satisfies the ascending chain condition on orbits. Let X be an indecomposable [0-indecomposable] left S-operand. There is a descending chain of suboperands of X defined in terms of maximal orbits. If this chain terminates after a finite number of terms, the last non-empty [non-zero] term defines a distinguished collection Open image in new window (X) [ Open image in new window 0(X)] of disjoint [0-disjoint] orbits in X. The assumption that Open image in new window (X) [ Open image in new window 0(X)] is finite for all appropriate X, together with the additional assumption that every left S-operand satisfies the d.c.c. on orbits, implies that S has a unique minimal left ideal [that the principal left ideals outside of the minimal ideal are linearly ordered].

A commutative semigroup is called power joined if for every element a, b there are positive integers m, n such that am=bn. A commutative power joined semigroup is archimedean (p. 131, [3]) and cannot be decomposed into the disjoint union of more than one subsemigroup. Every commutative semigroup is uniquely decomposed into the disjoint union of power joined subsemigroups which are called the power joined components. This paper determines the structure of commutative archimedean semigroups which have a finite number of power joined components. The number of power joined components of commutative archimedean semigroups is one or three or infinity.

We introduce a concept of so-called disjoint ordering for any collection of finite sets. It can be viewed as a generalization of a system of distinctive representatives for the sets. It is shown that disjoint ordering is useful for network routing. More precisely, we show that Hall's “marriage” condition for a collection of finite sets guarantees the existence of a disjoint ordering for the sets. We next use this result to solve a problem in optimal routing on hypercubes. We give a necessary and sufficient condition under which there are internally node-disjoint paths each shortest from a source node to any others(s⩽n) target nodes on ann-dimensional hypercube. When this condition is not necessarily met, we show that there are always internally node-disjoint paths each being either shortest or near shortest, and the total length is minimum. An efficient algorithm is also given for constructing disjoint orderings and thus disjoint short paths. As a consequence, Rabin's information disposal algorithm may be improved.

Let M be a matroid on a finite set E ( M ). Then M is packable by bases if E ( M ) is the disjoint union of bases. A partial packing of M is a collection of disjoint bases whose union is a proper subset of E ( M ). M is a randomly packable by bases if every partial packing can be extended to a packing of M . This paper determines the structure of the matroids that are randomly packable by bases. It also gives a characterization, in terms of forbidden restrictions, of the simple matroids that are randomly packable by 3-circuits.

It is well known that disjoint closed sets in a Euclidean space may be pushed apart a positive distance by a space homeomorphism. Answering a question raised by R.D. Anderson and F.E. Browder, we show that the same thing can be accomplished in any normed linear space with respect to any locally finite collection of disjoint closed sets. The desired space homeomorphism is obtained by pushing outward along rays from a point not contained in the union of the closed sets. An example showing this result does not hold for the non-normable Frechet spaces.

We characterize disjoint hypercyclicity and disjoint supercyclicity of finitely many linear fractional composition operators acting on spaces of holomorphic functions on the unit disc, answering a question of Bernal-González. We also study mixing and disjoint mixing behavior of projective limits of endomorphisms of a projective spectrum. In particular, we show that a linear fractional composition operator is mixing on the projective limit of the Sv spaces strictly containing the Dirichlet space if and only if the operator is mixing on the Hardy space. © 2011 Elsevier Inc., The first and the third authors are supported in part by MICINN and FEDER, Projects MTM2007-64222 and MTM2010-14909. The third author is also supported by Generalitat Valenciana, Project PROMETEO/2008/101. We thank the referees for their comments and suggestions.

For any [ n , k , d ; q ]-code the Griesmer bound says that n ⩾ ∑ i=0 k−1 ⌈ d q i ⌉ . The purpose of this paper is to characterize all [ n , k , q k -1 - 3 q μ ; q ]-codes meeting the Griesmer bound in the case where k ⩾ 3, q ⩾ 5 and 1 ⩽ μ k - 1. It is shown that all such codes have a generator matrix whose columns correspond to all points in PG( k - 1, q ) except for the points in a disjoint union of three μ-flats in PG( k - 1, q ).

We investigate the topology of branched surfaces K which have the disjoint union of embedded circles as their branch sets S K , and which admit expanding immersions f with injective induced homomorphisms f * : π 1 ( K , * ) → π 1 ( K , f ( * ) ) . If every connected component L of K ∖ S K is orientable, then L is homeomorphic to a surface of genus ⩽1 with holes. In particular if there is a component homeomorphic to a 2-torus with holes, then K is the union of immersed tori. If every L is a 2-sphere with holes, under an additional assumption K is the union of immersed annuli.

We show that the Hamming graph H ( 3 , q ) with diameter three is uniquely determined by its spectrum for q ⩾ 36 . Moreover, we show that for given integer D ⩾ 2 , any graph cospectral with the Hamming graph H ( D , q ) is locally the disjoint union of D copies of the complete graph of size q - 1 , for q large enough.

A poset is {\it $(\3+\1)$-free} if it contains no induced subposet isomorphic to the disjoint union of a 3-element chain and a 1-element chain. These posets are of interest because of their connection with interval orders and their appearance in the $(\3+\1)$-free Conjecture of Stanley and Stembridge. The dimension 2 posets $P$ are exactly the ones which have an associated permutation $\pi$ where $i\prec j$ in $P$ if and only if $i, Comment: 17 pages

We show that the edge disjoint paths problem is NP-complete in directed or undirected rectangular grids, even if the union G+H of the supply and the demand graphs is Eulerian.

In this paper we examine generalisations of the following problem posed by Laczkovich: Given an n×m rectangle with n and m integers, it can be written as a disjoint union of squares; what is the smallest number of squares that can be used? He also asked the corresponding higher dimensional analogue. For the two dimensional case Kenyon proved a tight logarithmic bound but left open the higher dimensional case. Using completely different methods we prove good upper and lower bounds for this case as well as some other variants.

Let A R be a real hyperplane arrangement and let A C be its complexification. Let M R and M C be the respective complements. Then M R is the disjoint union of convex chambers whose number is given by its only Betti number, b 0 (M R ) . A real arrangement and its complexification satisfy the M-property: b 0 (M R )=∑ q b q (M C ) , the number of chambers in M R equals the sum of the Betti numbers of M C . The no-broken-circuit set, nbc , is a field independent combinatorial object. It has been used to label a basis for H ∗ (M C ) but not to label the chambers of M R in a way that makes the M-property explicit. In this paper we use the nbc set to label a combinatorial object in the nerve of the arrangement, which is field independent. This allows for simultaneous choices of nbc bases in H ∗ (M R ) and H ∗ (M C ) . We also explore the geometrical connections between these bases.

The class semigroup of a commutative integral domainRis the semigroup S (R) of the isomorphism classes of the nonzero ideals ofRwith the operation induced by multiplication. The aim of this paper is to characterize the Prufer domainsRsuch that the semigroup S (R) is a Clifford semigroup, namely a disjoint union of groups each one associated to an idempotent of the semigroup. We find a connection between this problem and the following local invertibility property: an idealIofRis invertible if and only if every localization ofIat a maximal ideal ofRis invertible. We consider the (#) property, introduced in 1967 for Prufer domainsR, stating that if Δ1and Δ2are two distinct sets of maximal ideals ofR, then ∩{RM|M∈Δ1}≠∩{RM|M∈Δ2}. Let C be the class of Prufer domains satisfying the separation property (#) or with the property that each localization at a maximal ideal if finite-dimensional. We prove that, ifRbelongs to C , then the local invertibility property holds onRif and only if every nonzero element ofRis contained only in a finite number of maximal ideals ofR. Moreover ifRbelongs to C , then S (R) is a Clifford semigroup if and only if every nonzero element ofRis contained only in a finite number of maximal ideals ofR.

Let R be a commutative ring with identity. We denote by Spec(R) the set of prime ideals of R. Call a partial ordered set spectral if it is order isomorphic to (Spec(R),⊆) for some R. A longstanding open question about spectral sets (since 1976), is that of Lewis and Ohm [Canad. J. Math. 28 (1976) 820, Question 3.4]: “If (X,⩽) is an ordered disjoint union of the posets (X λ ,⩽ λ ), λ∈Λ , and if (X,⩽) is spectral, then are the (Xλ,⩽λ) also spectral?”. Let (X,⩽) be a poset and x∈X. Recall that the D-component of x is defined to be the intersection of all subsets of X containing x that are closed under specialization and generization (i.e., under ⩽ and ⩾). Let (X,⩽) be a spectral set which is an ordered disjoint union of the posets (X λ , ⩽ λ ),λ∈Λ . It is clear that (Xλ,⩽λ) is a disjoint union of D-components of X. Thus the conjecture of Lewis and Ohm is equivalent to the following question: “Is a D-component of a spectral set spectral?” This paper deals with topological properties of a D-component of a spectral set, improving the understanding of the conjecture of Lewis and Ohm. The concepts of up-spectral topology and down-spectral topology are introduced and studied.

IN THIS note we extend to the 3-dimensional case the results of M. Kreck on bordism of diffeomorphisms [3]. Some of this work is from the author’s doctoral dissertation [S]. It is a pleasure to acknowledge my indebtedness to Robion Kirby for his insight and encouragement. We also thank the referee for a careful reading and many useful suggestions. First recall the bordism relation for ditfeomorphisms introduced by Browder in [l]. Two orientation preserving diffeomorphisms hi: Mi + Mi of closed, oriented m-manifolds Mi(i = 0, 1) are bordant if there is an oriented bordism W between MO and MI and an orientation preserving diffeomorphism H: W -+ W such that HIMi = hi. The collection of bordism classes forms an abelian group A,,, under disjoint union. In [2], after several partial results by Winkelnkemper [9] and Medrano 141, Kreck proved

In contrast to the semilattice of groups case, an inverse semigroup S which is the union of strongly E-reflexive inverse subsemigroups need not be strongly E-reflexive. If, however, the union is saturated with respect to the Green's relation 6D, and in particular if the union is a disjoint one, then S is indeed strongly E-reflexive. This is established by showing that 6) -saturated inverse subsemigroups have certain pleasant properties. Finally, in contrast to the E-unitary case, it is shown that the class of strongly E-reflexive inverse semigroups is not closed under free inverse products. The reader is referred to [1], [2] for the basic theory of inverse semigroups, including the theory of free inverse products. Recall from [4], [5] that an inverse semigroup S is said to be strongly E-reflexive whenever S is a semilattice of E-unitary inverse semigroups, or alternatively, whenever there exists a semilattice of groups congruence on S such that only idempotents are linked to idempotents under -. In [4], [5] we studied this class of semigroups and showed that many of the properties of semilattices of groups and of E-unitary inverse semigroups generalise to this class, albeit sometimes in a weaker form. We continue this line of investigation here. In what is by now a classic theorem, Clifford showed that an inverse semigroup which is a union of groups is a semilattice of groups. We ask to what extent this is true for strongly E-reflexive inverse semigroups. It is already known that a semilattice of strongly E-reflexive inverse semigroups is again strongly E-reflexive [5]. The following simple example shows that we cannot hope for a full generalisation of Clifford's theorem. Consider the bisimple inverse o-semigroup S(G, a), where the endomorphism a of the group G is not injective. As noted in [4, p. 341], S(G, a) is not strongly E-reflexive. However, using [1, Lemma 1.31], it is easily seen that S(G, a) is a union of its maximal subgroups and copies of the bicyclic semigroup, and these are all E-unitary. The restriction we require will now be given, and the example just noted would seem to indicate that it is the weakest possible. Let S be an inverse semigroup with semilattice of idempotents E. Let U be an inverse subsemigroup of S which is 6D -saturated in the sense that x 6D y' E U implies x E U, where 6D denotes the usual Green's relation on S. The maximal group homomorphic image of U is denoted by U with udenoting the image of u (u E U). Let U' = {x E SIx > u for some u E U); note that U' may equal S. Received by the editors March 23, 1979. AMS (MOS) subject classifications (1970). Primary 20M10. ? 1980 American Mathematical Society 0002-9939/80/0000-0301 /$0 1.75 352 This content downloaded from 207.46.13.148 on Sun, 11 Sep 2016 04:20:48 UTC All use subject to http://about.jstor.org/terms STRONGLY E-REFLEXIVE INVERSE SEMIGROUPS 353 The first result shows that U' has some pleasant properties. PROPOSITION. (i) U' is an inverse subsemigroup of S which contains U, and xy E U'implies x E U'andy E U'. (ii) The rule: xp = uif x > u E U and x4 = 0 otherwise, gives a well-defined homomorphism 0: S U? such that k1 U is the canonical homomorphism onto U. PROOF. (i) xy > U E U = xx > xyy 1x uu X1 x > uu x R. u =X x E U', since U is 6D -saturated and 6R C 6D. Dually, y E U'. The remainder of the result is easily proven. (ii) Suppose x E U' with x > u E U and x > v E U. Then u = ex, v = fx where e=uuEUnE,f=vv-1EUnE. Hence efu=efv, and ef6EEn U, so that u= . It is then almost immediate that 0 is well-defined. The rest of the result involves a little routine calculation, using (i). REMARK. Taking S to be a semilattice with more than two elements, we see that U need not be an ideal of U' in Proposition 1. The proposition enables us to prove our main result. THEOREM. Let S be a union of 6D -saturated strongly E-reflexive inverse subsemigroups Si, i E I. Then S is strongly E-reflexive. PROOF. Each Si is a semilattice Ai of E-unitary inverse semigroups T7, X E Ai. It is easily shown that each T/x is 6D-saturated in S. Hence we may suppose without loss of generality that each Si is E-unitary. For each i E I, let Oi: S -> S?o be the homomorphism defined as in (ii) above, and let T be the direct product of the Si?. Then the pi induce a homomorphism 0: S -T with s0 having ith component s5ci, i E I. Now So is a semilattice of groups, since T is. Suppose that x4 = eo for some e E E, where x E Si say. Then x4i is the identity element of Si, and since S5 is E-unitary it follows that x E E; whence the result. COROLLARY. Let S be a disjoint union of strongly E-reflexive inverse subsemigroups. Then S itself is strongly E-reflexive. PROOF. Clearly each of the inverse subsemigroups in question is 6D -saturated in S. REMARK. The elementary theory of inverse semigroups shows that an inverse semigroup S which is a union of groups is a disjoint union of its maximal subgroups He, e E E, and that this is the 6D -decomposition of S. Hence S is the union of the 6D -saturated E-unitary inverse subsemigroups He. It is easy to show that the homomorphism 4 in the proof of the theorem is injective in this case. Hence S is a subdirect product of the He with zero added possibly. From this one can deduce, again by elementary means, that S is a semilattice of groups with the multiplication defined by linking homomorphisms. Thus, modulo some elementary results, our theory restricts to Clifford's classic theorems. Now let E be the semilattice { e, f, g} where e > g, f > g, and e, f are incomparable. Let S be the semilattice of groups Ge U Gf U Gg where Ge' Gg are trivial and Gf is the cyclic 2-group; let T be the semilattice of groups He U Hf U Hg This content downloaded from 207.46.13.148 on Sun, 11 Sep 2016 04:20:48 UTC All use subject to http://about.jstor.org/terms

An abstract notion of action of structures on one another was established by Marcev [2]: Let L and M be two first order languages having only the logical constants in common. Let R be a relational symbol not in LuM, and F a set of sentences in L u M u { R } (which is a two-sorted first order language). Then a s t ructure /~ for L is said to act on a structure 313 for M (in the sense of F) iff the disjoint union & o ] 3 constitutes a model of F under a suitable interpretation of R, where the range of the variables of L is g~_ and the range of the variables of M is Examples abound; we mention only a few: (i) L e t / k be a commutative ring with identity, ]3 an abelian group, and let R stand for unitary scalar multiplication, whose axioms constitute F. (ii) Let & be a group,]3 arbitrary, and let R stand for injective representation in the automorphism group of ]3 (cf. Rabin [3]). (iii) Let & be a lattice, ]3 arbitrary, and let F describe the embeddability of A into the lattice of all substructures (or congruence relations) of (iv) Let & be a field, ]3 an ordered abelian group, and let R stand for nontrivial valuation, whose axioms make up F. If 9.1 is a class of structures for L and ~5 a class of structures for M, let 9JF~B denote the class of all structures in 92 that act on at least one structure in ~ . Then we have the following theorem

If U is a connected separable metric space that is locally euclidean of dimension n, U is an n-manifold. We do distinguish n-manifolds and n-manifolds with boundary. By 1(U) we denote the collection of all n-manifolds Mn such that Mn = Ul1 Ui, where UiC U+i and each Ui is a topological copy of U. The size of the collection is quite variable and we list some examples from which obvious questions arise. 1. If S2 is the 2-sphere and El the real line, let U=S2XE'. In this case 91Z( U) has two members, U and E3, where E3 is euclidean 3-space. 2. Let Mn be a combinatorial compact n-manifold with nF64. If U is the complement of a flat n-cell in Mn, then 1( U) has U as its only member [5]. The same result when U is a cell follows from [2]. 3. If U is S2 with an infinite convergent sequence of points removed, then Mlt(U) consists of exactly the proper open connected sets (proper domains) in S2. A manifold such as U in example 2 above for which 1Z(U) consists of one element is said to have the monotone union property. If Mn is an n-manifold, then a standard decomposition of Mn is a representation of Mn as a disjoint union, Mn= PUR, where P =En and dim R

By a sin (1/x)-curve is meant a metric continuum that is a 1-1 continuous image of the disjoint union of an arc and a semi-open interval that has the image of the arc as continuum of convergence. It is shown that ifM is a compact metric space,A ⊂M an arc, whileM/A is an arc havingA/A as an end-point, thenM is an arc, a triod, some sin (1/x)-curve, or some sin (1/x)-curve with an arc attached at one point, or some sin (1/x)-curve with two arcs attached. The case of shrinking finitely many arcs is also considered in an attaching theorem.

We prove that if m≥ 2, then the minimumk∈N such that the k -cube {0, 1}kcan be decomposed as the disjoint union of m connected adjacent subsets satisfies 2log2m−log2log2m− 1 ≤k≤ 2⌈log2m⌉ − ⌊log2log2m⌋ + 5.

Let Ω be a measurable subset of R n of finite positive Lebesgue measures. The following two problems are considered: ( i ) Find commuting self-adjoint extensions of the minimal operators - i ∂ /∂ x k , k = 1,..., n (Ω open). ( ii ) Find a set Λ ⊂ R n such that the functions e λ = exp( i λ 1 x 1 +... + i λ n x n ) for λ ∈ Λ form an orthonormal basis for L 2 (Ω). The problems are known to be equivalent under mild regularity conditions on Ω, and existence holds in two cases: ( i ) there is a connected open set Ω′ such that the symmetric difference ΩΔΩ′ is a null set and Ω′ is a fundamental domain for a discrete total subgroup; and ( ii )Ω = [unk] a∈R ( a + [unk]), disjoint union neglecting null sets, in which [unk] is a fundamental domain and R is a “set of representors” for a finite group of translations. Case i is equivalent to a function theoretic condition of Forelli, and case ii is established when the existence of a discrete covariance group is assumed. Generalizations of the geometric results i and ii for spectral sets in arbitrary Lie groups are indicated.

An incremental connection problem is to add k disjoint paths from s i to t i , 1≤i≤k, in an operating network. A parallel distributed algorithm is presented, which solves the problem efficiently in a general situation. Its probable performance is analyzed in a random graph setup.

Inequalities are obtained between the various parameters of a distance-regular graph. In particular, if k1 is the valency and k2 is the number of vertices at distance two from a given vertex, then in general k1 ⩽ k2. For distance-regular graphs of diameter at least four, k1=k2 if and only if the graph is simply a circuit. However when the diameter is two or three there are distance-regular graphs other than circuits for which k1=k2.

Publisher Summary This chapter discusses the Pixley–Roy topology on spaces of subsets. In [PR], Pixley and Roy construct a nonseparable ccc {=countable chain condition = no disjoint collection of open sets is uncountable} Moore space by topologizing F(R) in a suitable fashion {R = reals}. When studying spaces of subsets of a space X, it is usually quite natural to confine attention to nonempty open sets: no basic open set of the Vietoris topology contains φ, and φ would be isolated in the Pixley–Roy topology A {φ} = [φ,φ]. Cospaces were invented to study their associated spaces and more generally, it is not unusual in topology to study a space by looking at a nice weaker topology.

Let (a1,b1;…;a k ,b k ] be an interval in ℝ k , open on the left and closed on the right. Precisely stated, we assume that aj < bj for j = 1,…,k and the interval consists now of all points (x1,…,x k ) in ℝ k such that aj < xj ≤ bj for j = 1,…,k. We shall call an interval of this kind a cell. For reasons of convenience, the empty set will also be called a cell. Observe now that the collection Γ of all cells is not empty and it has the property that if A and B belong to Γ, then A⋂B belongs to Γ and A\B can be written as a finite disjoint union ⋃C n of cells. In the case that B = A or B ⊃ A, all C n in the finite union ⋃C n are then equal to the empty set. In view of the mentioned properties of Γ the collection Γ is called a semiring of subsets of ℝ k . Note that the collection of all intervals that are closed on the left and open on the right is likewise a semiring. On the other hand, the collection of all open (closed) intervals is not a semiring because the boundaries of the intervals cause difficulties. For any cell A = (a1,b1;…, a k ,b k ] we call the product $$\prod\nolimits_j^k {_{ = 1}({b_j} - {a_j})} $$ (1) measure A, and we denote this number by µ(A). Furthermore, we define µ(ф) = 0. Of course, to say that µ(A) is the measure of A is a neutral terminology for what is called the length of A if k = 1, the area of A if k = 2 and the content or volume of A if k = 3. The measure is, therefore, a map from Γ into It ℝ having the following properties: (i) µ, is non-negative and µ(ф) = 0, (ii) µ is monotone, i.e., A ⊂ B in Γ implies µ(A) ≤ µ(B), (iii) µ is σ-additive, i.e., A = $$\bigcup\nolimits_1^\infty {{A_n}} $$ (2) (with A , all An ∈ Γ and all A n mutually disjoint) implies $$\mu (A) = \sum\nolimits_1^\infty {\mu ({A_n})} .$$ (3)

We have shown, at the beginning of chapter 4 why it is necessary to go beyond the framework of affine spaces, adjoining to them points at infinity This is now possible in the following way: we associate to the affine space X its universal space \( \hat X\) (cf. 3.D), which is a vector space in which X is embedded as an affine hyperplane whose direction is a vector hyperplane of \(\hat X\). Considering now the projectivization \(\tilde X = P\left( {\hat X} \right)\) , we see that \(\tilde X\) is the disjoint union of two sets: P( X), which is canonically identified with X, and P (\(\vec X\)), which, being the space of lines in \(\vec X\), is also the space of directions of lines in X. We denote it by \({\infty _X} = P\left( {\vec X} \right)\) We write \( \tilde X = X \cup {\infty _X}\), and say that ∞x is the hyperplane at infinity in X.

The classical Bochner’s tube theorem states that every holomorphic function on a connected tube domain Rn+igcC can be extended holomorphically to the convex hull of the tubeR+ich(2). H. Komatsu [4] has obtained a simple proofo the local versiono this theorem by using Cauchy’s integral formula. By making use of the theory o Fourier-Bros-Iagolnitzer transform, M. S. Baouendi and F. Treves [1] have generalized the result above. In particular they have obtained the microlocal version o Bochner’s tube theorem or generic CR-manifolds. In this paper we shall give a simple proo of this result. In the section 1, we formulate Bochner’s tube theorem for generic CR-submanffolds by employing the notion of specialization o shea o holomorphic unctions (cf. [5]). In the section 2 we give the new proof of the theorem by reducing the problem to the totally real case. 1. Statement of the result. Let N be a real analytic submanifold of a complex mani2old X. For p e N, we denote by H,(N) the complex tangent space to N at p. The submaniold N is said to be generic, i for all p e N, dimeHp(N)=dimcX-codim N. Let us assume hereafter thatN is generic. LetSX be the spherical normal bundle TX-{O}/R with the projection r’SX-N. The disjoint union X=(X--N)]JSX has the structure o real analytic manifold with boundary S.,X. It is cmlled the real monoidal transform o X with center N. Let i (resp. ) be the embedding i" N--+X (resp. (resp. ) be the natural inclusion map ]" X-N-+X (resp. ]" X--NoX).

the material has become plastic (see [7] [13]). This problem was studied by various authors in the case of a homogeneous material, i.e., A(x) = const., g(x) = const, (see [2] [3] [5] [6] [10] [13] [18] and the references given there). In this paper we are interested in the case of variable A, g and, more specifically, in the case where Q is a disjoint union of regions Qt-, each having uniform material; that is, X and g are piecewise constants. In § 1 we study a problem similar to the elastic-plastic variational inequality problem in case of a multiply connected domain with general boundary values. We prove C« regularity in the interior and show that the problem can be reduced to a 2-obstacles problem. Further, the "elastic" region coincides with the set where u does not touch either obstacle. In §2 we formulate the physical elastic-plastic torsion problem in the case where X, g are piecewise constants (with A = Xt-, g = g{ in Qi9 Q = [jiQi)By applying the results of §1 we establish the Cregularity of the

An allocation model [$n$ balls, $m (\geq n)$ cells, at most one ball in a cell] related to a hashing algorithm is studied. A ball $x$ goes into the cell $h(x)$, where $h(\cdot): \{1,\cdots, n\} \rightarrow \{1, \cdots, m\}$ is random. In case the cell $h(x)$ is already occupied, the ball $x$ is rejected and moved into the leftmost empty cell. This empty cell is found via the sequential search from left to right starting with the cell occupied by the last (before $x$) rejected ball. Denote $T_2(x)$ the number of the necessary probes. In the end, due to a resulting system of references, the $n$ occupied cells form a disjoint union of ordered chains, and to locate a ball $x$ it suffices to search only the cells of a subchain originating at the cell $h(x)$. Denote $T_1(x)$ the length of this subchain. The main result of the paper is: in probability, $\max T_1(x) = \log_bn - 2\log_b\log n + O(1),$ $\max T_2(x) = \log_bn - \log_b\log n + O(1),$ as $n \rightarrow \infty$, if $n/m$ is bounded away from $0, b = (1 - e^{-n/m})^{-1}$.

Let M: O=M 0 ⊂ ··· ⊂ M k , = M and N: O=N 0 ⊂ ··· ⊂ N l = M be two filtrations of M. We say that N refines M if and only if for all i = 0,..., l − 1, there is a j, 0 ≤ j ≤ k − 1 such that (N i +1 − N i ) ⊂ (M j +1 − M j ).

This chapter describes singular points and separatrices. Bendixson in 1901 essentially completed the geometric classification of isolated singular points of a differential equation in the plane by recognizing a way in which an isolating disk neighborhood of any such singular point could be broken up into a finite number of sectors of the following types: (1) hyperbolic, (2) elliptic, and (3) parabolic. Subsequent attempts at an analogous procedure for isolated singular points of differential equations in higher dimensions have met with little success. The components of the complement of the set of separatrices are classified according to their topological behavior. The chapter reviews this classification in relation to singular points. The set of separatrices can be decomposed into a disjoint union of manifolds. The chapter presents a theorem that states that if p is an isolated singular point of a flow a, then a spherical neighborhood B n of p is decomposed by the separatrix set of the reparametrized flow into the separatrix set S and regions of type H , Per , R , HH , HE , HP _, or HP +, where H refers to components of B n | S that do not adhere to the origin. The chapter also presents another theorem that states that a separatrix manifold K is a topological manifold on which a differentiable structure can be defined under which the flow α is of class C .

Let k be an algebraically closed field. We will consider finite dimensional k-algebras A and our aim is to describe some components or sometimes even all components of the Auslander-Reiten quiver of A. Components of the Auslander-Reiten quiver of A we just will call components of A. In case A is of tame representation, it seems that there is a large amount of components which are regular tubes. We recall from [3] that a tube is a translation quiver containing an oriented cycle, and with underlying topological space being of the form S 1 x ~Zo" The regular tubes are the translation quivers of the form ~ /r with r ~ i, and r is called the rank of the tube. Tubes usually occur in families indexed by some set I, and in this case, we will speak of a tubular I-series. In our investigation presented here, the index set I is always the projective line ~ik over k. Given a tubular I-series T i (i 6 I), with T i regular of rank r.,l we associate with it a diagram, called its type, which is constructed as follows: We form the disjoint union of diagrams ~ , with i 6 I, choose in any ~ one particular endr i r. l point, and identify all these endpoints in order to form a star. For example, given the path algebra A of an extended Dynkin diagram ~ with some orientation (where A = ~n' Dn' ~6' ~7 or ~8), then the regular A-modules form a tubular ~ik-series, consisting of regular tubes, and the tables in [4] show that its type in just A (For example, in case A = ~6' the simple regular representations of an oriented ~6-quiver form two Y-orbits of length 3, one T-orbit of length 2, all other T-orbits are of length i, thus there are two regular tubes of rank 3, one of rank 2, and all others are of rank i, so that the diagram of this tubular ~ik-series is the star ~6 ). One objective of the present paper is to outline a direct proof of this fact.

* A i A + A i " X + AB = {xylx c A, y ~ B}, A = o and = u A word w ~ is i=0+ i=l called primitive if w = fn, f c X , implies n = i. A non-empty language A such that A ~ X + is called a code if XlX2...x n = ylY2...y m and xi,Y j ~ A for every i and j implies n = m and x i = Yi for all i. A code A is said to be a prefix (suffix) code if A n AX + = ~ (A n X+A=~). For any language A, the relations PA and RA defined by x E y (PA) if and only if A..x = A..y

Keywords: universal graphs ; vertex-disjoint cycles ; edge-disjoint cycles Note: Professor Pach's number: [088] Reference DCG-ARTICLE-1994-003doi:10.1007/BF01305955 Record created on 2008-11-14, modified on 2017-05-12

The question arose: "Which Baire spaces are Blumberg?" and, in particular, the Blumberg problem: "Must every compact Hausdorff space be Blumberg?" Partial answers were given by R. Levy [5], [6] and H. E. White [8]. In fact, there is a non-Blumberg compact Hausdorff space. An unusual feature of our example is that it is the disjoint union of two spaces, one or the other of which fails to be Blumberg, depending on whether or not the continuum hypothesis holds. Let B be the Boolean algebra of Lebesgue measurable subsets of [0, 1], and let / be the ideal of null sets of B. The reduced measure algebra is the complete Boolean algebra B/I. Let St(B/I) be the Stone space of the reduced measure algebra. As is shown in [3], St(B/I) is a compact Hausdorff, extremally disconnected space in which first category sets are nowhere dense. Also, it has weight 2 ° and satisfies the countable chain condition. It can be shown that St(B/I) is the union of 2 o nowhere dense sets. From these facts, we obtain the following theorem.