Skip to content
DraconiticResearch
Search Sources API
194,226 studies31 sourcesUpdated 47 min ago
PreprintarXiv licencearXiv

An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix

  • Yiming Chen
Open at sourcePDFDOICite

Abstract

Let Mn be an n× n matrix with independent uniform sign entries. We prove that there exist absolute constants C,c>0 such that, for all sufficiently large n, ℙ ( |Per(Mn)| ≥ e−Cn√(n!) ) ≥ 1−n−c. This establishes the exponential scale lower bound suggested by Tao and Vu. The proof bounds the cumulative logarithmic loss of the sum of squared permanents of minors under row exposure.

Related

  1. Localization Lengths for Two-Dimensional Random Band Matrices: Stretched-Exponential Lower Bounds
    Xujie Lai, Fan Yang
    arXivPreprintarXiv licenceFull textMathematical physicsProbabilityarXiv
  2. Continuity of the phase transition for long-range Bernoulli percolation with exponential decay on ℤ2
    Omer Angel, Daniel de la Riva, Christoforos Panagiotis +1
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  3. A deterministic (1+ε)n approximation for the permanent of a nonnegative matrix
    Dingding Dong, Vishesh Jain
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. The Maximum Permanent of a Stochastic Matrix of Bounded Rank
    Yair Lavi
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Critical cusp cancellation and analytic response for a Bernoulli random interval map
    Davrbek Oltiboev, Furqat Vafoyev
    arXivPreprintarXiv licenceFull textDynamical systemsarXiv

Cite

BibTeXRIS
BibTeX
@misc{chen2026exponential,
  title = {{An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix}},
  author = {Yiming Chen},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2608.26707},
  eprint = {2608.26707},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.26707},
}
RIS
TY  - UNPB
TI  - An Exponential Lower Bound for the Permanent of Random Bernoulli Matrix
AU  - Yiming Chen
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2608.26707
UR  - https://arxiv.org/abs/2608.26707
AB  - Let M_n be an n× n matrix with independent uniform sign entries. We prove that there exist absolute constants C,c>0 such that, for all sufficiently large n, ℙ ( |Per(M_n)| ≥ e^−Cn√(n!) ) ≥ 1−n^−c. This establishes the exponential scale lower bound suggested by Tao and Vu. The proof bounds the cumulative logarithmic loss of the sum of squared permanents of minors under row exposure.
ER  -