tailieunhanh - Báo cáo toán học: "An extension of matroid rank submodularity and the Z-Rayleigh property"

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@ 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 . 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 .