Circular flow and circular chromatic number in the matroid context

摘要

This thesis considers circular flow-type and circular chromatic-type parameters ($phi$ and $chi$, respectively) for matroids. In particular we focus on orientable matroids and sixth root of unity matroids. These parameters are obtained via two approaches: algebraic and orientation-based. The general questions we discuss are: bounds for flow number; characterizations of Eulerian and bipartite matroids; and possible connections between the two possible extensions of $phi$: algebraic and orientation. In the case of orientable matroids, we obtain characterizations of bipartite rank-3 matroids and Eulerian uniform, rank-3 matroids; an asymptotic result regarding the flow number of uniform matroids; and an improvement on the known bound for flow number of matroids of arbitrary rank. This bound is further improved for the uniform case. For sixth root of unity matroids, we examine an algebraic extension of the parameters $chi$ and $phi$. We also introduce a notion of orientation and the corresponding flow and chromatic numbers applicable to this class. We investigate the possibility of a connection between the algebraic and orientation-based parameters, akin to that established for regular matroids by Hoffmanu27s Circulation Lemma and we obtain a partial connection. We extend the notion of ``Eulerianu27u27 to sixth root of unity matroids. We call such matroids hex-Eulerian. We show that every maximum-sized sixth root of unity matroid, of fixed rank, is hex-Eulerian. We also show that a regular matroid is hex-Eulerian if and only if it admits a nowhere-zero 3-flow. We include an extension of Tutteu27s chain groups, which characterize regular matroids, to what we term hex-chain modules which describe sixth root of unity matroids.