Seminar: An Algebraic Perspective On Perfect Graphs by Cemil Dibek

SEMINAR 

DEPARTMENT OF INDUSTRIAL ENGINEERING 

An Algebraic Perspective On Perfect Graphs

by

Cemil Dibek

Department of Operations Research and Financial Engineering

Princeton University 

Abstract:

For a graph G, if we define a certain quartic form  p_G(x) based on the adjacency relation in G, then the Motzkin-Straus theorem will imply that  p_G(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  p_H(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.

Short Bio: 

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)