Georgia Institute of Technology College of Sciences

Consider the following solitaire game on a graph. Given a chip configuration on the node set V, a move consists of taking a subset U of nodes and sending one chip from U to V\U along each edge of the cut determined by U. A starting configuration is winning if for every node there exists a sequence of moves that allows us to place at least one chip on that node. The (divisorial) gonality of a graph is defined as the minimum number of chips in a winning configuration. This notion belongs to the Baker-Norine divisor theory on graphs and can be seen as a combinatorial analog of gonality for algebraic curves. In this talk we will show that the gonality is lower bounded by the tree-width and, if time permits, that the parameter is NP-hard to compute. We will conclude with some open problems.

Lately there was a growing interest in studying self-similarity and fractal properties of graphs, which is largely inspired by applications in biology, sociology and chemistry. Such studies often employ statistical physics methods that borrow some ideas from graph theory and general topology, but are not intended to approach the problems under consideration in a rigorous mathematical way. To the best of our knowledge, a rigorous combinatorial theory that defines and studies graph-theoretical analogues of topological fractals still has not been developed. In this paper we introduce and study discrete analogues of Lebesgue and Hausdorff dimensions for graphs. It turned out that they are closely related to well-known graph characteristics such as rank dimension and Prague (or Nesetril-Rodl) dimension. It allowed us to formally define fractal graphs and establish fractality of some graph classes. We show, how Hausdorff dimension of graphs is related to their Kolmogorov complexity. We also demonstrate fruitfulness of this interdisciplinary approach by discover a novel property of general compact metric spaces using ideas from hypergraphs theory and by proving an estimation for Prague dimension of almost all graphs using methods from algorithmic information theory.

A special feature possessed by the graphs of social networks is triangle-dense. R. Gupta, T. Roughgarden and C. Seshadhri give a polynomial time graph algorithm to decompose a triangle-dense graph into some clusters preserving high edge density and high triangle density in each cluster with respect to the original graph and each cluster has radius 2. And high proportion of triangles of the original graph are preserved in these clusters. Furthermore, if high proportion of edges in the original graph is "locally triangle-dense", then additionally, high proportion of edges of the original graph are preserved in these clusters. In this talk, I will present most part of the paper "Decomposition of Triangle-dense Graphs" in SIAM J. COMPUT. Vol. 45, No. 2, pp. 197–215, 2016, by R. Gupta, T. Roughgarden and C. Seshadhri.

Let G be a 5-connected nonplanar graph. To show the Kelmans-Seymour conjecture, we keep contracting a connected subgraph on a special vertex z until the following happens: H does not contain K_4^-, and for any subgraph T of H such that z is a vertex in T and T is K_2 or K_3, H/T is not 5-connected. In this talk, we prove a lemma using the characterization of three paths with designated ends, which will be used in the proof of the Kelmans-Seymour conjecture.