Return to search

Negative Correlation Properties for Matroids

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.

Identiferoai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/4165
Date January 2008
CreatorsErickson, Alejandro
Source SetsUniversity of Waterloo Electronic Theses Repository
LanguageEnglish
Detected LanguageEnglish
TypeThesis or Dissertation

Page generated in 0.0016 seconds