Pólya's permanent problem
type: Item
instance of: scholarly article
title: Pólya's permanent problem
zbMATH Open document ID: 1062.05066
published in: The Electronic Journal of Combinatorics
publication date: 2005-04-25T00:00:00Z
full work available at URL: https://eudml.org/doc/124596
full work available at URL: v11i1r79.html
review text: Pólya's permanent problem has many equivalent forms: determining when all dicycles of a digraph have odd length, determining when a real square matrix is sign-nonsingular, which has applications in economics, determining whether the determinant of a nonnegative matrix equals its permanent, determining when the permanent can be computed as the determinant after changing some signs of the original matrix entries, determining whether a bipartite graph has a Pfaffian orientation, which has applications in chemistry, and various balance conditions. The author characterizes such graphs by his main theorem, that the following conditions are equivalent for a brace: a given graph is a brace with an unbalanced \(\{ -1,1\}\) edge weighting, it is a brace which does not have a well-fitted \(K_{3,3}\) subdivision, and it lies in the family consisting of the Heawood graph \(H_{14}\), all planar braces, and all graphs generated from planar braces using 4-cycle sums. This means the problem lies in NP \(\cap\) co-NP, and the author states that a polynomial-time algorithm can be derived from his lengthy proof.
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 15A15
Mathematics Subject Classification ID: 05A15
zbMATH DE Number: 2161284
zbMATH Keywords: Pfaffian orientations
zbMATH Keywords: sign-nonsingular matrix
zbMATH Keywords: unbalanced edge-weighting
zbMATH Keywords: brace
author: William McCuaig
reviewed by: Ki Hang Kim
MaRDI profile type: Publication
Recommended article: A Problem of Pólya
Recommended article: Solution of the Polya problem
Recommended article: The Polya-Tchebotarov problem
Recommended article: Pólya, Problem Solving, and Education
Recommended article: Q4525543
Recommended article: The Polaron problem
description: scientific article; zbMATH DE number 2161284