2 improved LaTeX formatting

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

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

1

# Simple matrix combinatorics

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 x 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 <= i <= j < k <= 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.