PIMS - SFU Discrete Mathematics Seminar: Jiaxi Nie

  • Date: 01/18/2022
  • Time: 14:30
Lecturer(s):
Jiaxi Nie, University of California San Diego
Location: 

Online

Topic: 

On Asymptotic Packing of Geometric Graphs

Description: 

Abstract:A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph K_n. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph G, we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of K_n.

Other Information: 

This seminar runs from 2:30-3:20pm PST. The seminar will be delivered online.