2016/08/25 by Pourmoradnasseri, Mozhgan, Theis, Dirk Oliver
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1608.07038
A fooling-set matrix has nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. '96 proved that the rank of such a matrix is at least √ n. It is known that the bound is tight (up to a multiplicative constant). We ask for the "typical" minimum rank of a fooling-set matrix: For a fooling-set zero-nonzero pattern chosen at random, is the minimum rank of a matrix with that zero-nonzero pattern over a field \mathbb F closer to its lower bound √(n) or to its upper bound n? We study random patterns with a given density p, and prove an Ω(n) bound for the cases when: (a) p tends to 0 quickly enough, (b) p tends to 0 slowly, and |\mathbb F|=O(1), (c) p∈(0,1] is a constant. We have to leave open the case when p→ 0 slowly and \mathbb F is a large or infinite field (e.g., \mathbb F=GF(2n), F=ℝ).