Seminars in January 2012

  • Ilhee Kim (김일희), A counterexample to a conjecture of Schwartz
    A counterexample to a conjecture of Schwartz
    Ilhee Kim (김일희)
    Princeton University, Princeton, NJ, USA
    2012/01/11 Wed 4PM-5PM
    In 1990, motivated by applications in the social sciences, Thomas Schwartz made a conjecture about tournaments which would have had numerous attractive consequences. In particular, it implied that there is no tournament with a partition A, B of its vertex set, such that every transitive subset of A is in the out-neighbour set of some vertex in B, and vice versa. But in fact there is such a tournament and so Schwartz’ conjecture is false. Our proof is non-constructive and uses the probabilistic method.
    This is joint work with Felix Brandt, Gaku Liu, Maria Chudnovsky, Sergey Norin, Alex Scott, Paul Seymour, and Stephan Thomassé.
    Tags:

  • Seok-Hee Hong (홍석희), Recent Advances in Straight-line Graph Drawing: Extending Steinitz’s Theorem, Fary’s Theorem and Tutte’s Barycenter Theorem
    Recent Advances in Straight-line Graph Drawing:
    Extending Steinitz’s Theorem, Fary’s Theorem and Tutte’s Barycenter Theorem
    Seok-Hee Hong (홍석희)
    School of IT, University of Sydney, Sydney, Australia
    2012/01/05 Thu 11AM-12AM
    One of the most well-studied criteria in Graph Drawing is straight-line
    planar representations of graphs. There are three seminal results on straight-line drawings of planar graphs: the Steinitz’s Theorem, Fary’s theorem, and Tutte’s Barycenter Theorem.
    In this talk, I will first review the recent advances in Graph Drawing on extending the Steinitz’s Theorem and Tutte’s Barycenter Theorem to non-convex representations: Star-shaped polyhedra and Star-shaped drawings. Then, I will announce the latest results on extending Fary’s theorem to non-planar graphs, namely 1-planar graphs.
    Tags:

Monthly Archives