On Monday, DOT will present a theorem of Ronyai, Babai, and Ganapathy which gives an upper bound to the number of zero / nonzero patterns of a sequence of n polynomials in m variables of degree at most d. The perhaps most interesting fact is that the bound does not depend on n---only on m, d, and the number of non-zeros in the pattern. We will then discuss an application, due to Leslie Hogben and coauthors, to random matrix theory: the minimum rank of a matrix with a prescribed, random, zero-nonzero pattern. |

Discrete Lunch >