Browsing Combinatorics and Optimization by Subject "matroids"
Now showing items 1-9 of 9
-
Disasters in Abstracting Combinatorial Properties of Linear Dependence
(University of Waterloo, 2020-05-15)A notion of geometric structure can be given to a set of points without using a coordinate system by instead describing geometric relations between finite combinations of elements. The fundamental problem is to then ... -
Entropic Matroids and Their Representation
(Multidisciplinary Digital Publishing Institute, 2019)This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have ... -
The Linkage Problem for Group-labelled Graphs
(University of Waterloo, 2009-09-24)This thesis aims to extend some of the results of the Graph Minors Project of Robertson and Seymour to "group-labelled graphs". Let $\Gamma$ be a group. A $\Gamma$-labelled graph is an oriented graph with its edges labelled ... -
Matrix Formulations of Matching Problems
(University of Waterloo, 2000)Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation ... -
Modularity and Structure in Matroids
(University of Waterloo, 2013-04-22)This thesis concerns sufficient conditions for a matroid to admit one of two types of structural characterization: a representation over a finite field or a description as a frame matroid. We call a restriction N of a ... -
On The Density of Binary Matroids Without a Given Minor
(University of Waterloo, 2016-12-21)This thesis is motivated by the following question: how many elements can a simple binary matroid with no $\PG(t,2)$-minor have? This is a natural analogue of questions asked about the density of graphs in minor-closed ... -
On the Excluded Minors for Dyadic Matroids
(University of Waterloo, 2019-01-17)The study of the class of dyadic matroids, the matroids representable over both $GF(3)$ and $GF(5)$, is a natural step to finding the excluded minors for $GF(5)$-representability. In this thesis we characterize the ternary ... -
Quadratically Dense Matroids
(University of Waterloo, 2020-07-08)This thesis is concerned with finding the maximum density of rank-$n$ matroids in a minor-closed class. The extremal function of a non-empty minor-closed class $\mathcal M$ of matroids which excludes a rank-2 uniform ... -
The search for an excluded minor characterization of ternary Rayleigh matroids
(University of Waterloo, 2008-01-24)Rayleigh matroids are a class of matroids with sets of bases that satisfy a strong negative correlation property. Interesting characteristics include the existence of an efficient algorithm for sampling the bases of a ...