Negative Correlation Properties for Matroids

by Erickson, Alejandro

Abstract (Summary)
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,f\in X\}) \leq P(\{X:e\in X\})P(\{X:f\in X\})$$

for certain measures, $P$, on the ground set.

Let $\mathcal M$ be a matroid. Let $(y_g:g\in E)$ be a weighting of the ground set and let

$${Z = \sum_{X}\left( \prod_{x\in X} y_x\right) }$$

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 is I-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.

Bibliographical Information:


School:University of Waterloo

School Location:Canada - Ontario

Source Type:Master's Thesis

Keywords:negative correlation matroid rayleigh balance association paving combinatorics and optimization


Date of Publication:01/01/2008

© 2009 All Rights Reserved.