On poset theoretic view point of combinatorics

Abstract

A lattice flavour in geometry has been vigorously introduced by Turtle, who treated a terminology of his own and gave a clear exposition to the connection between two theories; namely, Lattice theory and Geometry. G. Birkhoff, 1935 introduced geometrical lattices as natural consequences of lattice involved with geometry. With the introduction of fuzzy theory even geometry is taking a fascinating shape. Buckley and Eslami have studied fuzzy plane geometry. R.N. Lal & others introduced the concept of fuzziness in a linear geometry. Birkhoff studied the projective geometry by the lattice of all subspaces of a vector space. It has now become a subject of special interest to study thoroughly the structure of the lattice substructures of an algebraic structure. Several ideas of lattice theory were carried out for combinatorial study. Henry Crapo and Gian-Carlo Rota contended that further progress in the foundations of combinatorial theory would depend largely upon the understanding of certain order structures which would arise in combinatorial situations. Birkhoff introduced geometric lattices as natural consequences of lattices involved with geometries. He proved that such lattices are closely connected with geometric configuration of points, lines, planes etc. It should be noted that such configurations are not all lattices (many are simply posets), those which are lattices are especially interesting and many of these can be identified with classical mathematical structures. Birkhoff proved that every modular geometric lattice is a product of projective geometries and a Boolean algebra. This result led Birkhoff to characterize projective geometries as irreducible modular geometric lattices. Karl Menger obtained a similar but more complicated lattice theoretic characterization of affine geometries and discussed the subspace – lattice of real non-Euclidean (hyperbolic) geometries. The structure of lattice subspaces has not been studied systematically. Recently lattice-subspaces have been employed in economics. Therefore, there exists naturally an open question : How for geometric lattices can be translated into Economics? Benoumhani enriched the number theory by an elegant application of geometric lattices. In the first chapter we shall consider closure operator whose lattices of closed sets are not necessarily semi-modular. In the first section we characterize closure spaces with the Steinitz exchange property and discuss the connection with the Mac Lane exchange property and related exchange properties studied by Dlats, Gaskill and Rival, Edelman. Section 2 presents a generalization of Kurosh-Ore theorem for modular lattices to closure space which also have the Steinitz exchange property but may otherwise have subadditive rank functions only. Section 3 is devoted to the notion of a dimension function in a closure space which generally differs from the rank function. Particular attention is paid to cyclic sub-modular closure spaces. A characterization theorem for a cyclic sub modular closure space has been proved in term of monotone dimension function. The second chapter focuses on the fundamental correspondence-originally discovered by C. Greene, following his joint work with D. J. Kleitman - that associates a Ferrers shape (p) to every finite poset P. The number of boxes in the first k rows (resp. columns) of (p) equals the maximal number of elements in a union of k chains (resp. antichains) in P. The correspondence P  (P) is intimately related to at least three areas, of discrete mathematics: combinatorial optimization, lattice theory, and the combinatorics of tableaux. The main idea is to develop the theory - from scratch and with complete proofs - by consistently applying the poset-theoretic viewpoint. In this spirit, we begin our presentation in Section 2 by stating the fundamental theorem of Curtis Greene that introduces the map P  (P), and then formulate the basic properties of this correspondence. Sections 2 and 3 are devoted to tableau algorithms. We explain how the Robinson–Schensted correspondence and the Schutzenberger involution on standard Young tableaux arise in the special case of “permutation posets,” and show that the basic properties of these correspondence follow easily from this posettheoretic framework. In section 4, the original results of Greene and Kleitman on saturated families of chains and antichains are derived. In chapter third, we prove that if there is no edge in symmetric plane graph G intersected by its symmetry axis then the number of spanning trees of G can be expressed in terms of the product of the number of spanning trees of two smaller graphs, each of which has about half the number of vertices of G. Throughout this chapter, we assume that G = (V (G), E(G)) is a connected and unweighted graph with no loops, having vertex set V(G) = {al, a2, …, an} and edge set E(G) = {e1, e2, …, em}. Denote the degree of vertex ai by dG(ai) (or d(ai)), the diagonal matrix of G by D(G). The adjacency matrix of G by A(G), and the Laplacian matrix of G by L(G) = D(G) - A(G). We refer to Biggs for terminology and notation not defined in our work. Methods for enumerating spanning trees in a finite graph, a problem related to various areas of mathematics and physics, have been investigated for more than 150 years. We denote the number of spanning trees of the graph G by t(G). A well-known formula for t(G) is “the Matrix-Tree Theorem”, which expresses it as a determinant. The last chapter studies that for any base of the root lattice An, we can construct a signed graph naturally. A signed graph is a graph whose edges are signed by +1 or -1. For a given signed graph, Tsaranov, Seidel and Cameron constructed the corresponding root lattice. In the present work, we treated with signed graphs corresponding to the root lattice An. A connected graph is called a Fushimi tree if its all blocks are complete subgraphs. A Fushimi tree is said to be simple when by deleting any cut vertex, we have always its two connected components. Switching and local switching of signed graphs are also introduced by Cameron, Seidel and Tsaranov. A signed Fushimi tree is said to be a Fushimi tree with standard sign if it can be transformed to a signed Fushimi tree whose all edges are signed by +1, by a switching. We prove that any signed graph corresponding to An is a simple Fushimi tree with standard sign. Switching defines an equivalent relation in the set of all signed graphs. An equivalece class is called a switching class. Local switching partitions the all signed graphs on n vertices into clusters of switching classes. Our main result is that a simple Fushimi tree with standard sign is contained in the cluster given by the line. Some signed Fushimi trees are transformed to trees by a sequence of local Switching [T. Ishihara : Signed graphs associated with lattices An, J. Math., Univ. Tokushima, 36, 20002, 1-6]. Signed Cycles with odd party are transformed to trees by a sequence of local Switching, but Signed Cycles with even parity can’t be transformed to trees by no means. What kinds of graphs are transformed by a sequence of local Switching? It is important and interesting to give examples of signed graph which are transformed to trees by means of local Switching. In this chapter we shall study signed graph that are transformed to trees and shall give some simple examples of such Signed graph.