Thesis (PhD)--Stellenbosch University, 2015. / ENGLISH ABSTRACT : In this thesis, a number of combinatorial objects are enumerated. Du and Yin as well as Shin and Zeng (by a different approach) proved an elegant formula for the number of labelled trees with respect to a given in degree sequence, where each edge is oriented from a vertex of lower label towards a vertex of higher label. We refine their result to also take the number of sources (vertices of in degree 0) or sinks (vertices of out degree 0) into account. We find formulas for the mean and variance of the number of sinks or sources in these trees. We also obtain a differential equation and a functional equation satisfied by the generating function for these trees. Analogous results for labelled trees with two marked vertices, related to functional digraphs, are also established. We extend the work to count reachable vertices, sinks and leaf sinks in these trees. Among other results, we obtain a counting formula for the number of labelled trees on n vertices in which exactly k vertices are reachable from a given vertex v and also the average number of vertices that are reachable from a specified vertex in labelled trees of order n. In this dissertation, we also enumerate certain families of set partitions and related tree-like structures. We provide a proof for a formula that counts connected cycle-free families of k set partitions of {1, . . . , n} satisfying a certain coherence condition and then establish a bijection between these families and the set of labelled free k-ary cacti with a given vertex-degree distribution. We then show that the formula also counts coloured Husimi graphs in which there are no blocks of the same colour that are incident to one another. We extend the work to count coloured oriented cacti and coloured cacti. Noncrossing trees and related tree-like structures are also considered in this thesis. Specifically, we establish formulas for locally oriented noncrossing trees with a given number of sources and sinks, and also with given indegree and outdegree sequences. The work is extended to obtain the average number of reachable vertices in these trees. We then generalise the concept of noncrossing trees to find formulas for the number of noncrossing Husimi graphs, cacti and oriented cacti. The study is further extended to find formulas for the number of bicoloured noncrossing Husimi graphs and the number of noncrossing connected cycle-free pairs of set partitions. / AFRIKAANSE OPSOMMING : In hierdie tesis word ’n aantal kombinatoriese objekte geenumereer. Du en Yin asook Shin en Zeng (deur middel van ’n ander benadering) het ’n elegante formule vir die aantal geëtiketteerde bome met betrekking tot ’n gegewe ingangsgraadry, waar elke lyn van die nodus met die kleiner etiket na die nodus met die groter etiket toe georiënteer word. Ons verfyn hul resultaat deur ook die aantal bronne (nodusse met ingangsgraad 0) en putte (nodusse met uitgangsgraad 0) in ag te neem. Ons vind formules vir die gemiddelde en variansie van die aantal putte of bronne in hierdie bome. Ons bepaal verder ’n differensiaalvergelyking en ’n funksionaalvergelyking wat deur die voortbringende funksie van hierdie bome bevredig word. Analoë resultate vir geëtiketteerde bome met twee gemerkte nodusse (wat verwant is aan funksionele digrafieke), is ook gevind. Ons gaan verder voort deur ook bereikbare nodusse, bronne en putte in hierdie bome at te tel. Onder andere verkry ons ’n formule vir die aantal geëtiketteerde bome met n nodusse waarin presies k nodusse vanaf ’n gegewe nodus v bereikbaar is asook die gemiddelde aantal nodusse wat bereikbaar is vanaf ’n gegewe nodus. Ons enumereer in hierdie tesis verder sekere families van versamelingsverdelings en soortgelyke boom-vormige strukture. Ons gee ’n bewys vir ’n formule wat die aantal van samehangende siklus-vrye families van k versamelingsverdelings op {1, . . . , n} wat ’n sekere koherensie-vereiste bevredig, en ons beskryf ’n bijeksie tussen hierdie familie en die versameling van geëtiketteerde vrye k-êre kaktusse met ’n gegewe nodus-graad-verdeling. Ons toon ook dat hierdie formule ook gekleurde Husimi-grafieke tel waar blokke van dieselfde kleur nie insident met mekaar mag wees nie. Ons tel verder ook gekleurde georiënteerde kaktusse en gekleurde kaktusse. Nie-kruisende bome en soortgelyke boom-vormige strukture word in hierdie tesis ook beskou. On bepaal spesifiek formules vir lokaal georiënteerde nie-kruisende bome wat ’n gegewe aantal bronne en putte het asook nie-kruisende bome met gegewe ingangs- en uitgangsgraadrye. Ons gaan voort deur die gemiddelde aantal bereikbare nodusse in hierdie bome te bepaal. Ons veralgemeen dan die konsep van nie-kruisende bome en vind formules vir die aantal nie-kruisende Husimi-grafieke, kaktusse en georiënteerde kaktusse. Laastens vind ons ’n formule vir die aantaal tweegekleurde nie-kruisende Husimi-grafieke en die aantal nie-kruisende samehangende siklus-vrye pare van versamelingsverdelings.

Recommender systems automate the process of recommending products and services to customers based on various types of data including customer demographics, product features, and, most importantly, previous interactions between customers and products (e.g., purchasing, rating, and catalog browsing). Despite significant research progress and growing acceptance in real-world applications, two major challenges remain to be addressed to implement effective e-commerce recommendation applications. The first challenge is concerned with making recommendations based on sparse transaction data. The second challenge is the lack of a unified framework to integrate multiple types of input data and recommendation approaches.This dissertation investigates graph-based algorithms to address these two problems. The proposed approach is centered on consumer-product graphs that represent sales transactions as links connecting consumer and product nodes. In order to address the sparsity problem, I investigate the network spreading activation algorithms and a newly proposed link analysis algorithm motivated by ideas from Web graph analysis techniques. Experimental results with several e-commerce datasets indicated that both classes of algorithms outperform a wide range of existing collaborative filtering algorithms, especially under sparse data. Two graph-based models that enhance the simple consumer-product graph were proposed to provide unified recommendation frameworks. The first model, a two-layer graph model, enhances the consumer-product graph by incorporating the consumer/product attribute information as consumer and product similarity links. The second model is based on probabilistic relational models (PRMs) developed in the relational learning literature. It is demonstrated with e-commerce datasets that the proposed frameworks not only conceptually unify many of the existing recommendation approaches but also allow the exploitation of a wider range of data patterns in an integrated manner, leading to improved recommendation performance.In addition to the recommendation algorithm design research, this dissertation also employs the random graph theory to study the topological characteristics of consumer-product graphs and the fundamental mechanisms that generate the sales transaction data. This research represents the early step towards a meta-level analysis framework for validating the fundamental assumptions made by different recommendation algorithms regarding the consumer-product interaction generation process and thus supporting systematic recommendation model/algorithm selection and evaluation.

Since 2008, more than half of the world population lives in cities. To cope with this rapid urbanization in a sustainable manner, transit systems all around the world are likely to grow. By studying 33 networks in the world, this thesis identifies the properties and effects of metro network designs by using a graph theory approach. After the literature review, a new methodology was introduced to translate networks into graphs; it notably accounts for various transit specificities (e.g., presence of lines). Metro networks were then characterised according to their State, Form, and Structure; where State relates to the development phase of metros; Form investigates the link between metros and the built environment; Structure examines the intrinsic properties of metros, by notably looking at their connectivity. Subsequently, the complexity and robustness of metros were studied; metros were found to possess scale-free and small-world features although showing atypical topologies; robustness emphasizes on the presence of alternative paths. Three network design indicators (coverage, directness and connectivity) were then related to ridership (annual boardings per capita), and positive relations were observed, which suggests that network design plays an important role in their success. Finally, these concepts were applied to the Toronto metro plans announced by the Toronto regional transportation authority, Metrolinx; it was found that the grid-pattern nature of the plans could hinder the success of the metro; seven possible improvements were suggested. Overall, the topology of metro networks can play a key role in their success. The concepts presented here can particularly be useful to transit planners; they should also be used along with conventional planning techniques. New transit projects could benefit greatly from an analysis of their network designs, which in turn may play a relevant role in the global endeavour for sustainability.

Let G be a graph and k be an integer greater than or equal to the chromatic number of G. The k-colouring graph of G is the graph whose vertices are k-colourings of G, with two colourings adjacent if they colour exactly one vertex differently. We explore the Hamiltonicity and connectivity of such graphs, with particular focus on the k-colouring graphs of complete multipartite graphs. We determine the connectivity of the k-colouring graph of the complete graph on n vertices for all n, and show that the k-colouring graph of a complete multipartite graph K is 2-connected whenever k is at least the chromatic number of K plus one. Additionally, we examine a conjecture that every connected k-colouring graph is 2-connected, and give counterexamples for k greater than or equal to 4. As our main result, we show that for all k greater than or equal to 2t, the k-colouring graph of a complete t-partite graph is Hamiltonian. Finally, we characterize the complete multipartite graphs K whose k-colouring graphs are Hamiltonian when k is the chromatic number of K plus one. / Graduate

Vertex-distinguishing edge-colorings (vdec colorings) are a restriction of proper edge-colorings. These special colorings require that the sets of edge colors incident to every vertex be distinct. This is a relatively new field of study. We present a survey of known results concerning vdec colorings. We also define a new matrix which may be used to study vdec colorings, and examine its properties. We find several bounds on the eigenvalues of this matrix, as well as results concerning its determinant, and other properties. We finish by examining related topics and open problems.

Understanding of a global biological network structure by studying its simple local properties through the well-developed field of graph theory is of interest. In particular, in this research an observed biological network was explored through a simulation study. However, one difficulty in such exploration lies on the fitting of graphical models on biological network data. An Exponential Random Graph Model (ERGM) was considered to determine estimations of the several network attributes of complex biological network data. We also compared the estimates of observed network to our random simulated network for both Markov Chain Monte Carlo Maximum Likelihood Estimation (MCMCMLE) and Maximum Pseudo Likelihood Estimation (MPLE) methods under ERGM. The motivation behind this was to determine how different the observed network could be from a randomly simulated network if the physical numbers of attributes were approximately same. Cut-off points of some common attributes of interest for different order of nodes were determined through simulations. We implemented our method to a known regulatory network database of E. coli. / Department of Mathematical Sciences

Analysis of functional connectivity of simultaneously recorded multiple spike trains is one of the major issues in the neuroscience. The progress of the statistical methods to the analysis of functional connectivity of multiple spike trains is relatively slow. In this thesis two statistical techniques are presented to the analysis of functional connectivity of multiple spike trains. The first method is known as the modified correlation grid (MCG). This method is based on the calculation of cross-correlation function of all possible pair-wise spike trains. The second technique is known as the Cox method. This method is based on the modulated renewal process (MRP). The original paper on the application of the Cox method (Borisyuk et al., 1985) to neuroscience data was used to analyse only pairs and triplets of spike trains. This method is further developed in this thesis to support simultaneously recorded of any possible set of multiple spike trains. A probabilistic model is developed to test the Cox method. This probabilistic model is based on the MRP. Due to the common probabilistic basis of the probabilistic model and the Cox method, the probabilistic model is a convenient technique to test the Cox method. A new technique based on a pair-wise analysis of Cox method known as the Cox metric is presented to find the groups of coupled spike trains. Another new technique known as motif analysis is introduced which is useful in identifying interconnections among the spike trains. This technique is based on the triplet-wise analysis of the Cox method. All these methods are applied to several sets of spike trains generated by the Enhanced Leaky and Integrate Fire (ELIF) model. The results suggest that these methods are successful for analysing functional connectivity of simultaneously recorded multiple spike trains. These methods are also applied to an experimental data recorded from cat’s visual cortex. The connection matrix derived from the experimental data by the Cox method is further applied to the graph theoretical methods.

The aim of this thesis is to conduct a general investigation in the field of sparse matrices, to investigate and compare various techniques for handling sparse systems suggested in the literature, to develop some new techniques, and to discuss the feasibility of using sparsity techniques in the solution of overdetermined equations and the eigenvalue problem.

This dissertation is concerned with the existence and the isomorphism of designs. The first part studies the existence of designs. Chapter I shows how to obtain a design from a difference family. Chapters II to IV study the existence of an affine 3-(p^m,4,λ) design where the v-set is the Galois field GF(p^m). Associated to each prime p, this paper constructs a graph. If the graph has a 1-factor, then a difference family and hence an affine design exists. The question arises of how to determine when the graph has a 1-factor. It is not hard to see that the graph is connected and of even order. Tutte's theorem shows that if the graph is 2-connected and regular of degree three, then the graph has a 1-factor. By using the concept of quadratic reciprocity, this paper shows that if p Ξ 53 or 77 (mod 120), the graph is almost regular of degree three, i.e., every vertex has degree three, except two vertices each have degree tow. Adding an extra edge joining the two vertices with degree tow gives a regular graph of degree three. Also, Tutte proved that if A is an edge of the graph satisfying the above conditions, then it must have a 1-factor which contains A. The second part of the dissertation is concerned with determining if two designs are isomorphic. Here the v-set is any group G and translation by any element in G gives a design automorphism. Given a design B and its difference family D, two topological spaces, B and D, are constructed. We give topological conditions which imply that a design isomorphism is a group isomorphism.

In this paper we extend the study of Heffter arrays and the biembedding of graphs on orientable surfaces first discussed by Archdeacon in 2014. We begin with the definitions of Heffter systems, Heffter arrays, and their relationship to orientable biembeddings through current graphs. We then focus on two specific cases. We first prove the existence of embeddings for every K_(6n+1) with every edge on a face of size 3 and a face of size n. We next present partial results for biembedding K_(10n+1) with every edge on a face of size 5 and a face of size n. Finally, we address the more general question of ordering subsets of Z_n take away {0}. We conclude with some open conjectures and further explorations.