标题： 更优的排列的Füredi-Hajnal极限上界 显示英文标题

标题： Better upper bounds on the Füredi-Hajnal limits of permutations

摘要： 一个二元矩阵是一个元素来自集合$\{0,1\}$的矩阵。 我们说一个二元矩阵$A$包含一个二元矩阵$S$，如果$S$可以通过从$A$中删除一些行、一些列，并将一些$1$条目更改为$0$条目来获得。 如果$A$不包含$S$，我们说$A$避免$S$。 A $k$-排列矩阵 $P$ 是一个二进制 $k \times k$ 矩阵，在每一行恰好有一个 $1$-条目，在每一列恰好有一个 $1$-条目。 Füredi-Hajnal猜想，由Marcus和Tardos证明，指出对于每一个排列矩阵$P$，存在一个常数$c_P$，使得对于每一个$n \in \mathbb{N}$，每一个$n \times n$二进制矩阵$A$，如果其至少有$c_P n$$1$-条目，则包含$P$。 我们证明了随机$k$-排列矩阵$P$的$c_P \le 2^{O(k^{2/3}\log^{7/3}k / (\log\log k)^{1/3})}$几乎必然成立。 我们还证明了对于每个$k$-排列矩阵$P$，$c_P \le 2^{(4+o(1))k}$成立，从而改进了 Fox 对$c_P$的近期上界中的指数常数。 此外，我们改进了关于斯坦利-威尔夫极限$s_P$的$c_P$的上界，使其为$c_P \le O\big(s_P^{2.75} \log s_P\big)$。 我们还考虑了关于避免固定$d$-维$k$-排列矩阵的$d$-维$n$-排列矩阵数量的 Stanley-Wilf 猜想的高维推广，并证明了形式为$(2^k)^{O(n)} \cdot (n!)^{d-1-1/(d-1)}$和$n^{-O(k)} k^{\Omega(n)} \cdot (n!)^{d-1-1/(d-1)}$的几乎匹配的上界和下界。 显示英文摘要

摘要： A binary matrix is a matrix with entries from the set $\{0,1\}$. We say that a binary matrix $A$ contains a binary matrix $S$ if $S$ can be obtained from $A$ by removal of some rows, some columns, and changing some $1$-entries to $0$-entries. If $A$ does not contain $S$, we say that $A$ avoids $S$. A $k$-permutation matrix $P$ is a binary $k \times k$ matrix with exactly one $1$-entry in every row and one $1$-entry in every column. The F\"uredi-Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix $P$, there is a constant $c_P$ such that for every $n \in \mathbb{N}$, every $n \times n$ binary matrix $A$ with at least $c_P n$ $1$-entries contains $P$. We show that $c_P \le 2^{O(k^{2/3}\log^{7/3}k / (\log\log k)^{1/3})}$ asymptotically almost surely for a random $k$-permutation matrix $P$. We also show that $c_P \le 2^{(4+o(1))k}$ for every $k$-permutation matrix $P$, improving the constant in the exponent of a recent upper bound on $c_P$ by Fox. Moreover, we improve the upper bound on $c_P$ in terms of the Stanley-Wilf limit $s_P$ to $c_P \le O\big(s_P^{2.75} \log s_P\big)$. We also consider a higher-dimensional generalization of the Stanley-Wilf conjecture about the number of $d$-dimensional $n$-permutation matrices avoiding a fixed $d$-dimensional $k$-permutation matrix, and prove almost matching upper and lower bounds of the form $(2^k)^{O(n)} \cdot (n!)^{d-1-1/(d-1)}$ and $n^{-O(k)} k^{\Omega(n)} \cdot (n!)^{d-1-1/(d-1)}$, respectively.