Determining the chromatic number of the partition graph P(33) poses a considerable challenge. We can bound it to 4 ≤ χ(P(33)) ≤ 6, with exhaustive search confirming χ(P(33)) = 6. A potential mathematical proof strategy for this equality involves identifying a Z2-invariant S4 with non-trivial homology in the box complex of the partition graph P(33), namely Bedge(︁P(33))︁, and applying the Borsuk-Ulam theorem to compute its Z2-index. This provides a robust topological lower bound for the chromatic number of P(33), termed the Lovász bound. We have verified the absence of such an S4 within certain sections of Bedge(︁P(33))︁. We also validated this approach through a case study on the Petersen graph. This thesis offers a thorough examination of various topological lower bounds for a graph’s chromatic number, complete with proofs and examples. We demonstrate instances where these lower bounds converge to a single value and others where they diverge significantly from a graph’s actual chromatic number. We also classify all vertex pairs, triples, and quadruples of P(33) into unique equivalence classes, facilitating the derivation of all maximal complete bipartite subgraphs. This classification informs the construction of all simplices of Bedge(︁P(33)). Following a detailed and technical exploration, we uncover both the maximal size of the pairwise intersections of its maximal simplices and their underlying structure. Our study proposes an algorithm for building the box complex of the partition graph P(33) using our method of identifying maximal complete bipartite subgraphs. This reduces time complexity to O(n3), marking a substantial enhancement over brute-force techniques. Lastly, we apply discrete Morse theory to construct a simplicial complex homotopy equivalent to the box complex of P(33), using two methods: elementary collapses and the determination of a discrete Morse function on the box complex. This process reduces the dimension of the box complex from 35 to 12, streamlining future calculations of the Z2-index and the Lovász bound.

No description available.

No description available.

No description available.

In recent years there has been a trend towards large-scale logistics for individual members of the public, such as ride-sharing services and drone package delivery. Efficient coordination of pickups and deliveries is essential in order to keep costs and wait times down. In this thesis we present these types of problems in a more general framework, expanding applicability of our discussion to an even wider domain of problems. We present fast new al- gorithms with supporting theoretical and experimental analysis, providing certain guarantees about how close our algorithms compare to a theoretically optimal approach. / Master of Science / In recent years there has been a trend towards large-scale logistics for individual members of the public, such as ride-sharing services and drone package delivery. Efficient coordination of pickups and deliveries is essential in order to keep costs and wait times down. In this thesis we present these types of problems in a more general framework, expanding applicability of our discussion to an even wider domain of problems. We present fast new algorithms with supporting theoretical and experimental analysis, providing certain guarantees about how close our algorithms compare to a theoretically optimal approach.

Let G be a finite graph with vertex set V and edge set E. A graph complex on G is an abstract simplicial complex consisting of subsets of E. In particular, we may interpret such a complex as a family of subgraphs of G. The subject of this thesis is the topology of graph complexes, the emphasis being placed on homology, homotopy type, connectivity degree, Cohen-Macaulayness, and Euler characteristic. We are particularly interested in the case that G is the complete graph on V. Monotone graph properties are complexes on such a graph satisfying the additional condition that they are invariant under permutations of V. Some well-studied monotone graph properties that we discuss in this thesis are complexes of matchings, forests, bipartite graphs, disconnected graphs, and not 2-connected graphs. We present new results about several other monotone graph properties, including complexes of not 3-connected graphs and graphs not coverable by p vertices. Imagining the vertices as the corners of a regular polygon, we obtain another important class consisting of those graph complexes that are invariant under the natural action of the dihedral group on this polygon. The most famous example is the associahedron, whose faces are graphs without crossings inside the polygon. Restricting to matchings, forests, or bipartite graphs, we obtain other interesting complexes of noncrossing graphs. We also examine a certain "dihedral" variant of connectivity. The third class to be examined is the class of digraph complexes. Some well-studied examples are complexes of acyclic digraphs and not strongly connected digraphs. We present new results about a few other digraph complexes, including complexes of graded digraphs and non-spanning digraphs. Many of our proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this thesis provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees, which we successfully apply to a large number of graph and digraph complexes. / QC 20100622

Cette thèse traite du problème de séparation aveugle de sources non-négatives (c'est à dire des grandeurs positives ou nulles). La situation de séparation de mélanges linéaires instantanés de sources non-négatives se rencontre dans de nombreux problèmes de traitement de signal et d'images, comme la décomposition de signaux mesurés par un spectromètre (spectres de masse, spectres Raman, spectres infrarouges), la décomposition d'images (médicales, multi-spectrale ou hyperspectrales) ou encore l'estimation de l'activité d'un radionucléide. Dans ces problèmes, les grandeurs sont intrinsèquement non-négatives et cette propriété doit être préservée lors de leur estimation, car c'est elle qui donne un sens physique aux composantes estimées. La plupart des méthodes existantes de séparation de sources non-négatives requièrent de ``fortes" hypothèses sur les sources (comme l'indépendance mutuelle, la dominance locale ou encore l'additivité totale des sources), qui ne sont pas toujours vérifiées en pratique. Dans ce travail, nous proposons une nouvelle méthode de séparation de sources non-négatives fondée sur la répartition géométrique du nuage des observations. Les coefficients de mélange et les sources sont estimées en cherchant le cône simplicial d'ouverture minimale contenant le nuage des observations. Cette méthode ne nécessite pas l'indépendance mutuelle des sources, ni même leur décorrélation; elle ne requiert pas non plus la dominance locale des sources, ni leur additivité totale. Une seule condition est nécessaire et suffisante: l'orthant positif doit être l'unique cône simplicial d'ouverture minimale contenant le nuage de points des signaux sources. L'algorithme proposé est évalué avec succès dans deux situations de séparation de sources non-négatives de nature très différentes. Dans la première situation, nous effectuons la séparation de spectres de masse mesurés à la sortie d'un chromatographe liquide haute précision, afin d'identifier et quantifier les différents métabolites (petites molécules) présents dans l'urine d'un rat traité au phénobarbital. Dans la deuxième situation, nous estimons les différents compartiments pharmacocinétiques du radio-traceur FluoroDeoxyGlucose marqué au fluor 18 ([18F]-FDG) dans le cerveau d'un patient humain, à partir d'une série d'images 3D TEP de cet organe. Parmi ces pharmacocinétiques, la fonction d'entrée artérielle présente un grand intérêt pour l'évaluation de l'efficacité d'un traitement anti-cancéreux en oncologie. / This thesis addresses the problem of non-negative blind source separation (i.e. positive or zero quantities). The situation of linear instantaneous mixtures of non-negative sources occurs in many problems of signal and image processing, such as decompositions of signals measured by a spectrometer (mass spectra, Raman spectra, infrared spectra), decomposition of images (medical, multi-spectral and hyperspectral) or estimating of the activity of a radionuclide. In these problems, the sources are inherently non-negative and this property should be preserved during their estimation, in order to get physical meaning components. Most of existing non-negative blind source separation methods require ``strong" assumptions on sources (such as mutual independence, local dominance or total additivity), which are not always satisfied in practice. In this work, we propose a new geometrical method for separating non-negative sources. The mixing matrix and the sources are estimated by finding the minimum aperture simplicial cone containing the scatter plot of mixed data. The proposed method does not require the mutual independence of the sources, neither their decorrelation, nor their local dominance, or their total additivity. One condition is necessary and sufficient: the positive orthant must be the unique minimum aperture simplicial cone cone containing the scatter plot of the sources. The proposed algorithm is successfully evaluated in two different problems of non-negative sources separation. In the first situation, we perform the separation of mass spectra measured at the output of a liquid chromatograph to identify and quantify the different metabolites (small molecules) present in the urine of rats treated with phenobarbital . In the second situation, we estimate the different pharmacokinetics compartments of the radiotracer [18F]-FDG in human brain, from a set of 3D PET images of this organ, without blood sampling. Among these pharmacokinetics, arterial input function is of great interest to evaluate the effectiveness of anti-cancer treatment in oncology.

Submitted by Cláudia Bueno (claudiamoura18@gmail.com) on 2016-03-04T16:57:18Z No. of bitstreams: 2 Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-03-07T12:10:47Z (GMT) No. of bitstreams: 2 Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-07T12:10:47Z (GMT). No. of bitstreams: 2 Tese - Leila Roling Scariot da Silva - 2015.pdf: 821704 bytes, checksum: afe6afd0f3cea67708178512b59c2c09 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2015-10-30 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / Given a graph G, a defensive alliance of a set of vertices A⊆V(G) satisfying the condition that for each v ∈ A, |N[v] ∩ A| ≤ |N[v] − A|. The set S is an offensive alliance if the inaquality holds for every v ∈ N[S]−S. A alliance A is called global if is also a dominant set. In this paper, we establish lower bounds for Simplicial Graphs and further give closed formulas and upper bounds to decide the global, defensive, offensive, alliance numbers for lexicographic product of paths, cycles, stars and complete graphs. We establish a relationship to global defensive alliance numbers and complementary prism product to graphs. / A aliança é um conceito introduzido por Hedetniemi, Hedetniemi e Kristiansen em 2004, onde foram classificadas em defensiva, ofensiva ou poderosa. Informalmente, podemos entender uma aliança como uma coleção de entidades tal que a união é mais forte do que o indivíduo. Uma aliança, de qualquer entidade, pode tanto servir para proteção contra ataques, quanto para aumentar a capacidade para atacar outras entidades. Toda aliança é global se for um conjunto dominante. A complexidade computacional e aplicações para a defesa nacional, redes de computadores, distribuição computacional e redes sociais são exemplos que motivam os estudos sobre alianças em grafos. Neste trabalho nós lidamos com alguns limites e fórmulas fechadas de algumas famílias de produto lexicográfico para obter o número mínimo da aliança defensiva global e aliança ofensiva global e apresentamos uma relação entre grafos gerais e sua aliança defensiva global para prisma complementar, bem como obtivemos limites para algumas famílias de grafos como grafos simplicias.

This thesis encompasses research on Artificial Intelligence in support of automating scientific discovery in the fields of biology and medicine. At the core of this research is the ongoing development of a general-purpose artificial intelligence framework emulating various facets of human-level intelligence necessary for building cross-domain knowledge that may lead to new insights and discoveries. To learn and build models in a data-driven manner, we develop a general-purpose learning framework called Syntactic Nonparametric Analysis of Complex Systems (SYNACX), which uses tools from Bayesian nonparametric inference to learn the statistical and syntactic properties of biological phenomena from sequence data. We show that the models learned by SYNACX offer performance comparable to that of standard neural network architectures. For complex biological systems or processes consisting of several heterogeneous components with spatio-temporal interdependencies across multiple scales, learning frameworks like SYNACX can become unwieldy due to the the resultant combinatorial complexity. Thus we also investigate ways to robustly reduce data dimensionality by introducing a new data abstraction. In particular, we extend traditional string and graph grammars in a new modeling formalism which we call Simplicial Grammar. This formalism integrates the topological properties of the simplicial complex with the expressive power of stochastic grammars in a computation abstraction with which we can decompose complex system behavior, into a finite set of modular grammar rules which parsimoniously describe the spatial/temporal structure and dynamics of patterns inferred from sequence data.

Dans cette thèse, nous étudions les triangulations définies par un ensemble de points dans des espaces de topologies différentes. Nous proposons une définition générale de la triangulation de Delaunay, valide pour plusieurs classes d'espaces, ainsi qu'un algorithme de construction. Nous fournissons une implantation pour le cas particulier du tore plat tridimensionnel. Ce travail est motivé à l'origine par le besoin de logiciels calculant des triangulations de Delaunay périodiques, dans de nombreux domaines dont l'astronomie, l'ingénierie des matériaux, le calcul biomédical, la dynamique des fluides, etc. Les triangulations périodiques peuvent être vues comme des triangulations du tore plat. Nous fournissons une définition et nous développons un algorithme incrémentiel efficace pour calculer la triangulation de Delaunay dans le tore plat. L'algorithme est adapté de l'algorithme incrémentiel usuel dans R^d. Au contraire des travaux antérieurs sur les triangulations périodiques, nous évitons de maintenir plusieurs copies périodiques des points, lorsque cela est possible. Le résultat fourni par l'algorithme est toujours une triangulation du tore plat. Nous présentons une implantation de notre algorithme, à présent disponible publiquement comme un module de la bibliothèque d'algorithmes géométriques CGAL. Nous généralisons les résultats à une classe plus générale d'espaces quotients plats, ainsi qu'à des espaces quotients de courbure constante positive. Enfin, nous considérons le cas du tore double, qui est un exemple de la classe beaucoup plus riche des espaces quotients de courbure négative constante.