Suho Oh, Fun with wires

July 28th, 2014
Fun with wires
Suho Oh
University of Michigan/Texas State University, USA
2014/08/01 Friday 4PM-5PM
Room 3433
Wiring diagrams are widely used combinatorial objects that are mainly used to describe reduced words of a permutation. In this talk, I will mention a fun property I recently found about those diagrams, and then introduce other results and problems related to this property.

Chun-Hung Liu, Graph Structures and Well-Quasi-Ordering

April 30th, 2014
Graph Structures and Well-Quasi-Ordering
Chun-Hung Liu
Georgia Institute of Technology, USA
2014/07/29 Tuesday 4PM-5PM
Room 1409
Robertson and Seymour proved that graphs are well-quasi-ordered by the minor relation and the weak immersion relation. In other words, given infinitely many graphs, one graph contains another as a minor (or a weak immersion, respectively). Unlike the relation of minor and weak immersion, the topological minor relation does not well-quasi-order graphs in general. However, Robertson conjectured in the late 1980′s that for every positive integer k, the topological minor relation well-quasi-orders graphs that do not contain a topological minor isomorphic to the path of length k with each edge duplicated. We will sketch the idea of our recent proof of this conjecture. In addition, we will give a structure theorem for excluding a fixed graph as a topological minor. Such structure theorem were previously obtained by Grohe and Marx and by Dvorak, but we push one of the bounds in their theorems to the optimal value. This improvement is needed for our proof of Robertson’s conjecture. This work is joint with Robin Thomas.

Ilkyoo Choi, Choosability of Toroidal Graphs with Forbidden Structures

March 15th, 2014
Choosability of Toroidal Graphs with Forbidden Structures
2014/07/07 Monday 4PM-5PM
Room 1409
The choosability \(\chi_\ell(G)\) of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that \(\chi_\ell(G)\leq 7\), and \(\chi_\ell(G)=7\) if and only if G contains \(K_7\). Cai, Wang, and Zhu proved that a toroidal graph G without 7-cycles is 6-choosable, and \(\chi_\ell(G)=6\) if and only if G contains \(K_6\). They also prove that a toroidal graph G without 6-cycles is 5-choosable, and conjecture that \(\chi_\ell(G)=5\) if and only if G contains \(K_5\). We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither \(K_5\) nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither \(K^-_5\) (a \(K_5\) missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.

Spencer Backman, The generalized cycle-cocycle reversal system for partial graph orientations

March 10th, 2014
The generalized cycle-cocycle reversal system for partial graph orientations
Spencer Backman
Georgia Institute of Technology, USA
2014/06/30 Monday 4PM-5PM
Room 1409
We introduce a discrete dynamical system on the set of partial orientations of a graph, which generalizes Gioan’s cycle-cocycle reversal system. We explain how this setup allows for a new interpretation of the linear equivalence of divisors on graphs (chip-firing), and a new proof of Baker and Norine’s combinatorial Riemann-Roch formula. Fundamental connections to the max-flow min-cut theorem will be highlighted.

(KMRS Seminar) Sang-il Oum, An algorithm for path-width and branch-width of matroids

March 8th, 2014

FYI (KMRS Seminar)

An algorithm for path-width and branch-width of matroids
2014/06/27 Friday 3:15PM – 4::15PM
Room 3435
Branch-width and path-width are width parameters of graphs and matroids, which measure how easy it is to decompose a graph or a matroid into a tree-like or path-like structure via separations of small order. These parameters have been used not only for designing efficient algorithms with the inputs of small branch-width or path-width, but also for proving theoretical structural theorems by providing a rough structural description. We will describe a polynomial-time algorithm to construct a path-decomposition or a branch-decomposition of width at most k, if it exists, for a matroid represented over a fixed finite field for fixed k. Our approach is based on the dynamic programming combined with the idea developed by Bodlaender for his work on tree-width of graphs. For path-width, this is a new result. For branch-width, this improves the previous work by Hlineny and Oum (Finding branch-decompositions and rank-decompositions, SIAM J. Comput., 2008) which was very indirect; their algorithm is based on the upper bound on the size of minor obstructions proved by Geelen et al. (Obstructions to branch-decompositions of matroids, JCTB, 2006) and requires testing minors for each of these obstructions. Our new algorithm does not use minor obstructions. As a corollary, for graphs, we obtain an algorithm to construct a rank-decomposition of width at most k if it exists for fixed k. This is a joint work with Jisu Jeong (KAIST) and Eun Jung Kim (CNRS-LAMSADE).