Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: The quantifier semigroup for bipartite graphs. | The quantifier semigroup for bipartite graphs Leonard J. Schulman Submitted Jun 22 2010 Accepted May 17 2011 Published May 30 2011 Mathematics Subject Classification 06A15 06F05 Abstract In a bipartite graph there are two widely encountered monotone mappings from subsets of one side of the graph to subsets of the other side one corresponds to the quantifier there exists a neighbor in the subset and the other to the quantifier all neighbors are in the subset. These mappings generate a partially ordered semigroup which we characterize in terms of run-unimodal words. 1 Introduction Every bipartite graph G c U X V defines a Galois connection consisting of the following pair of maps between the boolean algebras 0 1 U and 0 1 V e 0 1 U 0 1 V defined by e S v G v Cl S 0 a 0 1 V 0 1 U defined by a T u G u c T Here G v denotes u u v G G and G u denotes v u v G G . Thus e S consists of vertices v for which there exists an edge connecting them to S while a T consists of vertices u all of whose edges connect to T. Each of the maps e and a is monotone increasing and they satisfy the Galois identities eae e aea a. These identities are equivalent to each other because of the identity e a where denotes complement with respect to U or V as appropriate. Galois connections are a unifying framework for many closure operators on set systems the closure being defined by either ea or ae depending on the situation 8 2 9 11 10 1 13 . Examples 1 U consists of the points of a topology V consists of its open sets G is membership. Here aeS the topological closure of S. 2 U consists of the points of a Euclidean space V schulman@. Caltech Pasadena CA 91125. Supported in part by NSF CCR-0326554 NSF CCF-0515342 NSA H98230-06-1-0074 and NSF CCF-0829909. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P123 1 consists of its closed affine halfspaces G is membership. Here aeS the convex span of S. 3 U consists of the points of a finite-dimensional vector space over some field V is the ring
