Take the 2-minute tour ×

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.

share|improve this question
Compute this for small values, and look in OEIS? –  Per Alexandersson Nov 25 '12 at 19:47
Bah, that nuked my computer... –  Per Alexandersson Nov 25 '12 at 20:11
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 –  Gerhard Paseman Nov 25 '12 at 20:27

1 Answer 1

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$.

share|improve this answer

Your Answer


