See by year See by month Jump to month

Ryan R. Martin (Iowa State University): On difference graphs and the local dimension of posets

Download as iCal file
Friday, 15. November 2019, 10:00 - 12:00
Abstract. The dimension of a partially-ordered set (poset) is the minimum number of linear extensions sufficient to ensure that for every incomparable $x$ and $y$, there is one of the extensions that yields $x < y$. Introduced by Dushnik and Miller, the dimension is a well-studied parameter. However, in any given realization of the dimension of a poset, a given element might not be in many linear extensions.

Torsten Ueckerdt introduced the invariant called local dimension which, instead, uses partial linear extensions and which is bounded 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$.

In this talk, we study the local dimension of show that the maximum local dimension of a poset of order n is $\Theta(n/\log n)$, the local dimension of the $n$-dimensional Boolean lattice is at least $\Theta(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 what are called difference graphs.

This is joint work with Jinha Kim (Seoul National University), Tomás Masarík (Charles University), Warren Shull (Emory University), Heather C. Smith (Davidson College), Andrew Uzzell (Holy Cross College), and Zhiyu Wang (University of South Carolina) as a part of the 2017 Graduate Research Workshop in Combinatorics.
Location : Bolyai Intézet, I. emelet, Riesz terem, Aradi vértanúk tere 1., Szeged


JEvents v3.1.8 Stable   Copyright © 2006-2013