Spreads of nonsingular pairs in symplectic vector spaces

Let V be a vector space of dimension 2n, n even, over a field F, equipped with a nonsingular symplectic form. We define a new algebraic/combinatorial structure, a spread of nonsingular pairs, or nsp-spread, on V and show that nsp-spreads exist in considerable generality. We further examine in detail some particular cases.     

An Enumerative Geometry for Magic and Magilatin Labellings

A magic labelling of a set system is a labelling of its points by distinct positive integers so that every set of the system has the same sum, the magic sum. Examples are magic squares (the sets are the rows, columns, and diagonals) and semimagic squares (the same, but without the diagonals). A magilatin labelling is like a magic labelling but the values need be distinct only within each set. We show that the number of n × n magic or magilatin labellings is a quasipolynomial function of the magic sum, and also of an upper bound on the entries in the square. Our results differ from previous ones because we require that the entries in the square all be different from each other, and because we derive our results not by ad hoc reasoning but from a general theory of counting lattice points in rational inside-out polytopes. We also generalize from set systems to rational linear forms. Dedicated to the memory of Claudia Zaslavsky, 1917–2006 Received August 10, 2005     

Polyhedral combinatorics of UPGMA cones

Distance-based methods such as UPGMA (Unweighted Pair Group Method with Arithmetic Mean) continue to play a significant role in phylogenetic research. We use polyhedral combinatorics to analyze the natural subdivision of the positive orthant induced by classifying the input vectors according to tree topologies returned by the algorithm. The partition lattice informs the study of UPGMA trees. We give a closed form for the extreme rays of UPGMA cones on n taxa, and compute the spherical volumes of the UPGMA cones for small n.     

Strongly inequivalent representations and Tutte polynomials of matroids

We develop constructive techniques to show that non-isomorphic 3-connected matroids that are representable over a fixed finite field and that have the same Tutte polynomial abound. In particular, for most prime powers q, we construct infinite families of sets of 3-connected matroids for which the matroids in a given set are non-isomorphic, are representable over GF(q), and have the same Tutte polynomial. Furthermore, the cardinalities of the sets of matroids in a given family grow exponentially as a function of rank, and there are many such families.In Memory of Gian-Carlo Rota     

Simplices with congruent k-faces

Let S be a non-degenerate simplex in $\mathbb{R}^{2}$. We prove that S is regular if, for some k $\in$ {1,...,n-2}, all its k-dimensional faces are congruent. On the other hand, there are non-regular simplices with the property that all their (n1)-dimensional faces are congruent.     

Positive Semigroups of Kernel Operators

Extending results of Davies and of Keicher on ℓ^p we show that the peripheral point spectrum of the generator of a positive bounded C₀-semigroup of kernel operators on L^p is reduced to 0. It is shown that this implies convergence to an equilibrium if the semigroup is also irreducible and the fixed space non-trivial. The results are applied to elliptic operators. Dedicated to the memory of H.H. Schaefer     

Infinite independent sets in distributive lattices

We show that a poset P contains a subset isomorphic to if and only if the poset J(P) consisting of ideals of P contains a subset isomorphic to the power set of κ. If P is a join-semilattice this amounts to the fact that P contains an independent set of size κ. We show that if κ := ω and P is a distributive lattice, then this amounts to the fact that P contains either or as sublattices, where Γ and Δ are two special meet-semilattices already considered by J. D. Lawson, M. Mislove and H. A. Priestley.Dedicated to the memory of Ivan RivalReceived April 22, 2003; accepted in final form July 11, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Superlinear problems without Ambrosetti and Rabinowitz growth condition

Superlinear elliptic boundary value problems without Ambrosetti and Rabinowitz growth condition are considered. Existence of nontrivial solution result is established by combining some arguments used by Struwe and Tarantello and Schechter and Zou (also by Wang and Wei). Firstly, by using the mountain pass theorem due to Ambrosetti and Rabinowitz is constructed a solution for almost every parameter λ by varying the parameter λ. Then, it is considered the continuation of the solutions.     

Bigeneration in complete lattices and principal separation in ordered sets

By a recent observation of Monjardet and Wille, a finite distributive lattice is generated by its doubly irreducible elements iff the poset of all join-irreducible elements has a distributive MacNeille completion. This fact is generalized in several directions, by dropping the finiteness condition and considering various types of bigeneration via arbitrary meets and certain distinguished joins. This leads to a deeper investigation of so-called L-generators resp. C-subbases, translating well-known notions of topology to order theory. A strong relationship is established between bigeneration by (minimal) L-generators and so-called principal separation, which is defined in order-theoretical terms but may be regarded as a strong topological separation axiom. For suitable L, the complete lattices with a smallest join-dense L-subbasis consisting of L-primes are the L-completions of principally separated posets.     

The generalized Füredi conjecture holds for finite linear lattices

We say that a rank-unimodal poset P has rapidly decreasing rank numbers, or the RDR property, if above (resp. below) the largest ranks of P, the size of each level is at most half of the previous (resp. next) one. We show that a finite rank-unimodal, rank-symmetric, normalized matching, RDR poset of width w has a partition into w chains such that the sizes of the chains are one of two consecutive integers. In particular, there exists a partition of the linear lattices L_n(q) (subspaces of an n-dimensional vector space over a finite field, ordered by inclusion) into chains such that the number of chains is the width of L_n(q) and the sizes of the chains are one of two consecutive integers.     

Fibonacci numbers, alternating parity sequences and faces of the tridiagonal Birkhoff polytope

We determine the number of alternating parity sequences that are subsequences of an increasing m-tuple of integers. For this and other related counting problems we find formulas that are combinations of Fibonacci numbers. These results are applied to determine, among other things, the number of vertices of any face of the polytope of tridiagonal doubly stochastic matrices.     

The Schwarz genus of the Stiefel manifold

In this paper we compute: the Schwarz genus of the Stiefel manifold _Vk(Rⁿ)$V_k({\mathbb{R}}^n)$ with respect to the action of the Weyl group _Wk:=(Z/2)^k?_Sk$W_k:={(\mathbb{Z}/2)}^k?{\mathfrak{S}}_k$, and the Lusternik–Schnirelmann category of the quotient space _Vk(Rⁿ)/_Wk$V_k({\mathbb{R}}^n)/W_k$. Furthermore, these results are used in estimating the number of critically outscribed parallelotopes around a strictly convex body, and Birkhoff–James orthogonal bases of a normed finite dimensional vector space.     

Über Morphismen halbmodularer Verbände

Morphisms and weak morphisms extend the concept of strong maps and maps of combinatorial geometry to the class of finite dimensional semimodular lattices. Each lattice which is the image of a semimodular lattice under a morphism is semimodular. In particular, each finite lattice is semimodular if and only if it is the image of a finite distributive lattice under a morphism. Regular and non-singular weak morphisms may be used to characterize modular and distributive lattices. Each morphism gives rise to a geometric closure operator which in turn determines a quotient of a semimodular lattice. A special quotient, the Higgs lift, is constructed and used to show that each morphism decomposes into elementary morphisms, and that each morphism may be factored into an injection and a contraction.

     

On linear spaces and matroids of arbitrary cardinality

In this paper, we study linear spaces of arbitrary finite dimension on some (possibly infinite) set. We interpret linear spaces as simple matroids and study the problem of erecting some linear space of dimension n to some linear space of dimension n + 1 if possible. Several examples of some such erections are studied; in particular, one of these erections is computed within some infinite iteration process.Dedicated to the memory of Gian-Carlo Rota     

The lattice of flats and its underlying flag matroid polytope

LetM be a matroid andF the collection of all linear orderings of bases ofM, orflags ofM. We define the flag matroid polytope Δ(F). We determine when two vertices of Δ(F) are adjacent, and provide a bijection between maximal chains in the lattice of flats ofM and certain maximal faces of Δ(F). Supported in part by NSA grant MDA904-95-1-1056.     

Orthomodular lattices from 3-dimensional quadratic spaces

If E is a vector space over a field K, then any regular symmetric bilinear form on E induces a polarity on the lattice of all subspaces of E. In the particular case where E is 3-dimensional, the set of all subspaces M of E such that both M and are not N-subspaces (which, in most cases, is equivalent to saying that M is nonisotropic), ordered by inclusion and endowed with the restriction of the above polarity, is an orthomodular lattice T(E, ). We show that if K is a proper subfield of K, with K F₂, and E a 3-dimensional K -subspace of E such that the restriction of to E × E is, up to multiplicative constant, a bilinear form on the K -space E , then T(E , ) is isomorphic to an irreducible 3-homogeneous proper subalgebra of T(E, ). Our main result is a structure theorem stating that, when K is not of characteristic 3, the converse is true, i.e., any irreducible 3-homogeneous proper subalgebra of T(E, ) is of this form. As a corollary, we construct infinitely many finite orthomodular lattices which are minimal in the sense that all their proper subalgebras are modular. In fact, this last result was our initial aim in this paper.Received June 4, 2003; accepted in final form May 18, 2004.     

Simpler Tests for Semisparse Subgroups

The main results of this article facilitate the search for quotients of regular abstract polytopes. A common approach in the study of abstract polytopes is to construct polytopes with specified facets and vertex figures. Any nonregular polytope may be constructed as a quotient of a regular polytope by a (so-called) semisparse subgroup of its automorphism group W (which will be a string C-group). It becomes important, therefore, to be able to identify whether or not a given subgroup N of a string C-group W is semisparse. This article proves a number of properties of semisparse subgroups. These properties may be used to test for semisparseness in a way which is computationally more efficient than previous methods. The methods are used to find an example of a section regular polytope of type {6, 3, 3} whose facets are Klein bottles. Received February 15, 2005     

Many varieties of lattices with nonsurjective epimorphisms

We use dominions to show that many varieties of lattices have nonsurjective epimorphisms. The variety D of distributive lattices is treated in detail. We show that the dominion in D of a sublattice is the closure of M under relative complementation in L. This dominion is also the largest sublattice of L in which M is epimorphically embedded. In any variety of lattices larger than D, the dominion of M in L is just M. Received May 1, 2001; accepted in final form October 4, 2005.     

Sublattices of product spaces: Hulls, representations and counting

The Cartesian product of lattices is a lattice, called a product space, with componentwise meet and join operations. A sublattice of a lattice L is a subset closed for the join and meet operations of L. The sublattice hullLQ of a subset Q of a lattice is the smallest sublattice containing Q. We consider two types of representations of sublattices and sublattice hulls in product spaces: representation by projections and representation with proper boundary epigraphs. We give sufficient conditions, on the dimension of the product space and/or on the sublattice hull of a subset Q, for LQ to be entirely defined by the sublattice hulls of the two-dimensional projections of Q. This extends results of Topkis (1978) and of Veinott [Representation of general and polyhedral subsemilattices and sublattices of product spaces, Linear Algebra Appl. 114/115 (1989) 681-704]. We give similar sufficient conditions for the sublattice hull LQ to be representable using the epigraphs of certain isotone (i.e., nondecreasing) functions defined on the one-dimensional projections of Q. This also extends results of Topkis and Veinott. Using this representation we show that LQ is convex when Q is a convex subset in a vector lattice (Riesz space), and is a polyhedron when Q is a polyhedron in Rⁿ.We consider in greater detail the case of a finite product of finite chains (i.e., totally ordered sets). We use the representation with proper boundary epigraphs and provide upper and lower bounds on the number of sublattices, giving a partial answer to a problem posed by Birkhoff in 1937. These bounds are close to each other in a logarithmic sense. We define a corner representation of isotone functions and use it in conjunction with the representation with proper boundary epigraphs to define an encoding of sublattices. We show that this encoding is optimal (up to a constant factor) in terms of memory space. We also consider the sublattice hull membership problem of deciding whether a given point is in the sublattice hull LQ of a given subset Q. We present a good characterization and a polynomial time algorithm for this sublattice hull membership problem. We construct in polynomial time a data structure for the representation with proper boundary epigraphs, such that sublattice hull membership queries may be answered in time logarithmic in the size |Q| of the given subset.     

Remarks on the frame envelope of a σ-frame

The familiar equivalence between σ-frames and σ-coherent frames, given by the frame envelopes of σ-frames, is shown to induce an equivalence between stably continuous σ-frames and stably continuous frames. Similarly, the analogue of the former for σ-biframes is proved to provide an equivalence between compact regular σ-biframes and compact regular biframes. As an application we obtain the equivalence between stably continuous σ-frames and compact regular σ-biframes due to Matutu as an easy consequence of its frame counterpart established earlier by Banaschewski and Brümmer. This provides an affirmative answer to a question posed by Dana Scott.