Cliquewidth and dimension

2024
book section
conference proceedings
dc.abstract.enWe prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension k as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: every such poset with sufficiently large dimension contains the Kelly example of dimension k as a subposet. Using this result, we obtain a full characterization of the minor-closed graph classes C such that posets with cover graphs in C have bounded dimension: they are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension. The proofs rely on Colcombet's deterministic version of Simon's factorization theorem, which is a fundamental tool in formal language and automata theory, and which we believe deserves a wider recognition in structural and algorithmic graph theory.pl
dc.affiliationWydział Matematyki i Informatyki : Instytut Informatyki Analitycznejpl
dc.conferenceThirty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
dc.conference.cityAlexandria, Virginia
dc.conference.countryUSA
dc.conference.datefinish2024-01-10
dc.conference.datestart2024-01-07
dc.conference.seriesACM/SIAM Symposium on Discrete Algorithms
dc.conference.seriesshortcutSODA
dc.conference.seriesweblinkhttps://www.siam.org/conferences-events/?_page=1&keywords=&_limit=15&event_timeframe=upcoming
dc.conference.shortcutSODA 2024
dc.conference.weblinkhttps://www.siam.org/conferences-events/past-event-archive/soda24/
dc.contributor.authorJoret, Gwenaëlpl
dc.contributor.authorMicek, Piotr - 142050 pl
dc.contributor.authorPilipczuk, Michałpl
dc.contributor.authorWalczak, Bartosz - 114113 pl
dc.contributor.editorWoodruff, David P.
dc.date.accessioned2024-01-24T11:25:29Z
dc.date.available2024-01-24T11:25:29Z
dc.date.issued2024pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.conftypeinternationalpl
dc.description.physical1437-1446pl
dc.description.versionostateczna wersja wydawcy
dc.identifier.bookweblinkhttps://search.worldcat.org/title/1418697661
dc.identifier.doi10.1137/1.9781611977912.58pl
dc.identifier.eisbn978-1-61197-791-2pl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/326046
dc.languageengpl
dc.language.containerengpl
dc.pubinfo[Philadelphia] : SIAM Society for Industrial and Applied Mathematicspl
dc.rightsDodaję tylko opis bibliograficzny*
dc.rights.licenceInna otwarta licencja
dc.rights.uri*
dc.share.typeinne
dc.subtypeConferenceProceedingspl
dc.titleCliquewidth and dimensionpl
dc.title.containerProceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)pl
dc.typeBookSectionpl
dspace.entity.typePublication
dc.abstract.enpl
We prove that every poset with bounded cliquewidth and with sufficiently large dimension contains the standard example of dimension k as a subposet. This applies in particular to posets whose cover graphs have bounded treewidth, as the cliquewidth of a poset is bounded in terms of the treewidth of the cover graph. For the latter posets, we prove a stronger statement: every such poset with sufficiently large dimension contains the Kelly example of dimension k as a subposet. Using this result, we obtain a full characterization of the minor-closed graph classes C such that posets with cover graphs in C have bounded dimension: they are exactly the classes excluding the cover graph of some Kelly example. Finally, we consider a variant of poset dimension called Boolean dimension, and we prove that posets with bounded cliquewidth have bounded Boolean dimension. The proofs rely on Colcombet's deterministic version of Simon's factorization theorem, which is a fundamental tool in formal language and automata theory, and which we believe deserves a wider recognition in structural and algorithmic graph theory.
dc.affiliationpl
Wydział Matematyki i Informatyki : Instytut Informatyki Analitycznej
dc.conference
Thirty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
dc.conference.city
Alexandria, Virginia
dc.conference.country
USA
dc.conference.datefinish
2024-01-10
dc.conference.datestart
2024-01-07
dc.conference.series
ACM/SIAM Symposium on Discrete Algorithms
dc.conference.seriesshortcut
SODA
dc.conference.seriesweblink
https://www.siam.org/conferences-events/?_page=1&keywords=&_limit=15&event_timeframe=upcoming
dc.conference.shortcut
SODA 2024
dc.conference.weblink
https://www.siam.org/conferences-events/past-event-archive/soda24/
dc.contributor.authorpl
Joret, Gwenaël
dc.contributor.authorpl
Micek, Piotr - 142050
dc.contributor.authorpl
Pilipczuk, Michał
dc.contributor.authorpl
Walczak, Bartosz - 114113
dc.contributor.editor
Woodruff, David P.
dc.date.accessioned
2024-01-24T11:25:29Z
dc.date.available
2024-01-24T11:25:29Z
dc.date.issuedpl
2024
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.conftypepl
international
dc.description.physicalpl
1437-1446
dc.description.version
ostateczna wersja wydawcy
dc.identifier.bookweblink
https://search.worldcat.org/title/1418697661
dc.identifier.doipl
10.1137/1.9781611977912.58
dc.identifier.eisbnpl
978-1-61197-791-2
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/326046
dc.languagepl
eng
dc.language.containerpl
eng
dc.pubinfopl
[Philadelphia] : SIAM Society for Industrial and Applied Mathematics
dc.rights*
Dodaję tylko opis bibliograficzny
dc.rights.licence
Inna otwarta licencja
dc.rights.uri*
dc.share.type
inne
dc.subtypepl
ConferenceProceedings
dc.titlepl
Cliquewidth and dimension
dc.title.containerpl
Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
dc.typepl
BookSection
dspace.entity.type
Publication
Affiliations

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

Views
13
Views per month
Views per city
Krakow
2

No access

No Thumbnail Available