Classification of the factorial functions of Eulerian binomial and Sheffer posets

We give a complete classification of the factorial functions of Eulerian binomial posets. The factorial function B(n) either coincides with n!, the factorial function of the infinite Boolean algebra, or ²n−1, the factorial function of the infinite butterfly poset. We also classify the factorial functions for Eulerian Sheffer posets. An Eulerian Sheffer poset with binomial factorial function B(n)=n! has Sheffer factorial function D(n) identical to that of the infinite Boolean algebra, the infinite Boolean algebra with two new coatoms inserted, or the infinite cubical poset. Moreover, we are able to classify the Sheffer factorial functions of Eulerian Sheffer posets with binomial factorial function B(n)=²n−1 as the doubling of an upside-down tree with ranks 1 and 2 modified. When we impose the further condition that a given Eulerian binomial or Eulerian Sheffer poset is a lattice, this forces the poset to be the infinite Boolean algebra BX or the infinite cubical lattice . We also include several poset constructions that have the same factorial functions as the infinite cubical poset, demonstrating that classifying Eulerian Sheffer posets is a difficult problem.     

On double bound graphs and forbidden subposets

For a poset P=(X,≤_P), the double bound graph (DB-graph) of P is the graph DB(P)=(X,E_DB(P)), where xy∈E_DB(P) if and only if x≠y and there exist n,m∈X such that n≤_Px,y≤_Pm. We obtain that for a subposet Q of a poset P,Q is an (n, m)-subposet of P if and only if DB(Q) is an induced subgraph DB(P). Using this result, we show some characterizations of split double bound graphs, threshold double bound graphs and difference double bound graphs in terms of (n, m)-subposets and double canonical posets.     

Groups with the same prime graph as the orthogonal group B n (3)

Let G be a finite group. The prime graph of G is denoted by Γ(G). It is proved in [1] that if G is a finite group such that Γ(G) = Γ(B _p (3)), where p > 3 is an odd prime, then G ? B _p (3) or C _p (3). In this paper we prove the main result that if G is a finite group such that Γ(G) = Γ(B _n (3)), where n ≥ 6, then G has a unique nonabelian composition factor isomorphic to B _n (3) or C _n (3). Also if Γ(G) = Γ(B ₄(3)), then G has a unique nonabelian composition factor isomorphic to B ₄(3), C ₄(3), or ² D ₄(3). It is proved in [2] that if p is an odd prime, then B _p (3) is recognizable by element orders. We give a corollary of our result, generalize the result of [2], and prove that B _2k+1(3) is recognizable by the set of element orders. Also the quasirecognition of B _2k (3) by the set of element orders is obtained.     

Linear extension diameter of subposets of Boolean lattice induced by two levels

The linear extension diameter of a finite poset P is the diameter of the graph on all linear extensions of P as vertices, two of them being adjacent whenever they differ in exactly one (adjacent) transposition. Recently, Felsner and Massow determined the linear extension diameter of the Boolean lattice B, and they posed a question of determining the linear extension diameter of a subposet of B induced by two levels. We solve the case of the 1st and kth level. The diametral pairs are obtained from minimal vertex covers of so called dependency graphs, a new concept which may be useful also for the general case.     

Two applications of semi-stable graphs

A Michigan graph G on a vertex set V is called semi-stable if for some υ?V, Γ(G_υ) = Γ(G)_υ. It can be shown that all regular graphs are semi-stable and this fact is used to show (i) that if Γ(G) is doubly transitive then G = K_n or K?_n, and (ii) that Γ(G) can be recovered from Γ(G_υ). The second result is extended to the case of stable graphs.     

On the genus of generalized unit and unitary Cayley graphs of a commutative ring

Let R be a commutative ring, U(R) be the set of all unit elements of R, G be a multiplicative subgroup of U(R) and S be a non-empty subset of G such that S ^?1={s ^?1:?s∈S}?S. In [16], K. Khashyarmanesh et al. defined a graph of R, denoted by Γ(R,G,S), which generalizes both unit and unitary Cayley graphs of R. In this paper, we derive several bounds for the genus of Γ(R,U(R),S). Moreover, we characterize all commutative Artinian rings R for which the genus of Γ(R,U(R),S) is one. This leads to the characterization of all commutative Artinian rings whose unit and unitary Cayley graphs have genus one.     

Monadic Algebras with finite degree

A monadic algebraA has finite degreen ifA/M has at most 2 ⁿ elements for every maximal idealM ofA and this bound is obtained for someM. Every countable monadic algebra with a finite degree is isomorphic to an algebra Γ(X, S) whereX is a Boolean space andS is a subsheaf of a constant sheaf with a finite simple stalk. This representation is used to prove that every proper equational class of monadic algebras has a decidable first-order theory.     

On distance two graphs of upper bound graphs

For a poset P=(X,≤), the upper bound graph (UB-graph) of P is the graph U=(X,E_U), where uv∈E_U if and only if u≠v and there exists m∈X such that u,v≤m. For a graph G, the distance two graph DS₂(G) is the graph with vertex set V(DS₂(G))=V(G) and u,v∈V(DS₂(G)) are adjacent if and only if d_G(u,v)=2. In this paper, we deal with distance two graphs of upper bound graphs. We obtain a characterization of distance two graphs of split upper bound graphs.     

On the Möbius function of the locally finite poset associated with a numerical semigroup

Let S be a numerical semigroup and let (?,≤ _S ) be the (locally finite) poset induced by S on the set of integers ? defined by x≤ _S y if and only if y?x∈S for all integers x and y. In this paper, we investigate the Möbius function associated to (?,≤ _S ) when S is an arithmetic semigroup.     

Menger's Theorem for Graphs Containing no Infinite Paths

Menger's theorem can be stated as follows: Let G = (V, E) be a finite graph, and let A and B be subsets of V. Then there exists a family F of vertex-disjoint paths from A to B and a subset S of V which separates A and B, such that S consists of a choice of precisely one vertex from each path in F.Erdös conjectured that in this form the theorem can be extended to infinite graphs. We prove this to be true for graphs containing no infinite paths, by showing that in this case the problem can be reduced to the case of bipartite graphs.     

Homogeneity conditions in graphs

Let P be a class of graphs; a graph Γ with vertex set V is locally P-homogeneous if whenever U ? V and the vertex subgraph (U) lies in P, then each automorphism of (U) extends to an automorphism of Γ. Let C be the class of connected graphs, Q the class of cones, R the class of “rakes”; we classify locally finite, locally C-homogeneous graphs, and prove that a locally finite, locally (Q ? R)-homogeneous graph is either locally C-homogeneous, or is the Levi graph of the sevenpoint projective plane.     

Zero-dimensional proximities and zero-dimensional compactifications

We introduce zero-dimensional proximities and show that the poset 〈Z(X),?〉 of inequivalent zero-dimensional compactifications of a zero-dimensional Hausdorff space X is isomorphic to the poset 〈Π(X),?〉 of zero-dimensional proximities on X that induce the topology on X. This solves a problem posed by Leo Esakia. We also show that 〈Π(X),?〉 is isomorphic to the poset 〈B(X),⊆〉 of Boolean bases of X, and derive Dwinger's theorem that 〈Z(X),?〉 is isomorphic to 〈B(X),⊆〉 as a corollary. As another corollary, we obtain that for a regular extremally disconnected space X, the Stone-?ech compactification of X is a unique up to equivalence extremally disconnected compactification of X.     

On Poset Boolean Algebras

Let (P,≤) be a partially ordered set. The poset Boolean algebra of P, denoted F(P), is defined as follows: The set of generators of F(P) is {x _p  : p∈P}, and the set of relations is {x _p ⋅x _q =x _p  : p≤q}. We say that a Boolean algebra B is well-generated, if B has a sublattice G such that G generates B and (G,≤ ^B |G) is well-founded. A well-generated algebra is superatomic. THEOREM 1. Let (P,≤) be a partially ordered set. The following are equivalent. (i) P does not contain an infinite set of pairwise incomparable elements, and P does not contain a subset isomorphic to the chain of rational numbers, (ii) F(P) is superatomic, (iii) F(P) is well-generated. The equivalence (i) ⇔ (ii) is due to M. Pouzet. A partially ordered set W is well-ordered, if W does not contain a strictly decreasing infinite sequence, and W does not contain an infinite set of pairwise incomparable elements. THEOREM 2. Let F(P) be a superatomic poset algebra. Then there are a well-ordered set W and a subalgebra B of F(W), such that F(P) is a homomorphic image of B. This is similar but weaker than the fact that every interval algebra of a scattered chain is embeddable in an ordinal algebra. Remember that an interval algebra is a special case of a poset algebra. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some Remarks on the Graph Γ I (R)

Let R be a commutative ring with nonzero identity and Z(R) its set of zero-divisors. The zero-divisor graph of R is Γ(R), with vertices Z(R)?{0} and distinct vertices x and y are adjacent if and only if xy = 0. For a proper ideal I of R, the ideal-based zero-divisor graph of R is Γ _I (R), with vertices {x ∈ R?I | xy ∈ I for some y ∈ R?I} and distinct vertices x and y are adjacent if and only if xy ∈ I. In this article, we study the relationship between the two graphs Γ(R) and Γ _I (R). We also determine when Γ _I (R) is either a complete graph or a complete bipartite graph and investigate when Γ _I (R) ? Γ(S) for some commutative ring S.     

Note on upper bound graphs and forbidden subposets

In the upper bound graph of a poset P, the vertex set is V(P) and xy is an edge if there exists an m∈V(P) with x,y≤_Pm. We show some characterizations on split upper bound graphs, threshold upper bound graphs and difference upper bound graphs in terms of m-subposets and canonical posets.     

Generalizations of Boolean products for lattice-ordered algebras

It is shown that the Boolean center of complemented elements in a bounded integral residuated lattice characterizes direct decompositions. Generalizing both Boolean products and poset sums of residuated lattices, the concepts of poset product, Priestley product and Esakia product of algebras are defined and used to prove decomposition theorems for various ordered algebras. In particular, we show that FL_w-algebras decompose as a poset product over any finite set of join irreducible strongly central elements, and that bounded n-potent GBL-algebras are represented as Esakia products of simple n-potent MV-algebras.     

On the combinatorial rank of a graded braided bialgebra

Let B be a graded braided bialgebra. Let S(B) denote the algebra obtained dividing out B by the two sided ideal generated by homogeneous primitive elements in B of degree at least two. We prove that S(B) is indeed a graded braided bialgebra quotient of B. It is then natural to compute S(S(B)), S(S(S(B))) and so on. This process yields a direct system whose direct limit comes out to be a graded braided bialgebra which is strongly N-graded as a coalgebra. Following V.K. Kharchenko, if the direct system is stationary exactly after n steps, we say that B has combinatorial rank n and we write κ(B)=n. We investigate conditions guaranteeing that κ(B) is finite. In particular, we focus on the case when B is the braided tensor algebra T(V,c) associated to a braided vector space (V,c), providing meaningful examples such that κ(T(V,c))≤1.     

Cover-preserving order embeddings into Boolean lattices

It is not known which finite graphs occur as induced subgraphs of a hypercube. This is relevant in the theory of parallel computing. The ordered version of the problem is: Which finite posets P occur as cover-preserving subposets of a Boolean lattice? Our main Theorem gives (for 0,1-posets) a necessary and sufficient condition, which involves the chromatic number of a graph associated to P. It is applied respectively to upper balanced, meet extremal, meet semidistributive, and semidistributive lattices P. More specifically, we consider isometric embeddings of posets into Boolean lattices. In particular, answering a question of Ivan Rival to the positive, a nontrivial invariant for the covering graph of a poset is found.