Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

Request Permissions   Purchase Content 


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.

References [Enhancements On Off] (What's this?)

  • [1] M. Akian, R. Bapat, and S. Gaubert, Max-plus algebra. In: Hogben, L., Brualdi, R., Greenbaum, A., Mathias, R. (eds.), Handbook of linear algebra. Chapman and Hall, London, 2007. MR 2279160 (2007j:15001)
  • [2] Béla Bollobás, Random graphs, 2nd ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001. MR 1864966 (2002j:05132)
  • [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 (58 #16408)
  • [4] Zur Izhakian, Tropical arithmetic and matrix algebra, Comm. Algebra 37 (2009), no. 4, 1445-1468. MR 2510993 (2010d:16059),
  • [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 (2012a:14137),
  • [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 (2001k:05180)
  • [10] Ki Hang Kim, Boolean matrix theory and applications, with a foreword by Gian-Carlo Rota. Monographs and Textbooks in Pure and Applied Mathematics, vol. 70, Marcel Dekker Inc., New York, 1982. MR 655414 (84a:15001)
  • [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 (2007b:15001),
  • [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

Similar Articles

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

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

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

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

American Mathematical Society