{"id":622,"date":"2014-03-10T09:46:20","date_gmt":"2014-03-10T13:46:20","guid":{"rendered":"http:\/\/matroidunion.org\/?p=622"},"modified":"2014-03-11T09:11:03","modified_gmt":"2014-03-11T13:11:03","slug":"which-biased-graphs-are-group-labelled-graphs","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=622","title":{"rendered":"Which biased graphs are group-labelled graphs?"},"content":{"rendered":"

This post is mainly about results that I proved together with Matt DeVos and Daryl Funk, partly while they were visiting the University of Western Australia after the 37ACCMCC (Dillon talked about this conference in his blog post<\/a> on December 16, 2013).<\/p>\n

First, let me remind you of what a biased graph is (more details can be found in my introductory post<\/a>). A biased graph is a pair $(G,\\mathcal{B})$, where $G$ is a graph and $\\mathcal{B}$ is a set of cycles of $G$ satisfying the theta-property<\/em>: there is no theta subgraph of $G$ that contains exactly two cycles in $\\mathcal{B}$. Cycles in $\\mathcal{B}$ are called\u00a0balanced<\/em>, while the other cycles of $G$ are\u00a0unbalanced<\/em>.<\/p>\n

A quite general way of constructing biased graphs is via group-labelled graphs<\/em>. Pick your favourite (say multiplicative) group $\\Gamma$ and graph $G$, and assign to each edge $e$ of $G$ an orientation and a value $\\phi(e)$ from $\\Gamma$: then what you have is a group-labelled graph. Now consider any walk $W$ in $G$, with edge sequence $e_1,e_2,\\ldots,e_k$ and extend $\\phi$ as<\/p>\n

$\\phi(W)=\\prod_{i=1}^{k}\\phi(e_i)^{\\textrm{dir}(e_i)}$,<\/p>\n

where $\\textrm{dir}(e_i)$ is 1 if $e_i$ is forward in $W$, and -1 otherwise.\u00a0Then we define a cycle $C$ of $G$ to be balanced if a simple closed walk $W$ around $C$ has $\\phi(W)=1$. It’s easy to see that this definition is independent of the choice for $W$, and in this way we get, indeed, a biased graph. In this case we identify the group-labelled graph with the associated biased graph. If a biased graph can be constructed in this way from a group $\\Gamma$, then we say that such a biased graph is $\\Gamma$-labellable<\/em>. If a biased graph is $\\Gamma$-labellable for some group $\\Gamma$, then we say that the biased graph is group-labellable<\/em>.\u00a0Not all biased graphs are group-labellable, hence the question that is the title of this post. As it turned out, there is a nice topological answer to this question.<\/p>\n

Theorem 1:\u00a0<\/strong>Let $(G,\\mathcal{B})$ be a biased graph; construct a 2-cell complex $K$ from $G$ by adding a disc with boundary $C$ for every $C \\in \\mathcal{B}$. Then the following are equivalent:<\/p>\n

    \n
  1. $(G,\\mathcal{B})$ is group-labellable.<\/li>\n
  2. $(G,\\mathcal{B})$ is $\\pi_1(K)$-labellable (where $\\pi_1(K)$ is the fundamental group of $K$).<\/li>\n
  3. Every unbalanced cycle of $G$ is noncontractible in $K$.<\/li>\n<\/ol>\n

    Before I explain a bit how the proof works, let me discuss some nice constructions that we derived using this theorem. For any group $\\Gamma$, the class of $\\Gamma$-labellable graphs is closed under minors, for both definition of minors given in my second post<\/a> on biased graphs. Using Theorem 1, we proved that if $\\Gamma$ is an infinite group then there are infinitely many excluded minors to the class of $\\Gamma$-labellable biased graphs. In fact, we proved something stronger, namely that there is an infinite list of excluded minors on $n$ vertices for every $n \\geq 3$.<\/p>\n

    Theorem 2:<\/strong> For every $n \\geq 3$ and $\\ell$ there exists a biased graph $(G,\\mathcal{B})$ with the following properties:<\/p>\n