Abstract: Die 0/1-Borsuk-Vermutung fragt, ob man jede Menge von 0/1-Vektoren im R^d in höchstens d+1 Mengen von kleinerem Durchmesser aufteilen kann. Man weiß, daß das in sehr hohen Dimensionen nicht geht (insbesondere für d=561, wie Kahn & Kalai, Nilli, Raigorodskii, und Weißbach gezeigt haben), was Gegenbeispiele für die berühmte Borsuk-Vermutung von 1933 liefert.
Wir werden uns hier aber mit der Frage beschäftigen, wie's denn in "niedrigen" Dimensionen aussieht. Dies führt einen ganz natürlich zu Färbungsproblemen für Hamming-Graphen und allgemeinere Borsuk-Graphen, auf die man Schranken und Konstruktionen aus der Kodierungstheorie anwenden kann. Insgesamt ergibt sich, daß es für das 0/1-Borsuk-Problem keine Gegenbeispiele mit d <= 9 gibt. Im Gegensatz dazu ist die allgemeine Borsuk-Vermutung immer noch für d = 4 offen.
Nebenbei werden wir für den Hamming-Graphen H_{9,2} zeigen, daß 13 <= chi(H_{9,2}) <= 4. Dies widerlegt die Vermutung, daß chi(H_{n,2}) = 2^{\lceil\log n\rceil} für alle n >= 2 gelten sollte.
Abstract: Some basic problems of statistical physics like the Ising problem and the dimer problem may be studied using discrete methods in a framework of graph theory. The graphs of crystal structures are finite or infinite lattices in two, three or more dimensions. After a general introduction I plan to speak about the following recent results, partly obtained together with Anna Galluccio and Jan Vondrak:
- An algorithm to compute generating function of perfect matchings and edge-cuts (which is equivalent to the Ising problem partition function) for graphs embedded on an arbitrary fixed orientable surface, and its implementation;
- A new expression for the generating function of perfect matchings of the 3-dimensional cubic lattice
- How the number of groundstates (degeneracy) depends on frustration of p.