Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I am interested in the following problem in combinatorics $\Cap$ Probability. Let $\lambda \in \mathbb{N}$ be a parameter. Consider a matrix of $2^\lambda$ rows and $2^\lambda$ columns. Each column differs from every other column in at least superpolynomial (in $\lambda$) rows. Does there exist some $t$ ($\in \mathbb{N}$) that is polynomial in $\lambda$ such that the following holds?

Condition: For every column $C$, rows $R_1,...,R_t$, let $Same_{C,R_1,...,R_t}$ denote the set of columns that have the same entries in Rows $R_1,...,R_t$ as the column $C$. Now choose $t$ random rows $R_1,...,R_t$. Can I be assured that, with all but negligible probability over the choice of the rows, there exists $m$ ($\in \mathbb{N}$) that is polynomial in $\lambda$ such that for every column $C$ its corresponding set $Same_{C,R_1,...,R_t}$ contains at most $m$ columns?

(Intuitively, I want to identify a column in this matrix -- upto a precision of polynomially many columns -- by choosing at most polynomially many rows at random.).


share|improve this question
User, I'm trying to format your answer but I'm not certain about a few things. Please take a look at the editing (you need $stuff$ for LaTeX) and fix any problems. –  Mr.Wizard Aug 15 '13 at 11:19
Thanks for the edit, that was of great help as I am new to the site. I made a few other changes on the same lines. –  user9052 Aug 15 '13 at 11:42
You're welcome. Please see editing help for more methods. –  Mr.Wizard Aug 15 '13 at 11:51
This is far more a question of the underlying math than of Mathematica. –  Daniel Lichtblau Aug 19 '13 at 16:21
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.