ProbXiv
Explorersign in
Problem archiveProblem record

Statement

In the same paper [11], Lovett proposed to study the size of all-zero rectangles in low-rank sparse real matrices, stating the following conjecture. Conjecture 5 ([11]). Let M be an n \times n real matrix with rank(M ) = r such that at most \varepsilonn2 entries of M are not zero, where \varepsilon \in (0,\sqrt{ }1/2). Then M contains an all-zero square submatrix of size at least n \cdot exp(−O( \varepsilonr)). \sqrt{ } A construction achieving the bound n \cdot exp(−O( \varepsilonr)) can be constructed with the help of set systems. Given a pair of set systems A, B \subset 2[r] , the intersection matrix of (A, B) is the matrix M , whose rows and columns are indexed by the elements of A and B, respectively, and M (A, B) = |A\capB|. Note that rank(M ) \leq r. Construction. Let F = [r] \sqrt{ } k be the family of all k-element subsets of [r], where k = \varepsilonr, and let M2 be the n \times n intersection matrix of (F , F ), where n = kr . The report passage is retained verbatim as the relevant context for this extracted problem.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.