Extensions of the linear bound in the Füredi-Hajnal conjecture
Extensions of the linear bound in the Füredi-Hajnal conjecture
复制标题
Füredi-Hajnal 猜想中线性界的扩展
DOI：
10.1016/j.aam.2006.05.002
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Marcus
中科院分区：
文献类型：
--
作者：
Martin Klazar;A. Marcus
本文给出了Marcus和Tardos关于n×n（0，1）-矩阵中1-元个数的线性界的两个推广，避免了固定置换矩阵.我们首先扩展的线性界限超图的有序顶点集，并使用以前的结果Klazar，我们证明了指数界的数量的超图的n个顶点，避免了一个固定的置换。这反过来又解决了Klazar的各种猜想以及Bränden和Mansour的猜想。然后，我们将原来的Füredi-Hajnal问题从普通矩阵推广到d维矩阵，并证明了避免d维置换矩阵的边长为n的d维（0，1）-矩阵的1-元素个数为O（nd−1）。
We present two extensions of the linear bound, due to Marcus and Tardos, on the number of 1-entries in an n×n(0,1)-matrix avoiding a fixed permutation matrix. We first extend the linear bound to hypergraphs with ordered vertex sets and, using previous results of Klazar, we prove an exponential bound on the number of hypergraphs on n vertices which avoid a fixed permutation. This, in turn, solves various conjectures of Klazar as well as a conjecture of Brändén and Mansour. We then extend the original Füredi–Hajnal problem from ordinary matrices to d-dimensional matrices and show that the number of 1-entries in a d-dimensional (0,1)-matrix with side length n which avoids a d-dimensional permutation matrix is O(nd−1).