矩阵的指数Erdős–Szekeres定理

摘要 1993年，Fishburn和Graham建立了经典Erdős–Szekeres定理的以下定性扩展。如果相对于足够大，则任何实矩阵都包含一个子矩阵，其中每一行和每一列都是单调的。我们证明了这样的最小值至多为，极大地改善了Bucić、Sudakov和Tran之前已知的双指数上界，并与指数尺度上已知的最优下界匹配。特别是，我们证明了以下在不对称设置中的惊人锐利转变。一方面，每个矩阵都包含一个子矩阵，其中每一行都是单调的。另一方面，存在不包含这样的子矩阵的矩阵。