Combinatorial and geometric dualities in graph homomorphism optimization problems (2021)
- Authors:
- Autor USP: PROENÇA, NATHAN BENEDETTO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- DOI: 10.11606/D.45.2021.tde-23092021-183204
- Subjects: FUNÇÃO TETA; OTIMIZAÇÃO COMBINATÓRIA; TEORIA DOS GRAFOS
- Keywords: 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
- Agências de fomento:
- Language: Inglês
- Abstract: 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 àsformulaçõ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
- Imprenta:
- Data da defesa: 19.07.2021
- Este periódico é de acesso aberto
- Este artigo é de acesso aberto
- URL de acesso aberto
- Cor do Acesso Aberto: gold
- Licença: cc-by-nc-sa
-
ABNT
PROENÇA, Nathan Benedetto. Combinatorial and geometric dualities in graph homomorphism optimization problems. 2021. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 2021. Disponível em: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-23092021-183204/. Acesso em: 24 abr. 2024. -
APA
Proença, N. B. (2021). Combinatorial and geometric dualities in graph homomorphism optimization problems (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://www.teses.usp.br/teses/disponiveis/45/45134/tde-23092021-183204/ -
NLM
Proença NB. Combinatorial and geometric dualities in graph homomorphism optimization problems [Internet]. 2021 ;[citado 2024 abr. 24 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-23092021-183204/ -
Vancouver
Proença NB. Combinatorial and geometric dualities in graph homomorphism optimization problems [Internet]. 2021 ;[citado 2024 abr. 24 ] Available from: https://www.teses.usp.br/teses/disponiveis/45/45134/tde-23092021-183204/
Informações sobre o DOI: 10.11606/D.45.2021.tde-23092021-183204 (Fonte: oaDOI API)
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
