On the structure of orthomodular posets

It is shown how all orthomodular posets (of various kinds) are constructible from families of sets satisfying various conditions, usually with the generating family emerging as identical with (or contained in) the family of frames (that is, maximal orthogonal subsets of the non-zero elements) of the constructed orthomodular poset.     

Random graphs and covering graphs of posets

For a graph G, we define c(G) to be the minimal number of edges we must delete in order to make G into a covering graph of some poset. We prove that, if p=n ^-1+(n) ,where (n) is bounded away from 0, then there is a constant k ₀>0 such that, for a.e. G _p , c(G _p )k ₀ n ¹⁺⁽ⁿ⁾ .In other words, to make G _p into a covering graph, we must almost surely delete a positive constant proportion of the edges. On the other hand, if p=n ^-1+(n) , where (n)0, thenc(G _p )=o(n ¹⁺⁽ⁿ⁾ ), almost surely.Partially supported by MCS Grant 8104854.     

Topological representation of posets

There is a canonical imbedding of a poset into a complete Boolean lattice and hence into a Boolean lattice. This gives it a representation as a collection of clopen sets of a Boolean space. There are reflective functions from a category of distributive posets to the subcategories of distributive and Boolean lattices and consequently a topological dual equivalence that extends the Stone duality of Boolean lattices.Presented by B. Jonsson.     

The dimension of orthomodular posets constructed by pasting Boolean algebras

The main aim of this paper is the calculation of the dimension of certain atomic amalgams. These consist of finite Boolean algebras (blocks) pasted together in such a way that a pair of blocks intersects either trivially in the bounds, or the intersection consists of the bounds, an atom, and its complement.     

Small orthomodular partial algebras

Orthomodular partial algebras (OMAs) can be seen as the algebraic representation of orthomodular posets. We use Greechie diagrams for the graphical representation of OMAs and investigate characterizations for the strong embeddability of a given OMA into a Boolean OMA. We present a complete list of the Greechie diagrams of OMAs up to 24 elements, and we show that there exists an infinite OMA that is generated by 4 elements.     

Torus graphs and simplicial posets

For several important classes of manifolds acted on by the torus, the information about the action can be encoded combinatorially by a regular n-valent graph with vector labels on its edges, which we refer to as the torus graph. By analogy with the GKM-graphs, we introduce the notion of equivariant cohomology of a torus graph, and show that it is isomorphic to the face ring of the associated simplicial poset. This extends a series of previous results on the equivariant cohomology of torus manifolds. As a primary combinatorial application, we show that a simplicial poset is Cohen-Macaulay if its face ring is Cohen-Macaulay. This completes the algebraic characterisation of Cohen-Macaulay posets initiated by Stanley. We also study blow-ups of torus graphs and manifolds from both the algebraic and the topological points of view.     

Adjacency posets of planar graphs

In this paper, we show that the dimension of the adjacency poset of a planar graph is at most 8. From below, we show that there is a planar graph whose adjacency poset has dimension 5. We then show that the dimension of the adjacency poset of an outerplanar graph is at most 5. From below, we show that there is an outerplanar graph whose adjacency poset has dimension 4. We also show that the dimension of the adjacency poset of a planar bipartite graph is at most 4. This result is best possible. More generally, the dimension of the adjacency poset of a graph is bounded as a function of its genus and so is the dimension of the vertex-face poset of such a graph.     

Sources in posets and comparability graphs

A vertex in a poset is a source if its indegree is zero. Further, a vertex in a comparability graph G is a source if there is a transitive orientation of G in which is a source. We characterize sources in comparability graphs in terms of forbidden subgraphs. Certain results follow, including a brief proof of a theorem by Olariu.     

Greechie diagrams of orthomodular partial algebras

Greechie diagrams are well known graphical representations of orthomodular partial algebras, orthomodular posets and orthomodular lattices. For each hypergraph D a partial algebra ⟦D⟧ = (A; ⊕, ′, 0) of type (2,1,0) can be defined. A Greechie diagram can be seen as a special hypergraph: different points of the hypergraph have different interpretations in the corresponding partial algebra ⟦D⟧, and each line in the hypergraph has a maximal Boolean subalgebra as interpretation, in which the points are the atoms. This paper gives some generalisations of the characterisations in [K83] and [D84] of diagrams which represent orthomodular partial algebras (= OMAs), and we give an algorithm how to check whether a given hypergraph D is an OMA-diagram whose maximal Boolean subalgebras are induced by the lines of the hypergraph. Received July 22, 2004; accepted in final form February 1, 2007.     

Some theorems on graphs and posets

In this journal, Leclerc proved that the dimension of the partially ordered set consisting of all subtrees of a tree T, ordered by inclusion, is the number of end points of T. Leclerc posed the problem of determining the dimension of the partially ordered set P consisting of all induced connected subgraphs of a connected graph G for which P is a lattice.In this paper, we prove that the poset P consisting of all induced connected subgraphs of a nontrivial connected graph G, partially ordered by inclusion, has dimension n where n is the number of noncut vertices in G whether or not P is a lattice. We also determine the dimension of the distributive lattice of all subgraphs of a graph.     

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.     

Simultaneous dominance representation of multiple posets

We characterize the codominance pairs-pairs of posets that admit simultaneous dominance representations in the (x, y)-and (–x, y)-coordinate systems-and present a linear algorithm to recognize them and construct codominance representations. We define dominance polysemy as a generalization of codominance and describe several related problems and preliminary results.This author's research, supported in part by NSF grant CCR-9300079, also appears in his doctoral thesis [15], written, at the Johns Hopkins University under the supervision of Professors Edward R. Scheinerman and Michael T. Goodrich.This author's research, supported in part by an NSERC operating grant and an FCAR team grant, was performed in part during a visit at INRIA Sophia Antipolis.     

Bipartite Q-polynomial distance-regular graphs and uniform posets

Let Γ denote a bipartite distance-regular graph with vertex set X and diameter D≥3. Fix x∈X and let L (resp., R) denote the corresponding lowering (resp., raising) matrix. We show that each Q-polynomial structure for Γ yields a certain linear dependency among RL ², LRL, L ² R, L. Define a partial order ≤ on X as follows. For y,z∈X let y≤z whenever ?(x,y)+?(y,z)=?(x,z), where ? denotes path-length distance. We determine whether the above linear dependency gives this poset a uniform or strongly uniform structure. We show that except for one special case a uniform structure is attained, and except for three special cases a strongly uniform structure is attained.     

The zero divisor graphs of Boolean posets

In this paper, it is proved that if B is a Boolean poset and S is a bounded pseudocomplemented poset such that S\Z(S) = {1}, then Γ(B) ≌ Γ(S) if and only if B ≌ S. Further, we characterize the graphs which can be realized as zero divisor graphs of Boolean posets.     

A note on chordal bound graphs and posets

We study relations between induced subgraphs and (n,m)-subposets. Using properties of (n,m)-subposets, we consider a characterization of chordal double bound graphs in terms of forbidden subposets. Furthermore, we deal with properties of a poset whose double bound graph is isomorphic to its upper bound graph or its comparability graph, etc.     

Vectorspacelike representation of absolute planes

The pointset E of an absolute plane can be provided with a binary operation "+" such that (E, +) becomes a loop and for each a E \ {o} the line [a] through o and a is a commutative subgroup of (E, +). Two elements a, b E \ {o} are called independent if [a] ∩ [b] = {o} and the absolute plane is called vectorspacelike if for any two independent elements we have E = [a] + [b] := {x + y | x [a], y [b]}. If is singular then (E, +) is a commutative group and is vectorspacelike iff is Euclidean. If is a hyperbolic plane then is vectorspacelike and in the continous case if a, b are independent, each point p has a unique representation as a quasilinear combination p = α · a + μ · b where α · a [a]and β · b [b] are points, α, β real numbers such that λ (o, λ · a) = |λ|· λ (o, a) and λ (o, μ · b) = |μ|. λ(o, b) and λ is the distance function. This work was partially supported by the Research Project of MIUR (Italian Ministery of Education and University) “Geometria combinatoria e sue applicazioni” and by the research group GNSAGA of INDAM. Dedicated to Walter Benz on the occasion of his 75 ^th birthday, in friendship     

Imprimitive distance-regular graphs and projective planes

We investigate a class of (imprimitive) covering graphs Γ of complete bipartite graphs K_k,k and show that they are in one-to-one correspondence with triples (P, l, P), where P is a projective plane of order k and (l, P) is a distinguished flag of P. If Γ is distance-transitive, then P ? l is a self-dual rank three translation plane and may be coordinatised by a semifield.