2017/12/25 by Manoj Changat, Prasanth G. Narasimha-Shenoi, Changat, Manoj +11
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Advanced Control Systems Optimization #Artificial intelligence #Combinatorics #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computer science #Crossover #Discrete Mathematics (cs.DM) #Engineering #FOS: Computer and information sciences #FOS: Mathematics #Gene Regulatory Network Analysis #Geometry #Mathematics #Metric Geometry (math.MG) #Physics #Point (geometry) #Political science #Public transport #Representation (politics) #Statistical physics #Topology (electrical circuits) #Transit (satellite) #Transport engineering #cs.DM #math.CO #math.MG
paper · pdf · doi:10.48550/arxiv.1712.09022
arxiv created 2017/12/25 · openalex publication_date 2017/12/25 · arxiv updated 2017/12/27 · openalex created_date 2018/01/05 · openalex updated_date 2026/07/28
k-point crossover operators and their recombination sets are studied from different perspectives. We show that transit functions of k-point crossover generate, for all k>1, the same convexity as the interval function of the underlying graph. This settles in the negative an open problem by Mulder about whether the geodesic convexity of a connected graph G is uniquely determined by its interval function I. The conjecture of Gitchoff and Wagner that for each transit set Rk(x,y) distinct from a hypercube there is a unique pair of parents from which it is generated is settled affirmatively. Along the way we characterize transit functions whose underlying graphs are Hamming graphs, and those with underlying partial cube graphs. For general values of k it is shown that the transit sets of k-point crossover operators are the subsets with maximal Vapnik-Chervonenkis dimension. Moreover, the transit sets of k-point crossover on binary strings form topes of uniform oriented matroid of VC-dimension k+1. The Topological Representation Theorem for oriented matroids therefore implies that k-point crossover operators can be represented by pseudosphere arrangements. This provides the tools necessary to study the special case k=2 in detail.