Seminars in June 2014

  • Spencer Backman, The generalized cycle-cocycle reversal system for partial graph orientations
    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.
    Tags:

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

    FYI (KMRS Seminar)

    An algorithm for path-width and branch-width of matroids
    Sang-il Oum
    KAIST
    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).
    Tags:

  • Matthew G. Parker, Exclusivity graphs from quantum graph states and mixed graph generalisations
    Exclusivity graphs from quantum graph states – and mixed graph generalisations
    Matthew G. Parker
    University of Bergen, Norway
    2014/06/24 Tuesday 4PM-5PM
    Room 1409
    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.
    Tags:

  • Vissarion Fisikopoulos, Polytopes defined by oracles: algorithms and combinatorics
    Polytopes defined by oracles: algorithms and combinatorics
    Vissarion Fisikopoulos
    University of Athens, Greece
    2014/06/23 Monday 4PM-5PM
    Room 1409
    We develop a new paradigm to construct polytopes whose vertices can be obtained by an effective oracle in a unique fashion. Our main motivation comes from computational algebraic geometry. From this perspective these polytopes, called resultant polytopes, characterize polynomials better than total degree thus offering the fundamental representation in sparse elimination theory. We propose an output-sensitive algorithm that requires the minimum number of oracle calls, each reducing to the construction of a regular triangulation of the input set of points. Its implementation has been proven, among others, a valuable computational tool in our study of the combinatorial characterization of 4-dimensional resultant polytopes. We present the results of this study, that is, upper and lower bounds on the number of faces of 4-dimensional resultant polytopes.
    Tags:

  • Jaehoon Kim, On r-dynamic coloring of graphs
    On r-dynamic coloring of graphs
    Jaehoon Kim
    KAIST/Univ. of Birmingham, UK
    2014/06/09 Monday 4PM-5PM
    Room 1409
    An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V(G) has neighbors in at least \min\{d(v),r\} different color classes. The r-dynamic chromatic number of a graph G, written \chi_r(G), is the least k such that G has such a coloring. By a greedy coloring algorithm, \chi_r(G)\le r\Delta(G)+1 and the equality holds if and only if G is r-regular with diameter 2 and girth 5. We improve the bound to \chi_r(G)\le \Delta(G)+2r when \delta(G)\ge 2r\ln n. In terms of the chromatic number, we prove \chi_r(G)\le r\chi(G) when G is k-regular with k \ge (3+o(1))r\ln r and show that \chi_r(G) may exceed r^{1.377}\chi(G) when k=r. We prove \chi_2(G)\leq \chi(G)+2 when G has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, \chi_2(G)\le 3\chi(G) when G has diameter 3, which is sharp. This is joint work with Sogol Jahanbekam, Suil O, and Douglas B. West.
    Tags:

  • Sariel Har-Peled, Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
    Quasi-Polynomial Time Approximation Scheme for Sparse Subsets of Polygons
    Sariel Har-Peled
    UIUC, USA
    2014/06/02 Monday 4PM-5PM
    Room 1409
    We describe how to approximate, in quasi-polynomial time, the largest independent set of polygons, in a given set of polygons. Our algorithm works by extending the result of Adamaszek and Wiese [AW13, AW14] to polygons of arbitrary complexity. Surprisingly, the algorithm also works for computing the largest subset of the given set of polygons that has some sparsity condition. For example, we show that one can approximate the largest subset of polygons, such that the intersection graph of the subset does not contain a cycle of length 4 (i.e., K2,2). To appear in SoCG 2014.

Monthly Archives