Combinatorics Seminars

Summer 2019

Speaker: Sunita Chepuri, University of Minnesota
Date and Time: Wednesday, August 7th 11am–12 pm
Place: Rome 771

Title:  Plabic R-Matrices
Abstract:  Postnikov's plabic graphs in a disk are used to parametrize totally nonnegative Grassmannians. One of the key features of this theory is that if a plabic graph is reduced, the face weights can be uniquely recovered from boundary measurements. On surfaces more complicated than a disk this property is lost. In this talk, we investigate a certain semi-local transformation of weights for plabic networks on a cylinder that preserves boundary measurements. We call this a plabic R-matrix. We explore the properties of the plabic R-matrix, including the symmetric group action it induces on plabic networks and its underlying cluster algebra structure.

Fall 2019
Speaker: Dan Cranston, VCU
Date and Time: Friday, August 30 4–5 pm
Place: Rome 771

Title: Using the Potential Method to Color Near-Bipartite Graphs
Abstract: A graph G is near-bipartite if we can partition V(G) as (I,F) where I is an independent set and F induces a forest. Similar to the problem of 3-coloring, deciding whether a graph is near-bipartite is NP-hard. Thus, we seek sufficient conditions. We show that a multigraph G is near-bipartite if 3|W|-2|E(G[W])|\ge -1 for every W\subseteq V(G), and G contains no K_4 and no Moser spindle. We show that a simple graph G is near-bipartite if 8|W|-5|E(G[W])|\ge -4 for every W\subseteq V(G) and G contains no subgraph in some finite family (each member of which is not near-bipartite). Each result is very sharp. Namely, if we weaken the lower bound in either hypothesis by 1, then the resulting statement is false infinitely often.

Both results are proved using the potential method, a powerful technique for coloring sparse graphs. As a consequence, both theorems lead to polynomial-time algorithms to find the desired partition. This is joint work with Matthew Yancey.