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...
| Identifer | oai:union.ndltd.org:nusl.cz/oai:invenio.nusl.cz:297719 |
| Date | January 2010 |
| Creators | Fink, Jiří |
| Contributors | Loebl, Martin, Koubek, Václav, Sereni, Jean-Sébastein |
| Source Sets | Czech ETDs |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis |
| Rights | info:eu-repo/semantics/restrictedAccess |
Page generated in 0.002 seconds