Simple view

Full metadata view

Authors

Statistics

On an extremal problem for poset dimension

2018
journal article
article
10.1007/s11083-017-9444-1
Journal
Order
20
Author
Guśpiel Grzegorz

Micek Piotr

Polak Adam
Volume
35
Issue
3
Pages
489-493
ISSN
0167-8094
eISSN
1572-9273
Keywords in English

partially ordered sets

poset dimension

extremal combinatorics

permutation matrices

Language
English
Container language
English
Abstract in English

Let be the largest integer such that every poset on n elements has a 2-dimensional subposet on elements. What is the asymptotics of ? It is easy to see that = n 1/2. We improve the best known upper bound and show = . For higher dimensions, we show =, where f is the largest integer such that every poset on n elements has a d-dimensional subposet on f elements.

Affiliation
Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej
cris.lastimport.wos2024-04-09T19:48:14Z
dc.abstract.enLet $f(n)$ be the largest integer such that every poset on n elements has a 2-dimensional subposet on $f(n)$ elements. What is the asymptotics of $f(n)$? It is easy to see that $f(n)$ = n 1/2. We improve the best known upper bound and show $f(n)$ = $O (n 2/3)$. For higher dimensions, we show $fd(n)$=$O(ndd+1)$, where f $d(n)$ is the largest integer such that every poset on n elements has a d-dimensional subposet on f $d(n)$ elements.pl
dc.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorGuśpiel, Grzegorz - 187176 pl
dc.contributor.authorMicek, Piotr - 142050 pl
dc.contributor.authorPolak, Adam - 177165 pl
dc.date.accessioned2018-11-02T14:44:54Z
dc.date.available2018-11-02T14:44:54Z
dc.date.issued2018pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number3pl
dc.description.physical489-493pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume35pl
dc.identifier.doi10.1007/s11083-017-9444-1pl
dc.identifier.eissn1572-9273pl
dc.identifier.issn0167-8094pl
dc.identifier.project2015/18/E/ST6/00299pl
dc.identifier.projectPolish Ministry of Science and Higher Education grant DI2013 000443pl
dc.identifier.projectPolish Ministry of Science and Higher Education program “Diamentowy Grant"pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/59273
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa*
dc.rights.licenceCC-BY
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subject.enpartially ordered setspl
dc.subject.enposet dimensionpl
dc.subject.enextremal combinatoricspl
dc.subject.enpermutation matricespl
dc.subtypeArticlepl
dc.titleOn an extremal problem for poset dimensionpl
dc.title.journalOrderpl
dc.typeJournalArticlepl
dspace.entity.typePublication

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month

Open Access

Thumbnail Image
License
cc-by

Except as otherwise noted, this item is licensed under the Attribution 4.0 International licence

Collections
Research publications
Exact sciences
ROD UJ