Superboolean rank and the size of the largest triangular submatrix of a random matrix

Authors:
Zur Izhakian, Svante Janson and John Rhodes

Journal:
Proc. Amer. Math. Soc. **143** (2015), 407-418

MSC (2010):
Primary 03G05, 06E25, 06E75, 60C05

Published electronically:
September 15, 2014

MathSciNet review:
3272765

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We explore the size of the largest (permuted) triangular submatrix of a random matrix, and more precisely its asymptotical behavior as the size of the ambient matrix tends to infinity. The importance of such permuted triangular submatrices arises when dealing with certain combinatorial algebraic settings in which these submatrices determine the rank of the ambient matrix and thus attract special attention.

- [1]
Leslie
Hogben (ed.),
*Handbook of linear algebra*, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, 2007. Associate editors: Richard Brualdi, Anne Greenbaum and Roy Mathias. MR**2279160** **[2]**Béla Bollobás,*Random graphs*, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR**1864966****[3]**B. Bollobás and P. Erdős,*Cliques in random graphs*, Math. Proc. Cambridge Philos. Soc.**80**(1976), no. 3, 419–427. MR**0498256****[4]**Zur Izhakian,*Tropical arithmetic and matrix algebra*, Comm. Algebra**37**(2009), no. 4, 1445–1468. MR**2510993**, 10.1080/00927870802466967- [5] Z. Izhakian and J. Rhodes, New representations of matroids and generalizations. Preprint, 2011. arXiv:1103.0503.
- [6] Z. Izhakian and J. Rhodes, Boolean representations of matroids and lattices. Preprint, 2011. arXiv:1108.1473
- [7] Z. Izhakian and J. Rhodes, C-dependence and c-rank of posets and lattices. Preprint, 2011. arXiv:1110.3553.
**[8]**Zur Izhakian and Louis Rowen,*Supertropical algebra*, Adv. Math.**225**(2010), no. 4, 2222–2286. MR**2680203**, 10.1016/j.aim.2010.04.007**[9]**Svante Janson, Tomasz Łuczak, and Andrzej Rucinski,*Random graphs*, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR**1782847****[10]**Ki Hang Kim,*Boolean matrix theory and applications*, Monographs and Textbooks in Pure and Applied Mathematics, vol. 70, Marcel Dekker, Inc., New York, 1982. With a foreword by Gian-Carlo Rota. MR**655414****[11]**K. H. Kim and F. W. Roush,*Kapranov rank vs. tropical rank*, Proc. Amer. Math. Soc.**134**(2006), no. 9, 2487–2494. MR**2213725**, 10.1090/S0002-9939-06-08426-7- [12] D. Matula, The largest clique size in a random graph. Tech. Rep., Dept. Comp. Sci., Southern Methodist Univerity, Dallas, Texas, 1976.
**[13]**Xing Sun and Andrew B. Nobel,*On the size and recovery of submatrices of ones in a random binary matrix*, J. Mach. Learn. Res.**9**(2008), 2431–2453. MR**2460888**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC (2010):
03G05,
06E25,
06E75,
60C05

Retrieve articles in all journals with MSC (2010): 03G05, 06E25, 06E75, 60C05

Additional Information

**Zur Izhakian**

Affiliation:
School of Mathematical Sciences, Tel Aviv University, Ramat Aviv, Tel Aviv 69978, Israel – and – Department of Mathematics, Bar-Ilan University, Ramat-Gan 52900, Israel

Email:
zzur@math.biu.ac.il

**Svante Janson**

Affiliation:
Department of Mathematics, Uppsala University, P.O. Box 480, SE-751 06 Uppsala, Sweden

Email:
svante.janson@math.uu.se

**John Rhodes**

Affiliation:
Department of Mathematics, 970 Evans Hall #3840, University of California, Berkeley, Berkeley, California 94720-3840

Email:
blvdbastille@aol.com, rhodes@math.berkeley.edu

DOI:
https://doi.org/10.1090/S0002-9939-2014-12301-X

Received by editor(s):
September 8, 2011

Received by editor(s) in revised form:
April 1, 2013

Published electronically:
September 15, 2014

Additional Notes:
The research of the first author was supported by the Israel Science Foundation (ISF grant No. 448/09) and by the Oberwolfach Leibniz Fellows Programme (OWLF), Mathematisches Forschungsinstitut Oberwolfach, Germany.

Communicated by:
Jim Haglund

Article copyright:
© Copyright 2014
American Mathematical Society