BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//jEvents 2.0 for Joomla//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Budapest
END:VTIMEZONE
BEGIN:VEVENT
UID:4d1q9jccnqgg5hca69l6t993bl@google.com
CATEGORIES:{lang hu}Kombinatorika szeminárium{/lang}{lang en}Combinatorics seminar{/lang}
SUMMARY:Ryan R. Martin (Iowa State University): On difference graphs and the local dimension of posets
LOCATION:Bolyai Intézet, I. emelet, Riesz terem, Aradi vértanúk tere 1., Szeged
DESCRIPTION;ENCODING=QUOTED-PRINTABLE:Abstract. The dimension of a partially-ordered set (poset) is the minimum n
umber of linear extensions sufficient to ensure that for every incomparable
$x$ and $y$, there is one of the extensions that yields $x < y$. Introduce
d 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 mig
ht not be in many linear extensions.\n\nTorsten Ueckerdt introduced the inv
ariant called local dimension which, instead, uses partial linear extension
s 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$.\n\nIn this talk, we study the local dimension of sh
ow 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 leas
t $\Theta(n/\log n)$ and make progress toward resolving a version of the re
movable pair conjecture for local dimension. We also connect the computatio
n of local dimension of a poset to the decomposition of the edges of a grap
h into what are called difference graphs.\n\nThis 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 Uzze
ll (Holy Cross College), and Zhiyu Wang (University of South Carolina) as a
part of the 2017 Graduate Research Workshop in Combinatorics.
DTSTAMP:20200129T120616Z
DTSTART;TZID=Europe/Budapest:20191115T100000
DTEND;TZID=Europe/Budapest:20191115T120000
SEQUENCE:0
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR