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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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&lt;=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&lt;=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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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&lt;=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&lt;=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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2017

Kód důvěrnosti údajů

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

Název statě ve sborníku

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms

ISBN

978-1-61197-478-2

ISSN

—

e-ISSN

neuvedeno

Počet stran výsledku

14

Strana od-do

2280-2293

Název nakladatele

ACM-SIAM

Místo vydání

Neuveden

Místo konání akce

Barcelona

Datum konání akce

16. 1. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—