TY - JOUR AB - The main result of this article is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even Δ-matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by Dvorak and Kupec. Using a reduction to even Δ-matroids, we then extend the tractability result to larger classes of Δ-matroids that we call efficiently coverable. It properly includes classes that were known to be tractable before, namely, co-independent, compact, local, linear, and binary, with the following caveat:We represent Δ-matroids by lists of tuples, while the last two use a representation by matrices. Since an n ×n matrix can represent exponentially many tuples, our tractability result is not strictly stronger than the known algorithm for linear and binary Δ-matroids. AU - Kazda, Alexandr AU - Kolmogorov, Vladimir AU - Rolinek, Michal ID - 6032 IS - 2 JF - ACM Transactions on Algorithms TI - Even delta-matroids and the complexity of planar boolean CSPs VL - 15 ER - TY - THES AB - This thesis is concerned with the inference of current population structure based on geo-referenced genetic data. The underlying idea is that population structure affects its spatial genetic structure. Therefore, genotype information can be utilized to estimate important demographic parameters such as migration rates. These indirect estimates of population structure have become very attractive, as genotype data is now widely available. However, there also has been much concern about these approaches. Importantly, genetic structure can be influenced by many complex patterns, which often cannot be disentangled. Moreover, many methods merely fit heuristic patterns of genetic structure, and do not build upon population genetics theory. Here, I describe two novel inference methods that address these shortcomings. In Chapter 2, I introduce an inference scheme based on a new type of signal, identity by descent (IBD) blocks. Recently, it has become feasible to detect such long blocks of genome shared between pairs of samples. These blocks are direct traces of recent coalescence events. As such, they contain ample signal for inferring recent demography. I examine sharing of IBD blocks in two-dimensional populations with local migration. Using a diffusion approximation, I derive formulas for an isolation by distance pattern of long IBD blocks and show that sharing of long IBD blocks approaches rapid exponential decay for growing sample distance. I describe an inference scheme based on these results. It can robustly estimate the dispersal rate and population density, which is demonstrated on simulated data. I also show an application to estimate mean migration and the rate of recent population growth within Eastern Europe. Chapter 3 is about a novel method to estimate barriers to gene flow in a two dimensional population. This inference scheme utilizes geographically localized allele frequency fluctuations - a classical isolation by distance signal. The strength of these local fluctuations increases on average next to a barrier, and there is less correlation across it. I again use a framework of diffusion of ancestral lineages to model this effect, and provide an efficient numerical implementation to fit the results to geo-referenced biallelic SNP data. This inference scheme is able to robustly estimate strong barriers to gene flow, as tests on simulated data confirm. AU - Ringbauer, Harald ID - 200 SN - 2663-337X TI - Inferring recent demography from spatial genetic structure ER - TY - JOUR AB - In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets. AU - Akopyan, Arseniy AU - Balitskiy, Alexey AU - Grigorev, Mikhail ID - 1064 IS - 4 JF - Discrete & Computational Geometry SN - 01795376 TI - On the circle covering theorem by A.W. Goodman and R.E. Goodman VL - 59 ER - TY - THES AB - The aim of this thesis was the development of new strategies for optical and optogenetic control of proliferative and pro-survival signaling, and characterizing them from the molecular mechanism up to cellular effects. These new light-based methods have unique features, such as red light as an activator, or the avoidance of gene delivery, which enable to overcome current limitations, such as light delivery to target tissues and feasibility as therapeutic approach. A special focus was placed on implementing these new light-based approaches in pancreatic β-cells, as β-cells are the key players in diabetes and especially their loss in number negatively affects disease progression. Currently no treatment options are available to compensate the lack of functional β-cells in diabetic patients. In a first approach, red-light-activated growth factor receptors, in particular receptor tyrosine kinases were engineered and characterized. Receptor activation with light allows spatio-temporal control compared to ligand-based activation, and especially red light exhibits deeper tissue penetration than other wavelengths of the visible spectrum. Red-light-activated receptor tyrosine kinases robustly activated major growth factor related signaling pathways with a high temporal resolution. Moreover, the remote activation of the proliferative MAPK/Erk pathway by red-light-activated receptor tyrosine kinases in a pancreatic β-cell line was also achieved, through one centimeter thick mouse tissue. Although red-light-activated receptor tyrosine kinases are particularly attractive for applications in animal models due to the deep tissue penetration of red light, a drawback, especially with regard to translation into humans, is the requirement of gene therapy. In a second approach an endogenous light-sensitive mechanism was identified and its potential to promote proliferative and pro-survival signals was explored, towards light-based tissue regeneration without the need for gene transfer. Blue-green light illumination was found to be sufficient for the activation of proliferation and survival promoting signaling pathways in primary pancreatic murine and human islets. Blue-green light also led to an increase in proliferation of primary islet cells, an effect which was shown to be mostly β-cell specific in human islets. Moreover, it was demonstrated that this approach of pancreatic β-cell expansion did not have any negative effect on the β-cell function, in particular on their insulin secretion capacity. In contrast, a trend for enhanced insulin secretion under high glucose conditions after illumination was detected. In order to unravel the detailed characteristics of this endogenous light-sensitive mechanism, the precise light requirements were determined. In addition, the expression of light sensing proteins, OPN3 and rhodopsin, was detected. The observed effects were found to be independent of handling effects such as temperature differences and cytochrome c oxidase dependent ATP increase, but they were found to be enhanced through the knockout of OPN3. The exact mechanism of how islets cells sense light and the identity of the photoreceptor remains unknown. Summarized two new light-based systems with unique features were established that enable the activation of proliferative and pro-survival signaling pathways. While red-light-activated receptor tyrosine kinases open a new avenue for optogenetics research, by allowing non-invasive control of signaling in vivo, the identified endogenous light-sensitive mechanism has the potential to be the basis of a gene therapy-free therapeutical approach for light-based β-cell expansion. AU - Gschaider-Reichhart, Eva ID - 418 SN - 2663-337X TI - Optical and optogenetic control of proliferation and survival ER - TY - JOUR AB - We prove a new central limit theorem (CLT) for the difference of linear eigenvalue statistics of a Wigner random matrix H and its minor H and find that the fluctuation is much smaller than the fluctuations of the individual linear statistics, as a consequence of the strong correlation between the eigenvalues of H and H. In particular, our theorem identifies the fluctuation of Kerov's rectangular Young diagrams, defined by the interlacing eigenvalues ofH and H, around their asymptotic shape, the Vershik'Kerov'Logan'Shepp curve. Young diagrams equipped with the Plancherel measure follow the same limiting shape. For this, algebraically motivated, ensemble a CLT has been obtained in Ivanov and Olshanski [20] which is structurally similar to our result but the variance is different, indicating that the analogy between the two models has its limitations. Moreover, our theorem shows that Borodin's result [7] on the convergence of the spectral distribution of Wigner matrices to a Gaussian free field also holds in derivative sense. AU - Erdös, László AU - Schröder, Dominik J ID - 1012 IS - 10 JF - International Mathematics Research Notices SN - 10737928 TI - Fluctuations of rectangular young diagrams of interlacing wigner eigenvalues VL - 2018 ER -