Combinatorial and geometric dualities in graph homomorphism optimization problems
Nathan Benedetto Proença · 2021
Um homomorfismo de grafos é uma função entre os vértices de dois grafos que mapeia pares de vértices adjacentes em pares de vértices adjacentes.Diversos parâmetros de grafos podem ser formulados em termos de encontrar um homomorfismo que maximize ou minimize um certo valor objetivo: o número cromático χ, o número de clique ω e a função ϑ de Lovász são exemplos notáveis.Este trabalho estuda otimização de homomorfismos de grafos utilizando otimização convexa e combinatória.Apresentamos um arcabouço, fundamentado na teoria de conjuntos pré-ordenados, que evidencia uma dualidade combinatória entre o número de clique e o número cromático, além de ser capaz de formular diversos parâmetros na literatura.Demonstramos resultados conhecidos sobre cantos convexos e anti-bloqueadores, e então utilizamos esses conceitos geométricos para explicar certas propriedades de alguns dos parâmetros que nos interessam.Em particular, descrevemos uma dualidade geométrica entre limitantes superiores ao número de estabilidade de um grafo e limitantes inferiores ao número cromático fracionário de um grafo.Utilizamos essa dualidade para fornecer um novo entendimento sobre a relação entre dois famosos limitantes espectrais introduzidos por Hoffman.Aproveitando os conceitos previamente discutidos, abordamos diretamente construções que definem cantos convexos e generalizações de homomorfismos a partir de cones de matrizes simétricas.Relacionamos a representação de Choi de uma transformação linear às formulações cônicas de homomorfismos, obtendo assim uma nova conexão entre ideias presentes na teoria quântica da informação.Diversos resultados e conceitos são apresentados de distintas maneiras no decorrer do texto, estabelecendo através de teoremas e exemplos a coesão entre as perspectivas combinatória e geométrica.