Spectral graph theory widely increases the interests in not only discovering new properties of well known graphs but also proving the well known properties for the new type of graphs. In fact all spectral properties of proverbial graphs are not acknowledged to us and in other hand due to the structure of nature, new classes of graphs are required to explain the phenomena around us and the spectral properties of these graphs can tell us more about the structure of them. These both themes are the body of our work here. We introduce here three models of random graphs and show that the eigenvalue counting function of Laplacians on these graphs has exponential decay bound. Since our methods heavily depend on the first nonzero eigenvalue of Laplacian, we study also this eigenvalue for the graph in both random and nonrandom cases.

Dies ist eine aktualisierte Version von einer gesperrten Publikation: 10.18452/14561. Grund der Sperrung: Persönliche Daten vom Deckblatt entfernt / Inhalt der Dissertation ist die Untersuchung der Evolutionsprozesse zufälliger diskreter Strukturen. Solche Evolutionsprozesse lassen sich üblicherweise wie folgt beschreiben. Anfangs beginnt man mit einer sehr einfachen Struktur (z.B. dem Graphen auf n Ecken, der keine Kanten hat) und einer Menge von "Bausteinen'' (z.B. der Kantenmenge des vollständigen Graphen auf n Ecken). Mit zunehmender Zeit werden zufällig mehr und mehr Bausteine eingefügt. Die grundlegende Frage, mit der sich diese Dissertation beschäftigt, ist die folgende: Wie sieht zu einem gegebenen Zeitpunkt die durch den Prozess erzeugte Struktur mit hoher Wahrscheinlichkeit aus? Obwohl das Hauptthema der Dissertation die Evolution zufälliger diskreter Strukturen ist, lassen sich die erzielten Ergebnisse auch unter den folgenden Gesichtspunkten zusammenfassen: Zufällige Greedy-Algorithmen: Es wird ein zufälliger Greedy-Algorithmus untersucht, der für einen gegebenen Graphen H einen zufälligen H-freien Graphen erzeugt. Extremale Ergebnisse: Es wird die Existenz von Graphen mit hoher Taillenweite und hoher chromatischer Zahl bewiesen, wobei bestehende Schranken verbessert werden. Asymptotische Enumeration: Es werden präzise asymptotische Schranken für die Anzahl dreiecksfreier Graphen mit n Ecken und m Kanten bewiesen. "Probabilistische'' Versionen klassischer Sätze: Es wird eine probabilistische Version des Satzes von Sperner bewiesen. / In this thesis, we study the evolution of random discrete structures. Such evolution processes usually fit into the following general framework. Initially (say at time 0), we start with a very simple structure (e.g. a graph on n vertices with no edges) and a set of "building blocks'' (e.g. the set of edges of the complete graph on n vertices). As time increases, we randomly add more and more elements from our set of building blocks. The basic question which we shall investigate is the following: what are the likely properties of the random structure produced by the process at any given time? Although this thesis is concerned with the evolution of random discrete structures, the results obtained can also be summarized according to the following keywords: Random greedy algorithms: we study the output of a random greedy algorithm which, for a given graph H, produces a random H-free graph. Extremal results: improving on previous bounds, we prove the existence of graphs with high girth and high chromatic number. Asymptotic enumeration: we prove sharp asymptotic bounds on the number of triangle-free graphs with n vertices and m edges for a large range of m. Probabilistic versions of "classical'' theorems: we prove a probabilistic version of Sperner's theorem on finite sets.

Diese Habilitationsschrift richtete auf zwei diskrete Strukturen aus: planare Strukturen und zufällige Graphen-Prozesse. Zunächst werden zufällige planare Strukturen untersucht, mit folgende Gesichtspunkte: - Wieviele planare Strukturen gibt es? - Wie kann effizient eine zufällige planare Struktur gleichverteilt erzeugt werden? - Welche asymptotischen Eigenschaften hat eine zufällige planare Struktur mit hoher Wahrscheinlichkeit? Um diese Fragen zu beantworten, werden die planaren Strukturen in Teile mit höherer Konnektivität zerlegt. Für die asymptotische Enumeration wird zuerst die Zerlegung als das Gleichungssystem der generierenden Funktionen interpretiert. Auf dem Gleichungssystem wird dann Singularitätenanalyse angewendet. Für die exakte Enumeration und zufällige Erzeugung wird die rekursive Methode verwendet. Für die typischen Eigenschaften wird die probabilistische Methode auf asymptotischer Anzahl angewendet. Des Weiteren werden zufällige Graphen-Prozesse untersucht. Zufällige Graphen wurden zuerst von Erdos und Renyi eingeführt und untersucht weitgehend seitdem. Ein zufälliger Graphen-Prozess ist eine Markov-Kette, deren Zustandsraum eine Menge der Graphen mit einer gegebenen Knotenmenge ist. Der Prozess fängt mit isolierten Konten an, und in jedem Ablaufschritt entsteht ein neuer Graph aus dem aktuellen Graphen durch das Hinzufügen einer neuen Kante entsprechend einer vorgeschriebenen Regel. Typische Fragen sind: - Wie ändert sich die Wahrscheinlichkeit, dass ein von einem zufälligen Graphen-Prozess erzeugter Graph zusammenhängend ist? - Wann erfolgt der Phasenübergang? - Wie groß ist die größte Komponente? In dieser Habilitationsschrift werden diese Fragen über zufällige Graphen-Prozesse mit Gradbeschränkungen beantwortet. Dafür werden probabilistische Methoden, insbesondere Differentialgleichungsmethode, Verzweigungsprozesse, Singularitätsanalyse und Fourier-Transformationen, angewendet. / This thesis focuses on two kinds of discrete structures: planar structures, such as planar graphs and subclasses of them, and random graphs, particularly graphs generated by random processes. We study first planar structures from the following aspects. - How many of them are there (exactly or asymptotically)? - How can we efficiently sample a random instance uniformly at random? - What properties does a random planar structure have, with high probability? To answer these questions we decompose the planar structures along the connectivity. For the asymptotic enumeration we interpret the decomposition in terms of generating functions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the recursive method. For typical properties of random planar structures we use the probabilistic method, together with the asymptotic numbers. Next we study random graph processes. Random graphs were first introduced by Erdos and Renyi and studied extensively since. A random graph process is a Markov chain whose stages are graphs on a given vertex set. It starts with an empty graph, and in each step a new graph is obtained from a current graph by adding a new edge according to a prescribed rule. Recently random graph processes with degree restrictions received much attention. In the thesis, we study random graph processes where the minimum degree grows quite quickly with the following questions in mind: - How does the connectedness of a graph generated by a random graph process change as the number of edges increases? - When does the phase transition occur? - How big is the largest component? To investigate the random graph processes we use the probabilistic method, Wormald''s differential equation method, multi-type branching processes, and the singularity analysis.

Spectral graph theory widely increases the interests in not only discovering new properties of well known graphs but also proving the well known properties for the new type of graphs. In fact all spectral properties of proverbial graphs are not acknowledged to us and in other hand due to the structure of nature, new classes of graphs are required to explain the phenomena around us and the spectral properties of these graphs can tell us more about the structure of them. These both themes are the body of our work here. We introduce here three models of random graphs and show that the eigenvalue counting function of Laplacians on these graphs has exponential decay bound. Since our methods heavily depend on the first nonzero eigenvalue of Laplacian, we study also this eigenvalue for the graph in both random and nonrandom cases.