Physical Sciences and Mathematics Commons^™

Extremal Problems In Matroid Connectivity, John Tyler Moss

LSU Doctoral Dissertations

Matroid k-connectivity is typically defined in terms of a connectivity function. We can also say that a matroid is 2-connected if and only if for each pair of elements, there is a circuit containing both elements. Equivalently, a matroid is 2-connected if and only if each pair of elements is in a certain 2-element minor that is 2-connected. Similar results for higher connectivity had not been known. We determine a characterization of 3-connectivity that is based on the containment of small subsets in 3-connected minors from a given list of 3-connected matroids. Bixby’s Lemma is a well-known inductive tool in …