No description available.

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.

Interactions between combinatorics and statistical mechanics have provided many fruitful insights in both fields. A compelling example is Kuperberg’s solution to the alternating sign matrix conjecture, and its following generalisations. In this thesis we investigate two models from statistical mechanics which have received attention in recent years. The first is the fully packed loop model. A conjecture from 2001 by Razumov and Stroganov opened the field for a large ongoing investigation of the O(1) loop model and its connections to a refinement of the fully packed loop model. We apply a combinatorial bijection originally found by de Gier to an older conjecture made by Propp. The second model is the hard particle model. Recent discoveries by Fendley et al. and results by Jonsson suggests that the hard square model with cylindrical boundary conditions possess some beautiful combinatorial properties. We apply both topological and purely combinatorial methods to related independence complexes to try and gain a better understanding of this model.

<p>Interactions between combinatorics and statistical mechanics have provided many fruitful insights in both fields. A compelling example is Kuperberg’s solution to the alternating sign matrix conjecture, and its following generalisations. In this thesis we investigate two models from statistical mechanics which have received attention in recent years.</p><p>The first is the fully packed loop model. A conjecture from 2001 by Razumov and Stroganov opened the field for a large ongoing investigation of the O(1) loop model and its connections to a refinement of the fully packed loop model. We apply a combinatorial bijection originally found by de Gier to an older conjecture made by Propp.</p><p>The second model is the hard particle model. Recent discoveries by Fendley et al. and results by Jonsson suggests that the hard square model with cylindrical boundary conditions possess some beautiful combinatorial properties. We apply both topological and purely combinatorial methods to related independence complexes to try and gain a better understanding of this model.</p>

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-07-25T17:05:28Z No. of bitstreams: 1 DENILSON DA SILVA PEREIRA - DISSERTAÇÃO PPGMAT 2010..pdf: 630527 bytes, checksum: 8a6ec5b5fb5e2a462945183d2180a573 (MD5) / Made available in DSpace on 2018-07-25T17:05:28Z (GMT). No. of bitstreams: 1 DENILSON DA SILVA PEREIRA - DISSERTAÇÃO PPGMAT 2010..pdf: 630527 bytes, checksum: 8a6ec5b5fb5e2a462945183d2180a573 (MD5) Previous issue date: 2010-12 / Neste trabalho estudamos a existência e multiplicidade de soluções para uma certa classe de problemas elípticos. Utilizaremos métodos variacionais juntamente com a teoria de Morse em dimensão infinita. / In this work, we study the existence and multiplicity of solution for a large class of Elliptic problems. The main tools used are variational methods together with the infinite dimensional Morse Theory.

Orientador: Ketty Abaroa de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-16T15:34:50Z (GMT). No. of bitstreams: 1 Lima_DahisyValadaodeSouza_M.pdf: 1595993 bytes, checksum: 49a95ad790c477c7d049695a123d9acd (MD5) Previous issue date: 2010 / Resumo: Dada uma variedade suave e fechada M, o complexo de Morse-Witten associado a uma função de Morse f : M ? R e a uma métrica Riemanniana g em M consiste de grupos de cadeia gerados pelos pontos críticos de f e um operador bordo que conta linhas de fluxos isoladas do fluxo gradiente negativo. A homologia do complexo de Morse-Witten é isomorfa à homologia singular de M. Dado um conjunto invariante isolado S, uma matriz de conexão para uma decomposição de Morse de S é uma matriz de homomorfismos entre os índices homológicos de Conley dos conjuntos de Morse. A matriz de conexão é capaz de prover informações dinâmicas sobre um fluxo. De fato, esta matriz pode detectar a existência de órbitas conectantes entre os conjuntos de Morse de S. O complexo de Morse-Witten está relacionado à teoria de matrizes de conexão. Mais precisamente, o operador bordo do complexo de Morse-Witten é um caso especial de matriz de conexão / Abstract: Given a smooth closed manifold M, the Morse-Witten complex associated to a Morse function f : M ? R and a Riemannian metric g on M consists of chain groups generated by the critical points of f and a boundary operator counting isolated flow lines of the negative gradient flow. The homology of the Morse-Witten complex is isomorphic to the singular homology of M. Give a isolated invariant set S, a connection matrix for a Morse decomposition of S is a matrix of homomorphism between the Conley homology indices of Morse sets. The connection matrix is capable of providing dynamical information of a flow. In fact, this matrix can detect the existence of connecting orbits among Morse sets of S: The Morse-Witten complex is related to connection matrices theory. More precisely, the boundary operator of the Morse-Witten complex is a special case of connection matrix / Mestrado / Matematica / Mestre em Matemática

Orientadores: Djairo Guedes de Figueiredo, Francisco Odair Vieira de Paiva / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-13T06:21:00Z (GMT). No. of bitstreams: 1 Silva_EdcarlosDomingosda_D.pdf: 993704 bytes, checksum: d68d4e58a916f7d2428f76207a8cb4da (MD5) Previous issue date: 2009 / Resumo: Nesta tese lidamos com três classes de sistemas gradientes ressonantes. A primeira classe é um sistema com ressonância do tipo Landesman-Lazer. A segunda classe é um sistema fortemente ressonante enquanto a terceira classe é um sistema com ressonância no infinito e na origem. Analisamos as questões de existência e multiplicidade de soluções em cada uma das classes mencionadas. Para obtermos os nossos principais resultados aplicamos alguns métodos variacionais, tais como, teoremas Min-Max e minimização. Além disso, usamos a Teoria de Morse para distinguirmos soluções dados por métodos variacionais distintos. / Abstract: In this thesis we deal with three classes of gradient elliptic systems with resonance. The first class is a resonant system of Landesman-Lazer type. The second class is a system of strong resonance type while the third class is a system with resonance at infinity and at origin. We are concerned about the questions of existence and multiplicity of solutions in each of the classes mentioned. To obtain our main results we apply variational methods, such as, Min-max theorems and minimization. Moreover, we use Morse Theory to distinguish the solutions given by different variational methods. / Doutorado / Doutor em Matemática

Orientador: Ketty Abaroa de Rezende / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-10T21:02:39Z (GMT). No. of bitstreams: 1 Silveira_MarianaRodriguesda_D.pdf: 1531895 bytes, checksum: 3c73a8eb791483b1f0216d6f2627969b (MD5) Previous issue date: 2008 / Resumo: Neste trabalho, apresentamos um algoritmo para um complexo de cadeias C e sua diferencial dada por uma matriz de conexão _ que determina uma seqüência espectral associada (Er, dr). Mais especificamente, um sistema gerador de Er em termos da base original de C é obtido bem como a identificação de todas as diferenciais dr p : Er p ! Er p-r. Explorando a implicação dinâmica da diferencial não nula, mostramos a existência de um caminho unindo a singularidade que gera E0 p e a singularidade que gera E0 p-r no caso em que a conexão direta pelo fluxo não existe. Este caminho é composto pela justaposição de órbitas do fluxo e do fluxo reverso e prova ser importante em algumas aplicações / Abstract: In this work, we present an algorithm for a chain complex C and its di_erential given by a connection matrix _ which determines an associated spectral sequence (Er, dr). More specifically, a system spanning Er in terms of the original basis of C is obtained as well as the identi_cation of all di_erentials dr p : Er p ! Er p-r. In exploring the dynamical implication of a nonzero di_erential, we prove the existence of a path joining the singularities generating E0 p and E0 p-r in the case that a direct connection by a _ow line does not exist. This path is made up of juxtaposed orbits of the _ow and of the reverse _ow and which proves to be importantin some applications / Doutorado / Geometria e Topologia/Sistemas Dinamicos / Doutor em Matemática

Orientador: Hélio Pedrini / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-24T00:14:20Z (GMT). No. of bitstreams: 1 Silva_RicardoDutrada_D.pdf: 13549105 bytes, checksum: 3d49e5116a70a72601ba4cc3b3c85762 (MD5) Previous issue date: 2013 / Resumo: A Teoria de Morse é importante para o estudo da topologia em funções escalares como elevação de terrenos e dados provenientes de simulações físicas, a qual relaciona a topologia de uma função com seus pontos críticos. A teoria contínua foi adaptada para dados discretos através de construções como os complexos de Morse-Smale e o complexo discreto de Morse. Complexos de Morse têm sido aplicados em processamento de imagens, no entanto, ainda existem desafios envolvendo algoritmos e considerações práticas para a computação e modelagem dos complexos para imagens. Complexos de Morse podem ser usados como um meio de definir a conexão entre pontos de interesse em imagens. Normalmente, pontos de interesse são considerados como elementos independentes descritos por informação local. Tal abordagem apresenta limitações uma vez que informação local pode não ser suficiente para descrever certas regiões da imagem. Pontos de mínimo e máximo são comumente utilizados como pontos de interesse em imagens, os quais podem ser obtidos a partir dos complexos de Morse, bem como sua conectividade no espaço de imagem. Esta tese apresenta uma abordagem dirigida por algoritmos e estruturas de dados para computar o complexo de Morse discreto em imagens bidimensionais. A construção é ótima e permite fácil manipulação do complexo. Resultados teóricos e experimentais são apresentados para mostrar que o método é eficaz. Experimentos realizados incluem a computação de homologia persistente e hierarquias de complexos sobre dados de elevação de terrenos. Outra contribuição é a proposição de um operador topológico, chamado Contexto Local de Morse, computado sobre complexos de Morse, para extrair vizinhanças de pontos de interesse para explorar a informação estrutural de imagens. O contexto local de Morse é usado no desenvolvimento de um algoritmo que auxilia a redução do número de casamentos incorretos entre pontos de interesse e na obtenção de uma medida de confiança para tais correspondências. A abordagem proposta é testada em pares de imagens sintéticas e de imagens subaquáticas, para as quais métodos existentes podem obter muitas correspondências incorretas / Abstract: The Morse theory is important for studying the topology of scalar functions such as elevation of terrains and data from physical simulations, which relates the topology of a function to critical points. The smooth theory has been adapted to discrete data through constructions such as the Morse-Smale complexes and the discrete Morse complex. Morse complexes have been applied to image processing, however, there are still challenges involving algorithms and practical considerations for computation and modeling of the complexes. Morse complexes can be used as means of defining the connectedness of interest points in images. Usually, interest points are considered as independent elements described by local information. Such an approach has its limitations since local information may not suffice for describing certain image regions. Minimum and maximum points are widely used as interest points in images, which can be obtained from Morse complexes, as well as their connectivity in the image space. This thesis presents an algorithmic and data structure driven approach to computing the discrete Morse complex of 2-dimensional images. The construction is optimal and allows easy manipulation of the complex. Theoretical and applied results are presented to show the effectiveness of the method. Applied experiments include the computation of persistent homology and hierarchies of complexes over elevation terrain data. Another contribution is the proposition of a topological operator, called Local Morse Context (LMC), computed over Morse complexes, for extracting neighborhoods of interest points to explore the structural information in images. The LMC is used in the development of a matching algorithm, which helps reducing the number of incorrect matches between images and obtaining a confidence measure of whether a correspondence is correct or incorrect. The approach is tested in synthetic and challenging underwater stereo pairs of images, for which available methods may obtain many incorrect correspondences / Doutorado / Ciência da Computação / Doutor em Ciência da Computação

Orientador: Francisco Odair Vieira de Paiva, Aloisio Freiria Neves / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-08T02:49:07Z (GMT). No. of bitstreams: 1 Malavazi_MazilioCoronel_M.pdf: 786706 bytes, checksum: 9e4d9aae3bd0fdd46d7adf64ce8958ef (MD5) Previous issue date: 2007 / Resumo: Nesta dissertação obtemos resultados de multiplicidade de soluções fracas não triviais para o problema -Du + V (x)u = f (x; u); x 2 RN; onde V é contínua, f é C1, com f (x; 0) = 0 e f é assintoticamente linear. Utilizamos métodos variacionais e a teoria de grupos críticos, para obtermos e distinguirmos as soluções. Apresentamos também resultados de existência de solução não trivial para o problema -Du + V (x)u = f (u); x 2 RN; onde V e f são funções contínuas. Utilizamos as técnicas de concentração de compacidade e de aproximação do domínio por subconjuntos limitados, para obtermos a solução / Abstract: In this dissertation we get resulted of multiplicity of not trivial weak solutions for the problem -Du + V (x)u = f (x; u); x 2 RN; where V is continuous, f is C1, with f (x; 0) = 0 and f is asymptotically linear. We use variationals methods and the theory of critical groups, to get and to distinguish the solutions. We also present results of existence of not trivial solution for the problem -Du + V (x)u = f (u); x 2 RN; where V and f are continuous functions. We use the techniques of concentration of compactness and approximation of the domain for bounded subsets, to get the solution / Mestrado / Mestre em Matemática