Seminars in May 2013

  • Jack Koolen, m-Walk-regular graphs, a generalization of distance-regular graphs
    m-Walk-regular graphs, a generalization of distance-regular graphs
    Jack Koolen
    Department of Mathematics, POSTECH
    2013/05/31 Friday 4PM-5PM
    Walk-regular graph were introduced by Godsil and McKay to understand when the characteristic polynomial of a graph in which a vertex is deleted does not depend on which vertex you delete. This notion was generalized to m-walk-regular graphs by Fiol and Garriga in order to understand how close you can come to a distance-regular graph.</p>

    We observed that for many results on distance-regular graphs they also hold for 2-walk-regular. In this talk I will give an overview of which results can be generalized to 2-walk-regular graphs, and I also will give many examples of 2,3,4,5,-walk-regular graphs which are not distance-regular. At this moment all 6-walk-regular graphs known are distance-regular.

    This is still work in progress and is joint work with M. Camara, E. van Dam and Jongyook Park.

    Tags:

  • Hyung-Chan An, Improving Christofides’ Algorithm for the s-t Path TSP
    Improving Christofides’ Algorithm
    for the s-t Path TSP
    Hyung-Chan An
    EPFL, Lausanne, Switzerland
    2013/05/24 Friday 4PM-5PM
    ROOM 3433
    We present a deterministic (1+√5)/2-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the two endpoints; Hoogeveen showed that the natural variant of Christofides’ algorithm is a 5/3-approximation algorithm for this problem, and this asymptotically tight bound in fact had been the best approximation ratio known until now. We modify this algorithm so that it chooses the initial spanning tree based on an optimal solution to the Held-Karp relaxation rather than a minimum spanning tree; we prove this simple but crucial modification leads to an improved approximation ratio, surpassing the 20-year-old barrier set by the natural Christofides’ algorithm variant. Our algorithm also proves an upper bound of (1+√5)/2 on the integrality gap of the path-variant Held-Karp relaxation. The techniques devised in this paper can be applied to other optimization problems as well: these applications include improved approximation algorithms and improved LP integrality gap upper bounds for the prize-collecting s-t path problem and the unit-weight graphical metric s-t path TSP.</p>

    This is joint work with Bobby Kleinberg and David Shmoys.

    Tags:

  • June Huh, Tropical Laplacian
    Tropical Laplacian
    June Huh
    Department of Mathematics, University of Michigan
    2013/05/10 Thu 2PM-3PM
    Room 2411
    Tropical Laplacian is a symmetric square matrix associated to a balanced graph on a sphere, defined in a similar way to the Laplacian of an abstract graph. We will see by examples how tropical Laplacian appears in the study of polytopes, matroids, and graphs. The speaker will pose many linear-algebra-level questions to audiences.
    Tags:

  • Antoine Deza, Combinatorial and geometric approaches to the colourful simplicial depth
    Combinatorial and geometric approaches to the colourful simplicial depth
    Antoine Deza
    Department of Computing and Software
    McMaster University
    Hamilton, Ontario, Canada
    2013/05/01 Wed 4PM-5PM – ROOM 3433
    In statistics, there are several measures of the depth of a point p relative to a fixed set S of sample points in dimension d. One of the most intuitive is the simplicial depth of p introduced by Liu (1990), which is the number of simplices generated by points in S that contain p. Obtaining a lower bound for the simplicial depth is a challenging problem. Carathéodory’s Theorem can be restated as: The simplicial depth is at least 1 if p belongs to the convex hull of S. Bárány (1982) showed that the simplicial depth is a least a fraction of all possible simplices generated from S. Gromov (2010) improved the fraction via a topological approach. Bárány’s result uses a colourful version of Carathéodory Theorem leading to the associated colourful simplicial depth. We present recent generalizations of the Colourful Carathéodory Theorem due to Arocha et al. and Holmsen et al. and our strengthening of these. We provide a new lower bound for the colourful simplicial depth improving the earlier bounds of Bárány and Matoušek and of Stephen and Thomas, and verify that the conjectured lower bound is tight for dimension ≤4.</p>

    Based on joint works with Frédéric Meunier (ENPC Paris), Tamon Stephen (Simon Fraser), Pauline Sarrabezolles (ENPC Paris), and Feng Xie (Microsoft)

    Tags:

Monthly Archives