April 30th, 2014
Graph Structures and Well-Quasi-Ordering
2014/07/29 Tuesday 4PM-5PM
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.
March 15th, 2014
Choosability of Toroidal Graphs with Forbidden Structures
2014/07/07 Monday 4PM-5PM
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.
March 10th, 2014
The generalized cycle-cocycle reversal system for partial graph orientations
2014/06/30 Monday 4PM-5PM
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.
March 8th, 2014
FYI (KMRS Seminar)
An algorithm for path-width and branch-width of matroids
2014/06/27 Friday 3:15PM – 4::15PM
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).
March 7th, 2014
Exclusivity graphs from quantum graph states – and mixed graph generalisations
2014/06/24 Tuesday 4PM-5PM
I describe a construction that maps any connected graph G on three or more vertices into a larger graph, H(G), whose independence number is strictly smaller than its Lovasz number which is equal to its fractional packing number. The vertices of H(G) represent all possible events consistent with the stabilizer group of the quantum graph state associated with G, and exclusive events are adjacent. The graph H(G) corresponds to the orbit of G under local complementation. Physically, the construction translates into graph-theoretic terms the connection between a graph state and a Bell inequality maximally violated by quantum mechanics. In the context of zero-error information theory, the construction suggests a protocol achieving the maximum rate of entanglement-assisted capacity, a quantum mechanical analogue of the Shannon capacity, for each H(G). The violation of the Bell inequality is expressed by the one-shot version of this capacity being strictly larger than the independence number. The construction also describes a pseudo-telepathy game which is always won when using quantum resources but not always using classical resources. Finally we generalise the graph state to the mixed graph state and discuss how the previous construction may, therefore, be generalized. Joint work with: Cabello, Scarpa, Severini, Riera, Rahaman.