Splitting pairs and the number of clusters generated by random pair incompatibilities
Skip to main content
eScholarship
Open Access Publications from the University of California

Splitting pairs and the number of clusters generated by random pair incompatibilities

  • Author(s): Pitman, Damien
  • et al.

Published Web Location

https://arxiv.org/pdf/math/0701656.pdf
No data is associated with this publication.
Abstract

We consider a random fitness landscape on the space of haploid diallelic genotypes with n genetic loci, where each genotype is considered either inviable or viable depending on whether or not there are any incompatibilities among its allele pairs. We suppose that each allele pair in the set of all possible allele pairs on the n loci is independently incompatible with probability p=c/(2n). We examine the connectivity of the viable genotypes under single locus mutations and show that, for 01, there are no viable genotypes with probability converging to one. The genotype space is equivalent to the n-dimensional hypercube and the viable genotypes are solutions to a random 2-SAT problem, so the same result holds for the connectivity of solutions in the hypercube to a random 2-SAT problem.

Item not freely available? Link broken?
Report a problem accessing this item