Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "On sums over partially ordered sets"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: On sums over partially ordered sets. | On sums over partially ordered sets Klaus Dohmen Institut fur Informatik Humboldt-Universitat zu Berlin Unter den Linden 6 D-10099 Berlin Germany e-mail dohmen@informatik.hu-berlin.de Submitted March 4 1999 Accepted July 13 1999. AMS Classification 05A15 05A19 05B35 06A15 Abstract We establish a general theorem for reducing sums of type yy x g y where g is a mapping from a partially ordered set into an abelian group. Conclusions concern the Mobius function the principle of inclusionexclusion the Tutte polynomial and Crapo s beta invariant. 1. Introduction Sums over partially ordered sets frequently occur in combinatorics and related fields. Each application of the principle of inclusion-exclusion for instance gives rise to such a sum. From a computational point of view the question wether such a sum can be reduced by excluding mutually cancelling terms is of fundamental importance e.g. when computing the probability content of a convex polyhedron 8 or when assessing the reliability of a network 6 12 . The difficulty lies in the circumstance that collections of mutually cancelling terms might not be disjoint whence in general such terms cannot be removed without affecting the value of the sum. In this paper we establish a very general theorem that offers the possibility of reducing sums of the specified type. After dualizing the theorem and deducing some corollaries the results are applied to the Mobius function of a partially ordered set and the principle of inclusion-exclusion thus rediscovering several recent results. Finally some conclusions to the Tutte polynomial and Crapo s beta invariant are drawn. THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R34 2 2. Sums over partially ordered sets We assume that the reader is familiar with partially ordered sets which are subsequently referred to as posets. Most order-theoretic terminologies and notations are standard and can be looked up in the text book of Stanley 13 . Some less standard terminologies are reviewed .