Probabilistic Methods in Discrete Applied Mathematics

• Thesis title in Czech: Pravděpodobnostní metody v diskrétní aplikované matematice
• Thesis title in English: Probabilistic Methods in Discrete Applied Mathematics
• Key words: Binární lineární kódy, Teorie grafů, Edwards-Anderson Ising model, Gray kódy
• English key words: Binary linear code, Graph theory, Edwards-Anderson Ising model, Gray codes
• Academic year of topic announcement: 2006/2007
• Thesis type: dissertation
• Thesis language: angličtina
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: prof. RNDr. Martin Loebl, CSc.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 01.10.2006
• Date of assignment: 01.10.2006
• Date and time of defence: 22.11.2010 10:00
• Date of electronic submission: 06.10.2010
• Date of submission of printed version: 06.10.2010
• Date of proceeded defence: 22.11.2010
• Opponents: prof. RNDr. Václav Koubek, DrSc.

Preliminary scope of work

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.

Preliminary scope of work in English

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.

Let $f(n)$ be the maximum integer such that for every set of at most $f(n)$ faulty vertices of $Q_n$, there exists a long fault-free cycle. Casta\ {n}eda and Gotchev conjectured that $f(n)=\binom{n}{2}-2$. First, we fount an elegant proof that $f(n) \ge n^2/10+n/2+1$ for $n\ge 15$ which was the first known quadratic lower bound. Later, we proved this conjecture using new technique of potentials which we introduced.