Nie jesteś zalogowany | zaloguj się

Wydział Matematyki, Informatyki i Mechaniki Uniwersytetu Warszawskiego

  • Skala szarości
  • Wysoki kontrast
  • Negatyw
  • Podkreślenie linków
  • Reset

Aktualności — Wydarzenia

Teoria Automatów


Dimension of posets of bounded cliquewidth

Prelegent: Michał Pilipczuk

2022-03-16 14:15

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.