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

Result code in 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>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture
Original language description
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).
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

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

Similar results(10)