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.

---