TY - JOUR AB - Experimental evolution studies are powerful approaches to examine the evolutionary history of lab populations. Such studies have shed light on how selection changes phenotypes and genotypes. Most of these studies have not examined the time course of adaptation under sexual selection manipulation, by resequencing the populations’ genomes at multiple time points. Here, we analyze allele frequency trajectories in Drosophila pseudoobscura where we altered their sexual selection regime for 200 generations and sequenced pooled populations at 5 time points. The intensity of sexual selection was either relaxed in monogamous populations (M) or elevated in polyandrous lines (E). We present a comprehensive study of how selection alters population genetics parameters at the chromosome and gene level. We investigate differences in the effective population size—Ne—between the treatments, and perform a genome-wide scan to identify signatures of selection from the time-series data. We found genomic signatures of adaptation to both regimes in D. pseudoobscura. There are more significant variants in E lines as expected from stronger sexual selection. However, we found that the response on the X chromosome was substantial in both treatments, more pronounced in E and restricted to the more recently sex-linked chromosome arm XR in M. In the first generations of experimental evolution, we estimate Ne to be lower on the X in E lines, which might indicate a swift adaptive response at the onset of selection. Additionally, the third chromosome was affected by elevated polyandry whereby its distal end harbors a region showing a strong signal of adaptive evolution especially in E lines. AU - De Castro Barbosa Rodrigues Barata, Carolina AU - Snook, Rhonda R. AU - Ritchie, Michael G. AU - Kosiol, Carolin ID - 13260 IS - 7 JF - Genome biology and evolution TI - Selection on the fly: Short-term adaptation to an altered sexual selection regime in Drosophila pseudoobscura VL - 15 ER - TY - JOUR AB - The self-assembly of nanoparticles driven by small molecules or ions may produce colloidal superlattices with features and properties reminiscent of those of metals or semiconductors. However, to what extent the properties of such supramolecular crystals actually resemble those of atomic materials often remains unclear. Here, we present coarse-grained molecular simulations explicitly demonstrating how a behavior evocative of that of semiconductors may emerge in a colloidal superlattice. As a case study, we focus on gold nanoparticles bearing positively charged groups that self-assemble into FCC crystals via mediation by citrate counterions. In silico ohmic experiments show how the dynamically diverse behavior of the ions in different superlattice domains allows the opening of conductive ionic gates above certain levels of applied electric fields. The observed binary conductive/nonconductive behavior is reminiscent of that of conventional semiconductors, while, at a supramolecular level, crossing the “band gap” requires a sufficient electrostatic stimulus to break the intermolecular interactions and make ions diffuse throughout the superlattice’s cavities. AU - Lionello, Chiara AU - Perego, Claudio AU - Gardin, Andrea AU - Klajn, Rafal AU - Pavan, Giovanni M. ID - 13346 IS - 1 JF - ACS Nano KW - General Physics and Astronomy KW - General Engineering KW - General Materials Science SN - 1936-0851 TI - Supramolecular semiconductivity through emerging ionic gates in ion–nanoparticle superlattices VL - 17 ER - TY - GEN AB - Asteroseismology has transformed stellar astrophysics. Red giant asteroseismology is a prime example, with oscillation periods and amplitudes that are readily detectable with time-domain space-based telescopes. These oscillations can be used to infer masses, ages and radii for large numbers of stars, providing unique constraints on stellar populations in our galaxy. The cadence, duration, and spatial resolution of the Roman galactic bulge time-domain survey (GBTDS) are well-suited for asteroseismology and will probe an important population not studied by prior missions. We identify photometric precision as a key requirement for realizing the potential of asteroseismology with Roman. A precision of 1 mmag per 15-min cadence or better for saturated stars will enable detections of the populous red clump star population in the Galactic bulge. If the survey efficiency is better than expected, we argue for repeat observations of the same fields to improve photometric precision, or covering additional fields to expand the stellar population reach if the photometric precision for saturated stars is better than 1 mmag. Asteroseismology is relatively insensitive to the timing of the observations during the mission, and the prime red clump targets can be observed in a single 70 day campaign in any given field. Complementary stellar characterization, particularly astrometry tied to the Gaia system, will also dramatically expand the diagnostic power of asteroseismology. We also highlight synergies to Roman GBTDS exoplanet science using transits and microlensing. AU - Huber, Daniel AU - Pinsonneault, Marc AU - Beck, Paul AU - Bedding, Timothy R. AU - Joss Bland-Hawthorn, Joss Bland-Hawthorn AU - Breton, Sylvain N. AU - Bugnet, Lisa Annabelle AU - Chaplin, William J. AU - Garcia, Rafael A. AU - Grunblatt, Samuel K. AU - Guzik, Joyce A. AU - Hekker, Saskia AU - Kawaler, Steven D. AU - Mathis, Stephane AU - Mathur, Savita AU - Metcalfe, Travis AU - Mosser, Benoit AU - Ness, Melissa K. AU - Piro, Anthony L. AU - Serenelli, Aldo AU - Sharma, Sanjib AU - Soderblom, David R. AU - Stassun, Keivan G. AU - Stello, Dennis AU - Tayar, Jamie AU - Belle, Gerard T. van AU - Zinn, Joel C. ID - 13447 T2 - arXiv TI - Asteroseismology with the Roman galactic bulge time-domain survey ER - TY - JOUR AB - Integrating light-sensitive molecules within nanoparticle (NP) assemblies is an attractive approach to fabricate new photoresponsive nanomaterials. Here, we describe the concept of photocleavable anionic glue (PAG): small trianions capable of mediating interactions between (and inducing the aggregation of) cationic NPs by means of electrostatic interactions. Exposure to light converts PAGs into dianionic products incapable of maintaining the NPs in an assembled state, resulting in light-triggered disassembly of NP aggregates. To demonstrate the proof-of-concept, we work with an organic PAG incorporating the UV-cleavable o-nitrobenzyl moiety and an inorganic PAG, the photosensitive trioxalatocobaltate(III) complex, which absorbs light across the entire visible spectrum. Both PAGs were used to prepare either amorphous NP assemblies or regular superlattices with a long-range NP order. These NP aggregates disassembled rapidly upon light exposure for a specific time, which could be tuned by the incident light wavelength or the amount of PAG used. Selective excitation of the inorganic PAG in a system combining the two PAGs results in a photodecomposition product that deactivates the organic PAG, enabling nontrivial disassembly profiles under a single type of external stimulus. AU - Wang, Jinhua AU - Peled, Tzuf Shay AU - Klajn, Rafal ID - 13354 IS - 7 JF - Journal of the American Chemical Society KW - Colloid and Surface Chemistry KW - Biochemistry KW - General Chemistry KW - Catalysis SN - 0002-7863 TI - Photocleavable anionic glues for light-responsive nanoparticle aggregates VL - 145 ER - TY - THES AB - Most energy in humans is produced in form of ATP by the mitochondrial respiratory chain consisting of several protein assemblies embedded into lipid membrane (complexes I-V). Complex I is the first and the largest enzyme of the respiratory chain which is essential for energy production. It couples the transfer of two electrons from NADH to ubiquinone with proton translocation across bacterial or inner mitochondrial membrane. The coupling mechanism between electron transfer and proton translocation is one of the biggest enigma in bioenergetics and structural biology. Even though the enzyme has been studied for decades, only recent technological advances in cryo-EM allowed its extensive structural investigation. Complex I from E.coli appears to be of special importance because it is a perfect model system with a rich mutant library, however the structure of the entire complex was unknown. In this thesis I have resolved structures of the minimal complex I version from E. coli in different states including reduced, inhibited, under reaction turnover and several others. Extensive structural analyses of these structures and comparison to structures from other species allowed to derive general features of conformational dynamics and propose a universal coupling mechanism. The mechanism is straightforward, robust and consistent with decades of experimental data available for complex I from different species. Cyanobacterial NDH (cyanobacterial complex I) is a part of broad complex I superfamily and was studied as well in this thesis. It plays an important role in cyclic electron transfer (CET), during which electrons are cycled within PSI through ferredoxin and plastoquinone to generate proton gradient without NADPH production. Here, I solved structure of NDH and revealed additional state, which was not observed before. The novel “resting” state allowed to propose the mechanism of CET regulation. Moreover, conformational dynamics of NDH resembles one in complex I which suggest more broad universality of the proposed coupling mechanism. In summary, results presented here helped to interpret decades of experimental data for complex I and contributed to fundamental mechanistic understanding of protein function. AU - Kravchuk, Vladyslav ID - 12781 SN - 2663-337X TI - Structural and mechanistic study of bacterial complex I and its cyanobacterial ortholog ER - TY - THES AB - Deep learning has become an integral part of a large number of important applications, and many of the recent breakthroughs have been enabled by the ability to train very large models, capable to capture complex patterns and relationships from the data. At the same time, the massive sizes of modern deep learning models have made their deployment to smaller devices more challenging; this is particularly important, as in many applications the users rely on accurate deep learning predictions, but they only have access to devices with limited memory and compute power. One solution to this problem is to prune neural networks, by setting as many of their parameters as possible to zero, to obtain accurate sparse models with lower memory footprint. Despite the great research progress in obtaining sparse models that preserve accuracy, while satisfying memory and computational constraints, there are still many challenges associated with efficiently training sparse models, as well as understanding their generalization properties. The focus of this thesis is to investigate how the training process of sparse models can be made more efficient, and to understand the differences between sparse and dense models in terms of how well they can generalize to changes in the data distribution. We first study a method for co-training sparse and dense models, at a lower cost compared to regular training. With our method we can obtain very accurate sparse networks, and dense models that can recover the baseline accuracy. Furthermore, we are able to more easily analyze the differences, at prediction level, between the sparse-dense model pairs. Next, we investigate the generalization properties of sparse neural networks in more detail, by studying how well different sparse models trained on a larger task can adapt to smaller, more specialized tasks, in a transfer learning scenario. Our analysis across multiple pruning methods and sparsity levels reveals that sparse models provide features that can transfer similarly to or better than the dense baseline. However, the choice of the pruning method plays an important role, and can influence the results when the features are fixed (linear finetuning), or when they are allowed to adapt to the new task (full finetuning). Using sparse models with fixed masks for finetuning on new tasks has an important practical advantage, as it enables training neural networks on smaller devices. However, one drawback of current pruning methods is that the entire training cycle has to be repeated to obtain the initial sparse model, for every sparsity target; in consequence, the entire training process is costly and also multiple models need to be stored. In the last part of the thesis we propose a method that can train accurate dense models that are compressible in a single step, to multiple sparsity levels, without additional finetuning. Our method results in sparse models that can be competitive with existing pruning methods, and which can also successfully generalize to new tasks. AU - Peste, Elena-Alexandra ID - 13074 SN - 2663-337X TI - Efficiency and generalization of sparse neural networks ER - TY - THES AB - Pattern formation is of great importance for its contribution across different biological behaviours. During developmental processes for example, patterns of chemical gradients are established to determine cell fate and complex tissue patterns emerge to define structures such as limbs and vascular networks. Patterns are also seen in collectively migrating groups, for instance traveling waves of density emerging in moving animal flocks as well as collectively migrating cells and tissues. To what extent these biological patterns arise spontaneously through the local interaction of individual constituents or are dictated by higher level instructions is still an open question however there is evidence for the involvement of both types of process. Where patterns arise spontaneously there is a long standing interest in how far the interplay of mechanics, e.g. force generation and deformation, and chemistry, e.g. gene regulation and signaling, contributes to the behaviour. This is because many systems are able to both chemically regulate mechanical force production and chemically sense mechanical deformation, forming mechano-chemical feedback loops which can potentially become unstable towards spatio and/or temporal patterning. We work with experimental collaborators to investigate the possibility that this type of interaction drives pattern formation in biological systems at different scales. We focus first on tissue-level ERK-density waves observed during the wound healing response across different systems where many previous studies have proposed that patterns depend on polarized cell migration and arise from a mechanical flocking-like mechanism. By combining theory with mechanical and optogenetic perturbation experiments on in vitro monolayers we instead find evidence for mechanochemical pattern formation involving only scalar bilateral feedbacks between ERK signaling and cell contraction. We perform further modeling and experiment to study how this instability couples with polar cell migration in order to produce a robust and efficient wound healing response. In a following chapter we implement ERK-density coupling and cell migration in a 2D active vertex model to investigate the interaction of ERK-density patterning with different tissue rheologies and find that the spatio-temporal dynamics are able to both locally and globally fluidize a tissue across the solid-fluid glass transition. In a last chapter we move towards lower spatial scales in the context of subcellular patterning of the cell cytoskeleton where we investigate the transition between phases of spatially homogeneous temporal oscillations and chaotic spatio-temporal patterning in the dynamics of myosin and ROCK activities (a motor component of the actomyosin cytoskeleton and its activator). Experimental evidence supports an intrinsic chemical oscillator which we encode in a reaction model and couple to a contractile active gel description of the cell cortex. The model exhibits phases of chemical oscillations and contractile spatial patterning which reproduce many features of the dynamics seen in Drosophila oocyte epithelia in vivo. However, additional pharmacological perturbations to inhibit myosin contractility leaves the role of contractile instability unclear. We discuss alternative hypotheses and investigate the possibility of reaction-diffusion instability. AU - Boocock, Daniel R ID - 12964 SN - 2663-337X TI - Mechanochemical pattern formation across biological scales ER - TY - JOUR AB - The many-body localization (MBL) proximity effect is an intriguing phenomenon where a thermal bath localizes due to the interaction with a disordered system. The interplay of thermal and nonergodic behavior in these systems gives rise to a rich phase diagram, whose exploration is an active field of research. In this paper, we study a bosonic Hubbard model featuring two particle species representing the bath and the disordered system. Using state-of-the-art numerical techniques, we investigate the dynamics of the model in different regimes, based on which we obtain a tentative phase diagram as a function of coupling strength and bath size. When the bath is composed of a single particle, we observe clear signatures of a transition from an MBL proximity effect to a delocalized phase. Increasing the bath size, however, its thermalizing effect becomes stronger and eventually the whole system delocalizes in the range of moderate interaction strengths studied. In this regime, we characterize particle transport, revealing diffusive behavior of the originally localized bosons. AU - Brighi, Pietro AU - Ljubotina, Marko AU - Abanin, Dmitry A. AU - Serbyn, Maksym ID - 13963 IS - 5 JF - Physical Review B SN - 2469-9950 TI - Many-body localization proximity effect in a two-species bosonic Hubbard model VL - 108 ER - TY - JOUR AB - We present a low-scaling diagrammatic Monte Carlo approach to molecular correlation energies. Using combinatorial graph theory to encode many-body Hugenholtz diagrams, we sample the Møller-Plesset (MPn) perturbation series, obtaining accurate correlation energies up to n=5, with quadratic scaling in the number of basis functions. Our technique reduces the computational complexity of the molecular many-fermion correlation problem, opening up the possibility of low-scaling, accurate stochastic computations for a wide class of many-body systems described by Hugenholtz diagrams. AU - Bighin, Giacomo AU - Ho, Quoc P AU - Lemeshko, Mikhail AU - Tscherbul, T. V. ID - 13966 IS - 4 JF - Physical Review B SN - 2469-9950 TI - Diagrammatic Monte Carlo for electronic correlation in molecules: High-order many-body perturbation theory with low scaling VL - 108 ER - TY - JOUR AU - Madani, Amiera AU - Sletten, Eric T. AU - Cavedon, Cristian AU - Seeberger, Peter H. AU - Pieber, Bartholomäus ID - 13970 JF - Organic Syntheses SN - 0078-6209 TI - Visible-light-mediated oxidative debenzylation of 3-O-Benzyl-1,2:5,6-di-O-isopropylidene-α-D-glucofuranose VL - 100 ER - TY - JOUR AB - Cooperative disease defense emerges as group-level collective behavior, yet how group members make the underlying individual decisions is poorly understood. Using garden ants and fungal pathogens as an experimental model, we derive the rules governing individual ant grooming choices and show how they produce colony-level hygiene. Time-resolved behavioral analysis, pathogen quantification, and probabilistic modeling reveal that ants increase grooming and preferentially target highly-infectious individuals when perceiving high pathogen load, but transiently suppress grooming after having been groomed by nestmates. Ants thus react to both, the infectivity of others and the social feedback they receive on their own contagiousness. While inferred solely from momentary ant decisions, these behavioral rules quantitatively predict hour-long experimental dynamics, and synergistically combine into efficient colony-wide pathogen removal. Our analyses show that noisy individual decisions based on only local, incomplete, yet dynamically-updated information on pathogen threat and social feedback can lead to potent collective disease defense. AU - Casillas Perez, Barbara E AU - Bod'Ová, Katarína AU - Grasse, Anna V AU - Tkačik, Gašper AU - Cremer, Sylvia ID - 13127 JF - Nature Communications TI - Dynamic pathogen detection and social feedback shape collective hygiene in ants VL - 14 ER - TY - DATA AB - basic data for use in code for experimental data analysis for manuscript under revision: Dynamic pathogen detection and social feedback shape collective hygiene in ants Casillas-Pérez B, Boďová K, Grasse AV, Tkačik G, Cremer S AU - Cremer, Sylvia ID - 12945 KW - collective behavior KW - host-pathogen interactions KW - social immunity KW - epidemiology KW - social insects KW - probabilistic modeling TI - Data from: "Dynamic pathogen detection and social feedback shape collective hygiene in ants" ER - TY - THES AB - High-performance semiconductors rely upon precise control of heat and charge transport. This can be achieved by precisely engineering defects in polycrystalline solids. There are multiple approaches to preparing such polycrystalline semiconductors, and the transformation of solution-processed colloidal nanoparticles is appealing because colloidal nanoparticles combine low cost with structural and compositional tunability along with rich surface chemistry. However, the multiple processes from nanoparticle synthesis to the final bulk nanocomposites are very complex. They involve nanoparticle purification, post-synthetic modifications, and finally consolidation (thermal treatments and densification). All these properties dictate the final material’s composition and microstructure, ultimately affecting its functional properties. This thesis explores the synthesis, surface chemistry and consolidation of colloidal semiconductor nanoparticles into dense solids. In particular, the transformations that take place during these processes, and their effect on the material’s transport properties are evaluated. AU - Calcabrini, Mariano ID - 12885 SN - 2663-337X TI - Nanoparticle-based semiconductor solids: From synthesis to consolidation ER - TY - JOUR AB - Following up on the recent work on lower Ricci curvature bounds for quantum systems, we introduce two noncommutative versions of curvature-dimension bounds for symmetric quantum Markov semigroups over matrix algebras. Under suitable such curvature-dimension conditions, we prove a family of dimension-dependent functional inequalities, a version of the Bonnet–Myers theorem and concavity of entropy power in the noncommutative setting. We also provide examples satisfying certain curvature-dimension conditions, including Schur multipliers over matrix algebras, Herz–Schur multipliers over group algebras and generalized depolarizing semigroups. AU - Wirth, Melchior AU - Zhang, Haonan ID - 12087 JF - Annales Henri Poincare SN - 1424-0637 TI - Curvature-dimension conditions for symmetric quantum Markov semigroups VL - 24 ER - TY - JOUR AB - In 1998 Burago and Kleiner and (independently) McMullen gave examples of separated nets in Euclidean space which are non-bilipschitz equivalent to the integer lattice. We study weaker notions of equivalence of separated nets and demonstrate that such notions also give rise to distinct equivalence classes. Put differently, we find occurrences of particularly strong divergence of separated nets from the integer lattice. Our approach generalises that of Burago and Kleiner and McMullen which takes place largely in a continuous setting. Existence of irregular separated nets is verified via the existence of non-realisable density functions ρ:[0,1]d→(0,∞). In the present work we obtain stronger types of non-realisable densities. AU - Dymond, Michael AU - Kaluza, Vojtech ID - 9652 JF - Israel Journal of Mathematics KW - Lipschitz KW - bilipschitz KW - bounded displacement KW - modulus of continuity KW - separated net KW - non-realisable density KW - Burago--Kleiner construction TI - Highly irregular separated nets VL - 253 ER - TY - JOUR AB - The power factor of poly(3,4-ethylenedioxythiophene):poly(styrene sulfonate) (PEDOT:PSS) film can be significantly improved by optimizing the oxidation level of the film in oxidation and reduction processes. However, precise control over the oxidation and reduction effects in PEDOT:PSS remains a challenge, which greatly sacrifices both S and σ. Here, we propose a two-step post-treatment using a mixture of ethylene glycol (EG) and Arginine (Arg) and sulfuric acid (H2SO4) in sequence to engineer high-performance PEDOT:PSS thermoelectric films. The high-polarity EG dopant removes the excess non-ionized PSS and induces benzenoid-to-quinoid conformational change in the PEDOT:PSS films. In particular, basic amino acid Arg tunes the oxidation level of PEDOT:PSS and prevents the films from over-oxidation during H2SO4 post-treatment, leading to increased S. The following H2SO4 post-treatment further induces highly orientated lamellar stacking microstructures to increase σ, yielding a maximum power factor of 170.6 μW m−1 K−2 at 460 K. Moreover, a novel trigonal-shape thermoelectric device is designed and assembled by the as-prepared PEDOT:PSS films in order to harvest heat via a vertical temperature gradient. An output power density of 33 μW cm−2 is generated at a temperature difference of 40 K, showing the potential application for low-grade wearable electronic devices. AU - Zhang, Li AU - Liu, Xingyu AU - Wu, Ting AU - Xu, Shengduo AU - Suo, Guoquan AU - Ye, Xiaohui AU - Hou, Xiaojiang AU - Yang, Yanling AU - Liu, Qingfeng AU - Wang, Hongqiang ID - 12113 JF - Applied Surface Science KW - Surfaces KW - Coatings and Films KW - Condensed Matter Physics KW - Surfaces and Interfaces KW - General Physics and Astronomy KW - General Chemistry SN - 0169-4332 TI - Two-step post-treatment to deliver high performance thermoelectric device with vertical temperature gradient VL - 613 ER - TY - JOUR AB - We study the large scale behavior of elliptic systems with stationary random coefficient that have only slowly decaying correlations. To this aim we analyze the so-called corrector equation, a degenerate elliptic equation posed in the probability space. In this contribution, we use a parabolic approach and optimally quantify the time decay of the semigroup. For the theoretical point of view, we prove an optimal decay estimate of the gradient and flux of the corrector when spatially averaged over a scale R larger than 1. For the numerical point of view, our results provide convenient tools for the analysis of various numerical methods. AU - Clozeau, Nicolas ID - 10173 JF - Stochastics and Partial Differential Equations: Analysis and Computations SN - 2194-0401 TI - Optimal decay of the parabolic semigroup in stochastic homogenization for correlated coefficient fields VL - 11 ER - TY - JOUR AB - Following E. Wigner’s original vision, we prove that sampling the eigenvalue gaps within the bulk spectrum of a fixed (deformed) Wigner matrix H yields the celebrated Wigner-Dyson-Mehta universal statistics with high probability. Similarly, we prove universality for a monoparametric family of deformed Wigner matrices H+xA with a deterministic Hermitian matrix A and a fixed Wigner matrix H, just using the randomness of a single scalar real random variable x. Both results constitute quenched versions of bulk universality that has so far only been proven in annealed sense with respect to the probability space of the matrix ensemble. AU - Cipolloni, Giorgio AU - Erdös, László AU - Schröder, Dominik J ID - 11741 JF - Probability Theory and Related Fields SN - 0178-8051 TI - Quenched universality for deformed Wigner matrices VL - 185 ER - TY - JOUR AB - High carrier mobility is critical to improving thermoelectric performance over a broad temperature range. However, traditional doping inevitably deteriorates carrier mobility. Herein, we develop a strategy for fine tuning of defects to improve carrier mobility. To begin, n-type PbTe is created by compensating for the intrinsic Pb vacancy in bare PbTe. Excess Pb2+ reduces vacancy scattering, resulting in a high carrier mobility of ∼3400 cm2 V–1 s–1. Then, excess Ag is introduced to compensate for the remaining intrinsic Pb vacancies. We find that excess Ag exhibits a dynamic doping process with increasing temperatures, increasing both the carrier concentration and carrier mobility throughout a wide temperature range; specifically, an ultrahigh carrier mobility ∼7300 cm2 V–1 s–1 is obtained for Pb1.01Te + 0.002Ag at 300 K. Moreover, the dynamic doping-induced high carrier concentration suppresses the bipolar thermal conductivity at high temperatures. The final step is using iodine to optimize the carrier concentration to ∼1019 cm–3. Ultimately, a maximum ZT value of ∼1.5 and a large average ZTave value of ∼1.0 at 300–773 K are obtained for Pb1.01Te0.998I0.002 + 0.002Ag. These findings demonstrate that fine tuning of defects with <0.5% impurities can remarkably enhance carrier mobility and improve thermoelectric performance. AU - Wang, Siqi AU - Chang, Cheng AU - Bai, Shulin AU - Qin, Bingchao AU - Zhu, Yingcai AU - Zhan, Shaoping AU - Zheng, Junqing AU - Tang, Shuwei AU - Zhao, Li Dong ID - 12331 IS - 2 JF - Chemistry of Materials SN - 0897-4756 TI - Fine tuning of defects enables high carrier mobility and enhanced thermoelectric performance of n-type PbTe VL - 35 ER - TY - JOUR AB - A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles. AU - Arroyo Guevara, Alan M AU - Klute, Fabian AU - Parada, Irene AU - Vogtenhuber, Birgit AU - Seidel, Raimund AU - Wiedera, Tilo ID - 11999 JF - Discrete and Computational Geometry SN - 0179-5376 TI - Inserting one edge into a simple drawing is hard VL - 69 ER -