Seminar: An Algebraic Perspective On Perfect Graphs by Cemil Dibek
DEPARTMENT OF INDUSTRIAL ENGINEERING
An Algebraic Perspective On Perfect Graphs
Department of Operations Research and Financial Engineering
For a graph G, if we define a certain quartic form pG(x) based on the adjacency relation in G, then the Motzkin-Straus theorem will imply that pG(x) is nonnegative for every graph G. In this work, we introduce the notion of sos-perfectness. A graph G is perfect if for every induced subgraph H of G, the chromatic number of H equals the clique number of H. A graph G is sos-perfect if pH(x) is sum of squares (sos) for every induced subgraph H of G. We show that a graph is perfect if and only if it is sos-perfect. This equivalence together with the strong perfect graph theorem allows us to explicitly provide an infinite family of nonnegative polynomials that are not sos.
Joint work with Amir Ali Ahmadi.
Cemil Dibek is a Ph.D. student at the Department of Operations Research and Financial Engineering at Princeton University. His research interests are in graph theory, combinatorial optimization, and semidefinite programming applications. Prior to joining Princeton, Cemil obtained a B.S. in both mathematics and industrial engineering at Bogazici University in 2015. He then received his M.S. from the Department of Industrial Engineering at Bogazici University in 2016, where he was also a teaching/research assistant.
All interested are cordially invited.
DATE : Thursday, December 19, 2019
TIME : 15:00-16:00
ROOM : VYKM 2, 5th floor of Engineering Building (Perkins Hall)