velikost textu

Probabilistic Methods in Discrete Applied Mathematics

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Probabilistic Methods in Discrete Applied Mathematics
Název v češtině:
Pravděpodobnostní metody v diskrétní aplikované matematice
Typ:
Disertační práce
Autor:
RNDr. Jiří Fink, Ph.D.
Školitel:
prof. RNDr. Martin Loebl, CSc.
Oponenti:
prof. RNDr. Václav Koubek, DrSc.
Jean-Sébastein Sereni
Id práce:
43975
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
22. 11. 2010
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
Binární lineární kódy, Teorie grafů, Edwards-Anderson Ising model, Gray kódy
Klíčová slova v angličtině:
Binary linear code, Graph theory, Edwards-Anderson Ising model, Gray codes
Abstrakt:
Jedním ze základních problémů moderní statistické fyziky je snaha porozumět \mbox{frustraci} a chaosu. Základním modelem je konečně dimenzionální Edwards-Anderson Ising model. V této práci zavádíme zobecnění tohoto modelu. Studujeme množinové systémy uzavřené na symetrické rozdíly. Ukážeme, že významnou otázku, zda groundstate v Ising modelu je jednoznačný, lze studovat v těchto množinových systémech. Krewerasova hypotéza říká, že každé perfektní párování v hyperkrychli $Q_n$ lze rozšířit na Hamiltonovskou kružnici. Tuto hypotézu jsme dokázali. Matching graf $\mg{G}$ grafu $G$ má za vrcholy perfektní párování v $G$ a hranami jsou spojeny ty dvojice perfektních párování, jejichž sjednocení tvoří Hamiltonovskou kružnici v $G$. Dokážeme, že matching graf $\mg{Q_n}$ je bipartitní a souvislý pro $n \ge 4$. Toto dokazuje Krewerasovu hypotézu, že graf $M_n$ je souvislý, kde $M_n$ vznikne z grafu $\mg{Q_n}$ kontrakcí vrcholů $\mg{Q_n}$, které odpovídají izomorfním perfektním párováním. Cesta v $Q_n$ vyhýbající se zadaným $f$ chybným vrcholům se nazývá dlouhá, jestliže její délka je alespoň $2^n - 2f - 2$. Analogicky kružnice je dlouhá, pokud její délka je alespoň $2^n - 2f$. Pokud jsou všechny chybné vrcholy ze stejné bipartitní třídy $Q_n$, pak jsou tyto délky nejlepší možné. Dokážeme, že pro každou množinu nejvýše $2n-4$ chybných vrcholů $Q_n$ a každé dva bezchybné vrcholy $u$ a $v$ splňující jednoduchou nutnou podmínku na okolí $u$ a $v$ existuje dlouhá cesta mezi $u$ a $v$. Počet chyb je nejlepší možný a zlepšuje předchozí známé výsledky. Také uvažujeme podstatně slabší podmínky na okolí $u$ a $v$. Dokážeme, že pro každou množinu nejvýše $(n^2+n-4)/4$ chybných vrcholů $Q_n$ existuje dlouhá cesta mezi libovolnými dvěma bezchybnými vrcholy, které mají nejvýše $3$ chybné sousedy. Označme $f(n)$ maximální číslo takové, že pro každou množinu nejvýše $f(n)$ chyb $Q_n$ existuje dlouhá kružnice. Casta\ {n}eda and Gotchev položili hypotézu, zda $f(n) = \binom{n}{2}-2$. Nejprve jsme našli elegantní důkaz, že \mbox{$f(n) \ge n^2/10+n/2+1$} pro $n \ge 15$, což byl první známý kvadratický dolní odhad. Později jsme tuto hypotézu dokázali pomocí nové techniky potenciálů, kterou jsme zavedli.
Abstract v angličtině:
One of the basic streams of modern statistical physics is an effort to understand the frustration and chaos. The basic model to study these phenomena is the finite dimensional Edwards-Anderson Ising model. We present a generalization of this model. We study set systems which are closed under symmetric differences. We show that the important question whether a groundstate in Ising model is unique can be studied in these set systems. Kreweras' conjecture asserts that any perfect matching of the $n$-dimensional hypercube $Q_n$ can be extended to a Hamiltonian cycle. We prove this conjecture. The {\it matching graph} $\mg{G}$ of a graph $G$ has a vertex set of all perfect matchings of $G$, with two vertices being adjacent whenever the union of the corresponding perfect matchings forms a Hamiltonian cycle. We prove that the matching graph $\mg{Q_n}$ is bipartite and connected for $n \ge 4$. This proves Kreweras' conjecture that the graph $M_n$ is connected, where $M_n$ is obtained from $\mg{Q_n}$ by contracting all vertices of $\mg{Q_n}$ which correspond to isomorphic perfect matchings. A fault-free path in $Q_n$ with $f$ faulty vertices is said to be \emph{long} if it has length at least $2^n-2f-2$. Similarly, a fault-free cycle in $Q_n$ is long if it has length at least $2^n-2f$. If all faulty vertices are from the same bipartite class of $Q_n$, such length is the best possible. We show that for every set of at most $2n-4$ faulty vertices in $Q_n$ and every two fault-free vertices $u$ and $v$ satisfying a simple necessary condition on neighbors of $u$ and $v$, there exists a long fault-free path between $u$ and $v$. This number of faulty vertices is tight and improves the previously known results. We also consider much weaker condition of neighbors of $u$ and $v$. We prove that for every set of at most $(n^2 + n - 4) / 4$ faulty vertices of $Q_n$, there exists a long fault-free path between any two vertices such that each of them has at most $3$ faulty neighbors.
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce RNDr. Jiří Fink, Ph.D. 1.14 MB
Stáhnout Abstrakt v českém jazyce RNDr. Jiří Fink, Ph.D. 43 kB
Stáhnout Abstrakt anglicky RNDr. Jiří Fink, Ph.D. 42 kB
Stáhnout Posudek vedoucího prof. RNDr. Martin Loebl, CSc. 175 kB
Stáhnout Posudek oponenta prof. RNDr. Václav Koubek, DrSc. 25 kB
Stáhnout Posudek oponenta Jean-Sébastein Sereni 1.34 MB
Stáhnout Záznam o průběhu obhajoby 202. Katedra aplikované matema 120 kB