Graduate Student Seminar: Perfect Graphs and Sums of Squares Speaker: Cemil Dibek

Abstract: We present an algebraic characterization of perfect graphs, i.e., graphs for which the clique number and the chromatic number coincide for every induced subgraph. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sums of squares. As a byproduct, we obtain several infinite families of nonnegative polynomials that are not sums of squares through graph-theoretic constructions.

Cemil Dibek is a PhD candidate in the department of ORFE at Princeton University. His research interests include: Polynomial optimization, Combinatorial optimization, and Structural graph theory. Before Princeton, he was a teaching/research assistant in the Dept. of Industrial Engineering at Bogazici University, where he completed his bachelor and master studies.