Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
add comment

1 Answer

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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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