Důkazy s pomocí počítače v extremální kombinatorice
advisor: | Mgr. Jan Volec, Ph.D. |
e-mail: | show e-mail |
type: | bachelor thesis, master thesis |
branch of study: | MINF |
key words: | Kombinatorika, lineární a semidefinitní programování, počítačově asistované důkazy |
description: | Hlavním tématem této práce je použití nedávno objevených metod - např. flag algeber či zlomkové obsazení (occupancy fraction) - jež umožňují použít metody spojité optimalizace pro diskrétní úlohy - na otevřené problémy v extremální kombinatorice. Typický problém z extremální kombinatoriky se snaží (asymptoticky) optimalizovat přes určitou třídu diskretních struktur (např. všech grafů na n vrcholech), daný parametr (např. počet k-prvkových podmnožin vrcholů jež indukují cyklus délky k). Cílem teto práce je zjistit, zda výše zmíněné metody umožnují vyřešení některého z otevřených problémů extremální teorie grafů, hypergrafů nebo permutací. |
last update: | 28.06.2022 10:12:17 |
administrator for this page:
Ľubomíra Dvořáková | last update: 09/12/2011