Thesis (MSc)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: Socially-based networks are of particular interest amongst the variety of communication networks arising in reality. They are distinguished by having small average path length and high clustering coefficient, and so are examples of small-world networks. This thesis studies both real examples and theoretical models of small-world networks, with particular attention to average path length. Existing models of small-world networks, due to Watts and Strogatz (1998) and Newman and Watts (1999a), impose boundary conditions on a one dimensional lattice, and rewire links locally and probabilistically in the former or probabilistically adding extra links in the latter. These models are investigated and compared with real-world networks. We consider a model in which randomness is provided by the Erdos-Rényi random network models superposed on a deterministic one dimensional structured network. We reason about this model using tools and results from random graph theory. Given a disordered network C(n, p) formed by adding links randomly with probability p to a one dimensional network C(n). We improve the analytical result regarding the average path length by showing that the onset of smallworld behaviour occurs if pn is bounded away from zero. Furthermore, we show that when pn tends to zero, C(n, p) is no longer small-world. We display that the average path length in this case approaches infinity with the network order. We deduce that at least εn (where ε is a constant bigger than zero) random links should be added to a one dimensional lattice to ensure average path length of order log n. / AFRIKAANSE OPSOMMING: Sosiaal-baseerde netwerke is van besondere belang onder die verskeidenheid kommunikasie netwerke. Hulle word onderskei deur ’n klein gemiddelde skeidingsafstand en hoë samedrommingskoëffisiënt, en is voorbeelde van kleinwêreld netwerke. Hierdie verhandeling bestudeer beide werklike voorbeelde en teoretiese modelle van klein-wêreld netwerke, met besondere aandag op die gemiddelde padlengte. Bestaande modelle van klein-wêreld netwerke, te danke aan Watts en Strogatz (1998) en Newman en Watts (1999a), voeg randvoorwaardes by tot eendimensionele roosters, en herbedraad nedwerkskakels gebaseer op lokale kennis in die eerste geval en voeg willekeurig ekstra netwerkskakels in die tweede. Hierdie modelle word ondersoek en vergelyk met werklike-wêreld netwerke. Ons oorweeg ’n prosedure waarin willekeurigheid verskaf word deur die Erdös- Renyi toevalsnetwerk modelle wat op ’n een-dimensionele deterministiese gestruktureerde netwerk geimposeer word. Ons redeneer oor hierdie modelle deur gebruik te maak van gereedskap en resultate toevalsgrafieke teorie. Gegewe ’n wanordelike netwerk wat gevorm word deur skakels willekeurig met waarskynlikheid p tot ‘n een-dimensionele netwerk C(n) toe te voeg, verbeter ons die analitiese resultaat ten opsigte van die gemiddelde padlengte deur te wys dat die aanvang van klein-wêreld gedrag voorkom wanneer pn weg van nul begrens is. Verder toon ons dat, wanneer pn neig na nul, C(n, p) nie meer klein-wêreld is nie. Ons toon dat die gemiddelde padlengte in hierdie geval na oneindigheid streef saam met die netwerk groote. Ons lei af dat ten minste εn (waar εn n konstante groter as nul is) ewekansige skakels bygevoeg moet word by ’n een-dimensionele rooster om ‘n gemiddelde padlengte van orde log n te verseker.

Rhythm is at the heart of all music. It is the variation of the duration of sound over time. A rhythm has two components: one is the striking of an instrument – called the "onset" – and the other is silence. Historically, musical forms and works were preferred and became popular by their rhythmic properties. Therefore, to study rhythm is to study the underpinnings of all of music. In this thesis, we explore basic rhythmic preferences in traditional music and, using this as a point of reference, methods are implemented to generate similar types of rhythms. Finally, a software platform to facilitate such an analysis is developed – it is the first of its kind available to our best knowledge as this research field has only recently emerged.

In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them. A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star. We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)2-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed. We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.

No description available.

The classical Erdos-Ko-Rado (EKR) Theorem states that if we choose a family of subsets, each of size k, from a fixed set of size (n > 2k), then the largest possible pairwise intersecting family has size t = (k-1n-1). We consider the probability that a randomly selected family of size t = tn has the EKR property (pairwise nonempty intersection) as n and k = kn tend to infinity, the latter at a specific rate. As t gets large, the EKR property is less likely to occur, while as t gets smaller, the EKR property is satisfied with high probability. We derive the threshold value for t using Janson's inequality. Using the Stein-Chen method we show that the distribution of X0, defined as the number of disjoint pairs of subsets in our family, can be approximated by a Poisson distribution. We extend our results to yield similar conclusions for Xi, the number of pairs of subsets that overlap in exactly i elements. Finally, we show that the joint distribution X0, X1, ⋯, Xb) can be approximated by a multidimensional Poisson vector with independent components.

Modelos e teorias científicas surgem da necessidade do homem entender melhor o funcionamento do mundo em que vive. Constantemente, novos modelos e técnicas são criados com esse objetivo. Uma dessas teorias recentemente desenvolvida é a da Criticalidade Auto-Organizada. No Capítulo 2 desta tese, apresentamos uma breve introdução a Criticalidade Auto-Organizada. Tendo a criticalidade auto-organizada como pano de fundo, no Capítulo 3, estudamos a dinâmica Bak-Sneppen (e diversas variantes) e a comparamos com alguns algoritmos de otimização. Apresentamos no Capítulo 4, uma revisão histórica e conceitual das redes complexas. Revisamos alguns importantes modelos tais como: Erdös-Rényi, Watts-Strogatz, de configuração e Barabási-Albert. No Capítulo 5, estudamos o modelo Barabási-Albert não-linear. Para este modelo, obtivemos uma expressão analítica para a distribuição de conectividades P(k), válida para amplo espectro do espaço de parâmetros. Propusemos também uma forma analítica para o coeficiente de agrupamento, que foi corroborada por nossas simulações numéricas. Verificamos que a rede Barabási-Albert não-linear pode ser assortativa ou desassortativa e que, somente no caso da rede Barabási-Albert linear, ela é não assortativa. No Capítulo 6, utilizando dados coletados do CD-ROM da revista Placar, construímos uma rede bastante peculiar -- a rede do futebol brasileiro. Primeiramente analisamos a rede bipartida formada por jogadores e clubes. Verificamos que a probabilidade de que um jogador tenha participado de M partidas decai exponencialmente com M, ao passo que a probabilidade de que um jogador tenha marcado G gols segue uma lei de potência. A partir da rede bipartida, construímos a rede unipartida de jogadores, que batizamos de rede de jogadores do futebol brasileiro. Nessa rede, determinamos várias grandezas: o comprimento médio do menor caminho e os coeficientes de agrupamento e de assortatividade. A rede de jogadores de futebol brasileiro nos permitiu analisar a evolução temporal dessas grandezas, uma oportunidade rara em se tratando de redes reais. / Models and scientific theories arise from the necessity of the human being to better understand how the world works. Driven by this purpose new models and techniques have been created. For instance, one of these theories recently developed is the Self-Organized Criticality, which is shortly introduced in the Chapter 2 of this thesis. In the framework of the Self-Organized Criticality theory, we investigate the standard Bak-Sneppen dynamics as well some variants of it and compare them with optimization algorithms (Chapter 3). We present a historical and conceptual review of complex networks in the Chapter 4. Some important models like: Erdös-Rényi, Watts-Strogatz, configuration model and Barabási-Albert are revised. In the Chapter 5, we analyze the nonlinear Barabási-Albert model. For this model, we got an analytical expression for the connectivity distribution P(k), which is valid for a wide range of the space parameters. We also proposed an exact analytical expression for the clustering coefficient which corroborates very well with our numerical simulations. The nonlinear Barabási-Albert network can be assortative or disassortative and only in the particular case of the linear Barabási-Albert model, the network is no assortative. In the Chapter 6, we used collected data from a CD-ROM released by the magazine Placar and constructed a very peculiar network -- the Brazilian soccer network. First, we analyzed the bipartite network formed by players and clubs. We find out that the probability of a footballer has played M matches decays exponentially with M, whereas the probability of a footballer to score G gols follows a power-law. From the bipartite network, we built the unipartite Brazilian soccer players network. For this network, we determined several important quantities: the average shortest path length, the clustering coefficient and the assortative coefficient. We were also able to analise the time evolution of these quantities -- which represents a very rare opportunity in the study of real networks.

Modelos e teorias científicas surgem da necessidade do homem entender melhor o funcionamento do mundo em que vive. Constantemente, novos modelos e técnicas são criados com esse objetivo. Uma dessas teorias recentemente desenvolvida é a da Criticalidade Auto-Organizada. No Capítulo 2 desta tese, apresentamos uma breve introdução a Criticalidade Auto-Organizada. Tendo a criticalidade auto-organizada como pano de fundo, no Capítulo 3, estudamos a dinâmica Bak-Sneppen (e diversas variantes) e a comparamos com alguns algoritmos de otimização. Apresentamos no Capítulo 4, uma revisão histórica e conceitual das redes complexas. Revisamos alguns importantes modelos tais como: Erdös-Rényi, Watts-Strogatz, de configuração e Barabási-Albert. No Capítulo 5, estudamos o modelo Barabási-Albert não-linear. Para este modelo, obtivemos uma expressão analítica para a distribuição de conectividades P(k), válida para amplo espectro do espaço de parâmetros. Propusemos também uma forma analítica para o coeficiente de agrupamento, que foi corroborada por nossas simulações numéricas. Verificamos que a rede Barabási-Albert não-linear pode ser assortativa ou desassortativa e que, somente no caso da rede Barabási-Albert linear, ela é não assortativa. No Capítulo 6, utilizando dados coletados do CD-ROM da revista Placar, construímos uma rede bastante peculiar -- a rede do futebol brasileiro. Primeiramente analisamos a rede bipartida formada por jogadores e clubes. Verificamos que a probabilidade de que um jogador tenha participado de M partidas decai exponencialmente com M, ao passo que a probabilidade de que um jogador tenha marcado G gols segue uma lei de potência. A partir da rede bipartida, construímos a rede unipartida de jogadores, que batizamos de rede de jogadores do futebol brasileiro. Nessa rede, determinamos várias grandezas: o comprimento médio do menor caminho e os coeficientes de agrupamento e de assortatividade. A rede de jogadores de futebol brasileiro nos permitiu analisar a evolução temporal dessas grandezas, uma oportunidade rara em se tratando de redes reais. / Models and scientific theories arise from the necessity of the human being to better understand how the world works. Driven by this purpose new models and techniques have been created. For instance, one of these theories recently developed is the Self-Organized Criticality, which is shortly introduced in the Chapter 2 of this thesis. In the framework of the Self-Organized Criticality theory, we investigate the standard Bak-Sneppen dynamics as well some variants of it and compare them with optimization algorithms (Chapter 3). We present a historical and conceptual review of complex networks in the Chapter 4. Some important models like: Erdös-Rényi, Watts-Strogatz, configuration model and Barabási-Albert are revised. In the Chapter 5, we analyze the nonlinear Barabási-Albert model. For this model, we got an analytical expression for the connectivity distribution P(k), which is valid for a wide range of the space parameters. We also proposed an exact analytical expression for the clustering coefficient which corroborates very well with our numerical simulations. The nonlinear Barabási-Albert network can be assortative or disassortative and only in the particular case of the linear Barabási-Albert model, the network is no assortative. In the Chapter 6, we used collected data from a CD-ROM released by the magazine Placar and constructed a very peculiar network -- the Brazilian soccer network. First, we analyzed the bipartite network formed by players and clubs. We find out that the probability of a footballer has played M matches decays exponentially with M, whereas the probability of a footballer to score G gols follows a power-law. From the bipartite network, we built the unipartite Brazilian soccer players network. For this network, we determined several important quantities: the average shortest path length, the clustering coefficient and the assortative coefficient. We were also able to analise the time evolution of these quantities -- which represents a very rare opportunity in the study of real networks.

With the publication of the famous Erdős-Ko-Rado Theorem in 1961, intersection problems became a popular area of combinatorics. A family of combinatorial objects is t-intersecting if any two of its elements mutually t-intersect, where the latter concept needs to be specified separately in each instance. This thesis is split into two parts; the first is concerned with intersecting injections while the second investigates intersecting posets. We classify maximum 1-intersecting families of injections from {1, ..., k} to {1, ..., n}, a generalisation of the corresponding result on permutations from the early 2000s. Moreover, we obtain classifications in the general t>1 case for different parameter limits: if n is large in terms of k and t, then the so-called fix-families, consisting of all injections which map some fixed set of t points to the same image points, are the only t-intersecting injection families of maximal size. By way of contrast, fixing the differences k-t and n-k while increasing k leads to optimal families which are equivalent to one of the so-called saturation families, consisting of all injections fixing at least r+t of the first 2r+t points, where r=|_ (k-t)/2 _|. Furthermore we demonstrate that, among injection families with t-intersecting and left-compressed fixed point sets, for some value of r the saturation family has maximal size . The concept that two posets intersect if they share a comparison is new. We begin by classifying maximum intersecting families in several isomorphism classes of posets which are linear, or almost linear. Then we study the union of the almost linear classes, and derive a bound for an intersecting family by adapting Katona's elegant cycle method to posets. The thesis ends with an investigation of the intersection structure of poset classes whose elements are close to the antichain. The overarching theme of this thesis is fixing versus saturation: we compare the sizes and structures of intersecting families obtained from these two distinct principles in the context of various classes of combinatorial objects.

No description available.

Conselho Nacional de Desenvolvimento CientÃfico e TecnolÃgico / The coloring problem is among the most studied in the Graph Theory due to its great theoretical and practical importance. Since the problem of coloring the vertices of a graph G either with the smallest amount of colors is NP-hard, various coloring heuristics are examined to obtain a proper colouring with a reasonably small number of colors. Given a graph G, the b heuristic of colouring comes down to decrease the amount of colors in a proper colouring c, so that, if all vertices of a color class fail to see any color in your neighborhood, then we can change the color to any color these vertices nonexistent in your neighborhood. Thus, we obtain a coloring c ′ with a color unless c. Irving and Molove defined the b-coloring of a graph G as a coloring where every color class has a vertex that is adjacent the other color classes. These vertices are called b-vertices. Irving and Molove also defined the b-chromatic number as the largest integer k, such that G admits a b-coloring by k colors. They showed that determine the value of the b-chromatic number of any graph is NP-hard, but polynomial for trees. Irving and Molove also defined the m-degree of a graph, which is the largest integer m(G) such that there are m(G) vertices with degree at least m(G) − 1. Irving and Molove showed that the m-degree is an upper limit to the b-chromatic number and showed that it is m(T) or m(T)−1 to every tree T, where its value is m(T) if, and only if, T has a good set. In this dissertation, we analyze the relationship between the girth, which is the size of the smallest cycle, and the b-chromatic number of a graph G. More specifically, we try to find the smallest integer g ∗ such that if the girth of G is at least g ∗ , then the b-chromatic number equals m(G) or m(G)−1. Show that the value of g ∗ is at most 6 could be an important step in demonstrating the famous conjecture of Erd˝os-Faber-LovÂasz, but the best known upper limit to g ∗ is 9. We characterize the graphs whose girth is at least 6 and not have a good set and show how b-color them optimally. Furthermore, we show how b-color, also optimally, graphs whose girth is at least 7 and not have good set. / O problema de coloraÃÃo està entre os mais estudados dentro da Teoria dos Grafos devido a sua grande importÃncia teorica e prÃtica. Dado que o problema de colorir os vÃrtices de um grafo G qualquer com a menor quantidade de cores à NP-difÃcil, vÃrias heurÃsticas de coloraÃÃo sÃo estudadas a fim de obter uma coloraÃÃo prÃpria com um nÃmero de cores razoavelmente pequeno. Dado um grafo G, a heurÃstica b de coloraÃÃo se resume a diminuir a quantidade de cores utilizadas em uma coloraÃÃo prÃpria c, de modo que, se todos os vÃrtices de uma classe de cor deixam de ver alguma cor em sua vizinhanÃa, entÃo podemos modificar a cor desses vÃrtices para qualquer cor inexistente em sua vizinhanÃa. Dessa forma, obtemos uma coloraÃÃo c′ com uma cor a menos que c. Irving e Molove definiram a b-coloraÃÃo de um grafo G como uma coloraÃÃo onde toda classe de cor possui um vÃrtice que à adjacente as demais classes de cor. Esses vÃrtices sÃo chamados b-vÃrtices. Irving e Molove tambÃm definiram o nÃmero b-cromÃtico como o maior inteiro k tal que G admite uma b-coloraÃÃo por k cores. Eles mostraram que determinar o nÃmero b-cromÃtico de um grafo qualquer à um problema NP-difÃcil, mas polinomial para Ãrvores. Irving e Molove tambÃm definiram o m-grau de um grafo, que à o maior inteiro m(G) tal que existem m(G) vÃrtices com grau pelo menos m(G)−1. Irving e Molove mostraram que o m-grau à um limite superior para nÃmero b-cromÃtico e mostraram que o mesmo à igual a m(T) ou a m(T)−1, para toda Ãrvore T, onde o nÃmero b-cromÃtico à igual a m(T) se, e somente se, T possui um conjunto bom. Nesta dissertaÃÃo, verificamos a relaÃÃo entre a cintura, que à o tamanho do menor ciclo, e o nÃmero b-cromÃtico de um grafo G. Mais especificamente, tentamos encontrar o menor inteiro g∗ tal que, se a cintura de G à pelo menos g∗, entÃo o nÃmero b-cromÃtico à igual a m(G) ou m(G)−1. Mostrar que o valor de g∗ à no mÃximo 6 poderia ser um passo importante para demonstrar a famosa Conjectura de ErdÃs-Faber-Lovasz, mas o melhor limite superior conhecido para g∗ à 9. Caracterizamos os grafos cuja cintura à pelo menos 6 e nÃo possuem um conjunto bom e mostramos como b-colori-los de forma Ãtima. AlÃm disso, mostramos como bicolorir, tambÃm de forma Ãtima, os grafos cuja cintura à pelo menos 7 e nÃo possuem conjunto bom.