John Lapinskas

John Lapinskas

Auto-generated profile, based on publicly available information

John Lapinskas

University of Oxford

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
28 February 2017 in Journal of the ACM
Verified
Journal Article
Open access
PDF file
AGAndreas Galanis
Andreas Galanis
AGAndreas Göbel
Andreas Göbel
LGLeslie Ann Goldberg
Leslie Ann Goldberg
JLJohn Lapinskas
John Lapinskas
DRDavid Richerby
David Richerby
The Moran process, as studied by Lieberman, Hauert, and Nowak, is a randomised algorithm modelling the spread of genetic mutations in populations. The algorithm runs on an underlying graph where individuals correspond to vertices. Initially, one vertex (chosen uniformly at random) possesses a mutation, with fitness r > 1. All other individuals have fitness 1. During each step of the algorithm, an individual is chosen with probability proportional to its fitness, and its state (mutant or nonmutant) is passed on to an out-neighbour which is chosen uniformly at random. If the underlying graph is strongly connected, then the algorithm will eventually reach fixation , in which all individuals are mutants, or extinction , in which no individuals are mutants. An infinite family of directed graphs is said to be strongly amplifying if, for every r > 1, the extinction probability tends to 0 as the number of vertices increases. A formal definition is provided in the article. Strong amplification is a rather surprising property—it means that in such graphs, the fixation probability of a uniformly placed initial mutant tends to 1 even though the initial mutant only has a fixed selective advantage of r > 1 (independently of n ). The name “strongly amplifying” comes from the fact that this selective advantage is “amplified.” Strong amplifiers have received quite a bit of attention, and Lieberman et al. proposed two potentially strongly amplifying families—superstars and metafunnels. Heuristic arguments have been published, arguing that there are infinite families of superstars that are strongly amplifying. The same has been claimed for metafunnels. In this article, we give the first rigorous proof that there is an infinite family of directed graphs that is strongly amplifying. We call the graphs in the family “megastars.” When the algorithm is run on an n -vertex graph in this family, starting with a uniformly chosen mutant, the extinction probability is roughly n − 1/2 (up to logarithmic factors). We prove that all infinite families of superstars and metafunnels have larger extinction probabilities (as a function of n ). Finally, we prove that our analysis of megastars is fairly tight—there is no infinite family of megastars such that the Moran algorithm gives a smaller extinction probability (up to logarithmic factors). Also, we provide a counterexample which clarifies the literature concerning the isothermal theorem of Lieberman et al.

1 February 2019 in Theoretical Computer Science
Verified
Journal Article
Closed access
LGLeslie Ann Goldberg
Leslie Ann Goldberg
JLJohn Lapinskas
John Lapinskas
JLJohannes Lengler
Johannes Lengler
FMFlorian Meier
Florian Meier
KPKonstantinos Panagiotou
Konstantinos Panagiotou
PPPascal Pfister
Pascal Pfister

23 June 2014 in Combinatorica
Verified
Journal Article
Closed access
PDF file
DHDan Hefetz
Dan Hefetz
DKDaniela Kühn
Daniela Kühn
JLJohn Lapinskas
John Lapinskas
DODeryk Osthus
Deryk Osthus

29 May 2014 in Proceedings of the London Mathematical Society
Verified
Journal Article
Open access
PDF file
DKDaniela Kühn
Daniela Kühn
JLJohn Lapinskas
John Lapinskas
DODeryk Osthus
Deryk Osthus
VPViresh Patel
Viresh Patel
A conjecture of Thomassen from 1982 states that, for every <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> k , there is an <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> f ( k ) so that every strongly <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> f ( k ) ‐connected tournament contains <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> k edge‐disjoint Hamilton cycles. A classical theorem of Camion, that every strongly connected tournament contains a Hamilton cycle, implies that <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> f ( 1 ) = 1 . So far, even the existence of <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> f ( 2 ) was open. In this paper, we prove Thomassen's conjecture by showing that <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> f ( k ) = O ( k 2 log 2 k ) . This is best possible up to the logarithmic factor. As a tool, we show that every strongly <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> 10 4 k log k ‐connected tournament is <!--${MathJax: TeX-AMS-MML_HTMLorMML}--> k ‐linked (which improves a previous exponential bound). The proof of the latter is based on a fundamental result of Ajtai, Komlós and Szemerédi on asymptotically optimal sorting networks.

20 December 2012 in Combinatorics, Probability and Computing
Verified
Journal Article
Closed access
PDF file
DKDaniela Kühn
Daniela Kühn
JLJohn Lapinskas
John Lapinskas
DODeryk Osthus
Deryk Osthus
We study the number of edge-disjoint Hamilton cycles one can guarantee in a sufficiently large graph G on n vertices with minimum degree δ=(1/2+α)n. For any constant α>0, we give an optimal answer in the following sense: let regeven(n,δ) denote the degree of the largest even-regular spanning subgraph one can guarantee in a graph on n vertices with minimum degree δ. Then the number of edge-disjoint Hamilton cycles we find equals regeven(n,δ)/2. The value of regeven(n,δ) is known for infinitely many values of n and δ. We also extend our results to graphs G of minimum degree δ ≥ n/2, unless G is close to the extremal constructions for Dirac's theorem. Our proof relies on a recent and very general result of Kühn and Osthus on Hamilton decomposition of robustly expanding regular graphs.

2 January 2015 in The Electronic Journal of Combinatorics
Verified
Journal Article
Open access
PDF file
JCJoanna Cyman
Joanna Cyman
TDTomasz Dzido
Tomasz Dzido
JLJohn Lapinskas
John Lapinskas
ALAllan Lo
Allan Lo
Consider a game played on the edge set of the infinite clique by two players, Builder and Painter. In each round, Builder chooses an edge and Painter colours it red or blue. Builder wins by creating either a red copy of $G$ or a blue copy of $H$ for some fixed graphs $G$ and $H$. The minimum number of rounds within which Builder can win, assuming both players play perfectly, is the on-line Ramsey number $\tilde{r}(G,H)$. In this paper, we consider the case where $G$ is a path $P_k$. We prove that $\tilde{r}(P_3,P_{\ell+1}) = \lceil 5\ell/4\rceil = \tilde{r}(P_3,C_{\ell})$ for all $\ell \ge 5$, and determine $\tilde{r}(P_4,P_{\ell+1})$ up to an additive constant for all $\ell \ge 3$. We also prove some general lower bounds for on-line Ramsey numbers of the form $\tilde{r}(P_{k+1},H)$.