4

I'm not an expert and while reading an article on grid coloring these two questions came to my mind:

  1. Given a $n \times n$ matrix randomly filled with values in $\{0,1\}$ ( $P(a_{ij} = 1) = 1/2$), what is the probability that it contains at least one $k \times k \quad (k \leq n)$ submatrix made of all $1$s or all $0$s ("monochromatic") ?

  2. Given a $n \times n$ matrix randomly filled with values in $\{0,1,2,3\}$, what is the probability that it contains at least one $k \times k \quad (k \leq n)$ submatrix composed only with two distinct values (i.e. every element of the submatrix belongs to some (not fixed) $\{v_1,v_2\} \subset \{0,1,2,3\}$) ?

Vor
  • 690
  • somewhat related: http://stackoverflow.com/q/7770945 – vadim123 May 28 '13 at 23:37
  • @vadim123: sorry I meant "monochromatic" submatrix (all 0s or all 1s). And also the set ${v_1,v_2}$ of the second question is not fixed. – Vor May 28 '13 at 23:39
  • That's why I said "somewhat" :-) – vadim123 May 28 '13 at 23:40
  • 1
    Also relevant (if you're interested in asymptotics as $n \rightarrow \infty$ instead of fixed small $n$ and $k$) is work on the Clique number of random graphs -- your problem essentially corresponds to a bipartite version of this, and odds are there's either already a reference out there or some of the same techniques (especially the second moment method, as in the notes at http://www.cs.berkeley.edu/~sinclair/cs271/n7.pdf ) will apply in your case. – Kevin P. Costello May 28 '13 at 23:47
  • You may be interested to know that for sufficiently large $n$ (with respect to $k$) the answer to Question 1 is exactly $1$, not just convergent to $1$. Indeed there is a density Ramsey theorem that any positive proportion of entries being $1$ will force a submatrix consisting entirely of $1$s once $n$ is large enough, so the answer to 2 is also eventually $1$. – Erick Wong May 28 '13 at 23:49
  • @ErickWong: thanks, and for $n \gg k$ it is 1 for question 2, too. Perhaps it is not clear from the question, but if the submatrix is monochromatic then every elements belong to a set ${v_1, v_2}$ where $v_1$ is the monochromatic color (the second probability is greater than the first one). – Vor May 28 '13 at 23:52
  • @Vor Here is a recent reference, hope you will find something helpful. The basic density result is quite elementary as I recall (Cauchy-Schwarz), but this paper should have sharper bounds. http://www.math.ucla.edu/~bsudakov/density-theorems.pdf – Erick Wong May 28 '13 at 23:59

0 Answers0