Konstruktion und Eigenschaften ganzzahliger Punktmengen

Titelangaben

Kurz, Sascha:
Konstruktion und Eigenschaften ganzzahliger Punktmengen.
Bayreuth , 2005
( Dissertation, 2005 , Universität Bayreuth, Fakultät für Mathematik, Physik und Informatik)

Volltext

Link zum Volltext (externe URL):

Abstract

In vielen Anwendungen in der Chemie, Physik, Biologie und in den Ingenieurswissenschaften treten diskrete Strukturen auf. Beispiele solcher diskreter Strukturen sind molekulare Graphen, fehler-korrigierende Codes, Designs, Matroide, Schaltfunktionen, Assoziationsschemata, endliche Geometrien oder Netzwerke. Die bloße theoretische Existenz einer solchen Struktur, auch mit den sich aus den Anwendungen ergebenen Nebenbedingungen, nutzt dem Anwender meist recht wenig. Die Herausforderung der sich die Mathematik in diesem Zusammenhang stellen muss, ist das schnelle redundanzfreie Erzeugen diskreter Strukturen unter Berücksichtigung von Nebenbedingungen. In dieser Dissertation sollen Punktmengen im Euklidischen Raum E^m mit paarweise ganzzahligen Abständen betrachtet werden. Für die Wahl dieses scheinbar recht speziellen Themas gibt es eine Reihe von Gründen. Zum einen gibt es interessante Anwendungen für dieses Problem, von denen wir ein paar im nächsten Kapitel vorstellen möchten. Die Fragestellung ist weiterhin mathematisch sehr interessant, da sie mehrere mathematische Teildisziplinen berührt. Zu nennen wären hier die Geometrie, Gruppentheorie, Zahlentheorie, Graphentheorie und Kombinatorik. Für die allgemeine Theorie der Konstruktion diskreter Strukturen sind die ganzzahligen Punktmengen von Interesse, da man hier nicht mit einem einzigen Konstruktionsalgorithmus zu befriedigenden Resultaten kommen kann, sondern fast die gesamte Bandbreite der bekannten allgemeinen Konstruktionsalgorithmen ausnutzen muss. Das Vorhandensein von stark einschränkenden Nebenbedingungen ist eine weitere sehr willkommene Eigenschaft. Ziel der Dissertation ist es, die Struktur und die Eigenschaften ganzzahliger Punktmengen genauer als bisher bekannt aufzuklären und Algorithmen zu entwickeln, mit denen man diese diskreten Strukturen effizient konstruieren kann. Trotz des speziellen Problems können Erkenntnisse auf das allgemeine Konstruktionsproblem diskreter Strukturen übertragen werden. Im Rahmen dieser Arbeit wurde eine Reihe neuer Resultate erzielt: - Nach Vorarbeiten in Abschnitt 2.3 können wir in Abschnitt 2.4 den Begriff der Charakteristik eines Dreiecks auf Simplizes beliebiger Dimension verallgemeinern. Den für die Konstruktion ganzzahliger planarer Punktmengen äußerst wichtigen Satz, dass je zwei Dreiecke aus 3 nicht kollinearen Punkten einer ganzzahligen planaren Punktmenge dieselbe Charakteristik besitzen, übertragen wir entsprechend auf beliebige Dimensionen. - In Kapitel 3 präsentieren wir eine Variante der ordnungstreuen Erzeugung, die für die Konstruktion ganzzahliger Punktmengen bzw. allgemeiner für die Konstruktion diskreter Strukturen mit strukturell ähnlichen, starken Nebenbedingungen besonders geeignet ist. - Den Eigenschaften und der Berechnung der Charakteristik von ganzzahligen Punktmengen haben wir uns in Kapitel 4 gewidmet. Die dortigen Betrachtungen führen unter anderem zu theoretischen Einsichten in die Struktur ganzzahliger planarer Punktmengen bzw. zu einer Laufzeitabschätzung für die von uns verwendete Konstruktionsmethode (in unserem Spezialfall). - In Kapitel 5 erweitern wir die Liste der bekannten minimalen Durchmesser ganzzahliger planarer Punktmengen. Bisher waren die minimalen Durchmesser ganzzahliger planarer Punktmengen aus n Punkten nur für n<=9 bekannt. In Abschnitt 5.4 bestimmen wir sie für n<=89. Für eine bestimmte Klasse ganzzahliger planarer Punktmengen haben wir in Abschnitt 5.2 die richtige Größenordnung des minimalen Durchmessers bestimmt. Für ganzzahlige planare Punktmengen ohne 3 kollineare Punkte waren die minimalen Durchmesser bisher ebenfalls nur für n<=9 bekannt. In Abschnitt 5.5 haben wir sie für n<=36 bestimmt. - Die Liste der bekannten minimalen Durchmesser von ganzzahligen räumlichen Punktmengen aus n Punkten konnten wir in Abschnitt 9.1 erweitern. Für n=9 mussten wir einen Wert aus der Literatur korrigieren und für 11<=n<=23 haben wir sie erstmals bestimmt. - In Kapitel 10 bestimmen wir die Anzahl ganzzahliger m-dimensionaler Simplizes mit Durchmesser d für einige Paare von Werten von m und d. - In Abschnitt 11.1 behandeln wir ganzzahlige m-dimensionale Punktmengen aus m+2 Punkten. Bisher waren nur Beispiele in den Dimensionen m=3,8 bekannt. Wir zeigen, dass es für ungerade Dimensionen m>=3 immer mindestens eine solche ganzzahlige Punktmenge gibt. Durch eine vollständige Suche zeigen wir, dass es in den Dimensionen m=2,4,6 und 10 keine derartigen Punktmengen gibt. - Für ganzzahlige m-dimensionale Punktmengen aus m+2 Punkten kann der minimale Durchmesser nur 3 oder 4 betragen. Bisher war nur bekannt, dass die untere Schranke 3 in den Dimensionen m=3,6,8 angenommen wird. In Abschnitt 11.2 zeigen wir, dass sie auch für 9<=m<=24 angenommen wird.

Abstract in weiterer Sprache

An integral point set P is a set of n points in the m-dimensional Euclidean space E^m with pairwise integral distances. The largest distance of a point set P is called its diameter diam(P). From the combinatorial point of view there is a natural interest in the minimum diameter d(m,n) for given parameters m and n. An m-dimensional point set is in semi-general position if no m+1 points lie in an (m-1)-dimensional hyperplane. If additionally no m+2 points are situated on an (m-1)-dimensional hypersphere we say that the point set is in general position. We denote the minimum diameter of an m-dimensional integral point set in semi-general position consisting of n points by $\overline{d}(m,n)$ and of a point set in general position by $\dot{d}(m,n)$. The aim of this thesis is to determine exact values of d(m,n), $\overline{d}(m,n)$, and $\dot{d}(m,n)$ by exhaustive computer enumeration and to give a bit more theoretical insight into the structure of integral point sets. Most of our presented algorithmic techniques can be applied in general for the construction of discrete structures. Due to the Heronian formula $$ A_\Delta=\frac{\sqrt{(a+b+c)(a+b-c)(a-b+c)(-a+b+c)}}{4} $$ for the area of a triangle with side lengths a, b, and c, one can uniquely (for $A_\Delta\neq 0$) write the area as $A_\Delta=q\sqrt{k}$ with a rational number q and a squarefree integer k. This value k is called the characteristic of a triangle. A long known theorem states that in a plane integral point set each non-degenerate triangle has the same characteristic. This is a crucial fact for an efficient generation of plane integral point sets. We generalize the definition of characteristic to m-dimensional simplices and prove the corresponding theorem. Our strategy to construct integral point sets consisting of n+1 points with the aid of a computer is to union two integral point sets consisting of n point with n-1 points in common. In this context we present a variation of Read's orderly generation algorithm and combine it with clique search. So far the minimum diameters d(2,n) of plane integral point sets have been known only for n<=9. We determine these values for n<=89. Here it turned out that plane integral point sets with minimum diameter d(2,n) for 9<=n<=89 consist of n-1 points situated on a line. We conjecture this pattern for n<= 9. For plane integral point sets P with $n^\varrho$ collinear points we prove $$ diam(P)\ge n^{\frac{\varrho}{4\log 2(1+\varepsilon)} \log\log n} $$ for $\varepsilon>0$, $n\ge n_0(\varepsilon)$, and $0<\varrho<1$. The previously known bounds for the minimum diameter are $$ c_1n<d(2,n)<n^{c_2\log\log n} $$ with suitable chosen constants $c_1$ and $c_2$. We present a possible strategy to prove $$n^{c_3\log\log n}<d(2,n)$$ and figure out some of the details. For plane integral point sets in semi-general position we extend the known values of $\overline{d}(2,n)$ from n<=9 to n<=36. In the 3-dimensional space we correct the value for d(3,9) given in the literature and determine d(3,n) in the range 11<=n<=23 and $\overline{d}(3,7)$ for the first time. We also give constructions which give good upper bounds for d(m,n) for arbitrary m and n. If n is small in comparison to m we give a construction showing d(m,n)<=17 for n<=m^2+m$. For d(m,m+1) only 3 or 4 is possible. So far d(m,m+1)=3 was shown only for m=3,6,8. We give examples for 8<=m<=24 and several other values of m. The generation of integral simplices is a first step for the generation of integral point sets. So we have enumerated several numbers $\alpha(m,d)$ of m-dimensional integral simplices with diameter d. The development of a very fast canonicity check for 4x4-matrices made it possible to enumerate the 8.430.487.428.682 integral tetrahedrons with diameter 800 in less than 10 hours. A simple loop from 1 to this number would also last nearly 9 hours on the same computer. For integral simplices with diameter 2 we rediscover a bijection into the set of partitions of m+1. Searching for a generalization we examine integral simplices having at most 2 different distances and corresponding graph classes. For integral point sets having at most 2 distances n<=m+2 was shown. So far examples reaching the upper bound were only known for m=3,8. We give a construction for odd m<=3. We solve an open problem of a bulgarian group by giving an effective algorithm to decide whether an integral point sets can be extended by a point keeping the property of pairwise integral distances or not.