Menores conformes e orientações Pfaffianas

• Processo: 18/04679-1
• Linha de fomento: Bolsas no Brasil - Pós-Doutorado
• Vigência (Início): 01 de setembro de 2018
• Vigência (Término): 30 de junho de 2020
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Pesquisador responsável: Orlando Lee
• Beneficiário: Nishad Bharat Kothari
• Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
• Vinculado ao auxílio: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural, AP.TEM
• Assunto(s): Teoria dos grafos Pfaffianos

Resumo

O conceito de orientação Pfaffiana foi introduzido por Kasteleyn (1963) para resolver o problema do dímero em mecânica estatística. Sua relevância vem do fato de que se um grafo admite uma orientação Pfaffiana, então seu número de emparelhamentos perfeitos pode ser calculado em tempo polinomial. Em geral, não se sabe se o problema de decidir se um grafo admite uma orientação Pfaffiana pode ser resolvido em tempo polinomial. Este é um problema de grande interesse para teóricos em Ciência da Computação. O conceito de orientação Pfaffiana está intrinsicamente ligado ao conceito de menor conforme em teoria dos grafos. Little (1975) provou que um grafo bipartido $G$ é Pfaffiano se e somente se $G$ não contém $K{3,3}$ como um menor conforme (ou seja, se e somente se $G$ é livre de $K_{3,3}$). Uma caracterização estrutural de grafos bipartidos livres de $K{3,3}$ foi obtida independentemente por McCuaig (2004) e Robertson, Seymour e Thomas (1999). Este resultado implica em um algoritmo polinomial para decidir se um grafo bipartido \'e Pfaffiano. Miranda (2006) e Whalen (2014) encontraram demonstrações alternativas deste fato. Em um trabalho conjunto com Murty (2016), caracterizamos grafos planares livres de $K_4$. O problema de caracterizar grafos não-planares livres de $K_4$ é muito mais difícil e temos evidência para acreditar que está relacionado ao problema de caracterizar grafos Pfaffianos. Temos conjecturas específicas suportadas por experimentos computacionais e pretendemos resolver o maior número possível delas neste projeto. (AU)

Publicações científicas

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

FABRES, PHELIPE A.; KOTHARI, NISHAD; DE CARVALHO, MARCELO H. Minimal braces. JOURNAL OF GRAPH THEORY, v. 96, n. 4, p. 490-509, MAR 2021. Citações Web of Science: 0.

LU, FULIANG; KOTHARI, NISHAD; FENG, XING; ZHANG, LIANZHU. Equivalence classes in matching covered graphs. DISCRETE MATHEMATICS, v. 343, n. 8 AUG 2020. Citações Web of Science: 0.

KOTHARI, NISHAD; DE CARVALHO, MARCELO H.; LUCCHESI, CLAUDIO L.; LITTLE, CHARLES H. C. On essentially 4-edge-connected cubic bricks. ELECTRONIC JOURNAL OF COMBINATORICS, v. 27, n. 1 JAN 24 2020. Citações Web of Science: 0.