Question

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.

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