Lecture: An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
Master data
Title: | An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture |
Description: | Vizing's conjecture (open since 1968) relates the sizes of dominating sets in two graphs to the size of a dominating set in their Cartesian product graph. In this paper, we formulate Vizing's conjecture itself as a Positivstellensatz existence question. In particular, we encode the conjecture as an ideal/polynomial pair such that the polynomial is nonnegative if and only if the conjecture is true. We demonstrate how to use semidefinite optimization techniques to computationally obtain numeric sum-of-squares certificates, and then show how to transform these numeric certificates into symbolic certificates approving nonnegativity of our polynomial. After outlining the theoretical structure of this computer-based proof of Vizing's conjecture, we present computational and theoretical results. In particular, we present exact low-degree sparse sum-of-squares certificates for particular families of graphs. |
Keywords: | Vizing’s conjecture; algebraic model; Gröbner basis; sum-of-squaresproblems; semidefinite programming |
Type: | Invited speaker |
Homepage: | http://www.issac-conference.org/2019/program.php |
Event: | ISSAC 2019 (Beihang University, Beijing) |
Date: | 17.07.2019 |
lecture status: |
Participants
Elisabeth Gaar (internal) |
|
||||
Angelika Wiegele (internal) |
|
||||
Daniel Krenn (external) |
|
||||
Susan Margulies
|
|
Assignment
Organisation | Address | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Categorisation
Subject areas | |
Research Cluster | No research Research Cluster selected |
Focus of lecture |
Classification raster of the assigned organisational units:
|
Group of participants |
|
Published? |
|
Keynote speaker |
|
working groups | No working group selected |
Cooperations
Research activities
Projects |
|
Publications |
|
Events | No related events |
Lectures | No related lectures |