Menores conformes e orientações Pfaffianas

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)