Date of Award
Spring 5-15-2022
Degree Type
Dissertation
Degree Name
Doctor of Philosophy (PhD)
Department
Mathematics
Advisor(s)
Graver, Jack E.
Keywords
Circuits, Clutter, Duality, Matroid, Operator, Powerset
Subject Categories
Mathematics | Physical Sciences and Mathematics
Abstract
Let \(\mathcal{V}\) denote a vector space over an arbitrary field with an inner product. For any collection \(\mathcal{S}\) of vectors from \(\mathcal{V}\) the collection of all vectors orthogonal to each vector in \(\mathcal{S}\) is a subspace, denoted as \(\mathcal{S}^{\perp_v}\) and called the \textit{orthogonal complement} of \(\mathcal{S}\). One of the fundamental theorems of vector space theory states that, \((\mathcal{S}^{\perp_v})^{\perp_v}\) is the subspace \textit{spanned} by \(\mathcal{S}\). Thus the ``spanning'' operator on the subsets of a vector space is the square of the ``orthogonal complement'' operator.
In matroid theory, the orthogonal complement of a matroid \(M\) is also well-defined and similarly results in another matroid. Although this new matroid is more commonly referred to as the `dual matroid', denoted as \(M^*\), and typically formed using a very different approach. There is an interesting relation between the circuits of a matroid \(M\) and the cocircuits of \(M\) (the circuits of its dual matroid \(M^*\)) which aligns much more closely to the orthogonal complement of a vector space.
We expand on this relation to define a powerset operator: \((\phantom{S})^*\). Given \(\mathcal{S} \subseteq \mathcal{P}(E)\), we denote \(\mathcal{S}^*\) to be the minimal sets of \(\{X \subseteq E \colon X \text{ is nonempty, } |X \cap A| \neq 1 \text{ for each } A \in \mathcal{S}\}\). We call this powerset operator the \textbf{circuit duality operator}. Unlike the vector space orthogonal complement operator, this circuit duality operator may not behave as nicely when applied to collections that do not correspond to a matroid.
This thesis is an investigation into the development of tools and additional operators to help understand the collections of sets that result in a matroid under one or more applications of the circuit duality operator.
Access
Open Access
Recommended Citation
Uricchio, Nathan, "Applications of Powerset Operators, Especially to Matroids" (2022). Dissertations - ALL. 1369.
https://surface.syr.edu/etd/1369