510 Mathematik
Refine
Year of publication
Document Type
- Preprint (52) (remove)
Language
- English (52)
Has Fulltext
- yes (52)
Is part of the Bibliography
- no (52)
Keywords
- Kongress (5)
- Kryptologie (5)
- Online-Publikation (4)
- Commitment Scheme (2)
- Degree Sequence (2)
- Moran model (2)
- Oblivious Transfer (2)
- Random Graph (2)
- San Jose (2)
- Switching Algorithm (2)
- Temporal Graph (2)
- Uniform Sampling (2)
- ancestral selection graph (2)
- duality (2)
- fixation probability (2)
- Λ−coalescent (2)
- Blind Signature (1)
- Block Korkin—Zolotarev reduction (1)
- Calderón problem (1)
- Chinese Remainder Theorem (1)
- Closest Vector Problem (1)
- Commitment (1)
- Commitment schemes (1)
- Dessins d'enfants (1)
- Discrete Logarithm (1)
- FID model (1)
- Factoring (1)
- Identification (1)
- Knapsack problem (1)
- Kochen-Specker theorem (1)
- Korkin—Zolotarev reduction (1)
- LLL-reduction (1)
- Lattice Reduction (1)
- Lattice basis reduction (1)
- Loewner monotonicity and convexity (1)
- Low density subset sum algorithm (1)
- Markov chain Monte Carlo Method (1)
- McEliece (1)
- Modular Multiplication (1)
- Non-Malleability (1)
- Noticeable Probability (1)
- Oracle Query (1)
- Prag <1999> (1)
- Private Information Retrieval (1)
- Public Key Cryptosystem (1)
- Public Parameter (1)
- Quadratic Residue (1)
- Random Oracle (1)
- Random String (1)
- Representation Problem (1)
- San Francisco (1)
- Santa Barbara (1)
- Security Parameter (1)
- Shortest lattice vector problem (1)
- Signature (1)
- Stable reduction algorithm (1)
- Subset sum problem (1)
- Thorne Kishino Felsenstein model (1)
- Trapdoor (1)
- cancer cell dormancy (1)
- compact Riemann surfaces (1)
- computational complexity (1)
- computational geometry (1)
- concurrent composition (1)
- cooperation (1)
- families of hash functions (1)
- finite resolution (1)
- hidden Markov model (1)
- highly regular nearby points (1)
- host-parasite population dynamics (1)
- hypervariable region (1)
- individual-based models (1)
- inner product (1)
- integer vector (1)
- invasion probability (1)
- invasion time (1)
- inverse coefficient problem, (1)
- local randomness (1)
- logarithmic geometry (1)
- multi-drug treatment (1)
- mutation parameter estimation (1)
- non-archimedean geometry (1)
- non-malleability (1)
- one-way functions (1)
- optimal transport (1)
- pair HMM (1)
- polynomial random number generator (1)
- random function generator (1)
- random geometric graph (1)
- random number generator (1)
- resistance mutation (1)
- security analysis of protocols (1)
- semidefinite optimization (1)
- sequence alignment (1)
- short integer relation (1)
- spatial host population structure (1)
- statistical alignment (1)
- stochastic population dynamics (1)
- subgroup growth (1)
- therapy evasion (1)
- treatment protocol design (1)
- treatment success (1)
- tropical geometry (1)
- tropical universal Jacobian (1)
- tropicalization (1)
- universal compactified Jacobian (1)
- von Neumann algebras (1)
Institute
Uniform sampling from the set G(d) of graphs with a given degree-sequence d=(d1,…,dn)∈Nn is a classical problem in the study of random graphs. We consider an analogue for temporal graphs in which the edges are labeled with integer timestamps. The input to this generation problem is a tuple D=(d,T)∈Nn×N>0 and the task is to output a uniform random sample from the set G(D) of temporal graphs with degree-sequence d and timestamps in the interval [1,T]. By allowing repeated edges with distinct timestamps, G(D) can be non-empty even if G(d) is, and as a consequence, existing algorithms are difficult to apply.
We describe an algorithm for this generation problem which runs in expected time O(M) if Δ2+ϵ=O(M) for some constant ϵ>0 and T−Δ=Ω(T) where M=∑idi and Δ=maxidi. Our algorithm applies the switching method of McKay and Wormald [1] to temporal graphs: we first generate a random temporal multigraph and then remove self-loops and duplicated edges with switching operations which rewire the edges in a degree-preserving manner.
Uniform sampling from the set G(d) of graphs with a given degree-sequence d=(d1,…,dn)∈Nn is a classical problem in the study of random graphs. We consider an analogue for temporal graphs in which the edges are labeled with integer timestamps. The input to this generation problem is a tuple D=(d,T)∈Nn×N>0 and the task is to output a uniform random sample from the set G(D) of temporal graphs with degree-sequence d and timestamps in the interval [1,T]. By allowing repeated edges with distinct timestamps, G(D) can be non-empty even if G(d) is, and as a consequence, existing algorithms are difficult to apply.
We describe an algorithm for this generation problem which runs in expected time O(M) if Δ2+ϵ=O(M) for some constant ϵ>0 and T−Δ=Ω(T) where M=∑idi and Δ=maxidi. Our algorithm applies the switching method of McKay and Wormald [1] to temporal graphs: we first generate a random temporal multigraph and then remove self-loops and duplicated edges with switching operations which rewire the edges in a degree-preserving manner.
n this paper we study invasion probabilities and invasion times of cooperative parasites spreading in spatially structured host populations. The spatial structure of the host population is given by a random geometric graph on [0,1]n, n∈N, with a Poisson(N)-distributed number of vertices and in which vertices are connected over an edge when they have a distance of at most rN∈Θ(Nβ−1n) for some 0<β<1 and N→∞. At a host infection many parasites are generated and parasites move along edges to neighbouring hosts. We assume that parasites have to cooperate to infect hosts, in the sense that at least two parasites need to attack a host simultaneously. We find lower and upper bounds on the invasion probability of the parasites in terms of survival probabilities of branching processes with cooperation. Furthermore, we characterize the asymptotic invasion time.
An important ingredient of the proofs is a comparison with infection dynamics of cooperative parasites in host populations structured according to a complete graph, i.e. in well-mixed host populations. For these infection processes we can show that invasion probabilities are asymptotically equal to survival probabilities of branching processes with cooperation.
Furthermore, we build in the proofs on techniques developed in [BP22], where an analogous invasion process has been studied for host populations structured according to a configuration model.
We substantiate our results with simulations.
Muller's ratchet, in its prototype version, models a haploid, asexual population whose size~N is constant over the generations. Slightly deleterious mutations are acquired along the lineages at a constant rate, and individuals carrying less mutations have a selective advantage. The classical variant considers {\it fitness proportional} selection, but other fitness schemes are conceivable as well. Inspired by the work of Etheridge et al. ([EPW09]) we propose a parameter scaling which fits well to the ``near-critical'' regime that was in the focus of [EPW09] (and in which the mutation-selection ratio diverges logarithmically as N→∞). Using a Moran model, we investigate the``rule of thumb'' given in [EPW09] for the click rate of the ``classical ratchet'' by putting it into the context of new results on the long-time evolution of the size of the best class of the ratchet with (binary) tournament selection, which (other than that of the classical ratchet) follows an autonomous dynamics up to the time of its extinction. In [GSW23] it was discovered that the tournament ratchet has a hierarchy of dual processes which can be constructed on top of an Ancestral Selection graph with a Poisson decoration. For a regime in which the mutation/selection-ratio remains bounded away from 1, this was used in [GSW23] to reveal the asymptotics of the click rates as well as that of the type frequency profile between clicks. We will describe how these ideas can be extended to the near-critical regime in which the mutation-selection ratio of the tournament ratchet converges to 1 as N→∞.
Using limit linear series on chains of curves, we show that closures of certain Brill-Noether loci contain a product of pointed Brill-Noether loci of small codimension. As a result, we obtain new non-containments of Brill-Noether loci, in particular that dimensionally expected non-containments hold for expected maximal Brill-Noether loci. Using these degenerations, we also give a new proof that Brill-Noether loci with expected codimension −ρ≤⌈g/2⌉ have a component of the expected dimension. Additionally, we obtain new non-containments of Brill-Noether loci by considering the locus of the source curves of unramified double covers.
We prove that the projectivized strata of differentials are not contained in pointed Brill-Noether divisors, with only a few exceptions. For a generic element in a stratum of differentials, we show that many of the associated pointed Brill-Noether loci are of expected dimension. We use our results to study the Auel-Haburcak Conjecture: We obtain new non-containments between maximal Brill-Noether loci in Mg. Our results regarding quadratic differentials imply that the quadratic strata in genus 6 are uniruled.
The free energy of TAP-solutions for the SK-model of mean field spin glasses can be expressed as a nonlinear functional of local terms: we exploit this feature in order to contrive abstract REM-like models which we then solve by a classical large deviations treatment. This allows to identify the origin of the physically unsettling quadratic (in the inverse of temperature) correction to the Parisi free energy for the SK-model, and formalizes the true cavity dynamics which acts on TAP-space, i.e. on the space of TAP-solutions. From a non-spin glass point of view, this work is the first in a series of refinements which addresses the stability of hierarchical structures in models of evolving populations.
Muller's ratchet, in its prototype version, models a haploid, asexual population whose size~N is constant over the generations. Slightly deleterious mutations are acquired along the lineages at a constant rate, and individuals carrying less mutations have a selective advantage. The classical variant considers {\it fitness proportional} selection, but other fitness schemes are conceivable as well. Inspired by the work of Etheridge et al. ([EPW09]) we propose a parameter scaling which fits well to the ``near-critical'' regime that was in the focus of [EPW09] (and in which the mutation-selection ratio diverges logarithmically as N→∞). Using a Moran model, we investigate the``rule of thumb'' given in [EPW09] for the click rate of the ``classical ratchet'' by putting it into the context of new results on the long-time evolution of the size of the best class of the ratchet with (binary) tournament selection, which (other than that of the classical ratchet) follows an autonomous dynamics up to the time of its extinction. In [GSW23] it was discovered that the tournament ratchet has a hierarchy of dual processes which can be constructed on top of an Ancestral Selection graph with a Poisson decoration. For a regime in which the mutation/selection-ratio remains bounded away from 1, this was used in [GSW23] to reveal the asymptotics of the click rates as well as that of the type frequency profile between clicks. We will describe how these ideas can be extended to the near-critical regime in which the mutation-selection ratio of the tournament ratchet converges to 1 as N→∞.
Motivated by the question of the impact of selective advantage in populations with skewed reproduction mechanims, we study a Moran model with selection. We assume that there are two types of individuals, where the reproductive success of one type is larger than the other. The higher reproductive success may stem from either more frequent reproduction, or from larger numbers of offspring, and is encoded in a measure Λ for each of the two types. Our approach consists of constructing a Λ-asymmetric Moran model in which individuals of the two populations compete, rather than considering a Moran model for each population. Under certain conditions, that we call the "partial order of adaptation", we can couple these measures. This allows us to construct the central object of this paper, the Λ−asymmetric ancestral selection graph, leading to a pathwise duality of the forward in time Λ-asymmetric Moran model with its ancestral process. Interestingly, the construction also provides a connection to the theory of optimal transport. We apply the ancestral selection graph in order to obtain scaling limits of the forward and backward processes, and note that the frequency process converges to the solution of an SDE with discontinous paths. Finally, we derive a Griffiths representation for the generator of the SDE and use it to find a semi-explicit formula for the probability of fixation of the less beneficial of the two types.