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
Number
3
Pages
489-493
ISSN
0167-8094
eISSN
1572-9273
Keywords in English

partially ordered sets

poset dimension

extremal combinatorics

permutation matrices

Language
English
Journal 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
Scopus© citations
2
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.source.integratorfalse
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
cris.lastimport.wos
2024-04-09T19:48:14Z
dc.abstract.enpl
Let $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.
dc.affiliationpl
Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej
dc.contributor.authorpl
Guśpiel, Grzegorz - 187176
dc.contributor.authorpl
Micek, Piotr - 142050
dc.contributor.authorpl
Polak, Adam - 177165
dc.date.accessioned
2018-11-02T14:44:54Z
dc.date.available
2018-11-02T14:44:54Z
dc.date.issuedpl
2018
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
3
dc.description.physicalpl
489-493
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
35
dc.identifier.doipl
10.1007/s11083-017-9444-1
dc.identifier.eissnpl
1572-9273
dc.identifier.issnpl
0167-8094
dc.identifier.projectpl
2015/18/E/ST6/00299
dc.identifier.projectpl
Polish Ministry of Science and Higher Education grant DI2013 000443
dc.identifier.projectpl
Polish Ministry of Science and Higher Education program “Diamentowy Grant"
dc.identifier.projectpl
ROD UJ / OP
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/59273
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa
dc.rights.licence
CC-BY
dc.rights.uri*
http://creativecommons.org/licenses/by/4.0/legalcode.pl
dc.share.type
otwarte czasopismo
dc.source.integrator
false
dc.subject.enpl
partially ordered sets
dc.subject.enpl
poset dimension
dc.subject.enpl
extremal combinatorics
dc.subject.enpl
permutation matrices
dc.subtypepl
Article
dc.titlepl
On an extremal problem for poset dimension
dc.title.journalpl
Order
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations
Wydział Matematyki i Informatyki
Guśpiel, Grzegorz
Micek, Piotr
Polak, Adam

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

Views
4
Views per month
Views per city
Ashburn
1
Dubai
1
Hanoi
1
Downloads
guspiel_micek_polak_on_an_extremal_problem_for_poset_dimension_2018.pdf
51
guspiel_micek_polak_on_an_extremal_problem_for_poset_dimension_2018.odt
30

Open Access

Thumbnail Image
License
CC-BY

Except as otherwise noted, this item is licensed under : Udzielam licencji. Uznanie autorstwa 4.0 Międzynarodowa

Collections
Research publications
Exact sciences
ROD UJ