Seminars in April 2009

  • Tommy R. Jensen, The Cycle Double Cover Problem for graphs
    The Cycle Double Cover Problem for graphs
    Tommy R. Jensen
    Department of Mathematics, Kyungpook National University, Daegu, Korea
    2009/04/24 Friday 4PM-5PM

    The Cycle Double Cover Problem in Graph Theory suggests that all 2-connected graphs share a certain property with 2-connected planar maps. Such a map clearly contains a collection of cycles, indeed the boundary cycles of its faces, such that each edge belongs to exactly
    two of them. The generalization of this property to nonplanar graphs remains one of the central open problems in Graph Theory.

    We investigate this problem by generalizing a suitable variation of the statement of another almost obvious property of planar maps, namely the Jordan Curve Theorem. The generalization suggests a new conjecture which is much stronger than the Cycle Double Cover Conjecture. In fact it would imply a very strong form of the Cycle Double Cover Conjecture, suggesting that every cycle in a 2-connected graph appears in at least one cycle double cover of the graph.

    We prove the stronger conjecture in a few important special cases.

    Tags:

  • Eric Vigoda, Markov Chain Monte Carlo and Approximating the Permanent
    Markov Chain Monte Carlo and Approximating the Permanent
    Eric Vigoda
    College of Computing, Georgia Institute of Technology, Atlanta, USA</a>
    2009/04/13 Monday 5PM-6PM
    The Markov Chain Monte Carlo (MCMC) method is a widely-used algorithmic approach for randomly sampling from and estimating the cardinality of large sets. In this talk I will give an introduction to the MCMC approach. Then I will explain a more sophisticated variant that gives a polynomial-time algorithm to approximate the permanent of a non-negative matrix. In graph-theoretic terminology, the permanent corresponds to the number of perfect matchings of a bipartite graph.
    Tags:

  • Mark H. Siggers, CSP Dichotomy and the Fibre Construction
    CSP Dichotomy and the Fibre Construction
    Mark H. Siggers
    Department of Mathematics, Kyungpook National University, Daegu, Korea</a>
    2009/04/10 Friday 4PM-5PM (Room 2411)
    In recent years Constraint Satisfaction Problems (CSPs) have gained popularity among graph theorists due to the fact that they can be viewed as a generalisation of graph homomorphism problems. An important conjecture in the field is the CSP Dichotomy Classification Conjecture. Much of the recent progress towards a solution to this conjecture has come from the field universal algebra, and the statement of the Classification Conjecture requires a fair bit of algebraic language. </p>

    We talk about a recent graph theoretic construction, called the fibre construction, which can be used to get some of the important results achieved with universal algebra. This construction provides combinatorial version of the Classification Conjecture, and allows one to easily address restricted versions of the Conjecture. Further it leads to results unexpected by the universal algebra community.

    Much of the material covered is joint work with Jaroslav Nešetřil and László Zádori.</div>

    Tags:

Monthly Archives