## KU Combinatorics Seminar Spring 2016

The Combinatorics Seminar meets on Friday in Snow 408 at 3-4pm.

Friday 1/22
Organizational meeting

Friday 1/29
Jeremy Martin
Divisors on Graphs

Abstract: I will discuss the chip-firing/sandpiles and the theory of divisors on graphs as an analogue to Riemann surfaces. The ultimate goal is to understand the graphical Riemann-Roch theorem proven by Baker and Norine (Adv. Math. 215 (2007), no.2, 766-788).

Friday 2/5
Hailong Dao
The dimension type of a Stanley-Reisner ring

Abstract: I will introduce an invariant for a local or graded ring called the dimension type. In the special case of a Stanley-Reisner ring, I will explain how this invariant can be used to detect Cohen-Macaulayness and chordality of the corresponding simplicial complex.

Friday 2/12
Marge Bayer
Linear Programming for Combinatorialists

Friday 2/19
Jeremy Martin
The Riemann-Roch Theorem for Graphs

Abstract: I will present the proof of the Riemann-Roch theorem for graphs described by Matt Baker in this blog post.

Friday 2/26
Thanh Vu (University of Nebraska, Lincoln)
Regularity of squarefree monomial ideals with partial linear resolutions

Abstract: In this talk, I will discuss an ongoing project with Long Dao where we study the regularity of squarefree monomial ideals whose minimal free resolutions are $$k$$-step linear. In particular, I will talk about the sharp linear bound for regularity of an ideal which is 2-step linear, and a log bound for regularity in the case of cubic squarefree monomial ideals which are 3-step linear. I will also discuss some generalization to the case of ideals generated in higher degrees, and the non-squarefree case.

Friday 3/4

Friday 3/11
Jeremy Martin
The Riemann-Roch Theorem for Graphs, II

Abstract: I will finish the proof of the Riemann-Roch theorem for graphs (which I got about halfway through on 2/19).

Friday 3/18
No seminar (Spring Break)

Friday 3/25
Nishant Chandgotia (Tel Aviv University)
Distance between walks on graphs

Abstract: Let $$H$$ be a finite connected undirected graph. The set of all bi-infinite walks $$(x_i)_{i\in\mathbb{Z}}$$ on $$H$$ can also be given a graph structure: we say $$(x_i)_{i\in\mathbb{Z}}$$ is adjacent to $$(y_i)_{i \in \mathbb{Z}}$$ if $$x_i$$ is adjacent to $$y_i$$ for all $$i \in \mathbb{Z}$$. Call this auxiliary graph $$H_{\text{walk}}$$. In this talk we will explore when and when not $$H_{\text{walk}}$$ has finite diameter; time permitting, we will hint at its connections with symbolic dynamics and the undecidability of the word problem.

Friday 4/1
Lucas Kramer (Bethel College)
Edge Colorings for the Color Blind

Abstract: Let $$c:E(G)\to [k]$$ be an edge-coloring of a graph $$G$$, not necessarily proper. For each vertex $$v$$, let $$\bar{c}(v)=(a_1,\ldots,a_k)$$, where $$a_i$$ is the number of edges incident to $$v$$ with color $$i$$. Reorder $$\bar{c}(v)$$ for every $$v$$ in $$G$$ in nonincreasing order to obtain $$c^*(v)$$, the color-blind partition of $$v$$. When $$c^*$$ induces a proper vertex coloring, that is, $$c^*(u)\neq c^*(v)$$ for every edge $$uv$$ in $$G$$, we say that $$c$$ is color-blind distinguishing. The minimum $$k$$ for which there exists a color-blind distinguishing edge coloring $$c:E(G)\to [k]$$ is the color-blind index of $$G$$, denoted $$\text{dal}(G)$$. We demonstrate that determining the color-blind index is more subtle than previously thought. In particular, determining if $$\text{dal}(G) \leq 2$$ is NP-complete. We also connect the color-blind index of a regular bipartite graph to 2-colorable regular hypergraphs and characterize when $$\text{dal}(G)$$ is finite for a class of 3-regular graphs.

Friday 4/8
No seminar

Friday 4/15
Marcus Gubanyi
The Tree Packing Conjecture for Families of Trees

Friday 4/22
Brian Benson (Kansas State)
Do graphs have curvature?

Abstract: Many notions from the geometry of surfaces and manifolds have a very natural interpretation on graphs. More precisely, some quantities defined on a manifold can be defined on a graph and the fundamental theorems relating these quantities to one another on the manifold can also be proved for the graph. For example, both the Laplace operator and the Cheeger constant can be defined analogously on manifolds and graphs. Further, the same relationships between the first eigenvalue of the Laplacian and the Cheeger constant hold in both settings.

Curvature is the most fundamental geometric idea for the study of manifolds, however, there are difficulties defining the curvature of a graph. We will give an intuitive review of curvature on manifolds, relying mostly on pictures. We will then discuss and compare several recently proposed notions of curvature on graphs. One of these notions, due to Ollivier, is related to the optimal transport problem.

Friday 4/29
No seminar

Friday 5/6
No seminar (Stop Day)

For seminars from previous semesters, please see the KU Combinatorics Group page.

Last updated Thu 4/28/16