Applications of Powerset Operators, Especially to Matroids

<p>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.</p><p>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. </p><p>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.</p><p>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.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Mathematics

Year

2022

Author dc:creator

• Uricchio, Nathan

Contributors dc:contributor

• Graver, Jack E.

• Circuits
• Clutter
• Duality
• Matroid
• Operator
• Powerset
• Mathematics
• Physical Sciences and Mathematics

Repository record dc:identifier

https://surface.syr.edu/etd/1369

OAI identifier oai:identifier

oai:surface.syr.edu:etd-2370