Seminars in May 2009

  • (Colloquium) Paul Seymour, Well-quasi-ordering tournaments and Rao’s degree-sequence conjecture
    FYI (Department Colloquium)
    Well-quasi-ordering tournaments and Rao’s degree-sequence conjecture
    Paul Seymour
    Department of Mathematics, Princeton University, Princeton, New Jersey, USA.
    2009/5/21 Thursday 4:30PM-5:30PM (Room 1501)

    Rao conjectured about 1980 that in every infinite set of degree sequences (of graphs), there are two degree sequences with graphs one of which is an induced subgraph of the other. We recently found a proof, and we sketch the main ideas.

    The problem turns out to be related to ordering digraphs by immersion (vertices are mapped to vertices, and edges to edge-disjoint directed paths). Immersion is not a well-quasi-order for the set of all digraphs, but for certain restricted sets (for instance, the set of tournaments) we prove it is a well-quasi-order.

    The connection between Rao’s conjecture and digraph immersion is as follows. One key lemma reduces Rao’s conjecture to proving the same assertion for degree sequences of split graphs (a split graph is a graph whose vertex set is the union of a clique and a stable set); and to handle split graphs it helps to encode the split graph as a directed complete bipartite graph, and to replace Rao’s containment relation with immersion.

    (Joint with Maria Chudnovsky, Columbia)

    Tags:

  • Maria Chudnovsky, Packing seagulls in graphs with no stable set of size three
    Packing seagulls in graphs with no stable set of size three
    Maria Chudnovsky
    Department of Industrial Engineering and Operations Research & Department of Mathematics, Columbia University, New York, USA
    2009/5/21 Thursday 2PM-3PM

    Hadwiger’s conjecture is a well known open problem in graph theory. It states that every graph with chromatic number k, contains a certain structure, called a “clique minor” of size k. An interesting special case of the conjecture, that is still wide open, is when the graph G does not contain three pairwise non-adjacent vertices. In this case, it should be true that G contains a clique minor of size t where t = \lceil |V(G)|/2 \rceil. This remains open, but Jonah Blasiak proved it in the subcase when |V(G)| is even and the vertex set of G is the union of three cliques. Here we prove a strengthening of Blasiak’s result: that the conjecture holds if some clique in G contains at least |V(G)|/4 vertices.

    This is a consequence of a result about packing “seagulls”. A seagull in G is an induced three-vertex path. It is not known in general how to decide in polynomial time whether a graph contains k pairwise disjoint seagulls; but we answer this for graphs with no stable sets of size three.

    This is joint work with Paul Seymour.

    Tags:

  • Mitsugu Hirasaka, Finding n such that every transitive permutation group of degree n is multiplicity-free
    Finding n such that every transitive permutation group of degree n is multiplicity-free
    Mitsugu Hirasaka
    Department of Mathematics, Pusan National University, Pusan, Korea</a>
    2009/5/1 Friday 4PM-5PM
    This is a joint work with Cai-Heng Li. Let \mathcal{MF} denote the set of positive integers n such that each transitive action of degree n is multiplicity-free, and \mathcal{PQ} denote the set of n\in \mathbb{N} such that n=pq for some primes p, q with p<q[/latex] and [latex](p,q-1)=1[/latex] where (m,l) is the greatest common divisor of m and n. Our main result shows that [latex]\mathcal{PQ}\backslash \mathcal{MF}[/latex] is the union of <center>[latex]\{pq\in \mathcal{PQ}\mid (p,q-2)=p, q\mbox{ is a Fermat prime}\}</center> and
    \{pq\in \mathcal{PQ}\mid q=2p-1\}
    where its proof owes much to classification of finite simple groups.
    Tags:

Monthly Archives