Gray codes from antimatroids

We show three main results concerning Hamiltonicity of graphs derived from antimatroids. These results provide Gray codes for the feasible sets and basic words of antimatroids.For antimatroid (E, ), letJ( ) denote the graph whose vertices are the sets of , where two vertices are adjacent if the corresponding sets differ by one element. DefineJ( ;k) to be the subgraph ofJ( )² induced by the sets in with exactlyk elements. Both graphsJ( ) andJ( ;k) are connected, and the former is bipartite.We show that there is a Hamiltonian cycle inJ( )×K ₂. As a consequence, the ideals of any poset % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWefv3ySLgznf% gDOfdaryqr1ngBPrginfgDObYtUvgaiuaacqWFpepuaaa!414C!\[\mathcal{P}\] may be listed in such a way that successive ideals differ by at most two elements. We also show thatJ( ;k) has a Hamilton path if (E, ) is the poset antimatroid of a series-parallel poset.Similarly, we show thatG( )×K ₂ is Hamiltonian, whereG( ) is the basic word graph of a language antimatroid (E, ). This result was known previously for poset antimatroids.Research supported in part by NSERC.Research supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant A3379.     

Universality of the automorphism group of the real line

We discuss the question, whether each automorphism group (of cardinality at most ) of a linear order is embeddable into the automorphism group of the real line. We show that the answer to this question is independent of the axioms of ZFC: the answer is positive, if we assume < and Souslin's hypothesis; the answer is negative, if we assume orV=L.     

A Higher-Order Analog of the Linking Number for a Pair of Divergence-Free Vector Fields

Pairs B, of divergence-free vector fields with compact support in are considered higher-order analog M(B, c (of order 3) of the Gauss helicity number H(B, )= , curl(A)=B; (of order 1) is constructed, which is invariant under volume-preserving diffeomorphisms. An integral expression for M is given. A degree-four polynomial m(B(x₁), B(x₂), ( ₁), ( ₂)), x₁, x₂, _{1 2} , is defined, which is symmetric in the first and second pairs of variables separately. M is the average value of m over arbitrary configurations of points. Several conjectures clarifying the geometric meaning of the invariant and relating it to invariants of knots and links are stated. Bibliography: 11 titles.     

On the dimension of the cartesian product of relations and orders

It is known that for incidence structures and , max , wheref dim stands for Ferrers relation. We shall show that under additional assumptions on and , both bounds can be improved. Especially it will be shown that the square of a three-dimensional ordered set is at least four-dimensional.     

Computing on-line the lattice of maximal antichains of posets

We consider the on-line computation of the lattice of maximal antichains of a finite poset . This on-line computation satisfies what we call the linear extension hypothesis: the new incoming vertex is always maximal in the current subposet of . In addition to its theoretical interest, this abstraction of the lattice of antichains of a poset has structural properties which give it interesting practical behavior. In particular, the lattice of maximal antichains may be useful for testing distributed computations, for which purpose the lattice of antichains is already widely used. Our on-line algorithm has a run time complexity of , where |P| is the number of elements of the poset, , |MA(P)| is the number of maximal antichains of and (P) is the width of . This is more efficient than the best off-line algorithms known so far.     

The space of minimal prime ideals in a 0-distributive semilattice

LetS be a 0-distributive semilattice and be its minimal spectrum. It is shown that is Hausdorff. The compactness of has been characterized in several ways. A representation theorem (like Stone's theorem for Boolean algebras) for disjunctive, 0-distributive semilattices is obtained.     

Minimum Cutsets for an Element of a Subspace Lattice over a Finite Vector Space

Let L_n(q) denote the lattice of subspaces of ann-dimensional vector space over the finite field of q elements, ordered byinclusion. In this note, we prove that for all n and m the minimum cutsetfor an element A with is justL(A) if m < n/ 2, is U(A) if m > n/ 2, and both L(A) andU(A) if m = n/ 2, where L(A) is the collection of all such that and , and U(A) the collection of all such that and . Hence a finite vector space analog isgiven for the theorem of Griggs and Kleitman that determines all the minimumcutsets for an element of a Boolean algebra.     

Positive elements in the algebra of the quantum moment problem

Summary Let denote the extended Weyl algebra, , the Weyl algebra. It is well known that every element of of the formA=B _k ^* B _k is positive. We prove that the converse implication also holds: Every positive elementA in has a quadratic sum factorization for some finite set of elements (B _k ) in . The corresponding result is not true for the subalgebra . We identify states on which do not extend to states on . It follows from a result of Powers (and Arveson) that such states on cannot be completely positive. Our theorem is based on a certain regularity property for the representations which are generated by states on , and this property is not in general shared by representations generated by states defined only on the subalgebra .Work supported in part by the NSF     

A characterization of the line set of an odd-dimensional Baer subspace

Generalizing a theorem of Beutelspacher and Seeger, we consider line sets inP=PG(2t + 1,q),t IN, with the following properties: (1) any (t + 1)-dimensional subspace ofP contains at least one line of , (2) if a pointx ofP is incident with at least two lines of then the points in the factor geometryP/x which are induced by the lines of throughx form a blocking set of type (t, 1) inP/x, (3) any line of is coplanar with at least one further line of . We will show that the examples of minimal cardinality are exactly the line sets of Baer subspaces ofP.     

On dualities between function spaces

By [6], the dualities between and , whereX andW are two sets and (i.e., the mappings satisfying for all and all index setsI), can be represented with the aid of functions . Here we show that they can be also represented with the aid of functions , whereR = (–, +). As an application, we show that every duality is completely determined by a suitable duality between 2 ^{X ×R} and 2 ^{W ×R} (i.e., a mapping 2 ^{X ×R} 2 ^{W ×R} satisfying for all {M _i} _iI 2 ^{X ×R} and all index setsI), applied to the epigraphs of the functions .     

Completions of orthomodular lattices II

If is a variety of orthomodular lattices generated by a set of orthomodular lattices having a finite uniform upper bound om the length of their chains, then the MacNeille completion of every algebra in again belongs to .The author gratefully acknowledges the support of NSERC.     

Infinite Independent Systems of Identities of an Associative Algebra over an Infinite Field of Characteristic Two

Let be the variety of associative (special Jordan, respectively) algebras over an infinite field of characteristic 2 defined by the identity ((((x ₁,x ₂),x ₃), ((x ₄,x ₅),x ₆)), (x ₇,x ₈)) = 0 (((x ₁ x ₂ · x ₃)(x ₄ x ₅ · x ₆))(x ₇ x ₈) = 0, respectively). In this paper, we construct infinite independent systems of identities in the variety ( , respectively). This implies that the set of distinct nonfinitely based subvarieties of the variety has the cardinality of the continuum and that there are algebras in with undecidable word problem.     

One-step prediction forP n-weakly stationary processes

The one-step prediction problem is studied in the context ofP _n-weakly stationary stochastic processes , where is an orthogonal polynomial sequence defining a polynomial hypergroup on . This kind of stochastic processes appears when estimating the mean of classical weakly stationary processes. In particular, it is investigated whether these processes are asymptoticP _n-deterministic, i.e. the prediction mean-squared error tends to zero. Sufficient conditions on the covariance function or the spectral measure are given for being asymptoticP _n-deterministic. For Jacobi polynomialsP _n(x) the problem of being asymptoticP _n-deterministic is completely solved.     

Some greedyt-intersecting families of finite sequences

Letn, s ₁,s ₂, ... ands _n be positive integers. Assume is an integer for eachi}. For , , and , denotes _p (a)={j|1jn,a _j p}, , and . is called anI _t ^p -intersecting family if, for any a,b ,a _i b _i =min(a _i ,b _i )p for at leastt i's. is called a greedyI _t ^P -intersecting family if is anI _t ^p -intersecting family andW _p (A)W _p (B+A ^c ) for anyAS _p ( ) and any with |B|=t–1.In this paper, we obtain a sharp upper bound of | | for greedyI _t ^p -intersecting families in for the case 2ps _i (1in) ands ₁>s ₂>...>s _n .This project is partially supported by the National Natural Science Foundation of China (No.19401008) and by Postdoctoral Science Foundation of China.     

A new product of algebras and a type reduction theorem

A construction is defined which associates, to every algebra of a fixed but arbitrary finite similarity type, a groupoidF . The identities ofF are finitely based if and only if those of are, andF is finite if and only if is finite. Up to isomorphism,F has the same endomorphism monoid and subalgebra lattice as , but the congruence lattice ofF is the result of adjoining a new 1 to the congruence lattice of .F is functorial, preserves the satisfaction (and the non-satisfaction) of most Mal'cev conditions, and produces, by composition with the operation of forming the generated variety, an isomorphism of the lattice of varieties of fixed type to an interval in the lattice of varieties of groupoids.The construction makes use of a new product operation, applicable to two algebras of differing similarity types, which is introduced and studied in this paper.Research supported by National Science Foundation grant MCS-8103455.Presented by K. A. Baker.     

Hypersurfaces of restricted type in Minkowski space

A submanifold M _n ^r of Minkowski space is said to be of restricted type if its shape operator with respect to the mean curvature vector is the restriction of a fixed linear transformation of to the tangent space of M _n ^r at every point of M _n ^r . In this paper we completely classify hypersurfaces of restricted type in . More precisely, we prove that a hypersurface of is of restricted type if and only if it is either a minimal hypersurface, or an open part of one of the following hypersurfaces: S ^k × , S _k ¹ × , H ^k × , S _n ¹ , H ⁿ , with 1kn–1, or an open part of a cylinder on a plane curve of restricted type.This work was done when the first and fourth authors were visiting Michigan State University.Aangesteld Navorser N.F.W.O., Belgium.     

Piecewise projective homeomorphisms and a noncommutative Steinberg extension

Let CP (R) be the group of compactly supported homeomorphisms ofR= which are piecewise with a parabolic defect at each breakpoint. An acyclic extension

On a theorem of Seidel and Walsh

Given a sequence ( _n ) _n in with there are functions such that , is a dense subset of , and the set of functions with this property is residual in . We will show that in and some related Banach spaceX there are functionsf with is dense in , and we will give a sufficient condition when the set of such functions is residual inX.     

Un théorème de Vitali-Hahn-Saks pour les semimartingales

Summary Let (, , P) be a complete probability space; let _t0 be an increasing right-continuous family of -complete sub--fields of ; let be a sequence of semimartingales. Assume that for all positive t and for all bounded predictable processes H, the r.v.'s converge in probability to a limit J(t, H) when n tends to infinity. Then there exists a semimartingale X such that, for all t and H, J(t, H)= .