The following combinatorial problem is a missing piece in a larger problem related to the smoothed analysis of algorithms, on which I am currently stuck.

Let $x$ be an $n \times n$ matrix with entries taking integer values in $\{1,2,..,p\}$. What is the smallest $n=n(p)$ that guarantees $x_{i,j}=x_{i,k}=x_{j+1,k}$ for some $i, j, k$ with $1 \le i \le j < k \le n$?

For $p=2$ I have checked that $n=n(2)=5$. For general $p$, I would like either an upper bound on $n(p)$ that is polynomial in $p$, or else an argument that the growth is superpolynomial.

  • $\begingroup$ Compute this for small values, and look in OEIS? $\endgroup$ – Per Alexandersson Nov 25 '12 at 19:47
  • 1
    $\begingroup$ Bah, that nuked my computer... $\endgroup$ – Per Alexandersson Nov 25 '12 at 20:11
  • $\begingroup$ I would expect the growth of n (or the growth of the proof of n) to be superpolynomial in p, as it is a certain kind of Ramsey problem. I bet even a clever implementation would nuke your computer along with a hundred others. Gerhard "But That's Just My Guess" Paseman, 2012.11.25 $\endgroup$ – Gerhard Paseman Nov 25 '12 at 20:27

This is a slightly disguised version of Ramsey's theorem. Writing $uv$, where $u \lt v$, for the edge between $u$ and $v$ in the complete graph on $\{1,\ldots,n\}$, there is a correspondence between your matrices and colourings $c$ of the graph by taking $x_{u+1, v} = c(uv)$. Then your triple $(i, j, k)$ corresponds to the triangle $(i-1)jk$ in the graph. We don't care about the matrix entries below the diagonal by the constraints on $(i, j, k)$, and we can take care of anything odd happening near the diagonal by using a few extra colours (slightly increasing $p$). So $n$ must grow exponentially with $p$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.