Antoine Vigneron, Reachability in a Planar Subdivision with Direction Constraints

March 3rd, 2018
Reachability in a Planar Subdivision with Direction Constraints
Antoine Vigneron
School of Electrical and Computer Engineering, UNIST, Ulsan, South Korea
2018/3/27 Tue 5PM
Given a planar subdivision with n vertices, each face having a cone of possible directions of travel, our goal is to decide which vertices of the subdivision can be reached from a given starting point s. We give an O(n log n)-time algorithm for this problem, as well as an Ω(n log n) lower bound in the algebraic computation tree model. We prove that the generalization where two cones of directions per face are allowed is NP-hard.

Otfried Cheong, The reverse Kakeya problem

March 2nd, 2018
The reverse Kakeya problem
Otfried Cheong
School of Computing, KAIST
2017/3/20 Tue 5PM
We prove a generalization of Pal’s 1921 conjecture that if a convex shape P can be placed in any orientation inside a convex shape Q in the plane, then P can also be turned continuously through 360 degrees inside Q. We also prove a lower bound of Ω(m n2) on the number of combinatorially distinct maximal placements of a convex m-gon P in a convex n-gon Q. This matches the upper bound proven by Agarwal et al.

Ringi Kim (김린기), Characterization of forbidden subgraphs for bounded star-chromatic number

March 2nd, 2018
Characterization of forbidden subgraphs for bounded star-chromatic number
Ringi Kim (김린기)
Department of Mathematical Sciences, KAIST
2018/3/6 Tue 5PM
The chromatic number of a graph is the minimum k such that the graph has a proper k-coloring. It is known that if T is a tree, then every graph with large chromatic number contains T as a subgraph. In this talk, we discuss this phenomena for star-coloring (a proper coloring forbidding a bicolored path on four vertices) and acyclic-coloring (a proper coloring forbidding bicolored cycles). Specifically, we will characterize all graphs T such that every graph with sufficiently large star-chromatic number (acyclic-chromatic number) contains T as a subgraph.

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

January 1st, 2018
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 ck2 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.

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

January 1st, 2018
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.