Font Size: a A A

Negative correlation properties for matroids

Posted on:2010-05-09Degree:M.MathType:Thesis
University:University of Waterloo (Canada)Candidate:Erickson, AlejandroFull Text:PDF
GTID:2440390002989955Subject:Mathematics
Abstract/Summary:PDF Full Text Request
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 PX:e,f∈X ≤PX:e∈ XP X:f∈X for certain measures, P, on the ground set.;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.;Let M be a matroid. Let (yg : g ∈ E) be a weighting of the ground set and let Z=X x∈Xyx be the polynomial which generates Z-sets, were Z ∈ {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 Ze indicate partial derivative. Then M is Z-Rayleigh if ZeZf -- ZZef ≥ 0 for every positive evaluation of the ygs.
Keywords/Search Tags:Negative correlation, Matroids
PDF Full Text Request
Related items