Properties of delta-matroids

• Název práce v češtině: Vlastnosti delta-matroidů
• Název v anglickém jazyce: Properties of delta-matroids
• Klíčová slova: delta-matroidy, axiom o výměně, splnitelnost omezení
• Klíčová slova anglicky: delta-matroids, exchange axiom, constraint satisfaction
• Akademický rok vypsání: 2018/2019
• Typ práce: bakalářská práce
• Jazyk práce: angličtina
• Ústav: Katedra algebry (32-KA)
• Vedoucí / školitel: RNDr. Alexandr Kazda, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 07.12.2018
• Datum zadání: 13.12.2018
• Datum potvrzení stud. oddělením: 20.12.2018
• Datum a čas obhajoby: 21.06.2019 08:00
• Datum odevzdání elektronické podoby: 16.05.2019
• Datum odevzdání tištěné podoby: 17.05.2019
• Datum proběhlé obhajoby: 21.06.2019
• Oponenti: Mgr. Michal Rolínek

Zásady pro vypracování

Student/ka si nastuduje a zpracuje součaný stav poznání struktury delta-matroidů a jejich souvislosti s hranovým problémem splnitelnosti omezujících podmínek. V případě zájmu je možné také pokusit se o vylepšení stávajících výsledků (např. charakterizace sudých delta-matroidů, které lze reprezentovat párováním v grafu).

Seznam odborné literatury

André Bouchet. Multimatroids I. coverings by independent sets. SIAM Journal on Discrete Mathematics, 10(4):626–646, 1997.

Tomas Feder. Fanout limitations on constraint systems. Theoretical Computer Science, 255(1-2):281–293, 2001.

Alexandr Kazda, Vladimir Kolmogorov, Michal Rolínek. Even Delta-Matroids and the Complexity of Planar Boolean CSPs, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'17). 2017, 307–326.