Pólya's permanent problem (Q1773170): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: William D. McCuaig / rank | |||
Property / reviewed by | |||
Property / reviewed by: Kim Hang Kim / rank | |||
Revision as of 08:52, 16 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pólya's permanent problem |
scientific article |
Statements
Pólya's permanent problem (English)
0 references
25 April 2005
0 references
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.
0 references
Pfaffian orientations
0 references
sign-nonsingular matrix
0 references
unbalanced edge-weighting
0 references
brace
0 references