No description available.

No description available.

No description available.

No description available.

No description available.

This dissertation has two parts. In the first part, we focus on random inner product kernel matrices. Under various assumptions, many authors have proved that the limiting empirical spectral distribution (ESD) of such matrices A converges to the Marchenko- Pastur distribution. Here, we establish the corresponding rate of convergence. The strategy is as follows. First, we show that for z = u + iv ∈ C, v > 0, the distance between the Stieltjes transform m_A (z) of ESD of matrix A and Machenko-Pastur distribution m(z) is of order O (log n \ nv). Next, we prove the Kolmogorov distance between ESD of matrix A and Marchenko-Pastur distribution is of order O(3\log n\n). It is the less sharp rate for much more general class of matrices. This uses a Berry-Esseen type bound that has been employed for similar purposes for other families of random matrices. In the second part, random geometric graphs on the unit sphere are considered. Observing that adjacency matrices of these graphs can be thought of as random inner product matrices, we are able to use an idea of Cheng-Singer to establish the limiting for the ESD of these adjacency matrices. / Mathematics

Over the last decade, cellular networks have grown rapidly from circuit-switch-based voice-only networks to IP-based data-dominant networks, embracing not only traditional mobile phones, but also smartphones and mobile computers. The ever-increasing demands for reliable and high-speed data services have challenged the capacity and coverage of cellular networks. Research and development on femtocells seeks to provide a solution to fill coverage holes and to increase the network capacity to accommodate more mobile terminals and applications that requires higher bandwidth. Among the challenges associated with introducing femtocells in existing cellular networks, interference management and resource allocation are critical. In this dissertation, we address fundamental aspects of resource allocation for cellular networks with coexisting femtocells and macrocells on the downlink side, addressing questions such as: How many additional resource blocks are required to add femtocells into the current cellular system? What is the best way to reuse resources between femtocells and macrocells? How can we efficiently assign limited resources to network users? In this dissertation, we develop an analytical model of resource allocation based on random graphs. In this model, arbitrarily chosen communication links interfere with each other with a certain probability. Using this model, we establish asymptotic bounds on the minimum number of resource blocks required to make interference-free resource assignments for all the users in the network. We assess these bounds using a simple greedy resource allocation algorithm to demonstrate that the bounds are reasonable in finite networks of plausible size. By applying the bounds, we establish the expected impact of femtocell networks on macrocell resource allocation under a variety of interference scenarios. We proceed to compare two reuse schemes, termed shared reuse and split reuse, using three social welfare functions, denoted utilitarian fitness, egalitarian fitness, and proportionally fair fitness. The optimal resource split points, which separate resource access by femtocells and macrocells, are derived with respect to the above fitness functions. A set of simple greedy resource allocation algorithms are developed to verify our analysis and compare fitness values of the two reuse schemes under various network scenarios. We use the obtained results to assess the efficiency loss associated with split reuse, as an aid to determining whether resource allocators should use the simpler split reuse scheme or attempt to tackle the complexity and overhead associated with shared reuse. Due to the complexity of the proportionally fair fitness function, optimal resource allocation for cellular networks with femtocells and macrocells is difficult to obtain. We develop a genetic algorithm-based centralized resource allocation algorithm to yield suboptimal solutions for such a problem. The results from the genetic algorithm are used to further assess the performance loss of split reuse and provide a baseline suboptimal resource allocation. Two distributed algorithms are then proposed to give a practical solution to the resource allocation problem. One algorithm is designed for a case with no communications between base stations and another is designed to exploit the sharing of information between base stations. The numerical results from these distributed algorithms are then compared against to the ones obtained by the genetic algorithm and the performance is found to be satisfactory, typically falling within 8\% of the optimum social welfare found via the genetic algorithm. The capability of the distributed algorithms in adapting to network changes is also assessed and the results are promising. All of the work described thus far is carried out under a protocol model in which interference between two links is a binary condition. Though this model makes the problem more analytically tractable, it lacks the ability to reflect additive interference as in the SINR model. Thus, in the final part of our work, we apply conflict-free resource allocations from our distributed algorithms to simulated networks and examine the allocations under the SINR model to evaluate feasibility. This evaluation study confirms that the protocol-model-based algorithms, with a small adjustment, offer reasonable performance even under the more realistic SINR model. This work was supported by the National Institute of Justice, Office of Justice Programs, U.S. Department of Justice under Award No. 2005-IJ-CX-K017 and the National Science Foundation under Grant No. 0448131. Any opinions, findings, and conclusions or recommendations expressed in this dissertation are those of the author and do not necessarily reflect the views of the National Institute of Justice or the National Science Foundation. The NSF/TEKES Wireless Research Exchange Program also contributed to this work by funding a summer study. / Ph. D.

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.

Thesis (MSc)--Stellenbosch University, 2011 / ENGLISH ABSTRACT: With billions of current internet users interacting through social networks, the need has arisen to analyze the structure of these networks. Many authors have proposed random graph models for social networks in an attempt to understand and reproduce the dynamics that govern social network development. This thesis proposes a random graph model that generates social networks using a community-based approach, in which users’ affiliations to communities are explicitly modeled and then translated into a social network. Our approach explicitly models the tendency of communities to overlap, and also proposes a method for determining the probability of two users being connected based on their levels of commitment to the communities they both belong to. Previous community-based models do not incorporate community overlap, and assume mutual members of any community are automatically connected. We provide a method for fitting our model to real-world social networks and demonstrate the effectiveness of our approach in reproducing real-world social network characteristics by investigating its fit on two data sets of current online social networks. The results verify that our proposed model is promising: it is the first community-based model that can accurately reproduce a variety of important social network characteristics, namely average separation, clustering, degree distribution, transitivity and network densification, simultaneously. / AFRIKAANSE OPSOMMING: Met biljoene huidige internet-gebruikers wat deesdae met behulp van aanlyn sosiale netwerke kommunikeer, het die analise van hierdie netwerke in die navorsingsgemeenskap toegeneem. Navorsers het al verskeie toevalsgrafiekmodelle vir sosiale netwerke voorgestel in ’n poging om die dinamika van die ontwikkeling van dié netwerke beter te verstaan en te dupliseer. In hierdie tesis word ’n nuwe toevalsgrafiekmodel vir sosiale netwerke voorgestel wat ’n gemeenskapsgebaseerde benadering volg, deurdat gebruikers se verbintenisse aan gemeenskappe eksplisiet gemodelleer word, en dié gemeenskapsmodel dan in ’n sosiale netwerk omskep word. Ons metode modelleer uitdruklik die geneigdheid van gemeenskappe om te oorvleuel, en verskaf ’n metode waardeur die waarskynlikheid van vriendskap tussen twee gebruikers bepaal kan word, op grond van hulle toewyding aan hulle wedersydse gemeenskappe. Vorige modelle inkorporeer nie gemeenskapsoorvleueling nie, en aanvaar ook dat alle lede van dieselfde gemeenskap vriende sal wees. Ons verskaf ’n metode om ons model se parameters te pas op sosiale netwerk datastelle en vertoon die vermoë van ons model om eienskappe van sosiale netwerke te dupliseer. Die resultate van ons model lyk belowend: dit is die eerste gemeenskapsgebaseerde model wat gelyktydig ’n belangrike verskeidenheid van sosiale netwerk eienskappe, naamlik gemiddelde skeidingsafstand, samedromming, graadverdeling, transitiwiteit en netwerksverdigting, akkuraat kan weerspieël.

We study graph parameters arising from different types of colourings of random graphs, defined broadly as an assignment of colours to either the vertices or the edges of a graph. The chromatic number X(G) of a graph is the minimum number of colours required for a vertex colouring where no two adjacent vertices are coloured the same. Determining the chromatic number is one of the classic challenges in random graph theory. In Chapter 3, we give new upper and lower bounds for the chromatic number of the dense random graph G(n,p)) where p ∈ (0,1) is constant. These bounds are the first to match up to an additive term of order o(1) in the denominator, and in particular, they determine the average colour class size in an optimal colouring up to an additive term of order o(1). In Chapter 4, we study a related graph parameter called the equitable chromatic number. This is defined as the minimum number of colours needed for a vertex colouring where no two adjacent vertices are coloured the same and, additionally, all colour classes are as equal in size as possible. We prove one point concentration of the equitable chromatic number of the dense random graph G(n,m) with m = pn(n-1)/2, p < 1-1/e² constant, on a subsequence of the integers. We also show that whp, the dense random graph G(n,p) allows an almost equitable colouring with a near optimal number of colours. We call an edge colouring of a graph G a rainbow colouring if every pair of vertices is joined by a rainbow path, which is a path where no colour is repeated. The least number of colours where this is possible is called the rainbow connection number rc(G). Since its introduction in 2008 as a new way to quantify how well connected a given graph is, the rainbow connection number has attracted the attention of a great number of researchers. For any graph G, rc(G)≥diam(G), where diam(G) denotes the diameter. In Chapter 5, we will see that in the random graph G(n,p), rainbow connection number 2 is essentially equivalent to diameter 2. More specifically, we consider G ~ G(n,p) close to the diameter 2 threshold and show that whp rc(G) = diam(G) ∈ {2,3}. Furthermore, we show that in the random graph process, whp the hitting times of diameter 2 and of rainbow connection number 2 coincide. In Chapter 6, we investigate sharp thresholds for the property rc(G)≤=r where r is a fixed integer. The results of Chapter 6 imply that for r=2, the properties rc(G)≤=2 and diam(G)≤=2 share the same sharp threshold. For r≥3, the situation seems quite different. We propose an alternative threshold and prove that this is an upper bound for the sharp threshold for rc(G)≤=r where r≥3.