Georgia Institute of Technology College of Sciences

Previous work of Chan-Church-Grochow and Baker-Wang shows that the set of spanning trees in a plane graph $G$ is naturally a torsor for the Jacobian group of $G$. Informally, this means that the set of spanning trees of $G$ naturally forms a group, except that there is no distinguished identity element. We generalize this fact to graphs embedded on orientable surfaces of arbitrary genus, which can be identified with ribbon graphs. In this generalization, the set of spanning trees of $G$ is replaced by the set of spanning quasi-trees of the ribbon graph, and the Jacobian group of $G$ is replaced by the Jacobian group of the associated regular orthogonal matroid $M$.

Our proof shows, more generally, that the family of "BBY torsors'' constructed by Backman-Baker-Yuen and later generalized by Ding admit natural generalizations to regular orthogonal matroids. In addition to shedding light on the role of planarity in the earlier work mentioned above, our results represent one of the first substantial applications of orthogonal matroids to a natural combinatorial problem about graphs. 

 Joint work with Matt Baker and Donggyu Kim. 

Abstract: Critical points significantly affect the behavior of gradient-based dynamics. Numerous works have been done for global minima of neural networks. Thus, the recent work characterizes non-global critical points. With the idea that gradient-based methods of neural networks favor “simple models”, this work focuses on the set of low-complexity critical points, i.e., those representing underparameterized network models. Specifically, we investigate: i) the existence and ii) geometry of such sets, iii) the output functions they represent, iv) saddles in them. The talk will discuss these results based on a simple example. The general theorems will also be included. No specific knowledge in neural networks is required. 

Let $G = (V,E)$ be a graph on $n$ vertices, and let $c : E \to P$, where $P$ is a set of colors. Let $\delta^c(G) = \min_{v \in V} \{ d^{c}(v) \}$ where $d^c(v)$ is the number of colors on edges incident to a vertex $v$ of $G$.  In 2011, Fujita and Magnant showed that if $G$ is a graph on $n$ vertices that satisfies $\delta^c(G)\geq n/2$, then for every two vertices $u, v$ there is a properly-colored $u,v$-path in $G$. We show that for sufficiently large graphs $G$ the same bound for $\delta^c(G)$ implies that any two vertices are connected by a rainbow path. This is joint work with Andrzej Czygrinow.