Busca avançada
Ano de início
Entree

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)
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.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.