On 03.05.2018 at 12:20 in S6, there is the following noon lecture:
Local Dimension of Posets: Lower & Upper Bounds and Removable Theorems
(joint work with J. Kim, R.R. Martin, W. Shull, H.C. Smith, A. Uzzell, Z. Wang)
The dimension of a partially-ordered set (poset) is the minimum number of linear extensions sufficient to ensure that for every incomparable elements x and y, there is one of the extensions that yields x < y and one other that yields y < x. Introduced by Dushnik and Miller, the dimension is a well-studied parameter. However, in any given realization of the dimension of a poset, an element might not need to be in many linear extensions. Ueckerdt recently introduced the invariant called local dimension which, instead, uses partial linear extensions and which is bounded from above by the Dushnik-Miller dimension. For instance, the dimension of the standard example of order n is n/2 but the local dimension is only 3.
We show that the maximum local dimension of a poset of order n is O(n / log n), the local dimension of the n-dimensional Boolean lattice is at least Omega(n / log n) and make progress toward resolving a version of the removable pair conjecture for local dimension. We also connect the computation of local dimension of a poset to the decomposition of the edges of a graph into so-called difference graphs.
Webmaster: kamweb.mff.cuni.cz Modified: 25. 02. 2019