{"id":1094,"date":"2014-11-17T22:54:08","date_gmt":"2014-11-18T03:54:08","guid":{"rendered":"http:\/\/matroidunion.org\/?p=1094"},"modified":"2014-11-15T22:54:26","modified_gmt":"2014-11-16T03:54:26","slug":"matroids-over-partial-fields-from-graphs-embedded-in-surfaces","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=1094","title":{"rendered":"Matroids over partial fields from graphs embedded in surfaces"},"content":{"rendered":"

Guest post by Daniel Slilaty.<\/em><\/p>\n

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

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

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

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

Proposition 1 (Zaslavsky [Za03])\u00a0<\/strong>Let $(G,B)$ be a biased graph and $\\mathbb F$ a field.<\/p>\n

    \n
  1. If $(G,B)$ is realizable over the multiplicative subgroup of $\\mathbb F$, then $F(G,B)$ is $\\mathbb\u00a0F$-representable.<\/li>\n
  2. If $(G,B)$ is realizable over the additive subgroup of $\\mathbb F$, then $L_0(G,B)$ is $\\mathbb F$-representable.<\/li>\n<\/ol>\n

    Partial fields have become a central and popular topic in modern matroid theory. (See Stefan van Zwam’s blog post from\u00a009-16-13<\/a> for an introduction to partial fields.) Briefly a partial field<\/em> 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$.<\/p>\n

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

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

      “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.<\/p>\n

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

      \"KleinRectangle-1\"<\/a><\/p>\n

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