Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "An extension of matroid rank submodularity and the Z-Rayleigh property"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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: An extension of matroid rank submodularity and the Z-Rayleigh property. | An extension of matroid rank submodularity and the Z-Rayleigh property Arun P. Mani Clayton School of Information Technology Monash University Clayton VIC 3800 Australia arunpmani@gmail.com Submitted Mar 24 2011 Accepted May 6 2011 Published May 16 2011 Mathematics Subject Classification 05B35 Abstract We define an extension of matroid rank submodularity called R-submodularity and introduce a minor-closed class of matroids called extended submodular matroids that are well-behaved with respect to R-submodularity. We apply R-submodularity to study a class of matroids with negatively correlated multivariate Tutte polynomials called the Z-Rayleigh matroids. First we show that the class of extended submodular matroids are Z-Rayleigh. Second we characterize a minor-minimal non-Z-Rayleigh matroid using its R-submodular properties. Lastly we use R-submodularity to show that the Fano and non-Fano matroids neither of which is extended submodular are Z-Rayleigh thus giving the first known examples of Z -Rayleigh matroids without the half-plane property. 1 Introduction and background One of the fundamental axioms of a matroid rank function is its submodular property. For a matroid M E p this is stated as follows 11 p.23 . SM For all X Y c E p X u Y p X n Y p X p Y . In this paper we define the following extension of submodularity. For mutually disjoint P1 P2 R c E we say P1 and P2 are R-submodular in M if there exists a bijection n 2R 2r such that for all C c R p Pi UP2UC p R C p PiunC p P2uR nC . Under our definition the property SM is equivalent to the 0-submodularity of sets X Y and Y X in the minor M X n Y for all X Y c E. We further say the matroid M E p is extended submodular if for all mutually disjoint subsets P1 P2 R c E the sets P1 and P2 are R-submodular in M and its minors. We show that the class of all extended THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P113 1 submodular matroids is closed under some fundamental matroid operations and includes the uniform .