Nie jesteś zalogowany | Zaloguj się

Dimension of posets of bounded cliquewidth

Prelegent(ci)
Michał Pilipczuk
Afiliacja
MIM UW
Termin
16 marca 2022 14:15
Pokój
p. 5050
Seminarium
Seminarium „Teoria automatów”

Dimension and boolean dimension are two structural measures for posets (partially ordered sets). Roughly speaking, they measure the minimum number of linear orders sufficient for encoding the poset. We will discuss a proof that posets of bounded cliquewidth have bounded boolean dimension and are dim-bounded; the latter means that the dimension is bounded by a function of the size of a largest standard example that can be found in a poset. The main tool in the proof is Simon's factorization and its deterministic variant due to Colcombet. All of this will be an excuse to give a gentle introduction into the (still fledgling) structural theory of posets, so multiple open problems will be stated.