All Articles

Speaker: Calum Buchanan, University of Vermont <https://www.uvm.edu/~cjbuchan>

Title: Subgraph complementation and minimum rank

Abstract:
It is possible to obtain any simple graph $G$ from any other graph $H$ on the same set of vertices by performing a sequence of subgraph complementations. That is, we can iteratively replace induced subgraphs by their graph complements until we obtain $G$ from $H$. We ask for the minimum number of subgraph complementations in such a sequence. When $H$ is the graph with no edges, we denote this parameter by $c_2(G)$. Finding $c_2(G)$ relates closely to the minimum rank problem. We show that $c_2 (G) = \operatorname{mr}(G,\mathbb{F}_2)$ when $\operatorname{mr}(G,\mathbb{F}_2)$ is odd or when $G$ is a forest; otherwise, $\operatorname{mr}(G,\mathbb{F}_2) \leq c_2 (G) \leq \operatorname{mr}(G,\mathbb{F}_2) + 1$. We then provide two conditions which are equivalent to having $c_2(G) = \operatorname{mr}(G,\mathbb{F}_2) + 1$. In this case, we can still interpret $\operatorname{mr}(G,\mathbb{F}_2)$ combinatorially using a variation of subgraph complementation. Finally, the class of gr!
 aphs $G$
 with $c_2(G) \leq k$ is hereditary and finitely defined for any natural number $k$. We exhibit the sets of minimal forbidden induced subgraphs for small values of $k$. This is joint work with Christopher Purcell and Puck Rombach.

 

It’s nice for speakers to see some of the audience, so we encourage you to leave your camera on during the talk.