Název: Extremální vlastnosti hypergrafů
Překlad názvu: Extremální vlastnosti hypergrafů
Autoři: Mach, Lukáš ; Kráľ, Daniel (vedoucí práce) ; Kaiser, Tomáš (oponent)
Typ dokumentu: Diplomové práce
Rok: 2011
Jazyk: eng
Abstrakt: [eng] [cze]
We give an overview of recent progress in the research of hypergraph jumps -- a problem from extremal combinatorics. The number $\alpha \in [0, 1)$ is a jump for $r$ if for any $\epsilon > 0$ and any integer $m \ge r$ any $r$-graph with $N > N(\epsilon, m)$ vertices and at least $(\alpha + \epsilon) {N \choose r}$ edges contains a subgraph with $m$ vertices and at least $(\alpha + c) {m \choose r}$ edges, where $c := c(\alpha)$ does depend only on $\alpha$. Baber and Talbot \cite{Baber} recently gave first examples of jumps for $r = 3$ in the interval $[2/9, 1)$. Their result uses the framework of flag algebras \cite{Raz07} and involves solving a semidefinite optimization problem. A software implementation of their method is a part of this work. V t\'eto pr\'aci pod\'ame p\v rehled o n\v ekter\'ych ned\'avn\'ych v\'ysledc\' ich o skoc\'ich v hypergrafech v oblasti exterm\'aln\'i kombinatoriky. \v C\'islo $\alpha \in [0, 1)$ je skok pro $r$, pokud pro ka\v zd\'e $\epsilon > 0$ a ka\v zd\'e cel\'e \v c\'islo $m \ge r$ jak\'ykoliv $r$-graf na $N > N(\epsilon, m)$ vrcholech a s alespo\v n $(\alpha + \epsilon) {N \choose r}$ hranami obsahuje podgraf na $m$ vrcholech s alespo\v n $(\alpha + c) {m \choose r}$ hranami, kde $c := c(\alpha)$ z\'avis\' i pouze na $\alpha$. Baber a Talbot \cite{Baber} ned\'avno uk\'azali prvn\'i p\v r\'iklad existence skoku pro $r = 3$ v intervalu $[2/9, 1)$. Jejich v\'ysledek pou\v z\'iv\'a kalkul flag algeber \cite{Raz07}, kter\'y vede k re\v sen\'i probl\'emu semidefinitn\'i optimalizace. Sou\v c\'ast\'i pr\'ace je softwarov\'a implementace jejich metody.
Klíčová slova: extremální kombinatorika; flag algebra; skoky v hypergrafech; extremal combinatorics; flag algebra; hypergraph jumps

Instituce: Fakulty UK (VŠKP) (web)
Informace o dostupnosti dokumentu: Dostupné v digitálním repozitáři UK.
Původní záznam: http://hdl.handle.net/20.500.11956/49611

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-313900


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Univerzita Karlova > Fakulty UK (VŠKP)
Vysokoškolské kvalifikační práce > Diplomové práce