On the permanent of random Bernoulli matrices

被引：15

作者：

Tao, Terence ^{[2
]}

Vu, Van ^{[1
]}

机构：

[1] Rutgers State Univ, Dept Math, Piscataway, NJ 08854 USA

[2] Univ Calif Los Angeles, Dept Math, Los Angeles, CA 90095 USA

来源：

ADVANCES IN MATHEMATICS | 2009年 / 220卷 / 03期

基金：

美国国家科学基金会;

关键词：

Random matrices; Permanent; SINGULARITY; PROBABILITY;

D O I：

10.1016/j.aim.2008.09.006

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We show that the permanent of an n x n matrix with iid Bernoulli entries +/- 1 is of magnitude n((1/2+o(1))n) with probability 1-o(1). In particular, it is almost surely non-zero. (C) 2008 Elsevier Inc. All rights reserved.

引用

页码：657 / 669

页数：13

共 14 条

[1]

Alon N., 2004, PROBABILISTIC METHOD

[2]

[Anonymous], 1994, Combin Probab Comput

[3]

Bourgain Jean., SINGULARITY PROBABIL

[4] ON A LEMMA OF LITTLEWOOD AND OFFORD [J].

ERDOS, P .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1945, 51 (12) :898-902

[5] ON THE PROBABILITY THAT A RANDOM +/-1-MATRIX IS SINGULAR [J].

KAHN, J ;

KOMLOS, J ;

SZEMEREDI, E .

JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 1995, 8 (01) :223-240

[6]

Komlos J., 1968, Studia Sci. Math. Hungar., V3, P387

[7]

KOMLOS J, 2001, RANDOM GRAPHS

[8]

Komlos J., 1967, Studia Sci. Math. Hungar., V2, P7

[9] Limiting behavior of random permanents [J].

Rempala, G ;

Wesolowski, J .

STATISTICS & PROBABILITY LETTERS, 1999, 45 (02) :149-158

[10]

REMPALA G, 2000, RANDOM OPER STOCHAST, V8, P305

← 1 2 →