On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F09%3A00207379" target="_blank" >RIV/00216208:11320/09:00207379 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

Popis výsledku v původním jazyce

For a given permutation matrix P, let f_P(n) be the maximum number of 1-entries in an nxn (0,1)-matrix avoiding P and let S_P(n) be the set of all nxn permutation matrices avoiding P. The Füredi-Hajnal conjecture asserts that c(P):=lim(n--}infinity) f_P(n)/n is finite, while the Stanley-Wilf conjecture asserts that s(P):=lim(n--}infinity) n-th root of S_P(n) is finite. In 2004, Marcus and Tardos proved the Füredi-Hajnal conjecture, which together with the reduction introduced by Klazar in 2000 proves the Stanley-Wilf conjecture. We focus on the values of the Stanley-Wilf limit (s(P)) and the Füredi-Hajnal limit (c(P)). We improve the reduction and obtain s(P){=2.88c(P)^2 which decreases the general upper bound on s(P) from s(P){=const^(const^(klog(k)))to s(P){=const^(klog(k)) for any kxk permutation matrix P. In the opposite direction, we show c(P)=O(s(P)^4.5). For a lower bound, we present for each k a kxk permutation matrix satisfying c(P)=Omega(k^2).

Název v anglickém jazyce

On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

Popis výsledku anglicky

For a given permutation matrix P, let f_P(n) be the maximum number of 1-entries in an nxn (0,1)-matrix avoiding P and let S_P(n) be the set of all nxn permutation matrices avoiding P. The Füredi-Hajnal conjecture asserts that c(P):=lim(n--}infinity) f_P(n)/n is finite, while the Stanley-Wilf conjecture asserts that s(P):=lim(n--}infinity) n-th root of S_P(n) is finite. In 2004, Marcus and Tardos proved the Füredi-Hajnal conjecture, which together with the reduction introduced by Klazar in 2000 proves the Stanley-Wilf conjecture. We focus on the values of the Stanley-Wilf limit (s(P)) and the Füredi-Hajnal limit (c(P)). We improve the reduction and obtain s(P){=2.88c(P)^2 which decreases the general upper bound on s(P) from s(P){=const^(const^(klog(k)))to s(P){=const^(klog(k)) for any kxk permutation matrix P. In the opposite direction, we show c(P)=O(s(P)^4.5). For a lower bound, we present for each k a kxk permutation matrix satisfying c(P)=Omega(k^2).

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

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 periodika

Journal of Combinatorial Theory Series A

ISSN

0097-3165

e-ISSN

—

Svazek periodika

116

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

13

Strana od-do

—

Kód UT WoS článku

000261900700003

EID výsledku v databázi Scopus

—