Two vertices are said to be identifed if they are combined to form one vertex whose neighborhood is the union of their neighborhoods. A graph is total domination dot-critical if identifying any pair of adjacent vertices decreases the total domination number. On the other hand, a graph is total domination dot-stable if identifying any pair of adjacent vertices leaves the total domination number unchanged. Identifying any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most two. Among other results, we characterize total domination dot-critical trees with total domination number three and all total domination dot-stable graphs.

A Steiner triple system of order v, denoted STS(v), is said to be tricyclic if it admits an automorphism whose disjoint cyclic decomposition consists of three cycles. In this thesis we give necessary and sufficient conditions for the existence of a tricyclic STS(v) when one of the cycles is of length one. In this case, the STS(v) will contain a subsystem which admits an automorphism consisting of a fixed point and a single cycle. The subsystem is said to be 1-rotational.

Graph Neural Networks and Transformers are very powerful frameworks for learning machine learning tasks. While they were evolved separately in diverse fields, current research has revealed some similarities and links between them. This work focuses on bridging the gap between GNNs and Transformers by offering a uniform framework that highlights their similarities and distinctions. We perform positional encodings and identify key properties that make the positional encodings node embeddings. We found that the properties of expressiveness, efficiency and interpretability were achieved in the process. We saw that it is possible to use positional encodings as node embeddings, which can be used for machine learning tasks such as node classification, graph classification, and link prediction. We discuss some challenges and provide future directions.

A central problem in neuroscience is to understand how memories are formed as a result of the activities of neurons. Valiant’s neuroidal model attempted to address this question by modeling the brain as a random graph and memories as subgraphs within that graph. However the question of memory capacity within that model has not been explored: how many memories can the brain hold? Valiant introduced the concept of interference between memories as the defining factor for capacity; excessive interference signals the model has reached capacity. Since then, exploration of capacity has been limited, but recent investigations have delved into the capacity of the Assembly Calculus, a derivative of Valiant's Neuroidal model. In this paper, we provide rigorous definitions for capacity and interference and present theoretical formulations for the memory capacity within a finite set, where subsets represent memories. We propose that these results can be adapted to suit both the Neuroidal model and Assembly calculus. Furthermore, we substantiate our claims by providing simulations that validate the theoretical findings. Our study aims to contribute essential insights into the understanding of memory capacity in complex cognitive models, offering potential ideas for applications and extensions to contemporary models of cognition.

<p>Denote by $k_t(G)$ the number of cliques of order $t$ in a graph $G$ having $n$ vertices. Let $k_t(n) = \min\{k_t(G)+k_t(\overline{G}) \}$ where $\overline{G}$ denotes the complement of $G$. Let $c_t(n) = {k_t(n)}/{\tbinom{n}{t}}$ and $c_t$ be the limit of $c_t(n)$ for $n$ going to infinity. A 1962 conjecture of Erd\H{o}s stating that $c_t = 2^{1-\tbinom{t}{2}}$ was disproved by Thomason in 1989 for all $t\geq 4$. Tighter counterexamples have been constructed by Jagger, {\v S}{\v t}ov{\' \i}{\v c}ek and Thomason in 1996, by Thomason for $t\leq 6$ in 1997, and by Franek for $t=6$ in 2002. Further tightenings $t=6,7$ and $8$ was recently obtained by Deza, Franek, and Liu.</p> <p>We investigate the computational framework used by Deza, Franek, and Liu. In particular, we present the benefits and limitations of different parallel computer memory architectures and parallel programming models. We propose a functional decomposition approach which is implemented in C++ with POSIX thread (Pthread) libraries for multi-threading. Computational benchmarking on the parallelized framework and a performance analysis including a comparison with the original computational framework are presented.</p> / Master of Science (MSc)

Query processing is a core task in probabilistic databases: Given a query and a database that encodes uncertainty in data by means of probability distributions, the problem is to compute possible query answers together with their respective probabilities of being correct. This thesis advances the state of the art in two aspects of query processing in probabilistic databases: complexity analysis and query evaluation techniques. A dichotomy is established for non-repeating, con- junctive relational algebra queries with negation that separates #P-hard queries from those with PTIME data complexity. A framework for computing proba- bilities of relational algebra queries is presented; the probability computation algorithm is based on decomposition methods and provides exact answers in the case of exhaustive decompositions, or anytime approximate answers with absolute or relative error guarantees in the case of partial decompositions. The framework is extended to queries with aggregation operators. An experimental evaluation of the proposed algorithms’ implementations within the SPROUT query engine complements the theoretical results. The SPROUT² system uses this query engine to compute answers to queries on uncertain, tabular Web data.

Adinkras and arithmetical graphs have divergent origins. In the spirit of Feynman diagrams, adinkras encode representations of supersymmetry algebras as graphs with additional structures. Arithmetical graphs, on the other hand, arise in algebraic geometry, and give an arithmetical structure to a graph. In this thesis, we will interpret adinkras as arithmetical graphs and see what can be learned. Our work consists of three main strands. First, we investigate arithmetical structures on the underlying graph of an adinkra in the specific case where the underlying graph is a hypercube. We classify all such arithmetical structures and compute some of the corresponding volumes and linear ranks. Second, we consider the case of a reduced arithmetical graph structure on the hypercube and explore the wealth of relationships that exist between its linear rank and several notions of genus that appear in the literature on graph theory and adinkras. Third, we study modifications of the definition of an arithmetical graph that incorporate some of the properties of an adinkra, such as the vertex height assignment or the edge dashing. To this end, we introduce the directed arithmetical graph and the dashed arithmetical graph. We then explore properties of these modifications in an attempt to see if our definitions make sense, answering questions such as whether the volume is still an integer and whether there are still only finitely many arithmetical structures on a given graph.

[pt] Os dados adquiridos nos experimentos físicos e nas imagens geométricas ou médicas são tipicamente discretas. Esses dados são interpretados como amostras de uma função desconhecida, porém cujas derivadas servem para caracterizar o dado. Por exemplo, o movimento de um fluido é descrito por um campo de velocidades, uma curva é caracterizada pela evolução da sua curvatura, as imagens médicas são geralmente segmentadas por estimativas de gradiente, entre outros. É possível obter derivadas coerentes a partir de filtragem dos dados. Porém, em dados multi-dimensionais, os filtros usuais privilegiam direções alinhadas com os eixos, o que pode gerar problemas quando essas derivadas são interpretadas geometricamente. Por exemplo, a curvatura estimada dependeria da orientação da curva, perdendo o sentido geométrico da curvatura. O objetivo do presente trabalho é melhorar a invariância geométrica dos filtros de derivadas. / [en] Typical data acquired in physical experiments or in geometrical or medical imaging are discrete. This data is generally interpreted as samples of an unknown function, whose derivatives still serve for the data characterisation. For example, the movement of a fluid is described as a velocity field, a curve is characterised by the evolution of its curvature, images used in medical sciences are usually segmented by estimates of their gradients, among others. It is possible to obtain coherent derivatives by filtering the data. However, with multidimensional data, the usual filters present a bias towards to favor directions aligned with the axis, which may induce problems when the derivatives are interpreted geometrically. For example, the estimated curvature would depend on the orientation of the curve, loosing the geometric meaning of the curvature. The goal of the present work is to improve the geometric invariance of derivative filters.

[pt] Nesse trabalho, mostramos como simular um fluido em duas dimensões em um domínio com fronteiras arbitrárias. Nosso trabalho é baseado no esquema stable fluids desenvolvido por Joe Stam. A implementação é feita na GPU (Graphics Processing Unit), permitindo velocidade de interação com o fluido. Fazemos uso da linguagem Cg (C for Graphics), desenvolvida pela companhia NVidia. Nossas principais contribuições são o tratamento das múltiplas fronteiras, onde aplicamos interpolação bilinear para atingir melhores resultados, armazenamento das condições de fronteira usa apenas um canal de textura, e o uso de confinamento de vorticidade. / [en] In this work we show how to simulate fluids in two dimensions in a domain with arbitrary bondaries. Our work is based on the stable fluid scheme developed by Jo Stam. The implementation is done in GPU (Graphics Processinfg Unit), thus allowing fluid interaction speed. We use the language Cg (C for Graphics) developed by the company Nvídia. Our main contributions are the treatment of domains with multiple boundaries, where we apply bilinear interpolation to obtain better results, the storage of the bondaty conditions in a unique texturre channel, and the use of vorticity confinement.

Orientador: Lourdes de la Rosa Onuchic / Banca: Rosana Giaretta Sguerra Miskulin / Banca: Raquel Normandia Moreira Brumatti / Resumo: Esta pesquisa tem como objetivo trabalhar a Análise Combinatória, fazendo uso da Metodologia de Ensino-Aprendizagem-Avaliação de Matemática através da Resolução de Problemas. Abordamos, em nossa fundamentação teórica, a Análise Combinatória contida na Matemática Discreta, iniciando a pesquisa com uma introdução histórica da Análise Combinatória, seguida por uma análise de livros didáticos e pela busca de trabalhos de outros autores que se referiam ao ensino e à aprendizagem desse conteúdo. Criamos três projetos para trabalhar com a metodologia de ensino adotada por nós, em três cenários diferentes, onde a pesquisadora assumiu três posturas diferentes frente ao problema da pesquisa: como uma professora-pesquisadora, com seus próprios alunos, em sua sala de aula; como uma pesquisadora, ministrando uma oficina de trabalho, em um encontro de Educação Matemática, tendo como participantes, professores, educadores matemáticos e até alunos da Licenciatura em Matemática; e, como uma pesquisadora, em Encontros em Educação Matemática, divulgando sua pesquisa. Através da análise dos dados, obtidos nas aplicações dos três projetos, pudemos mostrar como os participantes desses projetos se envolveram ao fazer uso da metodologia de ensino adotada e relatamos as contribuições que trouxeram para nossa pesquisa. Verificamos que houve envolvimento ativo dos participantes na construção de novos conceitos e conteúdos, através da resolução dos problemas propostos, por meio de um trabalho investigativo, que proporcionou uma aprendizagem com compreensão e significado, com resultados importantes para a prática docente. Esta pesquisa foi desenvolvida seguindo a Metodologia de Pesquisa apresentada por Thomas A. Romberg. / Abstract: This paper has the objective to study the Combinatory Analysis using Methodology of Teaching-Learning-Assessment of Mathematics through Problem Solving. In our theoretical fundamentation we address the Combinatory Analysis contained in the Discrete Mathematics, starting the research with a historical introduction of the Combinatory Analysis followed by a review of textbooks and the search for other author's articles concerning this content's teaching and learning. We have developed three projects to apply the teaching methodology we adopted in three different settings, where the researcher played three distinct roles facing the research's problem: a) as a teacher-researcher, with her own students in her own classroom; b) as a researcher, conducting a workshop in a Mathematical Education conference, with teachers, mathematics educators and graduate students; c) as a researcher, in Mathematics Education Conferences divulgating her research. By analyzing all the data obtained in the application of the three projects we could show how the participants were engaged in using the adopted teaching methodology and we also reported the contributions they have brought to our research. We could verify that there was significant involvement from all the participants in the construction of new concepts and contents by solving the proposed problems in an investigative way, providing a different learning, full of understanding and meaning, with very significant results in terms of teaching practice. This research was developed following the Research Methodology presented by Thomas A. Romberg. / Mestre