Realization and counting problems for planar structures: trees and linkages, polytopes and polyominoes

Abstract

Part I of my thesis is about planar linkages. We consider motions of linkages that avoid crossings of bars. We study problems related to self-touching frameworks, in which multiple edges converge to geometrically overlapping configurations. Chapter 2 is about the unfoldability of trees. We show that every monotone tree is unfoldable. A δ-perturbation of a self-touching configuration is a repositioning of the vertices within disks of radius δ, which is consistent with the combinatorial embedding in R2. In Chapter 3 we prove that every self-touching configuration can be perturbed within δ. The classical Maxwell-Cremona Theorem is a powerful tool that establishes a bijection between the set of classical equilibrium stresses of a planar configuration and the set of three-dimensional polyhedral terrains that project onto it. In Chapter 4 we present a generalization of the Maxwell- Cremona Correspondence for self-touching configurations and generalized polyhedral terrains.

Part II is about the number of spanning trees of a planar graph with applications to the embedding of polytopes on small integer grids using the Maxwell-Cremona lifting. In Chapter 5 we give lower and upper bounds for the maximum number of spanning trees. We present a new method based on transfer matrices for computing the asymptotic number of spanning trees of recursively constructible families of graphs. We discuss several techniques for obtaining upper bounds. Apart from the general case, we study the particular cases when the graph has smallest face cycle 4 and 5, for which the best results are obtained using a probabilistic method. These results are used in Chapter 6 for obtaining improved bounds on the minimum size of the integral grid in which all combinatorial types of 3-polytopes can be embedded.

In Part III we analyze, using numerical methods, the growth in the number of polyominoes on a twisted cylinder as the number of cells increases. These polyominoes are related to classical polyominoes (connected subsets of a square grid) that lie in the plane. We thus obtain improved lower bounds on the growth rate of the number of these polyominoes, which is also known as Klarner's constant.

Teil I dieser Arbeit beschäftigt sich mit planaren Gelenksystemen. Wir betrachten Bewegungen der Gelenksysteme, die Kreuzungen von Stangen vermeiden. Wir untersuchen Probleme im Zusammenhang mit sich selbst berührenden Fachwerken, in welchen mehrfache Kanten zu geometrisch überlappenden Konfigurationen konvergieren. Kapitel 2 handelt von der Entfaltbarkeit von Bäumen. Wir zeigen, dass jeder monotone Baum sich entfalten lässt. Eine δ-Störung einer sich selbst berührenden Konfiguration ist eine Neupositionierung der Eckpunkte innerhalb von Kreisscheiben mit Radius δ, die konsistent ist mit der kombinatorischen Einbettung in der Ebene. In Kapitel 3 zeigen wir, dass es für jede sich selbst berührende Konfiguration eine δ-Störung gibt. Das klassische Maxwell-Cremona Theorem ist ein mächtiges Werkzeug, welches eine Bijektion herstellt zwischen der Menge der klassischen Spannungen im Gleichgewichtszustand einer planaren Konfiguration und der Menge der drei dimensionalen polyhedrischen Terrains, die darauf projiziert werden. In Kapitel 4 stellen wir eine Verallgemeinerung der Maxwell-Cremona- Korrespondenz für sich selbst berührende Konfigurationen und verallgemeinerte polyhedrische Terrains vor.

Teil II handelt von der Anzahl der aufspannenden Bäume eines planaren Graphen mit Anwendungen auf die Einbettung von Polytopen in kleine ganzzahlige Gitter unter Benutzung der Maxwell-Cremona Hebung. In Kapitel 5 geben wir untere und obere Schranken für die maximale Anzahl von aufspannenden Bäumen an. Wir stellen eine neue Methode vor, basierend auf Transfermatrizen zum Berechnen der asymptotischen Anzahl von aufspannenden Bäumen von rekursiv konstruierbaren Familien von Graphen. Wir diskutieren mehrere Techniken, um obere Schranken zu erhalten. Neben dem allgemeinen Fall betrachten wir die Spezialfälle, dass der kleinste Kreis, der ein Gebiet im Graphen berandet, Länge vier oder fünf hat. In diesen Fällen werden die besten Ergebnisse mit einer probabilistischen Methode erzielt. Diese Ergebnisse werden in Kapitel 6 benutzt, um verbesserte Schranken für die kleinste Gröβe eines ganzzahligen Gitters zu erhalten, in dem alle kombinatorischen Typen von 3-Polytopen eingebettet werden können.

In Teil III analysieren wir unter Benutzung von numerischen Methoden das Wachstum in der Anzahl von Polyominos auf einem verdrehten Zylinder für steigende Anzahlen von Zellen. Diese Polyominos sind verwandt mit klassischen Polyominos (zusammenhängende Zellen eines quadratischen Gitters), die in der Ebene liegen. Dadurch erhalten wir verbesserte untere Schranken für die Wachstumsrate der Anzahl dieser Polyominos, die auch als Klarners Konstante bekannt ist.