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

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10360666" target="_blank" >RIV/00216208:11320/17:10360666 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1137/1.9781611974782.150" target="_blank" >http://dx.doi.org/10.1137/1.9781611974782.150</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/1.9781611974782.150" target="_blank" >10.1137/1.9781611974782.150</a>

Result language
angličtina
Original language name
Better upper bounds on the Füredi-Hajnal limits of permutations
Original language description
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 x k matrix with exactly one 1-entry in every row and one 1-entry in every column. The Füredi-Hajnal conjecture, proved by Marcus and Tardos, states that for every permutation matrix P, there is a constant c_P such that for every positive integer n, every n times n binary matrix A with at least c_Pn 1-entries contains P. We show that c_P<=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<=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. 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) (n!)^{d-1-1/(d-1)} and n^{-O(k)} k^Omega(n) (n!)^{d-1-1/(d-1)}, respectively.
Czech name
—
Czech description
—

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
ISBN
978-1-61197-478-2
ISSN
—
e-ISSN
neuvedeno
Number of pages
14
Pages from-to
2280-2293
Publisher name
ACM-SIAM
Place of publication
Neuveden
Event location
Barcelona
Event date
Jan 16, 2017
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—

Similar results(10)