Ergebnis 1 von 6
Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Transactions of the American Mathematical Society, 2020-03, Vol.373 (3), p.2157-2172
2020

Details

Autor(en) / Beteiligte
Titel
Better bounds for poset dimension and boxicity
Ist Teil von
  • Transactions of the American Mathematical Society, 2020-03, Vol.373 (3), p.2157-2172
Erscheinungsjahr
2020
Link zum Volltext
Quelle
American Mathematical Society Journals and Series
Beschreibungen/Notizen
  • The dimension of a poset P is the minimum number of total orders whose intersection is P. We prove that the dimension of every poset whose comparability graph has maximum degree \Delta is at most \Delta \log ^{1+o(1)} \Delta . This result improves on a 30-year old bound of Füredi and Kahn and is within a \log ^{o(1)}\Delta factor of optimal. We prove this result via the notion of boxicity. The boxicity of a graph G is the minimum integer d such that G is the intersection graph of d-dimensional axis-aligned boxes. We prove that every graph with maximum degree \Delta has boxicity at most \Delta \log ^{1+o(1)} \Delta , which is also within a \log ^{o(1)}\Delta factor of optimal. We also show that the maximum boxicity of graphs with Euler genus g is \Theta (\sqrt {g \log g}), which solves an open problem of Esperet and Joret and is tight up to a constant factor.
Sprache
Englisch
Identifikatoren
ISSN: 0002-9947
eISSN: 1088-6850
DOI: 10.1090/tran/7962
Titel-ID: cdi_crossref_primary_10_1090_tran_7962
Format

Weiterführende Literatur

Empfehlungen zum selben Thema automatisch vorgeschlagen von bX