The past three decades have seen extraordinary progress in the manipulation of neutral atoms with laser light, to the point where it is now routine to trap and cool both individual atoms and entire atomic clouds to temperatures of only a few tens of nanoKelvin in a controlled and repeatable fashion. In this thesis we study several applications of Rydberg atoms - atoms with an electron in a highly excited state - within such ultracold atomic systems. Due to their highly-excited electron, Rydberg atoms have a number of exaggerated properties: in addition to being physically large, they have long radiative lifetimes, and interact strongly both with one another and with applied external fields. Rydberg atoms consequently find many interesting applications within ultracold atomic physics. We begin this thesis by analysing the way in which a rubidium atom prepared in an excited Rydberg state decays to the ground state. Using quantum defect theory to model the wavefunction of the excited electron, we compute branching ratios for the various decay channels that lead out of the Rydberg states of rubidium. By using these results to carry out detailed simulations of the radiative cascade process, we show that the dynamics of spontaneous emission from Rydberg states cannot be adequately described by a truncated atomic level structure. We then investigate the stability of ultra-large diatomic molecules formed by pairs of Rydberg atoms. Using quantum defect theory to model the electronic wavefunctions, we apply molecular integral techniques to calculate the equilibrium distance and binding energy of these molecular Rydberg states. Our results indicate that these Ryberg macro-dimers are predicted to show a potential minimum, with equilibrium distances of up to several hundred nanometres. In the second half of this thesis, we present a new method of symbolically evaluating functions of matrices. This method, which we term the method of path-sums, has applications to the simulation of strongly-correlated many-body Rydberg systems, and is based on the combination of a mapping between matrix multiplications and walks on weighted directed graphs with a universal result on the structure of such walks. After presenting and proving this universal graph theoretic result, we develop the path-sum approach to matrix functions. We discuss the application of path-sums to the simulation of strongly-correlated many-body quantum systems, and indicate future directions for the method.

Dans cette thèse, nous étudions la complexité paramétrée de problèmes combinatoires dans les graphes. Plus précisément, nous présentons une multitude d’algorithmes de programmation dynamique ainsi que des réductions montrant que certains de ces algorithmes sont optimaux. Nous nous intéressons principalement à la treewidth, un paramètre de graphes pouvant être vu comme une mesure de distance entre la structure d’un graphe et la structure topologique d’un arbre. Certains de nos algorithmes sont aussi paramétrés par la taille de la solution demandée et le degré maximum du graphe donné en entrée. Nous avons obtenu un certain nombre de résultats dont certains d’entre eux sont listés ci-dessous. Nous présentons un encadrement du nombre de graphes étiquetés de treewidth bornée. Nous étendons le domaine d’application de la théorie de la bidimensionalité par contraction au delà des graphes ne contenant pas de graphe apex en tant que mineur. Nous montrons aussi que la technique des structures de Catalan, outil améliorant l’efficacité des algorithmes résolvant des problèmes de connexité lorsque le graphe d’entrée est creux, ne peut être appliquée à la totalité des problèmes de connectivité, même si l’on ne considère, parmi les graphes creux, que les graphes planaires. Nous considérons le problème F-M-Deletion qui, étant donné une collection de graphes F, un graphe G et un entier k, demande s’il est possible de retirer au plus k sommets de G de telle sorte que le graphe restant ne contienne aucun graphe de F en tant que mineur. Nous considérons aussi la version topologique de ce problème, à savoir F-TM-Deletion. Ces deux problèmes généralisent des problèmes de modification de graphes bien connus tels que Vertex Cover, Feedback Vertex Set et Vertex Planarization. En fonction de la collection de graphes F, nous utilisons différentes techniques de programmation dynamique pour résoudre F-M-Deletion et F-TM-Deletion paramétrés par la treewidth. Nous utilisons des techniques standards, la structure des graphes frontières et l’approche basée sur le rang. En dernier lieu, nous appliquons ces techniques algorithmiques à deux problèmes issus du réseau de communications, à savoir une variation du problème classique de domination et un problème consistant à trouver un arbre couvrant possédant certaines propriétés, et un problème issu de la bioinformatique consistant à construire un arbre contenant en tant que mineur (topologique) un ensemble d’arbres donnés correspondant à des relations d’évolution entre ensembles d’espèces. / In this thesis, we study the Parameterized Complexity of combinatorial problems on graphs. More precisely, we present a multitude of dynamic programming algorithms together with reductions showing optimality for some of them. We mostly deal with the graph parameter of treewidth, which can be seen as a measure of how close a graph is to the topological structure of a tree. We also parameterize some of our algorithms by two other parameters, namely the size of a requested solution and the maximum degree of the input graph. We obtain a number of results, some of which are listed in the following. We estimate the number of labeled graphs of bounded treewidth. We extend the horizon of applicability of the theory of contraction Bidimensionality further than apex-minor free graphs, leading to a wider applicability of the design of subexponential dynamic programming algorithms. We show that the Catalan structure technique, that is a tool used to improve algorithm efficiency for connectivity problems where the input graph is restricted to be sparse, cannot be applied to all planar connectivity problems. We consider the F-M-Deletion problem that, given a set of graphs F, a graph G, and an integer k, asks if we can remove at most k vertices from G such that the remaining graph does not contain any graph of F as a minor. We also consider the topological version of this problem, namely F-TM-Deletion. Both problems generalize some well-known vertex deletion problems, namely Vertex Cover, Feedback Vertex Set, and Vertex Planarization. Depending on the set F, we use distinct dynamic programming techniques to solve F-M-Deletion and F-TM-Deletion when parameterized by treewidth. Namely, we use standard techniques, the rank based approach, and the framework of boundaried graphs. Finally, we apply these techniques to two problems originating from Networks, namely a variation of the classical dominating set problem and a problem that consists in finding a spanning tree with specific properties, and to a problem from Bioinformatics, namely that of construcing a tree that contains as a minor (or topological minor) a set of given trees corresponding to the evolutionary relationships between sets of species.

of doctoral thesis Structural graph theory Jan Hladký In the thesis we make progress on the Loebl-Komlós-Sós Conjecture which is a classic problem in the field of Extremal Graph Theory. We prove the following weaker version of the Conjecture: For every α > 0 there exists a number k0 such that for every k > k0 we have that every n-vertex graph G with at least (1 2 +α)n vertices of degrees at least (1+α)k contains each tree T of order k as a subgraph. The proof of our result follows a strategy common to approaches which employ the Szemerédi Regularity Lemma: the graph G is decomposed, a suitable combinatorial structure inside the decomposition is found, and then the tree T is embedded into G using this structure. However the decomposition given by the Regularity Lemma is not of help when G sparse. To surmount this shortcoming we develop a decomposition technique that applies also to sparse graphs: each graph can be decomposed into vertices of huge degrees, regular pairs (in the sense of the Regularity Lemma), and two other components each exhibiting certain expander-like properties. The results were achieved in a joint work with János Komlós, Diana Piguet, Miklós Simonovits, Maya Jakobine Stein and Endre Szemerédi. 1

No description available.

Complex network models of functional connectivity have emerged as a paradigm shift in brain mapping over the past decade. Despite significant attention within the neuroimaging and cognitive neuroscience communities, these approaches have hitherto not been extensively explored in neurosurgery. The aim of this thesis is to investigate how the field of connectomics can contribute to understanding the effects of focal brain lesions and to functional brain mapping in neurosurgery. This datasets for this thesis include a clinical population with focal brain tumours and a cohort focused on healthy adolescent brain development. Multiple network analyses of increasing complexity are performed based upon resting state functional MRI. In patients with focal brain tumours, the full complement of resting state networks were apparent, while also suggesting putative patterns of network plasticity. Connectome analysis was able to identify potential signatures of node robustness and connections at risk that could be used to individually plan surgery. Focal lesions induced the formation of new hubs while down regulating previously established hubs. Overall these data are consistent with a dynamic rather than a static response to the presence of focal lesions. Adolescent brain development demonstrated discrete dynamics with distinct gender specific and age-gender interactions. Network architecture also became more robust, particularly to random removal of nodes and edges. Overall these data provide evidence for the early vulnerability rather than enhanced plasticity of brain networks. In summary, this thesis presents a combined analysis of pathological and healthy development datasets focused on understanding the functional effects of focal brain lesions at a network level. The coda serves as an introduction to a forthcoming study, known as Connectomics and Electrical Stimulation for Augmenting Resection (CAESAR), which is an evolution of the results and methods herein.

The Discrete Nodal Domain Theorem states that an eigenfunction of the k-th largest eigenvalue of a generalized graph Laplacian has at most k (weak) nodal domains. We show that the number of strong nodal domains cannot exceed the size of a maximal induced bipartite subgraph and that this bound is sharp for generalized graph Laplacians. Similarly, the number of weak nodal domains is bounded by the size of a maximal bipartite minor. (author's abstract) / Series: Preprint Series / Department of Applied Statistics and Data Processing

A identificação de formas apresenta inúmeras aplicações na área de visão computacional, pois representa uma poderosa ferramenta para analisar as características de um objeto. Dentre as aplicações, podemos citar como exemplos a interação entre humanos e robôs, com a identificação de ações e comandos, e a análise de comportamento para vigilância com a biometria não invasiva. Em nosso trabalho nós desenvolvemos um novo descritor de formas 2D baseado na utilização de redes complexas e teoria espectral de grafos. O contorno da forma de um objeto é representado por uma rede complexa, onde cada ponto pertencente a forma será representado por um vértice da rede. Utilizando uma dinâmica gerada artificialmente na rede complexa, podemos definir uma série de matrizes de adjacência que refletem a dinâmica estrutural da forma do objeto. Cada matriz tem seu espectro calculado, e os principais autovalores são utilizados na construção de um vetor de características. Esse vetor, após aplicar as operações de módulo e normalização, torna-se nossa assinatura espectral de forma. Os principais autovalores de um grafo estão relacionados com propriedades topológicas do mesmo, o que permite sua utilização na descrição da forma de um objeto. Para validar nosso método, nós realizamos testes quanto ao seu comportamento frente a transformações de rotação e escala e estudamos seu comportamento quanto à contaminação das formas por ruído Gaussiano e quanto ao efeito de oclusões parciais. Utilizamos diversas bases de dados comumente utilizadas na literatura de análise de formas para averiguar a eficiência de nosso método em tarefas de recuperação de informação. Concluímos o trabalho com a análise qualitativa do comportamento de nosso método frente a diferentes curvas e estudando uma aplicação na análise de sequências de caminhada. Os resultados obtidos em comparação aos outros métodos mostram que nossa assinatura espectral de forma apresenta bom resultados na precisão de recuperação de informação, boa tolerância a contaminação das formas por ruído e oclusões parciais, e capacidade de distinguir ações humanas e identificar os ciclos de uma sequência de caminhada. / The shape is a powerful feature to characterize an object and the shape analysis has several applications in computer vision area. We can cite the interaction between human and robots, surveillance, non-invasive biometry and human actions identifications among other applications. In our work we have developed a new 2d shape descriptor based on complex network and spectral graph theory. The contour shape of an object is represented by a complex network, where each point belonging shape is represented by a vertex of the network. A set of adjacencies matrices is generated using an artificial dynamics in the complex network. We calculate the spectrum of each adjacency matrix and the most important eigenvalues are used in a feature vector. This vector, after applying module and normalization operations, becomes our spectral shape signature. The principal eigenvalues of a graph are related to its topological properties. This allows us use eigenvalues to describe the shape of an object. We have used shape benchmarks to measure the information retrieve precision of our method. Besides that, we have analyzed the response of the spectral shape signature under noise, rotation and occlusions situations. A qualitative study of the method behavior has been done using curves and a walk sequence. The achieved comparative results to other methods found in the literature show that our spectral shape signature presents good results in information retrieval tasks, good tolerance under noise and partial occlusions situation. We present that our method is able to distinguish human actions and identify the cycles of a walk sequence.

For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent domination number i (G)) of G is the minimum cardinality amongst its dominating sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1- critical, if the domination number k decreases whenever an edge is added. Further, G is hamiltonian if it has a cycle that passes through each of its vertices. This dissertation assimilates research generated by two conjectures: Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian. Conjecture 2. If G is k-1-critical, then I ( G) = i ( G). The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture 2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)

The queens graph Qn has the squares of then x n chessboard as its vertices; two squares are adjacent if they are in the same row, column or diagonal. A set D of squares of Qn is a dominating set for Qn if every square of Qn is either in D or adjacent to a square in D. If no two squares of a set I are adjacent then I is an independent set. Let 'J'(Qn) denote the minimum size of a dominating set of Qn and let i(Qn) denote the minimum size of an independent dominating set of Qn. The main purpose of this thesis is to determine new values for'!'( Qn). We begin by discussing the most important known lower bounds for 'J'(Qn) in Chapter 2. In Chapter 3 we state the hitherto known values of 'J'(Qn) and explain how they were determined. We briefly explain how to obtain all non-isomorphic minimum dominating sets for Q8 (listed in Appendix A). It is often useful to study these small dominating sets to look for patterns and possible generalisations. In Chapter 4 we determine new values for')' ( Q69 ) , ')' ( Q77 ), ')' ( Q30 ) and i (Q45 ) by considering asymmetric and symmetric dominating sets for the case n = 4k + 1 and in Chapter 5 we search for dominating sets for the case n = 4k + 3, thus determining the values of 'I' ( Q19) and 'I' (Q31 ). In Chapter 6 we prove the upper bound')' (Qn) :s; 1 8 5n + 0 (1), which is better than known bounds in the literature and in Chapter 7 we consider dominating sets on hexagonal boards. Finally, in Chapter 8 we determine the irredundance number for the hexagonal boards H5 and H7, as well as for Q5 and Q6 / Mathematical Sciences / D.Phil. (Applied Mathematics)

Graph augmentation concerns the addition of edges to a graph to satisfy some connectivity property of a graph. Previous research in this field has been preoccupied with edge augmentation; however the research in this document focuses on the addition of vertices to a graph to satisfy a specific connectivity property: ensuring that all the nodes of the graph are contained within cycles. A distinction is made between graph augmentation (edge addition), and graph enlargement (vertex addition). This document expands on previous research into a graph matching problem known as the “shoe matching problem” and the role of a graph enlargement algorithm in finding this solution. The aim of this research was to develop new and efficient algorithms to solve the graph enlargement problem as applied to the shoe matching problem and to improve on the naïve algorithm of Sanders. Three new algorithms focusing on graph enlargement and the shoe matching problem are presented, with positive results overall. The new enlargement algorithms: cost-optimised, matrix, and subgraph, succeeded in deriving the best result (least number of total nodes required) in 37%, 53%, and 57% of cases respectively (measured across 120 cases). In contrast, Sanders’s algorithm has a success rate of only 20%; thus the new algorithms have a varying success rate of approximately 2 to 3 times that of Sanders’s algorithm. / Computing / M. Sc. Computing