Geodesic
On the Gibson barrier for the Pólya problem
Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 8, pp. 73-86
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study lower bounds on the number of nonzero entries in $(0,1)$ matrices such that the permanent is always convertible to the determinant by placing $\pm$ signs on matrix entries. 
@article{FPM_2010_16_8_a6,
     author = {G. Dolinar and A. E. Guterman and B. Kuzma},
     title = {On the {Gibson} barrier for the {P\'olya} problem},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {73--86},
     year = {2010},
     volume = {16},
     number = {8},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a6/}
}
TY  - JOUR
AU  - G. Dolinar
AU  - A. E. Guterman
AU  - B. Kuzma
TI  - On the Gibson barrier for the Pólya problem
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2010
SP  - 73
EP  - 86
VL  - 16
IS  - 8
UR  - http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a6/
LA  - ru
ID  - FPM_2010_16_8_a6
ER  - 
%0 Journal Article
%A G. Dolinar
%A A. E. Guterman
%A B. Kuzma
%T On the Gibson barrier for the Pólya problem
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2010
%P 73-86
%V 16
%N 8
%U http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a6/
%G ru
%F FPM_2010_16_8_a6
G. Dolinar; A. E. Guterman; B. Kuzma. On the Gibson barrier for the Pólya problem. Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 8, pp. 73-86. http://geodesic.mathdoc.fr/item/FPM_2010_16_8_a6/

[1] Brualdi R. A., Shader B. L., “On sign-nonsingular matrices and the conversion of the permanent into the determinant”, Applied Geometry and Discrete Mathematics, The Victor Klee Festschrift on the Occasion of Professor Klee's 65th Birthday., DIMACS, Ser. Discret. Math. Theor. Comput. Sci., 4, Amer. Math. Soc., Providence; Assoc. Comp. Mach., New York, 1991, 117–134 | MR

[2] Brualdi R. A., Shader B. L., Matrices of Sign-Solvable Linear Systems, Cambridge Tracts Math., 116, Cambridge Univ. Press, Cambridge, 1995 | MR | Zbl

[3] Gibson P. M., “An identity between permanents and determinants”, Amer. Math. Mon., 76 (1969), 270–271 | DOI | MR | Zbl

[4] Gibson P. M., “Conversion of the permanent into the determinant”, Proc. Amer. Math. Soc., 27 (1971), 471–476 | DOI | MR | Zbl

[5] Klee V., Ladner R., Manber R., “Signsolvability revisited”, Linear Algebra Appl., 59 (1984), 132–157 | DOI | MR

[6] Little C. H. C., “A characterization of convertible $(0,1)$-matrices”, J. Combin. Theory Ser. B, 18 (1975), 187–208 | DOI | MR | Zbl

[7] Marcus M., Minc H., “On the relation between the determinant and the permanent”, Illinois J. Math., 5 (1961), 376–381 | MR | Zbl

[8] McCuaig W., “Pólya's permanent problem”, Electron. J. Combin., 11 (2004), R79 | MR | Zbl

[9] Minc H., Permanents, Addison-Wesley, 1978 | MR | Zbl

[10] Pólya G., “Aufgabe 424”, Arch. Math. Phys. Ser. 3, 20 (1913), 271

[11] Szegő G., “Lösung zu Aufgabe 424”, Arch. Math. Phys., 21 (1913), 291–292

[12] Valiant L. G., “The complexity of computing the permanent”, Theor. Comput. Sci., 8 (1979), 189–201 | DOI | MR | Zbl

[13] Vazirani V. V., Yannakakis M., “Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs”, Discrete Appl. Math., 25 (1989), 179–190 | DOI | MR | Zbl