Grafy dla dorosłych albo struktury porządkowe

Prowadzący: Marcin Briański


Ordnung muss sein
Kategorie: informatyka teoretyczna matematyka

Opis

Te warsztaty biorą sobie na cel przybliżenie wam kombinatoryki skończonych struktur z porządkiem zwane dalej posetami (od partially ordered set). W skrócie będziemy rozważać relację na skończonych zbiorach spełniającą naturalne warunki jakie oczekiwalibyśmy od porządku. Zaczniemy od klasycznych wyników opisujących ogólne własności posetów, skupimy się nieco na kracie podzbiorów z relacją inkluzji. Jeżeli nam starczy czasu postaramy się poznać związki posetów i ich wymiaru z planarnością albo czemu poniższy poset jest taki trudny.

https://ars.els-cdn.com/content/image/1-s2.0-S0195669813001273-gr1.jpg

Być może, jeżeli uczestnicy będą zainteresowani, poznamy parę algorytmicznych aspektów związanych z teorią porządków.

Wymagania

W sumie większość pojęć którymi będziemy się posługiwać zostaną wprowadzone w trakcie warsztatów albo w treści zadań kwalifikacyjnych. Z innych rzeczy przydadzą się podstawy teorii grafów (ścieżka, spacer, sąsiedztwo, planarność etc).