On f-vectors of polytopes and matroids

Thesis (Ph.D.)--University of Washington, 2016-08

Phylum-wide transcriptome analysis of oogenesis and early embryogenesis in selected nematode species

Oogenesis is a prerequisite for embryogenesis in Metazoa. During both biological processes important decisions must be made to form the embryo and hence ensure the next generation: (1) Maternal gene products (mRNAs, proteins and nutrients) must be supplied to the embryo. (2) Polarity must be established and axes must be specified. While incorporation of maternal gene products occurs during oogenesis, the time point of polarity establishment and axis specification varies among species, as it is accomplished either prior, during, or after fertilisation. But not only the time point when these events take place varies among species but also the underlying mechanisms by which they are triggered. For the nematode model Caenorhabditis elegans the underlying pathways and gene regulatory networks (GRNs) are well understood. It is known that there the sperm entry point initiates a primary polarity in the 1-celled egg and with it the establishment of the anteroposterior axis. However, studies of other nematodes demonstrated that polarity establishment can be independent of sperm entry (Goldstein et al., 1998; Lahl et al., 2006) and that cleavage patterns, symmetry formation and cell specification also differ from C. elegans. In contrast to the studied Chromadorea (more derived nematodes including C. elegans), embryos of some marine Enoplea (more basal representatives) even show no discernible early polarity and blastomeres can adopt variable cell fates (Voronov and Panchin 1998). The underlying pathways controlling the obviously variant embryonic processes in non-Caenorhabditis nematodes are essentially unknown. In this thesis I addressed this issue by performing a detailed unbiased comparative transcriptome analysis based on microarrays and RNA sequencing of selected developmental stages in a variety of nematodes from different phylogenetic branches with C. elegans as a reference system and a nematomorph as an outgroup representative. In addition, I made use of available genomic data to determine the presence or absence of genes for which no expression had been detected. In particular, I focussed on components of selected pathways or GRNs which are known to play essential roles during C. elegans development and/or other invertebrate or vertebrate model systems. Oogenesis must be regulated differently in non-Caenorhabditis nematodes, as crucial controlling components of Wnt and sex determination signaling are absent in these species. In this respect, I identified female-specific expression of potential polarity associated genes during gonad development and oogenesis in the Enoplean nematode Romanomermis culicivorax. I could show that known downstream components of the polarity complexes PAR-3/-6/PKC-3 and PAR-1/-2 are absent in non-Caenorhabditis species. Even PAR-2 as part of the polarity complex does not exist in these nematodes. Instead, transcriptomes of nematodes (including C. elegans), show expression of other polarity-associated complexes such as the Lgl (Lethal giant larvae) complex. This result could pose an alternative route for nematodes and nematomorphs to initiate polarity during early embryogenesis. I could show that crucial pathways of axis specification, such as Wnt and BMP are very different in C. elegans compared to other nematodes. In the former, Wnt signaling, for instance, is mediated by four paralogous beta-catenins, while other Chromadorea have fewer and Enoplea only one beta-catenin. The transcriptomes of R. culicivorax and the nematomorph show that regulators of BMP (e.g. Chordin), are specifically expressed during early embryogenesis only in Enoplea and the close outgroup of nematomorphs. In conclusion, my results demonstrate that the molecular machinery controlling oogenesis and embryogenesis in nematodes is unexpectedly variable and C. elegans cannot be taken as a general model for nematode development. Under this perspective, Enoplean nematodes show more similarities with outgroups than with C. elegans. It appears that certain pathway components were lost or gained during evolution and others adopted new functions. Based on my findings I can conjecture, which pathway components may be ancestral and which were newly acquired in the course of nematode evolution.

Some results on orbifold quotients and related objects

The quotient of a finite-dimensional Euclidean space by a finite linear group inherits different structures from the initial space, e.g. a topology, a metric and a piecewise linear structure. The question when such a quotient is a manifold leads to the study of finite groups generated by reflections and rotations, i.e. by orthogonal transformations whose fixed point subspace has codimension one or two. We classify such groups and thereby complete earlier results by M. A. Mikhaîlova from the 70s and 80s. Moreover, we show that a finite group is generated by reflections and) rotations if and only if the corresponding quotient is a Lipschitz-, or equivalently, a piecewise linear manifold (with boundary). For the proof of this statement we show in addition that each piecewise linear manifold of dimension up to four on which a finite group acts by piecewise linear homeomorphisms admits a compatible smooth structure with respect to which the group acts smoothly. This solves a challenge by Thurston and confirms a conjecture by Kwasik and Lee. In the topological category a counterexample to the above mentioned characterization is given by the binary icosahedral group. We show that this is the only counterexample up to products. In particular, we answer the question by Davis of when the underlying space of an orbifold is a topological manifold. As a corollary of our results we generalize a fixed point theorem by Steinberg on unitary reflection groups to finite groups generated by reflections and rotations. As an application thereof we answer a question by Petrunin on quotients of spheres.

Integrability for Relativistic Spin Networks

The evaluation of relativistic spin networks plays a fundamental role in the Barrett-Crane state sum model of Lorentzian quantum gravity in 4 dimensions. A relativistic spin network is a graph labelled by unitary irreducible representations of the Lorentz group appearing in the direct integral decomposition of the space of L^2 functions on three-dimensional hyperbolic space. To `evaluate' such a spin network we must do an integral; if this integral converges we say the spin network is `integrable'. Here we show that a large class of relativistic spin networks are integrable, including any whose underlying graph is the 4-simplex (the complete graph on 5 vertices). This proves a conjecture of Barrett and Crane, whose validity is required for the convergence of their state sum model.

A Lorentzian Signature Model for Quantum General Relativity

We give a relativistic spin network model for quantum gravity based on the Lorentz group and its q-deformation, the Quantum Lorentz Algebra. We propose a combinatorial model for the path integral given by an integral over suitable representations of this algebra. This generalises the state sum models for the case of the four-dimensional rotation group previously studied in gr-qc/9709028. As a technical tool, formulae for the evaluation of relativistic spin networks for the Lorentz group are developed, with some simple examples which show that the evaluation is finite in interesting cases. We conjecture that the `10J' symbol needed in our model has a finite value.

A Recommender System based on the Immune Network

Abstract-The immune system is a complex biological system with a highly distributed, adaptive and self-organising nature. This paper presents an artificial immune system (AIS) that exploits some of these characteristics and is applied to the task of film recommendation by collaborative filtering (CF). Natural evolution and in particular the immune system have not been designed for classical optimisation. However, for this problem, we are not interested in finding a single optimum. Rather we intend to identify a sub-set of good matches on which recommendations can be based. It is our hypothesis that an AIS built on two central aspects of the biological immune system will be an ideal candidate to achieve this: Antigen - antibody interaction for matching and antibody - antibody interaction for diversity. Computational results are presented in support of this conjecture and compared to those found by other CF techniques.

A Recommender System based on Idiotypic Artificial Immune Networks

The immune system is a complex biological system with a highly distributed, adaptive and self-organising nature. This paper presents an Artificial Immune System (AIS) that exploits some of these characteristics and is applied to the task of film recommendation by Collaborative Filtering (CF). Natural evolution and in particular the immune system have not been designed for classical optimisation. However, for this problem, we are not interested in finding a single optimum. Rather we intend to identify a sub-set of good matches on which recommendations can be based. It is our hypothesis that an AIS built on two central aspects of the biological immune system will be an ideal candidate to achieve this: Antigen-antibody interaction for matching and idiotypic antibody-antibody interaction for diversity. Computational results are presented in support of this conjecture and compared to those found by other CF techniques.

A Comparison of two Proof Critics: Power vs. Robustness

Proof critics are a technology from the proof planning paradigm. They examine failed proof attempts in order to extract information which can be used to generate a patch which will allow the proof to go through. We consider the proof of the $quot;whisky problem$quot;, a challenge problem from the domain of temporal logic. The proof requires a generalisation of the original conjecture and we examine two proof critics which can be used to create this generalisation. Using these critics we believe we have produced the first automatic proofs of this challenge problem. We use this example to motivate a comparison of the two critics and propose that there is a place for specialist critics as well as powerful general critics. In particular we advocate the development of critics that do not use meta-variables.

The NumbersWithNames Program

We present the NumbersWithNames program which performs data-mining on the Encyclopedia of Integer Sequences to find interesting conjectures in number theory. The program forms conjectures by finding empirical relationships between a sequence chosen by the user and those in the Encyclopedia. Furthermore, it transforms the chosen sequence into another set of sequences about which conjectures can also be formed. Finally, the program prunes and sorts the conjectures so that themost plausible ones are presented first. We describe here the many improvements to the previous Prolog implementation which have enabled us to provide NumbersWithNames as an online program. We also present some new results from using NumbersWithNames, including details of an automated proof plan of a conjecture NumbersWithNames helped to discover.

Strong shift equivalence, algebraic K-theory, and isolating zero-dimensional dynamics on manifolds

We study the relations of shift equivalence and strong shift equivalence for matrices over a ring $\mathcal{R}$, and establish a connection between these relations and algebraic K-theory. We utilize this connection to obtain results in two areas where the shift and strong shift equivalence relations play an important role: the study of finite group extensions of shifts of finite type, and the Generalized Spectral Conjectures of Boyle and Handelman for nonnegative matrices over subrings of the real numbers. We show the refinement of the shift equivalence class of a matrix $A$ over a ring $\mathcal{R}$ by strong shift equivalence classes over the ring is classified by a quotient $NK_{1}(\mathcal{R}) / E(A,\mathcal{R})$ of the algebraic K-group $NK_{1}(\calR)$. We use the K-theory of non-commutative localizations to show that in certain cases the subgroup $E(A,\mathcal{R})$ must vanish, including the case $A$ is invertible over $\mathcal{R}$. We use the K-theory connection to clarify the structure of algebraic invariants for finite group extensions of shifts of finite type. In particular, we give a strong negative answer to a question of Parry, who asked whether the dynamical zeta function determines up to finitely many topological conjugacy classes the extensions by $G$ of a fixed mixing shift of finite type. We apply the K-theory connection to prove the equivalence of a strong and weak form of the Generalized Spectral Conjecture of Boyle and Handelman for primitive matrices over subrings of $\mathbb{R}$. We construct explicit matrices whose class in the algebraic K-group $NK_{1}(\mathcal{R})$ is non-zero for certain rings $\mathcal{R}$ motivated by applications. We study the possible dynamics of the restriction of a homeomorphism of a compact manifold to an isolated zero-dimensional set. We prove that for $n \ge 3$ every compact zero-dimensional system can arise as an isolated invariant set for a homeomorphism of a compact $n$-manifold. In dimension two, we provide obstructions and examples.

Unistructuralité des algèbres amassées de type Ã

Assem, Schiffler et Shramchenko ont émis comme conjecture que toute algèbre amassée est unistructurelle, c'est-à-dire que l'ensemble des variables amassées détermine uniquement la structure d'algèbre amassée. En d'autres mots, il existe une unique décomposition de l'ensemble des variables amassées en amas. Cette conjecture est prouvée dans le cas des algèbres amassées de type Dynkin ou de rang 2. Le but de ce mémoire de la prouver également dans le cas des algèbres amassées de type Ã. Nous utilisons les triangulations de couronnes et l'indépendance algébrique des amas pour prouver l'unistructuralité des algèbres provenant de couronnes, donc de type Ã. Nous prouvons également la conjecture des automorphismes pour les algèbres de type à comme conséquence immédiate.

Modelagem eletroquímica e do distúrbio ácido-básico em atletas de karatê participantes do campeonato mundial WKO 2014

The objective of this study was to analyze the electrochemical and acid-base disorders in high performance athletes during the World Karate Championship hosted by the WKO (World Karate Organization) in 2014. In this study 19 male athletes were analyzed (age 34 ± 8), black belts and with over 5 years of experience in the sport. Capillary blood samples from the digital pulp of the finger were collected in three stages: rest, 5 minutes after and 10 minutes after fighting (kumite). The sample was analyzed using blood gas analyzer GEM Premier 3000, using the parameters pH, Na+, K+, Ca2+, lactate e HCO3−. The values related to acid-base disturbance presented statistical differences (p <0.05) in most of the collected moments. The lactate levels found were 2.77 ± 0.97mmol / L in rest, 6.57 ± 2.1 for 5 minutes after and 4.06 ± 1.55 for 10 minutes after combat. The samples collected for the electrolytic markers showed no statistical differences in their values (p <0.05). Through the data collected, we conjecture that the sport can be characterized as a high-intensity exercise and with a predominance of the glycolytic system. The analysis of acid-base disturbance is an efficient method to assist in the control of training loads.

Spectral graph theory with applications to quantum adiabatic optimization

In this dissertation I draw a connection between quantum adiabatic optimization, spectral graph theory, heat-diffusion, and sub-stochastic processes through the operators that govern these processes and their associated spectra. In particular, we study Hamiltonians which have recently become known as ``stoquastic'' or, equivalently, the generators of sub-stochastic processes. The operators corresponding to these Hamiltonians are of interest in all of the settings mentioned above. I predominantly explore the connection between the spectral gap of an operator, or the difference between the two lowest energies of that operator, and certain equilibrium behavior. In the context of adiabatic optimization, this corresponds to the likelihood of solving the optimization problem of interest. I will provide an instance of an optimization problem that is easy to solve classically, but leaves open the possibility to being difficult adiabatically. Aside from this concrete example, the work in this dissertation is predominantly mathematical and we focus on bounding the spectral gap. Our primary tool for doing this is spectral graph theory, which provides the most natural approach to this task by simply considering Dirichlet eigenvalues of subgraphs of host graphs. I will derive tight bounds for the gap of one-dimensional, hypercube, and general convex subgraphs. The techniques used will also adapt methods recently used by Andrews and Clutterbuck to prove the long-standing ``Fundamental Gap Conjecture''.

Undersampled Critical Branching Processes on Small-World and Random Networks Fail to Reproduce the Statistics of Spike Avalanches

The power-law size distributions obtained experimentally for neuronal avalanches are an important evidence of criticality in the brain. This evidence is supported by the fact that a critical branching process exhibits the same exponent t~3=2. Models at criticality have been employed to mimic avalanche propagation and explain the statistics observed experimentally. However, a crucial aspect of neuronal recordings has been almost completely neglected in the models: undersampling. While in a typical multielectrode array hundreds of neurons are recorded, in the same area of neuronal tissue tens of thousands of neurons can be found. Here we investigate the consequences of undersampling in models with three different topologies (two-dimensional, small-world and random network) and three different dynamical regimes (subcritical, critical and supercritical). We found that undersampling modifies avalanche size distributions, extinguishing the power laws observed in critical systems. Distributions from subcritical systems are also modified, but the shape of the undersampled distributions is more similar to that of a fully sampled system. Undersampled supercritical systems can recover the general characteristics of the fully sampled version, provided that enough neurons are measured. Undersampling in two-dimensional and small-world networks leads to similar effects, while the random network is insensitive to sampling density due to the lack of a well-defined neighborhood. We conjecture that neuronal avalanches recorded from local field potentials avoid undersampling effects due to the nature of this signal, but the same does not hold for spike avalanches. We conclude that undersampled branching-process-like models in these topologies fail to reproduce the statistics of spike avalanches.

A Recommender System based on Idiotypic Artificial Immune Networks

The immune system is a complex biological system with a highly distributed, adaptive and self-organising nature. This paper presents an Artificial Immune System (AIS) that exploits some of these characteristics and is applied to the task of film recommendation by Collaborative Filtering (CF). Natural evolution and in particular the immune system have not been designed for classical optimisation. However, for this problem, we are not interested in finding a single optimum. Rather we intend to identify a sub-set of good matches on which recommendations can be based. It is our hypothesis that an AIS built on two central aspects of the biological immune system will be an ideal candidate to achieve this: Antigen-antibody interaction for matching and idiotypic antibody-antibody interaction for diversity. Computational results are presented in support of this conjecture and compared to those found by other CF techniques.