For more information about this meeting, contact Jason Morton.
|Title:||An Algebraic Exploration of Dominating Sets and Vizing's Conjecture|
|Seminar:||Applied Algebra and Network Theory Seminar|
|Speaker:||Susan Margulies, Penn State|
|Systems of polynomial equations are commonly used to model combinatorial problems such as independent set, graph coloring, Hamiltonian path, etc.. In this talk, we formulate the dominating set problem as a system of polynomial equations, and then illustrate that the universal Grobner basis of this ideal is described by a combinatorial property directly related to dominating sets: mainly, an iteration of the complements of domination-critical graphs. We then present an algebraic formulation of Vizing's conjecture (a central question in domination theory and open since 1968), that involves the union of varieties and thus, the intersection of ideals. We conclude with a brief discussion of the computational ramifications of this formulation.|
Room Reservation Information
|Date:||08 / 31 / 2011|
|Time:||02:30pm - 03:20pm|