Matroids over partial fields from graphs embedded in surfaces

Guest post by Daniel Slilaty.

In a series of three posts by Irene Pivotto (on 08-26-13, 10-07-13, and 10-28-13) subscribers to The Matroid Union blog were introduced to biased graphs and their matroids. Again, a biased graph is a pair $(G,B)$ in which $G$ is a graph and $B$ is a collection of cycles in $G$ (called balanced) for which any theta subgraph of $G$ contains 0, 1, or 3 balanced cycles, i.e. not exactly two balanced cycles. (A theta subgraph is the union of a pair of cycles that intersect along a path.)

Biased graphs were first defined by Zaslavsky [Za91] and they are primarily used to characterize two types of matroids: single-element coextensions of graphic matroids and frame matroids [Za94]. Frame matroids contain the very important class of Dowling Geometries whose centrality within matroid theory was first displayed by Kahn and Kung [KK82] and more recently by Geelen, Gerards, and Whittle [GGW14]. Given a biased graph $(G,B)$, denote the frame matroid by $F(G,B)$ and the complete lift matroid by $L_0(G,B)$ (i.e., the single-element coextension of $M(G)$ defined by $B$).

The canonical examples of biased graphs are given by gains over a group. Formally, this is a function $\varphi\colon\vec E(G)\to\Gamma$ where $\vec E(G)$ is the collection of oriented edges of a graph (if $e$ is an oriented edge, then $-e$ is the same underlying edge oriented in the opposite direction) and $\Gamma$ is a group such that $-\varphi(e)=\varphi(-e)$ for additive groups and $\varphi(e)^{-1}=\varphi(-e)$ for multiplicative groups. In this post we will only consider abelian groups. One advantage of abelian groups over nonabelian ones is that gain functions, up to a certain type of equivalence, gives rise to and can be specified by homomorphisms $\hat\varphi\colon Z_1(G)\to\Gamma$ in which $Z_1(G)$ is the integer cycle space of the graph. Given $\varphi$, let $B_\varphi$ be the collection of cycles in $G$ for which $\hat\varphi(\vec C)$ is the identity element of $\Gamma$ (0 when $\Gamma$ is additive, 1 when $\Gamma$ is multiplicative). Now $(G,B_\varphi)$ is a biased graph.

Given a biased graph $(G,B)$, a homomorphism $\hat\varphi\colon Z_1(G)\to\Gamma$ such that $B_\varphi=B$ is called a $\Gamma$-realization of $(G,B)$. The following proposition by Zaslavsky can be stated for skew fields as well as ordinary fields.

Proposition 1 (Zaslavsky [Za03]) Let $(G,B)$ be a biased graph and $\mathbb F$ a field.

  1. If $(G,B)$ is realizable over the multiplicative subgroup of $\mathbb F$, then $F(G,B)$ is $\mathbb F$-representable.
  2. If $(G,B)$ is realizable over the additive subgroup of $\mathbb F$, then $L_0(G,B)$ is $\mathbb F$-representable.

Partial fields have become a central and popular topic in modern matroid theory. (See Stefan van Zwam’s blog post from 09-16-13 for an introduction to partial fields.) Briefly a partial field is a pair $\mathbb P=(R,U)$ in which $R$ is a commutative ring and $U$ is a subgroup of the multiplicative group of units of $R$ such that $-1\in U$.

Proposition 2 (van Zwam [vZ09]) Let $\mathbb P=(R,U)$ be a partial field and $(G,B)$ a biased graph.

  1. Let $\varphi\colon\vec E(G)\to U$ be a $U$-realization of $(G,B)$. If $\varphi(\vec C)$ is a fundamental element of $\mathbb P$ for each cycle $C$ of $G$, then the frame matroid $F(G,B)$ is $\mathbb P$-representable.
  2. Let $\varphi\colon\vec E(G)\to R_+$ be an $R_+$-realization of $(G,B)$. If $\varphi(\vec C)\in U$ for every unbalanced cycle $C$ of $(G,B)$, then $L_0(G,B)$ is $\mathbb P$-representable.

“Well-connected” examples of matroids representable over various partial fields can sometimes be hard to come by. The largest possible simple $\mathbb P$-matroids of a given rank are known for various partial fields, but not every $\mathbb P$-matroid of a given rank must be contained within a $\mathbb P$-matroid of maximum size. Sometimes biased graphs defined by embeddings in surfaces can provide interesting examples of $\mathbb P$-matroids as well. Given a graph $G$ embedded in a closed surface $S$, invariance of homology gives us a natural homomorphism $\natural\colon Z_1(G)\to H_1(S)$ where $H_1(S)$ is the first homology group of the surface calculated with integer coefficients. Now given a partial field $\mathbb P=(R,U)$ there may be some choice of $\sigma\colon H_1(S)\to\mathbb P$ such that the biased graph $(G,B_{\sigma\natural})$ satisfies the conditions of Proposition 2.

Two of my favorite examples come from graphs embedded in the Klein Bottle. The Klein bottle is the surface obtained by identifying two Möbius bands along their circular boundary. In the figure below we have the lighter and darker Möbius bands. The first homology group $H_1(K)$ of the Klein bottle is $\mathbb Z\times\mathbb Z_2$. Of particular usefulness for us is the fact that any cycle $C$ embedded in the Klein bottle now has $\pm\natural(\vec C)\in\{(0,0),(1,0),(0,1),(1,1),(2,0)\}$.

KleinRectangle-1

Now let $G$ be a nice large graph embedded in the Klein bottle with high face width e.g., a square grid.

  • The dyadic partial field $\mathbb D=(\mathbb Q,U)$ has $U=\{\pm 2^i:i\in\mathbb Z\}$. Define $\sigma\colon\mathbb Z\times\mathbb Z_2\to\mathbb Q_+$ by $(1,0)\mapsto 1$ and $(0,1)\mapsto 0$. This yields $\sigma(a,b)\in\{0,\pm 1,\pm 2\}\subset U$ and so $L_0(G,B_{\sigma\natural})$ is $\mathbb D$-representable by
    Proposition 2 (2).
  • The 2-cyclotomic partial field $\mathbb K_2=(\mathbb Q(x),U)$ has $U=\{\pm x^i(1-x)^j(1+x)^k:i,j,k\in\mathbb Z\}$. Define $\sigma\colon\mathbb Z\times\mathbb Z_2\to U$ by $(1,0)\mapsto x$ and $(0,1)\mapsto \pm1$. Either choice for $\sigma(0,1)$ yields $\sigma(a,b)\in\{1,x,-x,x^{-1},-x^{-1},x^2,x^{-2}\}$ and each element of this set is a fundamental element of $\mathbb K_2$ [vZ09]. Thus $F(G,B_{\sigma\natural})$ is $\mathbb K_2$-representable by Proposition 2(1). Representations of matroids over $\mathbb K_2$ have homomorphic images over other interesting partial fields as well, e.g., the golden-mean and Gersonides partial fields.

These are two very nice examples, but are there more? Do other surfaces yield interesting partial fields to work with? Other surfaces have restrictions on the homology classes of cycles embedded on their surface although these restrictions are not as tight as those for the Klein bottle. The first homology group for the torus is $\mathbb Z\times\mathbb Z$ and cycles must be in homology class $(a,b)$ where the greatest common divisor of $a$ and $b$ is 1. The first homology group of Dyck’s surface (i.e., the connected sum of the torus and the projective plane) is $\mathbb Z\times\mathbb Z\times \mathbb Z_2$ and cycles must be in homology classes $(a,b,0)$, $(a,b,1)$, or $(2a,2b,0)$ where the greatest common divisor of $a$ and $b$ is 1. Then again, is it necessary to restrict ones attention to graphs embedded in surfaces? There are other interesting topological spaces that could be explored as well: dunce hats and connected sums of surfaces with dunce hats, for example.

References

[KK82] J. Kahn, J. Kung, Varieties of combinatorial geometries, Trans. Amer. Math. Soc. 271 (1982) 485–499.

[GGW14] J. Geelen, B. Gerards, G. Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc. 61 (2014) 736–743.

[vZ09] S. van Zwam, Partial Fields in Matroid Theory, Doctoral dissertation, Technische Universiteit Eindhoven, Netherlands, 2009.

[Za89] T. Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989) 32–52.

[Za91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory Ser. B 51 (1991) 46–72.

[Za94] T. Zaslavsky, Frame matroids and biased graphs, European J. Combin. 15 (1994) 303–307.

[Za03] T. Zaslavsky, Biasedgraphs IV: Geometrical realizations, J. Combin. Theory Ser. B 89 (2003) 231–297.

Leave a Reply

Your email address will not be published. Required fields are marked *