Seminars in June 2016

  • Chun-Hung Liu, Packing and covering topological minors and immersions
    Packing and covering topological minors and immersions
    Chun-Hung Liu
    Department of Mathematics, Princeton University, Princeton, NJ, USA
    2016/06/29 Wed 4PM-5PM
    A set F of graphs has the Erdős-Posa property if there exists a function f such that every graph either contains k disjoint subgraphs each isomorphic to a member in F or contains a set of at most f(k) vertices intersecting all such subgraphs. In this talk I will address the Erdős-Posa property with respect to three closely related graph containment relations: minor, topological minor, and immersion. We denote the set of graphs containing H as a minor, topological minor and immersion by M(H),T(H) and I(H), respectively. Robertson and Seymour in 1980’s proved that M(H) has the Erdős-Posa property if and only if H is planar. And they left the question for characterizing H in which T(H) has the Erdős-Posa property in the same paper. This characterization is expected to be complicated as T(H) has no Erdős-Posa property even for some tree H. In this talk, I will present joint work with Postle and Wollan for providing such a characterization. For immersions, it is more reasonable to consider an edge-variant of the Erdős-Posa property: packing edge-disjoint subgraphs and covering them by edges. I(H) has no this edge-variant of the Erdős-Posa property even for some tree H. However, I will prove that I(H) has the edge-variant of the Erdős-Posa property for every graph H if the host graphs are restricted to be 4-edge-connected. The 4-edge-connectivity cannot be replaced by the 3-edge-connectivity.
    Tags:

  • Suil O (오수일), Interlacing families and the Hermitian spectral norm of digraphs
    Interlacing families and the Hermitian spectral norm of digraphs
    Suil O (오수일)
    Department of Mathematics, Simon Fraser University, Burnaby, B.C., Canada
    2016/6/1 Wed 4PM-5PM
    Recently, Marcus, Spielman, and Srivastava proved the existence of infinite families of bipartite Ramanujan graphs of every degree at least 3 by using the method of interlacing families of polynomials. In this talk, we apply their method to prove that for any connected graph G, there exists an orientation of G such that the spectral radius of the corresponding Hermitian adjacency matrix is at most that of the universal cover of G.
    Tags:

Monthly Archives