Combinatorial and geometric dualities in graph homomorphism optimization problems

• Ano de defesa: 2021
• Autor(a) principal: Proença, Nathan Benedetto
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Biblioteca Digitais de Teses e Dissertações da USP
• Palavras-chave em Português: Cantos convexos; Conic programming; Convex corners; Fractional chromatic number; Função teta de Lovász; Graph homomorphisms; Homomorfismos de grafos; Lovász theta function; Número cromático fracionário; Programação cônica; Quantum information theory; Teoria quântica da informação
• Link de acesso: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-23092021-183204/

A graph homomorphism is a function between the vertex set of two graphs which maps pairs of adjacent vertices to pairs of adjacent vertices. Many graph parameters can be expressed in terms of finding a homomorphism that maximizes or minimizes a certain objective function: the chromatic number , the clique number , and the Lovász function are noteworthy examples. This work studies graph homomorphisms optimization using combinatorial and convex optimization. Grounded on the theory of preordered sets, we develop a framework that captures a combinatorial duality between the clique and coloring numbers, and that formulates several graph parameters in the literature. We demonstrate known results on convex corners and antiblockers, and we use these geometric concepts to explain some properties of the graph parameters of interest. In particular, we present a geometric duality between upper bounds for the stability number of a graph and lower bounds for the fractional chromatic number of a graph. We use this duality to provide a new understanding of the relationship between two famous spectral bounds introduced by Hoffman. Building on the concepts previously presented, we study convex corners and generalizations of graph homomorphisms which use cones of symmetric matrices. We relate the Choi representation of linear transformations with conic formulations of graph homomorphisms, thus uncovering a new connection between ideas from quantum information theory. Several results and concepts are approached in distinct ways throughout the text, establishing with theorems and examples the cohesion between the combinatorial and geometric perspectives.