# Negative Correlation Properties for Matroids

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

Advisor:

School:University of Waterloo

School Location:Canada - Ontario

Source Type:Master's Thesis

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

ISBN:

Date of Publication:01/01/2008