Vortrag: An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture
Stammdaten
Titel: | An Optimization-Based Sum-of-Squares Approach to Vizing's Conjecture |
Beschreibung: | 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. |
Schlagworte: | Vizing’s conjecture; algebraic model; Gröbner basis; sum-of-squaresproblems; semidefinite programming |
Typ: | Vortrag auf Einladung |
Homepage: | http://www.issac-conference.org/2019/program.php |
Veranstaltung: | ISSAC 2019 (Beihang University, Beijing) |
Datum: | 17.07.2019 |
Vortragsstatus: |
Beteiligte
Elisabeth Gaar (intern) |
|
||||||
Angelika Wiegele (intern) |
|
||||||
Daniel Krenn
|
|
||||||
Susan Margulies
|
|
Zuordnung
Organisation | Adresse | ||||
---|---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
AT - 9020 Klagenfurt am Wörthersee |
Kategorisierung
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Vortragsfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
TeilnehmerInnenkreis |
|
Publiziert? |
|
Keynote-Speaker |
|
Arbeitsgruppen | Keine Arbeitsgruppe ausgewählt |
Kooperationen
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte |
|
Publikationen |
|
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge | Keine verknüpften Vorträge vorhanden |