Skip navigation
Please use this identifier to cite or link to this item:
Title: Perfect Graphs and Sums of Squares
Authors: Dibek, Cemil
Advisors: AhmadiChudnovsky, Amir AliMaria
Contributors: Operations Research and Financial Engineering Department
Keywords: Induced subgraphs
Nonnegative and sum of squares polynomials
Perfect graphs
Polynomial optimization
Semidefinite programming
Strongly perfect graphs
Subjects: Operations research
Issue Date: 2021
Publisher: Princeton, NJ : Princeton University
Abstract: A graph is perfect if the clique number and the chromatic number coincide for any of its induced subgraphs. A polynomial is a sum of squares (sos) if it can be written as a sum of squares of some other polynomials. In the first technical chapter of this thesis, we bring these two notions together by presenting an algebraic characterization of perfect graphs. We show that a graph is perfect if and only if certain nonnegative polynomials associated with the graph are sos. As a byproduct, we obtain several infinite families of nonnegative polynomials that are not sos through graph-theoretic constructions. We also establish a number of other connections between structural graph theory and real algebra. In the subsequent chapters, we focus on problems that are relevant to sos polynomials and perfect graphs individually. In one chapter, we study separable plus quadratic (SPQ) polynomials. Motivated by the fact that nonnegative separable and nonnegative quadratic polynomials are sos, we study whether nonnegative SPQ polynomials are (i) the sum of a nonnegative separable and a nonnegative quadratic polynomial, and (ii) a sum of squares. We establish that the answer to question (i) is positive for univariate plus quadratic polynomials and for convex SPQ polynomials, but negative already for bivariate quartic SPQ polynomials. For question (ii), we provide a complete characterization of the answer based on the degree and the number of variables of the SPQ polynomial. We also prove that testing nonnegativity of SPQ polynomials is NP-hard when the degree is at least four. We end the chapter by presenting applications of SPQ polynomials to problems in statistics and nonlinear optimization. In the last two chapters, we focus on the study of graphs that are closely related to the class of perfect graphs, namely even-hole-free graphs and strongly perfect graphs. Although the class of even-hole-free graphs is a widely studied class of graphs, the complexity of the maximum independent set problem in this class is a long-standing open problem. We take a step forward in this direction by showing that there is a polynomial-time algorithm to solve the maximum independent set problem in the class of (pyramid, even hole)-free graphs. Regarding strongly perfect graphs, although their characterization by a set of forbidden induced subgraphs remains open, we provide several new infinite families of minimal non-strongly-perfect graphs. We also present a new proof of the characterization of claw-free strongly perfect graphs, which is shorter and quite different from the original proof.
Alternate format: The Mudd Manuscript Library retains one bound copy of each dissertation. Search for these copies in the library's main catalog:
Type of Material: Academic dissertations (Ph.D.)
Language: en
Appears in Collections:Operations Research and Financial Engineering

Files in This Item:
File Description SizeFormat 
Dibek_princeton_0181D_13937.pdf1.66 MBAdobe PDFView/Download

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.