most recent 30 from http://mathoverflow.net 2013-05-20T14:54:39Z http://mathoverflow.net/feeds/user/29391 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/114435/simple-matrix-combinatorics Anonymous 2012-11-25T18:33:27Z 2012-11-25T20:00:31Z

<p>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.</p> <p>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 &lt; k \le n$?</p> <p>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. </p>