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

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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). 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). (en)
Title	On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture (en)
skos:prefLabel	On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture (en)
skos:notation	RIV/00216208:11320/09:00207379!RIV10-MSM-11320___
http://linked.open...avai/riv/aktivita	Z
http://linked.open...avai/riv/aktivity	Z(MSM0021620838)
http://linked.open...iv/cisloPeriodika	2
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Cibulka, Josef
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	331361
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/09:00207379
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	constants; Füredi-Hajnal; Stanley-Wilf; conjecture (en)
http://linked.open.../riv/klicoveSlovo	Füredi-Hajnal Stanley-Wilf conjecture constants
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[E284F3D1EF6D]
http://linked.open...i/riv/nazevZdroje	Journal of Combinatorial Theory Series A
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...UplatneniVysledku	2009
http://linked.open...v/svazekPeriodika	116
http://linked.open...iv/tvurceVysledku	Cibulka, Josef
http://linked.open...ain/vavai/riv/wos	000261900700003
http://linked.open...n/vavai/riv/zamer	Moderní metody, struktury a systémy informatiky
issn	0097-3165
number of pages	13 (xsd:int)
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture On constants in the Füredi-Hajnal and the Stanley-Wilf conjecture

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software