Seminars in September 2012

  • Andreas Holmsen, On the Erdős-Szekeres Problem
    On the Erdős-Szekeres Problem
    Andreas Holmsen
    Department of Mathematical Sciences, KAIST
    2012/9/21 Fri 4PM-5PM
    In 1935 Erdős and Szekeres showed that every “sufficiently large” set of points in general position in the plane contains a “large” subset which is in convex position. Since then many mathematicians have tried to determine good bounds for “sufficiently large” in  terms of “large”, as well as given numerous generalizations and refinements. In this talk I will survey this famous problem and extend it to a natural object which we call generalized wiring diagram. This unifies several proposed generalizations, and as a result we will settle several conjectures in this area. This is joint work with Michael Dobbins and Alfredo Hubard.
    Tags:

  • Younjin Kim (김연진), Cycle-saturated graphs with minimum number of edges
    Cycle-saturated graphs with minimum number of edges
    Younjin Kim (김연진)
    Department of Mathematical Sciences, KAIST
    2012/9/14 Fri 4PM-5PM
    A graph G is called H-saturated if it does not contain any copy of H, but for any edge e in the complement of G the graph G+e contains some H. The minimum size of an n-vertex H-saturated graph is denoted by sat(n,H). We prove sat(n,Ck) = n + n/k + O((n/k2) + k2) holds for all n≥k≥3, where Ck is a cycle with length k.
    Joint work with Zoltan Füredi.
    Tags:

Monthly Archives