Seminars in November 2009

  • (Colloquium) Ken-ichi Kawarabayashi, The disjoint paths problem: Algorithm and Structure
    FYI (Department Colloquium)
    The disjoint paths problem: Algorithm and Structure
    Ken-ichi Kawarabayashi (河原林 健一)
    National Institute of Informatics, Tokyo, Japan.
    2009/11/26 Thursday 4:30PM-5:30PM (Room 1501)

    In this talk, we shall discuss the following well-known problem, which
    is called the disjoint paths problem.

    Given a graph G with n vertices and m edges, k pairs of vertices (s1,t1),(s2,t2),…,(sk,tk) in G (which are sometimes called terminals). Are there disjoint paths P1,…,Pk in G such that Pi joins si and ti for i=1,2,…,k?

    We discuss recent progress on this topic, including algorithmic aspect of the disjoint paths problem.

    We also discuss some structure theorems without the k disjoint paths. Topics include the uniquely linkage problem and the connectivity function that guarantees the existence of the k disjoint paths.

    Tags:

  • Ken-ichi Kawarabayashi, Graphs without subdivisions
    Graphs without subdivisions
    Ken-ichi Kawarabayashi (河原林 健一)
    National Institute of Informatics, Tokyo, Japan.
    2009/11/24 Tuesday 4PM-5PM

    Hajos’ conjecture is false, and it seems that graphs without a subdivision of a big complete graph do not behave as well as those without a minor of a big complete graph.

    In fact, the graph minor theorem (a proof of Wagner’s conjecture) is not true if we replace the minor relation by the subdivision relation. I.e, For every infinite sequence G1,G2, … of graphs, there exist distinct integers i<j such that Gi is a minor of Gj, but if we replace ”minor” by ”subdivision”, this is no longer true.

    This is partially because we do not really know what the graphs without a subdivision of a big complete graph look like.

    In this talk, we shall discuss this issue. In particular, assuming some moderate connectivity condition, we can say something, which we will present in this talk.

    Topics also include coloring graphs without a subdivision of a large complete graph, and some algorithmic aspects. Some of the results are joint work with Theo Muller.

    Tags:

  • Soon-Yi Kang (강순이), The Product and Quotient of Generating Series for Partitions and Sums of Squares
    The Product and Quotient of Generating Series for Partitions and Sums of Squares
    Soon-Yi Kang (강순이)
    Department of Mathematical Sciences, KAIST
    2009/11/13 Friday 4PM-5PM

    We first present how to extend Ramanujan’s method in partition congruences and show a congruence relation that the coefficients of the quotient of generating series for partitions and sums of squares satisfy. Then we observe a combinatorial interpretation of the product of them and see whether we could find some arithmetic properties of its coefficients.

    Tags:

Monthly Archives