Seminars in November 2012

  • Mohit Kumbhat, Choosability with separation in graphs and hypergraphs
    Choosability with separation in graphs and hypergraphs
    Mohit Kumbhat
    Department of Mathematics, Sungkyunkwan University, Suwon, South Korea
    2012/11/22 Thu 4PM-5PM
    For a hypergraph G and a positive integer c, let χℓ(G,c) be the minimum value of ℓ such that G is L-colorable from every list L with |L(v)|=ℓ for each v∈V(G) and |L(u)∩L(v)|≤c for all e=uv∈E(G). This parameter was studied by Kratochvíl, Tuza and Voigt for various kinds of graphs. In this talk, we present the asymptotics of χℓ(G,c) for complete graphs, complete multipartite graphs and hypergraphs. This is a joint work with Z. Füredi and A. Kostochka.
    Tags:

  • Gary MacGillivray, Graph Partitions
    Graph Partitions
    Gary MacGillivray
    Department of Mathematics and Statistics, University of Victoria, Victoria, B.C. Canada
    2012/11/9 Fri 4PM-5PM
    We consider partitions of the vertices of a graph into a fixed number of labelled cells such that (i) the subgraph induced by each cell belongs to a family that depends on the cell, and (ii) edges joining vertices in different cells are allowed only if the cells correspond to adjacent vertices in a given pattern graph H. Both polynomiality and NP-completeness results are presented. Tha focus is on methods that give polynomial time algorithms.
    This is a joint work with Peter Dukes and Steve Lowdon.
    Tags:

  • (Colloquium) Jaroslav Nešetřil, Limits of Structures and Sparse-Dense Dichotomy

    FYI (Department Colloquium)

    Limits of Structures and Sparse-Dense Dichotomy
    Jaroslav Nešetřil
    Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University, Prague
    2012/11/1 Thu 4:30PM-5:30PM (Room 1501, Bldg. E6)
    Based on the newly understood dichotomy of sparse and dense structures, we provide the general framework for study of structural (mostly graph) limits. Our approach uses both model theoretic and analytic tools and uses structural theory of bounded expansion classes.
    Tags:

Monthly Archives