On a theorem by Benson and Conway

We define some purely lattice theoretic translations of algebraic notions related to submodule lattices, leading to new structural features of modular lattices and to generalisations of the Benson-Conway Theorem.     

The cardinality of FM(1+1+n)

The aim of this note is to develop a counting formula for the modular lattice FM(1+1+n) freely generated by two single elements and an n-element chain. This answers Problem 44 in Birkhoff [1] which asks one to determine FM(1+1+n). The proof of our recursive formula is based on the scaffolding method developed by R. Wille.     

Representing posets with k-tournaments

In this paper, we introduce a binary relation on the vertex set of a k-tournament, and using this relation show that every finite poset with cardinality n4 can be represented by a k-tournament for every k satisfying 3kn–1.     

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.     

Matchings and radon transforms in lattices. I. Consistent lattices

An element in a lattice is join-irreducible if x=ab implies x=a or x=b. A meet-irreducible is a join-irreducible in the order dual. A lattice is consistent if for every element x and every join-irreducible j, the element xj is a join-irreducible in the upper interval [x, î]. We prove that in a finite consistent lattice, the incidence matrix of meet-irreducibles versus join-irreducibles has rank the number of join-irreducibles. Since modular lattices and their order duals are consistent, this settles a conjecture of Rival on matchings in modular lattices.     

Comparability graphs of lattices

A theorem of N. Terai and T. Hibi for finite distributive lattices and a theorem of Hibi for finite modular lattices (suggested by R.P. Stanley) are equivalent to the following: if a finite distributive or modular lattice of rank d contains a complemented rank 3 interval, then the lattice is (d+1)-connected.In this paper, the following generalization is proved: Let L be a (finite or infinite) semimodular lattice of rank d that is not a chain (d∈N₀). Then the comparability graph of L is (d+1)-connected if and only if L has no simplicial elements, where z∈L is simplicial if the elements comparable to z form a chain.     

Maximal chains of isomorphic subgraphs of countable ultrahomogeneous graphs

For a countable ultrahomogeneous graph G=〈G,ρ〉$\mathbb{G}=〈G,\rho 〉$ let P(G)$\mathbb{P}(\mathbb{G})$ denote the collection of sets A⊂G$A\subset G$ such that 〈A,ρ∩[A]²〉≅G$〈A,\rho \cap {[A]}^2〉\cong \mathbb{G}$. The order types of maximal chains in the poset 〈P(G)∪{∅},⊂〉$〈\mathbb{P}(\mathbb{G})\cup \{\varnothing \},\subset 〉$ are characterized as:     

Vertex coloring acyclic digraphs and their corresponding hypergraphs

We consider vertex coloring of an acyclic digraph in such a way that two vertices which have a common ancestor in receive distinct colors. Such colorings arise in a natural way when bounding space for various genetic data for efficient analysis. We discuss the corresponding down-chromatic number and derive an upper bound as a function of , the maximum number of descendants of a given vertex, and the degeneracy of the corresponding hypergraph. Finally, we determine an asymptotically tight upper bound of the down-chromatic number in terms of the number of vertices of and .     

Fixed points of posets and clique graphs

The fixed point property for partial orders has been the object of much attention in the past twenty years. Recently, M. Roddy ([7]) proved this famous conjecture of Rival (see [6]): the class of finite orders with the fixed point property is closed under finite products.In this article, we prove that a finite order has the fixed point property if the sequence of iterated clique graphs of its comparability graph tends to the trivial graph.     

Meet decompositions in complete lattices

In the present paper we shall study infinite meet decompositions of an element of a complete lattice. We give here a generalization of some results of papers [2] and [3].     

Solution to a problem of C. D. Godsil regarding bipartite graphs with unique perfect matching

We give the solution to the following question of C. D. Godsil[2]: Among the bipartite graphsG with a unique perfect matching and such that a bipartite graph obtains when the edges of the matching are contracted, characterize those having the property thatG ⁺G, whereG ⁺ is the bipartite multigraph whose adjacency matrix,B ⁺, is diagonally similar to the inverse of the adjacency matrix ofG put in lower-triangular form. The characterization is thatG must be obtainable from a bipartite graph by adding, to each vertex, a neighbor of degree one. Our approach relies on the association of a directed graph to each pair (G, M) of a bipartite graphG and a perfect matchingM ofG.     

On computing the number of linear extensions of a tree

An algorithm requiring O(n ²) arithmetic operations for computing the number of linear extensions of a poset whose covering graph is a tree is given.This research was partially funded by the National Science and Engineering Research Council of Canada under Grant Number A4219.     

The saga of the High School Identities

This paper surveys and updates results and open problems related to the variety defined by the High School Identities as well as the variety generated by the positive numbers with exponentiation.In Celebration of the Sixtieth Birthday of Ralph N. McKenzieReceived August 24, 2002; accepted in final form September 13, 2004.     

On the contraction of vectorial lattice representations

For modular lattices of finite length, vector space representations are shown to give rise to contracted representations of homomorphic imagesDedicated to the memory of Alan Day     

Inverses of trees

LetT be a tree with a perfect matching. It is known that in this case the adjacency matrixA ofT is invertible and thatA ^?1 is a (0, 1, ?1)-matrix. We show that in factA ^?1 is diagonally similar to a (0, 1)-matrix, hence to the adjacency matrix of a graph. We use this to provide sharp bounds on the least positive eigenvalue ofA and some general information concerning the behaviour of this eigenvalue. Some open problems raised by this work and connections with Möbius inversion on partially ordered sets are also discussed.     

Semimodular lattices with isomorphic graphs

Two discrete modular lattice and have isomorphic graphs if and only if is of the form A × and is of the form A × for some lattices A and and . We prove that for discrete semimodular lattices and this latter condition holds if and only if and have isomorphic graphs and the isomorphism preserves the order on all cover-preserving sublattices of which are isomorphic to the seven-element, semimodular, nonmodular lattice (see Figure 1). This answers in the affirmative a question posed by J. Jakubik.     

Extremal problems for linear orders on [n] p

Let be a product order on [n] ^p i.e. for A, B [n] ^p , 1a ₁<a ₂<...<a _p º-n and 1<-b ₁<b ₂<...<b _p <-n we have AB iff a _i<-b _i for all i=1, 2,..., p. For a linear extension < of (ordering [n] ^p as ) let F _< ^[n],p (m) count the number of A _i 's, i<-m such that 1A _i. Clearly, for every m and <, where <l denotes the lexicographic order on [n] ^p . In this note we prove that the colexicographical order, <c, provides a corresponding lower bound i.e. that holds for any linear extension < of .This project together with [2] was initiated by the first author and continued in colaboration with the second author. After the death of the first author the work was continued and finalized by the second and the third author.Research supported by NSF grant DMS 9011850.     

Sublattices of complete lattices with continuity conditions

Various embedding problems of lattices into complete lattices are solved. We prove that for any join-semilattice S with the minimal join-cover refinement property, the ideal lattice Id S of S is both algebraic and dually algebraic. Furthermore, if there are no infinite D-sequences in J(S), then Id S can be embedded into a direct product of finite lower bounded lattices. We also find a system of infinitary identities that characterize sublattices of complete, lower continuous, and join-semidistributive lattices. These conditions are satisfied by any (not necessarily finitely generated) lower bounded lattice and by any locally finite, join-semidistributive lattice. Furthermore, they imply M. Erné’s dual staircase distributivity.On the other hand, we prove that the subspace lattice of any infinite-dimensional vector space cannot be embedded into any ℵ₀-complete, ℵ₀-upper continuous, and ℵ₀-lower continuous lattice. A similar result holds for the lattice of all order-convex subsets of any infinite chain.Dedicated to the memory of Ivan RivalReceived April 4, 2003; accepted in final form June 16, 2004.This revised version was published online in August 2005 with a corrected cover date.     

Small sublattices with large dominions

Two examples of finite sublattices with infinite dominions are given. It is proven that this cannot occur in a finitely generated lattice variety. Received May 10, 2001; accepted in final form October 6, 2005.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.