Geodesic
On the Gibson barrier for the P\'olya problem
Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 8, pp. 73-86.

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {16},
     number = {8},
     year = {2010},
     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\'olya problem
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2010
SP  - 73
EP  - 86
VL  - 16
IS  - 8
PB  - mathdoc
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\'olya problem
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2010
%P 73-86
%V 16
%N 8
%I mathdoc
%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\'olya 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