Seminars in January 2018

• O-joung Kwon (권오정), Erdős-Pósa property of chordless cycles and its applications

  Erdős-Pósa property of chordless cycles and its applications

  O-joung Kwon (권오정)
  Technische Universität Berlin, Berlin, Germany

  2018/1/12 Fri 4PM-5PM

  A chordless cycle in a graph G is an induced subgraph of G which is a cycle of length at least four. We prove that the Erdős-Pósa property holds for chordless cycles, which resolves the major open question concerning the Erdős-Pósa property. Our proof for chordless cycles is constructive: in polynomial time, one can find either k+1 vertex-disjoint chordless cycles, or ck² log k vertices hitting every chordless cycle for some constant c. It immediately implies an approximation algorithm of factor O(OPT log OPT) for Chordal Vertex Deletion. We complement our main result by showing that chordless cycles of length at least ℓ for any fixed ℓ≥ 5 do not have the Erdős-Pósa property.

  Tags:

  • 권오정

• Joonkyung Lee (이준경), Counting tree-like graphs in locally dense graphs

  Counting tree-like graphs in locally dense graphs

  Joonkyung Lee (이준경)
  Mathematical Institute, University of Oxford, Oxford, UK

  2018/1/8 Mon 4PM-5PM

  We prove that a class of graphs obtained by gluing complete multipartite graphs in a tree-like way satisfies a conjecture of Kohayakawa, Nagle, Rödl, and Schacht on random-like counts for small graphs in locally dense graphs. This implies an approximate version of the conjecture for graphs with bounded tree-width. We also prove an analogous result for odd cycles instead of complete multipartite graphs.
  The proof uses a general information theoretic method to prove graph homomorphism inequalities for tree-like structured graphs, which may be of independent interest.

  Tags:

  • 이준경