Geometry Day

An extended version of the Geometry Seminar, on Tuesday Jan 9 (10:40-15:30), Malá Strana, Prague.

  • Petr Hliněný: On refined hardness of the crossing number (10:40 - 12:00, S6):
    • Minimizing the crossing number of a graph is a notoriously computationally hard problem, even under very restrictive settings of the input. We survey some of the many known hardness results in this area, and present a new hardness reduction for the anchored crossing number of two planar graphs with the minimal nontrivial number of anchors.
  • Tomáš Kaiser: Higher-dimensional quadrangulations I (12:10 - 13:10, S6):
    • A well-known result of Youngs states that quadrangulations of the projective plane are either bipartite or 4-chromatic. Starting from this result, I will discuss an extension of the notion of quadrangulation to higher dimensions (developed by Matej Stehlik and the speaker) and show that Youngs' result generalises in a natural way. I will explain a link to Schrijver graphs which provides a new viewpoint on Lovasz' classic proof of the Kneser conjecture, and led to the discovery of an explicit family of edge-critical factors of Schrijver graphs. Joint work with Matej Stehlik.
  • Lunch break (13:10 - 14:00)
  • Tomáš Kaiser: Higher-dimensional quadrangulations II (14:00 - 14:30, S5):
    • A well-known result of Youngs states that quadrangulations of the projective plane are either bipartite or 4-chromatic. Starting from this result, I will discuss an extension of the notion of quadrangulation to higher dimensions (developed by Matej Stehlik and the speaker) and show that Youngs' result generalises in a natural way. I will explain a link to Schrijver graphs which provides a new viewpoint on Lovasz' classic proof of the Kneser conjecture, and led to the discovery of an explicit family of edge-critical factors of Schrijver graphs. Joint work with Matej Stehlik.
  • Roman Nedela: Isomorphisms of maps in linear time and recognition of symmetries of cyclic strings (14:30 - 15:30, S5):

Everybody is welcome to attend.

Organizers: Martin Balko, Maria Saumell, and Pavel Valtr

Valid XHTML 1.0 Transitional