TAILIEUCHUNG - Báo cáo toán học: "A β INVARIANT FOR GREEDOIDS AND ANTIMATROIDS GARY GORDON"

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í toán học quốc tế đề tài: A β INVARIANT FOR GREEDOIDS AND ANTIMATROIDS GARY GORDON. | A p INVARIANT FOR GREEDOIDS AND ANTIMATROIDS GARY GORDON Department of Mathematics Lafayette College Easton PA 18042 gordong@ Submitted November 12 1996 Accepted March 28 1997. Abstract. We extend Crapo s 0 invariant from matroids to greedoids concentrating especially on antimatroids. Several familiar expansions for 0 G have greedoid analogs. We give combinatorial interpretations for 0 G for simplicial shelling antimatroids associated with chordal graphs. When G is this antimatroid and b G is the number of blocks of the chordal graph G we prove 0 G 1 b G . 1. Introduction In this paper we define a p invariant for antimatroids and greedoids. This continues the program of extending matroid invariants to greedoids which was begun in 17 where the 2-variable Tutte polynomial was defined for greedoids. The Tutte polynomial has been studied for several important classes of greedoids including partially ordered sets rooted graphs rooted digraphs and trees. Recently the one-variable characteristic polynomial 19 was extended from matroids to greedoids. Crapo s p invariant for matroids was introduced in 12 . If M is a matroid then p M is a non-negative integer which gives information about whether M is connected and whether M is the matroid of a series-parallel network. In particular p M 0 iff M is disconnected or M consists of a single loop 12 and P M 1 iff M is the matroid of a series-parallel network or M consists of a single isthmus 6 . More recently see 24 interest has focused on characterizing matroids with small p. A standard reference for many of the basic properties of p M is 28 . In Section 2 we give several elementary results each of which extends a corresponding matroid result. We define p G in terms of the Tutte polynomial then show p G has the same subset expansion as in the matroid case Proposition and obeys a slightly different deletion-contraction recursion Proposition . It is still true that p G1 G2 0 but the converse is false .

• Báo cáo khoa học
• tài liệu báo cáo nghiện cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học
• các bài toán hay
• trình bày báo cáo
• báo cáo ngành văn học
• báo cáo tiếng anh
• nghiên cứu văn thơ
• giọng điệu trào phúng
• nghiên cứu khoa học
• báo cáo khoa học
• thơ lục bát
• chính sách phát triển
• gia đình việt nam
• nghiên cứu xã hội