Superboolean rank and the size of the largest triangular submatrix of a random matrix
HTML articles powered by AMS MathViewer
- by Zur Izhakian, Svante Janson and John Rhodes PDF
- Proc. Amer. Math. Soc. 143 (2015), 407-418 Request permission
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.References
- 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
- Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966, DOI 10.1017/CBO9780511814068
- B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), no. 3, 419–427. MR 498256, DOI 10.1017/S0305004100053056
- Zur Izhakian, Tropical arithmetic and matrix algebra, Comm. Algebra 37 (2009), no. 4, 1445–1468. MR 2510993, DOI 10.1080/00927870802466967
- Z. Izhakian and J. Rhodes, New representations of matroids and generalizations. Preprint, 2011. arXiv:1103.0503.
- Z. Izhakian and J. Rhodes, Boolean representations of matroids and lattices. Preprint, 2011. arXiv:1108.1473
- Z. Izhakian and J. Rhodes, C-dependence and c-rank of posets and lattices. Preprint, 2011. arXiv:1110.3553.
- Zur Izhakian and Louis Rowen, Supertropical algebra, Adv. Math. 225 (2010), no. 4, 2222–2286. MR 2680203, DOI 10.1016/j.aim.2010.04.007
- Svante Janson, Tomasz Łuczak, and Andrzej Rucinski, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000. MR 1782847, DOI 10.1002/9781118032718
- 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
- K. H. Kim and F. W. Roush, Kapranov rank vs. tropical rank, Proc. Amer. Math. Soc. 134 (2006), no. 9, 2487–2494. MR 2213725, DOI 10.1090/S0002-9939-06-08426-7
- D. Matula, The largest clique size in a random graph. Tech. Rep., Dept. Comp. Sci., Southern Methodist Univerity, Dallas, Texas, 1976.
- 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
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
- 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
- © Copyright 2014 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 143 (2015), 407-418
- MSC (2010): Primary 03G05, 06E25, 06E75, 60C05
- DOI: https://doi.org/10.1090/S0002-9939-2014-12301-X
- MathSciNet review: 3272765