Spring 2016

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

Please contact Jeremy Martin if you are interested in speaking.

**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**

No seminar (Graduate Visiting Weekend)

**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