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.
Torsten Ueckerdt introduced t
he invariant called local dimension which, instead, uses partial linear ext
ensions and which is bounded above by the Dushnik-Miller dimension. For ins
tance, 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 dim
ension 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 lattic
e is at least $\Theta(n/\log n)$ and make progress toward resolving a versi
on of the removable pair conjecture for local dimension. We also connect th
e computation of local dimension of a poset to the decomposition of the edg
es of a graph into what are called difference graphs.
This is join
t work with Jinha Kim (Seoul National University), Tomás Masarík (Charles U
niversity), Warren Shull (Emory University), Heather C. Smith (Davidson Col
lege), Andrew Uzzell (Holy Cross College), and Zhiyu Wang (University of So
uth Carolina) as a part of the 2017 Graduate Research Workshop in Combinato
rics.
DTSTAMP:20240328T140601Z
DTSTART;TZID=Europe/Budapest:20191115T100000
DTEND;TZID=Europe/Budapest:20191115T120000
SEQUENCE:0
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR