You are not logged in | Log in

Dimension of posets of bounded cliquewidth

Speaker(s)
Michał Pilipczuk
Affiliation
MIM UW
Date
March 16, 2022, 2:15 p.m.
Room
room 5050
Seminar
Seminar Automata Theory

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.