On difference graphs and the local dimension of posets

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F20%3A10422322" target="_blank" >RIV/00216208:11320/20:10422322 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=0nO8c8IpPZ" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=0nO8c8IpPZ</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.ejc.2019.103074" target="_blank" >10.1016/j.ejc.2019.103074</a>

Result language
angličtina
Original language name
On difference graphs and the local dimension of posets
Original language description
The dimension of a partially-ordered set (poset), introduced by Dushnik and Miller (1941), has been studied extensively in the literature. Recently, Ueckerdt (2016) proposed a variation called local dimension which makes use of partial linear extensions. While local dimension is bounded above by dimension, they can be arbitrarily far apart as the dimension of the standard example is n while its local dimension is only 3. Hiraguchi (1955) proved that the maximum dimension of a poset of order n is n/2. However, we find a very different result for local dimension, proving a bound of Theta(n/log n). This follows from connections with covering graphs using difference graphs which are bipartite graphs whose vertices in a single class have nested neighborhoods. We also prove that the local dimension of the n-dimensional Boolean lattice is Omega(n/log n) and make progress toward resolving an analogue of the removable pair conjecture for local dimension. (C) 2019 Elsevier Ltd. All rights reserved.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2020
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)