Negative Correlation Properties for Matroids

negative correlation;matroid;Rayleigh;balance;negative association;paving;Combinatorics and Optimization

Erickson, Alejandro

University of Waterloo

关键词: negative correlation;    matroid;    Rayleigh;    balance;    negative association;    paving;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/4165/1/Erickson_Alejandro.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

In pursuit of negatively associated measures, this thesis focuses on certain negative correlation properties in matroids.In particular, the results presented contribute to the search for matroids which satisfy $$P({X:e,fin X}) leq P({X:ein X})P({X:fin X})$$ for certain measures, $P$, on the ground set.Let $mathcal M$ be a matroid.Let $(y_g:gin E)$ be a weighting of the ground set and let $${Z = sum_{X}left( prod_{xin X} y_xight) }$$be the polynomial which generates Z-sets, were Z $in {$ B,I,S $}$.For each of these, the sum is over bases, independent sets and spanning sets, respectively.Let $e$ and $f$ be distinct elements of $E$ and let $Z_e$ indicate partial derivative.Then $mathcal M$ is Z-Rayleigh if $Z_eZ_f-ZZ_{ef}geq 0$ for every positive evaluation of the $y_g$s. The known elementary results for the B, I and S-Rayleigh properties and two special cases called negative correlation and balance are proved.Furthermore, several new results are discussed.In particular, if a matroid is binary on at most nine elements or paving or rank three, then it isI-Rayleigh if it is B-Rayleigh.Sparse paving matroids are B-Rayleigh.The I-Rayleigh difference for graphs on at most seven vertices is a sum of monomials times squares of polynomials and this same special form holds for all series parallel graphs.