Topological Representation of the Transit Sets of k-Point Crossover Operators
Manoj Changat Prasanth G. Narasimha-Shenoi Ferdoos Hossein Nezhad Matjaž Kovše Shilpa Mohandas Abisha Ramachandran Peter F. Stadler
math.CO cs.DM math.MG








Topological Representation of the Transit Sets of 
       k-Point Crossover Operators



Manoj Changat[Department of Futures Studies, 
  University of Kerala, Trivandrum, IN 695 581, India, {mchangat,ferdows.h.n,rshilpam,cyanabisha}@gmail.com],
        Prasanth G. Narasimha-Shenoi[Department of Mathematics, 
  Government College, Chittur, Palakkad, IN 678 104, India, prasanthgns@gmail.com],
        Ferdoos Hossein Nezhad1,

        Matjaž Kovše[School of Basic Sciences, IIT Bhubaneswar, Bhubaneswar, India, kovse@iitbbs.ac.in],
        Shilpa Mohandas1, 
        Abisha Ramachandran1,
        Peter F. Stadler 
[Bioinformatics Group, Department of Computer Science &
  Interdisciplinary Center for Bioinformatics, Universität Leipzig,
  Härtelstraße 16-18, D-04107 Leipzig, Germany; 
  German Centre for Integrative Biodiversity Research 
  (iDiv) Halle-Jena-Leipzig, Competence Center for Scalable Data
  Services and Solutions Dresden-Leipzig, Leipzig Research Center for 
  Civilization Diseases, and Centre for Biotechnology and Biomedicine at 
  Leipzig University at Universität Leipzig;
  Max Planck Institute for Mathematics in the Sciences, Inselstraße 22,
  D-04103 Leipzig, Germany; 
  RNomics Group, Fraunhofer Institute for Cell Therapy and Immunology,
  D-04103 Leipzig, Germany;
  Institute for Theoretical Chemistry, University of Vienna,
  Währingerstrasse 17, A-1090 Wien, Austria;
  Santa Fe Insitute, 1399 Hyde Park Rd., Santa Fe NM 87501, USA., studla@bioinf.uni-leipzig.de]


 









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 R_k(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.











§ INTRODUCTION


Crossover operators are a crucial component of Genetic Algorithms and
related approaches in Evolutionary Computation. Their purpose is to combine
the genetic information of two parents to produce one or more offsprings
that are “mixtures” of their parents. In this contribution we will be
concerned with the specific setting of crossover operators for strings of
fixed length n over an alphabet 𝒜 of a≥ 2 letters. Given
two parental strings x=(x_1x_2… x_n) and y=(y_1y_2… y_n) one
may for instance construct recombinant offsprings of the form (x_1x_2…
x_iy_i+1y_i+2… y_n) and (y_1y_2… y_ix_i+1x_i+2…
x_n). The index i serves as a breakpoint at which the two parents
recombine. This so-called one-point crossover can be generalized to two or
more breakpoints.

  Given x,y,z∈𝒜^n we say that z is a k-point crossover
  offspring of x and y if there are indices
  0=i_0≤ i_1≤ i_2 ≤ i_k=n so that
  for all ℓ, 1≤ℓ≤ k, either
  z_j=x_j for all j∈{i_ℓ-1+1,…, i_ℓ} or
  z_j=y_j for all j∈{i_ℓ-1+1,…, i_ℓ}.

Note that this definition states that x and y are broken up into
at most k intervals that are alternately included into z.  This
convention simplifies the mathematical treatment considerably and also
conforms to the usual practice of including crossovers with fewer than the
maximum number of breakpoints. Uniform crossover, where each letter z_i
is freely chosen from one of the two parents, is obtained by allowing
k=n-1 breakpoints. We note, furthermore, that our definition ensures that
the parental strings are also included in the set of possible offsprings.

Properties of k-point crossover have been studied extensively in the
past. <cit.> described key algebraic properties and
isomorphisms between the search spaces induced by crossover and mutation
with small populations have been analyzed by <cit.>. A formal
treatment of multi-point crossover with an emphasis on disruption analysis
can be found in <cit.>. A general review of genetic algorithms
from the perspective of stochastic processes on populations can be found in
<cit.>. In this context, crossover operators are represented by
stochastic matrices. A similar matrix-based formalism is explored in
<cit.>. Coordinate transformations, more precisely the Walsh
transform <cit.> and its generalizations to non-binary
alphabets <cit.> have played an important role in explaining the
functioning of GAs in terms of building blocks and the Schema theorem
<cit.>.  As a generalization, an abstract treatment of crossover
in terms of equivalence relations has been given by <cit.>.

<cit.> proposed to consider the function R: X× X→ 2^X
that assigns to each possible pair of parents the set of all possible
recombinants. They asked which properties of R could be used to
characterize crossover operators in general and explored properties of
k-point crossover on strings. In particular, they noted the following
four properties:


  (T1)  x,y∈ R(x,y) for all x,y∈ X,

  (T2)  R(x,y)=R(y,x) for all x,y∈ X,

  (T3)  R(x,x)={x} for all x∈ X,

  (GW4) z∈ R(x,y) implies |R(x,z)|≤|R(x,y)|.

Mulder introduced the concept of transit functions
characterized by the axioms (T1), (T2), and (T3) as a unifying approach to
intervals, convexities, and betweenness in graphs and posets in last decade
of the 20th century. Available as preprint only but frequently cited for
more than a decade, the seminal paper was published only recently
<cit.>. For example, given a connected graph G, its geodetic
intervals, i.e., the sets of vertices lying on shortest paths between a
pair of prescribed endpoints x,y∈ V(G) form a transit function usually
denoted by I_G(x,y) <cit.> and referred as the interval function of a graph G. Unequal crossover, where (T3)
is violated, has been rarely explored in the context of evolutionary
computation, which the exception of the work by <cit.>. In this
contribution we restrict ourselves exclusively to the simpler case of
homologous string recombination.  Thus, from here on we will assume
  that R satisfies (T1), (T2), and (T3).

A common interpretation of transit functions is to view R(x,y) as the
subset of X lying  x and y. Indeed, a transit
function is a betweenness if it satisfies the two additional axioms


  (B1) z∈ R(x,y) and z y implies y∉ R(x,z).

  (B2) z∈ R(x,y) implies R(x,z)⊆ R(x,y).

It is natural, therefore, to regard a pair of distinct points x and y
without other points between them as adjacent. The corresponding
graph G_R has X as its vertex set and {x,y}∈ E(G_R) if and only
if R(x,y)={x,y} and x y. The graph G_R is known as the
underlying graph of R.

<cit.> introduced the notion of geometric crossover
  operators relative to a connected reference graph G with vertex set
X by requiring – in our notation – that R(x,y)⊆ I_G(x,y) for
all x,y∈ X. In the setting of <cit.>, the reference graph
G was given externally in terms of a metric on X. When studying
crossover in its own right it seems natural to consider the transits sets
of R in relation to the intervals of G_R itself.  Hence we say that R
is MP-geometric if

  
  (MG) R(x,y)⊆ I_G_R(x,y) for all x,y∈ X.

Note the condition (MG) is an axiom for transit functions independent of
any externally prescribed structure on X. <cit.> considered a
different notion of “geometric” referring transit functions that satisfy
(B2) and the axiom


  (B3) z∈ R(x,y) and w∈ R(x,z) implies z∈ R(w,y).

Mulder's version of “geometric” is less pertinent for our purposes
because crossover operators usually violate (B2).

Another interpretation of R, which is just as useful in the context of
crossover operators, is to regard R(x,y) as the set of offsprings
reachable from the parents x and y in a single generation. It is
natural then to associate with R a function R: X× X→
2^X so that z∈R(x,y) if and if only z eventually can be generated
from x and y and all their following generations of
offsprings. Formally, z∈R(x,y) if there is a finite sequence
of pairs {x_k,y_k} so that z∈ R(x_m,y_m), {x_k,y_k}∈
R(x_k-1,y_k-1) for all k=1,…, m, x_0=x, and y_0=y.  By
construction, R(x,y)⊆R(x,y) for all x,y∈ X.  If
R is a transit function, then R is also a transit function.

We say that R(x,y) is closed if R(x,y)=R(x,y).
Equivalently, a transit set R(x,y) is closed if and only if
R(u,v)⊆ R(x,y) holds for all u,v∈ R(x,y), since in this case
nothing can be generated from the children of x and y that is not
accessible already from x and y itself. In particular, all singletons
and all adjacencies, i.e., individual vertices and the edges of G_R, are
always closed. A transit function R is called monotone if it
satisfies


  (M) For all x,y∈ X and u,v∈ R(x,y) implies R(u,v)⊆
  R(x,y),

i.e., if all transit sets are closed. By construction, R
satisfies (M) for any transit function R. A simple argument[(i)
  R(x,y)⊆R(x,y) by definition, (ii) R(x,y)={x,y}
  implies R(x,y)={x,y}, (iii) if R(x,y)={x,y}
  but R(x,y){x,y} either (i) or axiom (T1) is violated.] shows that
R(x,y)={x,y} if and only if R(x,y)={x,y}. Thus R and
R have the same underlying graph G_R=G_R. The
sets {R(x,y) | x,y∈ X }, finally, generate a convexity
ℭ_R consisting of all intersections of the (finitely many)
transit sets R(x,y).

One of the most fruitful lines of research in the field of transit
functions is the search for axiomatic characterizations of a wide variety
of different types of graphs and other discrete structures in terms of
their transit functions.  <cit.> showed that a function I: V
× V → 2^V is the geodesic interval function of a
connected graph if and only if I satisfies a set of axioms that are
phrased in terms of I only.  Later, <cit.> improved the
axiomatic characterization of I(u,v) by formulating a nice set of
(minimal) axioms. The all-paths function A of a connected graph G
(defined as A(u,v)= {z∈ V(G): z lies on some u,v-path in G})
admits a similar axiomatic characterization <cit.>.  These
results immediately raise the question whether other types of transit
functions can be characterized in terms of transit axioms only.

Since k-point crossover on strings over a fixed alphabet forms a rather
specialised class of recombination operators we ask here whether it can
be defined completely in terms of properties of its transit function
R_k. Beyond the immediate interest in k-point crossover operators we
can hope in this manner to identify generic properties of crossover
operators also on more general sets X.

This contribution is organised as follows. In section <ref> we
consider transit functions whose underlying graphs G_R are Hamming
graphs since, as we show in section <ref>, k-point crossover
belongs to this class. We then investigate the properties of k-point
crossover in more detail from the point of view of transit functions.  In
section <ref> we switch to a graph-theoretical perspective and
derive a complete characterization of k-point crossover on binary
alphabets, making use of key properties of partial cubes. In order to
generalize these results we consider topological aspects of k-point
crossover in section <ref> and explore its relationship
with oriented matroids. We conclude our presentation with several open
questions.



§ HAMMING GRAPHS AND THEIR GEODESIC INTERVALS



In most applications, k-point crossover will be applied to binary strings
or, less frequently, to strings over a larger, fixed-size alphabet
𝒜. In a population genetics context, however, the number of
allels may be different for each locus, hence we consider the most general
case here, where each sequence position is taken from a distinct alphabet
𝒜_i with a_i:=|𝒜_i|≥2 for 1≤ i n. The
Hamming graph ∏_i K_a_i is the Cartesian products of complete
graphs K_a_i with a_i vertices; we refer to the book by
<cit.> for more details on Hamming graphs and
product graphs in general. The special case a_i=2 for all i is usually
called n-dimensional hypercube K_2^n. The shortest path distance on
∏_i K_a_i is the Hamming distance d(x,y), which counts the number
of sequence positions at which the string x and y differ.

Given a transit function R and a point x ∈ X let δ(x)=|{y ∈
X    |    |R(x,y)|=2}|, i.e., δ(x)=δ_R(x) is the degree
of x in the underlying graph G_R. We write δ(R) = max_x∈ Xδ(x) for the maximal degree of the underlying graph.

The purpose of this section is to characterize transit functions whose
underlying graphs are Hamming graphs. Our starting point is the following
characterization of hypercubes, which follows from results by
<cit.> and <cit.>:


  Suppose G is connected and each pair of distinct adjacent edges lies in
  exactly one 4-cycle. Then G is isomorphic to n-dimensional hypercube
  if and only if the minimum degree δ of G is finite and |V(G)|=
  2^δ.




Graphs with the property that any pair of vertices has zero or exactly 2
common neighbours are called (0,2)-graphs <cit.>. We note
that the condition |V(G)|=2^δ in Proposition <ref>
is necessary as demonstrated by the example in Fig. <ref>.
Proposition <ref> can be translated into the language of
transit functions as follows:


  Let R be a transit function on a set X with a connected underlying
  graph. Then the underlying graph G_R is isomorphic to n-dimensional
  hypercube K_2^n if and only if R satisfies:
  
  
  (A1) For every x,u,v such that |R(x,u)|=|R(x,v)|=2 there exist
    unique y such that |R(y,u)|=|R(y,v)|=2,
  
  (A2)  δ(R)=n and |X|=2^n.
  

Later, <cit.> generalized Proposition <ref> to
arbitrary Hamming graphs. For any vertex x in the graph G let N_i(x)
denote the number of maximal i-cliques K_i in G that contain the
vertex x.



  Let G be a simple connected graph such that two non-adjacent vertices
  in G either have exactly 2 common neighbors or none at all, and
  suppose G has neither K_4 ∖ e nor K_2  K_3 ∖ e
  (Figure <ref>) as induced subgraph.  Then
  N_i(x) is independent of x and G is isomorphic to the Hamming graph
  if and only if |V(G)|=∏_h=1^ph^N_i(x), where p is the
  maximum integer such that N_p(x) is nonzero.




These results can again be translated into the language of transit
functions:

  
  Let R be a transit function with a connected underlying graph. Then the
  underlying graph G_R is isomorphic to Hamming graph K_a^n if and only
  if R satisfies:
  
  
  (A1) For every x,u,v such that |R(x,u)|=|R(x,v)|=2 there
    exists unique y such that |R(y,u)|=|R(y,v)|=2,
  
  (A2')  δ(R)=n(a-1) and |X|=a^n,
  
  (A3) There exist no x,y,u,v such that
    |R(x,u)|=|R(x,v)|=|R(y,u)|=|R(y,v)|=|R(x,y)|=2 and |R(u,v)|>2,
  
  (A4) There exist no x,y,u,v, w, z such that

    |R(x,u)|=|R(x,v)|=|R(y,u)|=|R(y,v)|=|R(v,w)|=|R(y,z)|=|R(w,z)|=|R(x,w)|=2
    and 
    |R(u,v)|, |R(u,w)|,|R(u,z)|,|R(x,y)|,|R(x,z)|,|R(v,z)|,|R(y,w)| > 2.



The representation of Hamming graphs as n-fold Cartesian products of
complete graphs H=∏_i=1^n K_a_i implies a “coordinatization”,
that is, a labeling of the vertices the reflects this product structure.
The geodesic intervals in Hamming graphs then have very simple description:

    I_H(x,y) = { z = (z_1,z_2,… z_n) | z_i∈{x_i,y_i} for  
      1≤ i≤ n }

where (x_1,x_2,… x_n) and (y_1,y_2,… y_n) are the coordinates
of the vertices x and y.  Thus G_I_H(x,y) is a subhypercube of
dimension d(x,y) as shown in example in the book by
<cit.>.  The intervals of Hamming graphs have
several properties that will be useful for our purposes.  A graph is called
antipodal if for every vertex v there is a unique “antipodal vertex”
v̅ with maximum distance from v.


  Let Q be an induced sub-hypercube of a Hamming graph H.  Then for
  every x∈ Q there is a unique vertex x̅∈ Q so that Q =
  I_H(x,x̅).


  This follows from a well known fact that hypercubes are antipodal graphs
  <cit.>.
  
It is well known that I_H satisfies the monotone axiom (M) and thus
also (B2).


  Let Q' and Q” be two induced sub-hypercubes in a Hamming graph
  H. Then Q'∩ Q” is again an induced (possibly empty) sub-hypercube
  of H.


  For every coordinate i, Q_i'={x_i|x'∈ Q} and Q_i”={x_i|x∈
  Q”} contains at most two different letters from the alphabet
  𝒜_i. Q'∩ Q”=∏_i (Q_i'∩ Q_i”), and hence a
  hypercube.
  
As an immediate consequence we note that I_H satisfies even the stronger
property


  (MM) For all u,v,x,y∈ X holds: if R(u,v)∩
  R(x,y)∅ then there are p,q∈ X so that R(u,v)∩
  R(x,y)=R(p,q).


The disadvantage of the results so far is that we have to require
explicitly that G_R is connected. In the light of condition (MG) above
it seems natural to require connectedness of G_R for recombination
operators in general.

To-date, only sufficient conditions for connectedness of G_R are
known. Following ideas outlined by <cit.>, we can show
directly that the following property is sufficient:


  (CG) For all a,x,y,z ∈ X:
  If R(a,x) ⊆ R(a,y), then
  R(a,x) ⊆ R(a,z)⊆ R(a,y) if and only if z ∈ R(x,y).

As a technical device we will employ the partial order ≤_a of X
defined, for given a∈ X, by x ≤_a y if and only if R(a,x)
⊆ R(a,y). As usual, we write x <_ay if x ≤_a y and
x≠ y. For R=I_G we have the equivalence x ∈ I_G(a,y) if and if only
x≤_a y.


  The underlying graph G_R of a transit function R is connected if R
  satisfies axiom (CG).


  Let R be a transit function satisfying axiom (CG). Let a,b ∈ X be
  two distinct elements, and let 𝐂=(a=a_0,a_1,… a_t=b) be a
  maximal ≤_a-chain between a and b, where the elements are
  labeled in increasing order a=a_0 <_a a_1 <_a a_2 <_a … <_a a_t=b.

  We claim that, for any i, 0≤ i ≤ n, elements a_i and
  a_i+1 form an edge in G_R. To see this assume that, on the
  contrary, there is an element x ∈ R(a_i,a_i+1) ∖{a_i,a_i+1} for some i.  Then (CG) implies R(a,a_i) ⊆
  R(a,x)⊆ R(a,a_i+1), i.e., a_i <_a x <_a x_i+1,
  contradicting maximality of the chain 𝐂. Hence 𝐂
  consists of consecutive edges whence G_R is a connected graph.
  

However, property (CG) is much too strong for our purposes: Setting x=a
makes the condition in (CG) trivial, i.e., the axiom reduces to
“R(a,z)⊆ R(a,y) if and only if z∈ R(a,y)”. Since
R(a,z)⊆ R(a,y) implies z∈ R(a,y) we are simply left with
axiom (B2), i.e., (CG) implies (B2). As we shall see below, however, string
crossover in general does not satisfy (B2) and thus (CG) cannot not hold in
general.  Similarly, we cannot use Lemma 1 of <cit.>, which
states that G_R is connected whenever R is a transit function
satisfying (B1) and (B2).

Allowing conditions not only on R but also on its closure R
we can make use of the fact that  G_R=G_R. Since
R satisfies the monotonicity axion (M) by construction, (B2) is
also satisfied. Thus R_G is connected if at least one of the following
two conditions is satisfied: (i) R satisfies (B1), or
(ii)  R satisfies


  (CG') x∈R(a,z) and z∈R(a,y) if and only
  if z∈R(x,y)

The latter is equivalent to (CG) whenever R satisfies (M). To see this
observe that R(a,x) ⊆ R(a,y) implies x∈ R(a,y) and by (M)
R(x,y)⊆ R(a,y).

So far, we lack a condition for the connectedness of G_R that can be
expressed by first order logic in terms of R alone.



§ BASIC PROPERTIES OF K-POINT CROSSOVER



We first show that the underlying graphs of k-point crossover transit
functions are Hamming graphs.


  G_R_k = ∏_i=1^n K_a_i for all 1≤ k≤ n-1.


  Since R_j(x,y)⊆ R_k(x,y) for j≤ k by definition, it
  suffices to consider R_1. By definition, R_1(x,y)={x,y} if and only
  if x and y differ in a single coordinate, i.e., for which d(x,y)=1,
  i.e., x and y are adjacent in ∏_i=1^n K_a_i.  Obviously,
  R_k(x,y)=R_1(x,y) in this case.  If there are two or more sequence
  positions that are different between the parents, then the crossover
  operator can “cut” between them to produce and generate an off-spring
  different from either parent so that |R_1(x,y)|>2.
  

From Lemma <ref> and Corollary <ref> we immediately
conclude that the k-point crossover transit function R_k satisfies
(A1), (A2'), (A3), and (A4).


  
  Let R_k be the k-point crossover function. Then R_k(x,y) =
  I_G_R_k(x,y) for all x,y∈ X and all k≥ 1.


  By construction z∈R_k(x,y) agrees in each position with at
  least one of the parents, i.e., z_i∈{x_i,y_i} for 1≤ i≤ n,
  and thus R_k(x,y) ⊆ I_G_R(x,y). Conversely, choose
  an arbitrary z∈ I_G(x,y). Find the first position k in the
  coordinate representation in which z disagrees with x and form the
  recombinant y'∈ R_1(x,y) that agrees with x for i<k and with y
  for all i≥ k.  Then form the x'∈ R_1(x,y')⊆R_1(x,y) by recombining again after position k. By
  construction, x' agrees with z at least for all i≤ k, i.e., in at
  least one position more than x. Since x'∈R_1(x,y) we can
  repeat the argument at most n time to find a sequence x^(n)∈R_1(x,y) that agrees with z in all positions. Since
  R_1(x,y)⊆ R_k(x,y) for all k≥ 1, we conclude that z∈R_k(x,y).
  
As an immediate corollary we have:

  k-point crossover is MP-geometric for all k≥ 1.

MP-geometricity is a desirable property for crossover operators in general
because it ensures that repeated application eventually produces the entire
geodesic interval of the underlying graph structure.

Lemma <ref> also implies a negative answer to one of the
questions posed by <cit.>: “Is the geodesic convexity uniquely
determined by the geodesic interval function I(u,v) of a connected
graph?”. More precisely, Lemma <ref> shows that the k-point
crossover transit function R_k also generates the geodesic convexity and
hence that the geodesic convexity is not uniquely determined by the
interval function I as the I_G_R_k(x,y), being the interval in a
hypercube, is itself convex.

A trivial consequence of Lemma <ref>, furthermore, is the well
known fact that the transit function of uniform crossover R_n-1 is the
interval function on the Hamming graph:

  R_n-1(x,y)=R_n-1(x,y) = I_G_R(x,y) for all x,y∈ X.

For small distances, k-point crossover also produces the full geodesic
interval in a single step:
 
  R_k(x,y)=I_G_R(x,y) if and only if d(x,y)≤ k+1.


  If d(x,y)≤ k+1 we can place one cross-over cut between any two
  position at which x and y differ. In this way we obtain all possible
  recombinations, i.e., R_k(x,y) is a subhypercube of dimension k+1 in
  the underlying graph G_R. Conversely if  d(x,y) > k+1 then there is
  z ∈ I_G_R(x,y) such that z requires more than k cross-over
  cuts between positions at which x and y, which completes the proof.
  

Next, we observe that the transit sets of k-point crossover can be
constructed recursively.

R_k(u,v)= ⋃_z ∈ R_k-1(u,v)[R_1(u,z) ∪ R_1(z,v)].


  W.l.o.g we can assume that u= 0 … 0 and v= 1 … 1.  Let a ∈
  R_k(u,v) and without loss of generality we can assume that a ends with
  0. Let a_j denote the coordinate, with the last appearance of 1 in
  a. Let b be an element with b_i=a_i for 1 ≤ i ≤ j and
  b_i=1 otherwise. It follows that b ∈ R_k-1(u,v) and moreover a
  ∈ R_1(b,v).
  

A key property in the theory of transit functions is the so-called Pasch
axiom


  (Pa) For p, a, b∈ X, a'∈ R(p,a) and b'∈ R(p,b) implies
  that R(a',b)∩ R(b',a) ≠∅.






R_1 satisfies the Pasch axiom (Pa).


  Consider three arbitrary strings a, b, and p. Then a'∈ R_1(a,p)
  is a concatenation of a prefix of a with the corresponding suffix of
  p, or vice versa. Each b'∈ R_1(b,p) has an analogous
  representation, leading to four cases depending on whether p is a prefix
  or a suffix of a' and b', resp., see Fig. <ref>. In case 1,
  a'∈ R_1(b',a) if a' has a shorter p-suffix than b'. Otherwise
  b'∈ R_1(a',b).  In case 2, a' has a p-prefix up to k and b'
  has a p-suffix starting at l. If the two parts of p overlap, i.e.,
  l≤ k then (b_1… b_l,p_l+1… p_k,a_k+1… a_n)∈
  R_1(b,a')∩ R_1(a,b'). If k<l then a common crossover product is
  obtained by recombining both b with a' and a with b' at position
  k. Case 3, a' has a p-suffix and b' has an p-prefix, can be
  treated analogously. Case 4, in which p matches a prefix of both a'
  and b' can be treated as in case 1. In summary, thus R_1(a',b)∩
  R_1(a,b')∅ for any choice of a'∈ R_1(a,p) and b'∈
  R_1(b,p), i.e., R_1 satisfies (Pa).
  


  R_k satisfies axiom (Pa) for all k≥1.


For fixed a,b,p let a'∈ R_k(a,p) and b'∈ R_k(b,p).
By Theorem <ref> we have

    R_k(a',b) = ⋃_z∈ R_k-1(a',b)[ R_1(a',z)∪ R_1(z,b) ]     
       R_k(a,b') = ⋃_y∈ R_k-1(a,b')[ R_1(b',y)∪ R_1(y,a) ]

and hence

    R_k(a',b)∩ R_k(a,b') = 
       ( ⋃_z∈ R_k-1(a',b)[ R_1(a',z)∪ R_1(z,b) ] ) ∩( ⋃_y∈ R_k-1(a,b')[ R_1(b',y)∪ R_1(y,a) ] )
     = 
       (
    ( ⋃_z∈ R_k-1(a',b)[ R_1(a',z)∪ R_1(z,b) ] ) ∩( ⋃_y∈ R_k-1(a,b') R_1(b',y) )
    )
       ∪
       (
    ( ⋃_z∈ R_k-1(a',b)[ R_1(a',z)∪ R_1(z,b) ] ) ∩( ⋃_y∈ R_k-1(a,b') R_1(y,a))
    )
       ⊇⋃_z∈ R_k-1(a',b)  y∈ R_k-1(b',a) [ R_1(a',z)∩ R_1(y,a)]

Since z=b∈ R_k-1(a',b) and y=b'∈ R_k-1(a,b') we conclude
R_k(a',b)∩ R_k(a',b) ⊇ R_1(a',b)∩ R_1(a,b') ∅
by Lemma <ref>.  


The Pasch axiom (Pa) implies in particular (B3), as shown by
<cit.>. Lemma 1 of <cit.> therefore implies
that R_k also satisfies

  
  (C4) z∈ R(x,y) implies R(x,z)∩ R(z,y)={z},

which in turn implies (B1).

Furthermore, R also satisfies (M) and therefore in particular
(B2). As an immediate consequence we conclude that R_k is
geometric in the sense of Nebeský. Note that this is not true for R_k
itself since (B2) is violated for all k<n-1 for all pairs of vertices
with distance d(x,x̅)=n. Lemma 1 of <cit.>, furthermore,
implies that G_R_k=G_R_k is connected since R_k
is a transit function satisfying (B1) and (B2).

The requirement that G is connected in Corollary <ref> and
<ref> can therefore be replaced also by requiring that
R satisfies (Pa).

The main result of <cit.>, see also <cit.>,
states that a geometric transit function R equals the interval function
of its underlying graph, R=I_G_R, if and only if R satisfies in
addition the two axioms

  
  (S1)
    |R(x,y)|=|R(z,w)|=2,
    x ∈ R(y,w), and
    y,w∈ R(x,z),
    implies z ∈ R(y,w).
  
  (S2)
    |R(x,y)|=|R(y,w)|=2, y
    ∈ R(x,y), w ∉ R(x,z), z ∉ R(y,w) implies y ∈ R(x,w).

Again we need (S1) and (S2) to hold for R rather than R
itself.


The 1-point crossover operator R_1 satisfies the (S1) axiom.

 Let R_1 be 1-point crossover operator.  Since
  |R(u,x)|=|R(v,y)|=2, it follows that u and x as well as v and y
  differ in only a single coordinate. Writing
  u=(u_1, u_2, …, u_i, u_i+1,…,u_n) and 
  assuming u∈ R(x,y) we must have either
  
    
  (1)  u=(u_1,u_2,…,u_i,u_i+1,…,u_n) = 
                   (x_1,x_2,…,x_i,y_i+1,…,y_n), or 
    
  (2)  u=(u_1,u_2,…,u_i,u_i+1,…,u_n) =
                   (y_1,y_2,…,y_i,x_i+1,…,x_n).
  
  W.l.o.g., suppose u is of the form (1), therefore 
  u_1, u_2, …,u_i=x_1,x_2,…,x_i and 
  u_i+1,…,u_n=y_i+1,…,y_n. Let x∈ R(u,v). 
  Since u is of the form (1), we have 
  u_1, u_2, …,u_i=x_1,x_2,…,x_i and 
  x_i+1,…,x_n=v_i+1,…,v_n. Let y∈ R(u,v). 
  since u is of the form (1), we have 
  y_1,y_2,…,y_i=v_1,v_2,…,v_i and 
  y_i+1,…,y_n=u_i+1,…,u_n. 
  Hence v=(v_1,v_2,…,v_i,v_i+1,…,v_n) 
  can be written as
 
  v=(y_1,y_2, …, y_i,x_i+1,…,x_n), which 
  implies v∈ R(x, y). Thus the axiom (S1) follows.
  


The 1-point crossover operator R_1 satisfies axiom (S2).


From |R(u,x)|=|R(v,y)|=2, it follows that u and x differ 
in only one coordinate, say i, and v and y differ in a single
coordinate, say j. W.l.o.g., let i≤ j. 
Since v∉ R(x,y), y and v differ only in position j, 
we conclude that

  
  (*)  x_j,…,x_n≠ v_j,…,v_n.

From x∈ R(u,v) and (*) we obtain 
x_1,…,x_j-1=v_1,…,v_j-1=y_1,…, y_i-1. 
Hence x_j,…,x_n=u_j,…, u_n. 
Therefore x=(x_1,…, x_j-1, x_j,…,x_n) =
(y_1,…, y_j-1, u_j,…, u_n). 
This implies x∈ R(u,y) and axiom (S2) follows.
 

As shown in <cit.>, the axiom


  (MO) R(x,y) ∩ R(y,z) ∩ R(z,x) ∅

implies both (S1) and (S2).

On hypercubes, i.e., assuming an alphabet with just two letters, uniform
crossover R=R_k satisfies |R(x,y) ∩ R(y,z) ∩
R(z,x)|=1. The unique median m=R(x,y) ∩ R(y,z) ∩ R(z,x) is
defined coordinate-wise by majority voting of x_i,y_i,z_i∈{0,1}, see
<cit.>. On hypercubes, R_k thus satisfy (MO).
This argument fails, however, for general Hamming graphs. The reason is
that axiom (MO) fails for each position at which the three sequences
x,y,z are pairwise distinct: {0,1}∩{1,2}∩{2,0}=∅.

For z ∈ R_k(x,y) let I denote the set of indices 0=i_0≤ i_1≤ i_2
≤ i_k=n from definition <ref> such that z is a k-point
crossover offspring of x and y. If z is an offspring such that x is
placed before y in the definition we denote this by z=x×_Iy and
z=y×_Ix otherwise.


  Let d(a,b) > k+1. If s=a ×_I b, t=a ×_I b 
  and |I|=k, then
 
  s ×_j t ∉ R_k(a,b) and 
  t ×_j s ∉ R_k(a,b) holds for all j ∉ I.


  Since j ∉ I it follows that 
  s ×_j t = (a ×_I b)×_j (b ×_I a) and 
  t ×_j s = (b ×_I a)×_j (a ×_I b), 
  we have s ×_j t, t ×_j j 
  ∈ R_k+1(a,b) ∖ R_k(a,b).
  

<cit.> conjectured that for each transit set R_k(x,y)
there is a unique pair of parents from which it is generated unless
R_k(x,y) is a hypercube. We settle this conjecture affirmatively:


If d(u,v),d(x,y)>k+1 then
R_k(u,v) = R_k(x,y) if and only if {u,v} = {x,y}.

 The implication from right to left is trivial. 
  For other direction we use Lemma <ref>. 
  Assume, for contradiction, that R_k(u,v) = R_k(x,y) and 
  {u,v}≠{x,y}. Then x,y ∈ R_k(u,v) and u,v ∈ R_k(x,y). 
  From R_k(u,v) = R_k(x,y) it follows also that 
  R_k(u,v)=R_k(x,y), which in turn implies 
  d(u,v)=d(x,y). Therefore, there exists a set of indices I, 
  |I| = k, such that x=u ×_I v and y=v ×_I u. 
  From d(x,y)>k+1 and Lemma <ref> we conclude that 
  there exist j ∉ I such that x ×_j y ∉ R_k(u,v). 
  Hence R_k(u,v) ≠ R_k(x,y). This contradiction completes 
  the proof of the theorem.
   

For the special case k=1, Theorem <ref> for k=1
implies the following statement.


  (H3) For every x,y,u,v ∈ X, u≠ v, x ≠ y, |R(x,y)|>4,
  R(u,v) ⊆ R(x,y) implies that either R(u,v)={u,v} or
  {u,v}={x,y}.

For x,y∈ X with d(x,y)=t ≥ 3, the transit set R_1(x,y) induces a
cycle of size 2t, an hence the only other transit sets that are included
in R_1(x,y) are singletons and edges. 




§ GRAPH THEORETICAL APPROACH FOR K-POINT CROSSOVER OPERATORS




Transit sets R(x,y) inherit a natural graph structure as an induced
subgraph of the underlying graph G_R. In the case of crossover operators
and their corresponding transit sets R_k(x,y), the distance in the
underlying graph plays a crucial role in their characterization.

Recall that n-dimensional hypercubes are antipodal graphs, i.e., for any
vertex v there is a unique antipodal vertex v with
d(v,v)= diam (G) = n, where diam (G) denotes the diameter of graph G. The vertex v is
obtained from v by reversing all coordinates.
    

  R_k(x,y) induces an antipodal graph such that 
  x=y, y=x, and for each u ∈
  R_k(x,y) of the form u=x ×_I y we have 
  u=y ×_I x.

 
  The definition of R_k immediately implies that x and y are at the
  maximal distance from each other and every other v ∈ R_k(x,y), v=x
  ×_I y, has a unique vertex at maximal distance in R_k(x,y),
  that is v=y ×_I x.
  

Note that here v and v are antipodal in a subgraph
R_k(x,y) and will not be antipodal in the underlying graph G_R, unless
d(v,v)= diam(G_R).  This is not the only property inherited
from hypercubes. We say that H is an isometric subgraph of a graph
G if for every pair of vertices u,v ∈ V(H) the distance from G is
preserved, i.e., if d_H(u,v)=d_G(u,v). Isometric subgraphs of hypercubes
are known as partial cubes <cit.>.  <cit.> showed (1) that R_1(x,y)
induces C_2t, a cycle of length 2t, where t=d(x,y), and (2) that
d_C_2t(u,v)=d_G_R_1(u,v) holds for every pair u,v ∈
R_1(x,y). In other words R_1(x,y) is a partial cube. Theorem
<ref> implies that this result holds in general:

The k-point crossover operator R_k induces a partial cube.

In particular, therefore, R_k always induces a connected subgraph of G_R. 

In the remainder of this section we consider only the binary case.

 
  Let R be a transit function R on a set X. Then we set uv ∥
  xy if and only if v,x ∈ R(u,y) and u,y ∈ R(v,x).
 
The binary relation ∥ was introduced by <cit.>
in the context of a characterisation of so called X-nets, a structure
from phylogenetic combinatorics that is intimately connected with partial
cubes. Indeed, <cit.> showed that ∥ can be used
to characterize partial cubes:

  Let G be a graph and R=I_G, then G is a partial cube if and only if
  the relation ∥ is an equivalence relation on the set of its
  edges.

By the definition, the relation ∥ is reflexive and
symmetric. Therefore it suffices to require that ∥ is a
transitive relation. Proposition <ref> thus can be translated
into the language of transit functions:


Let R be a transit function on a set X. Then the underlying graph G_R
is partial cube if and only if R satisfies:


  (AX) for all a,b,c,d,e,f ∈ X, with
  |R(a,b)|=|R(c,d)|=|R(e,f)|=2 and ab ∥ cd and cd ∥
  ef it follows that ab ∥ ef .


It is worth noting that the axiom (AX) can be also described purely in a
transit sets notation as follows:


  (AX') for all a,b,c,d,e,f ∈ X, with
  |R(a,b)|=|R(c,d)|=|R(e,f)|=2 and b,c ∈ R(a,d), a,d ∈ R(b,c),
  d,e ∈ R(c,f) and c,f ∈ R(d,e) it follows that b,e ∈ R(a,f)
  and a,f ∈ R(b,e).




For a partial cube G, the equivalence classes of the relation ∥
are called cuts and we denote the set of all cuts by
𝒞={C_1,C_2,…, C_n}, where n is the dimension of the
smallest hypercube into which G embeds isometrically.  Cuts form a
minimal edge partition of the edge set in a partial cube with the property
that removal of all edges from a given cut results in a disconnected graph
with exactly two connected components. These are called splits
<cit.>.

Cuts of the partial cubes correspond to the coordinates in the
corresponding isometric embedding into the hypercube and they induce a
binary labelling of the strings: for a cut C_i vertices from one part of
the split induced by C_i are labeled “0” in coordinate i, and
vertices from the other part of the split are labeled “1” in coordinate
i. For a any pair of parallel edges xy, uv in a partial cube the
notation can be chosen such that d(u,x) = d(v,y) = d(u,y)-1 =
d(v,x)-1. The distance between any two vertices in a partial cube
therefore can be computed as the Hamming distance between the corresponding
binary labelings, which in turn correspond to the number of cuts that
separate the two vertices. In other words, any shortest path between two
vertices in a partial cube is determined by the cuts it
traverses. Moreover, any shortest path traverses each cut at most once. We
refer to <cit.> for the
details; there, the cuts are called Θ-classes.

Let us denote the cuts appearing in the partial cube R_1(x,y) by
C(x,y). We have |C(x,y)|=d(x,y). For any pair of vertices x,y in a
hypercube with d(x,y)=t we have t! possible ways to choose a shortest
path between them, because each of the t! possible orders in which the
corresponding cuts that are traversed results in a distinct path. Therefore
there are also t! ways to choose an isometric cycle through x and
y. The definition of the 1-point crossover operator, on the other hand,
identifies a unique isometric cycle between x, y ∈ V(G_R).

The binary labelling of vertices in a partial cube naturally induces a
lexicographic ordering of vertices. Similarly, by taking first the
labelling of the minimal vertex and concatenating it with the labelling of
the remaining vertex, we can also lexicographically order the edges of a
partial cube. The idea can further be generalized to a lexicographic ordering of
all paths and cuts of a partial cube. The following result shows the
1-point crossover is intimately related to this lexicographic order.


  Let x,y ∈ X={0,1}^n. Then R_1(x,y) consist of all vertices
  appearing on lexicographically minimal and maximal paths between x and
  y.


  The statement follows immediately from the definition of the 1-point
  crossover operator.
  


  Is it true that R_k(x,y) consist of all vertices appearing on
  k!/2 pairs of first and last lexicographically minimal and
  maximal paths between x and y?




For x,y ∈ X{0,1}^n and any shortest path between them, there is
exactly one path along which the cuts appear in the reverse order. Consider
any u∈ R_1(x,y)∖{x,y}. There is is exactly one shortest path
between u and x in R_1(x,y).  For k>1 and d(x,y)=t both x and
y have exactly t neighbours in R_k(x,y). Moreover as shown above, see
example <ref>, for u ∈ R_k(x,y), it may be the case that
R_k(x,u)=R_k(x,u) ⊆ R_k(x,y). Hence the lexicograpic
order of cuts does not uniquely determine a shortest path in
R_k(u,x). The structure of R_k(u,v) hence is much richer and calls for
more “dimensions”. We explore this structure in more details in the
sections <ref> below.


  Compute the size of cuts for R_k, i.e., the number of edges belonging
  to the common cut.


The degree sequence of the graphs induced by 1-point crossover and
uniform crossover operators are monotone. In the first case all values are
equal to 2, and in the second case they equal the length of the string
n.



Let d(a,b)=t > k+1 > 2. Determine degree sequences of the graphs induced
by R_k(a,b).

We will solve this problem completely for the special case of 2-point
crossover operators in Section <ref>.


  
  Let a,b ∈ X={0,1}^n and k>1. Then the maximum and minimum degree
  of a graph induced by R_k(a,b) equal n and k+1, respectively.


  Clearly the graph induced by R_2(a,b) includes all neighbours of x
  and y in {0,1}^n, hence the maximum degree of a graph induced by
  R_2(a,b), and consequently of graphs induced by R_k(a,b), for k>2,
  is n.  W.l.o.g., let a=0…0 and b=1…1. Then R_k(a,b)
  consist of all binary strings with less than k+1 blocks of consecutive
  0's or 1's. Hence the minimum degree in a graph induced by R_k(a,b) is
  attained by vertex corresponding to a binary string consisting of exactly
  k different blocks of consecutive 0's or 1's, and they have exactly
  k+1 neighbours in a graph induced by R_k(a,b).
  
A solution of Problem <ref> could help solve 

  Does R_k induce a k-connected graph?


For an axiomatic characterization of R_1 in terms of transit functions
axioms it is easy to translate graph theoretic properties related to the
fact that R_1(x,y) induces an isometric cycle in {0,1}^n in the
language of transit functions. In addition, however, it would also be
necessary to express a consistent ordering of the cuts that appear in the
isometric cycles in terms of transit function. While this appears possible,
it seems to be cumbersome and does not promise additional insights into the
structure of the transit sets. Hence we do not pursue this issue further.



§ COMBINATORIAL PROPERTIES OF RECOMBINATION SETS
 

Since the monotonicity axiom (M) fails for k-point crossover with
  k<n-1, <cit.> proposed the axiom


  * (GW3) For all x,y∈ X and all u,v∈ R(x,y) holds
   |R(u,v)|≤ |R(x,y)|.

stipulating monotonicity in size. This is proper relaxation of (M), which
obviously (M) implies (GW3). In order to derive explicit expressions for
|R_k(x,y)| we note that, for given vertices x and y, the hypercube
can be relabeled in such a way that x becomes the all-zero string and y
is a 01-string with 1's at exactly the positions where x and y differ.
Thus the size of the recombination sets |R_k(x,y)| =: r_k(t) depends only
on the order k of the recombination operator and the Hamming distance
t:=d(x,y). In the following we write 

    Φ_h(n):= ∑_i=0^h ni .

In order to compute r_k(t), we have to distinguish the case of small and
large Hamming distances.
  


Let 1≤ k < t. Then 

    r_k(t) = 
       
        2^t              if   t ≤ k 
      
        2 Φ_k(t-1)    if   t > k



  Consider two strings x and y.  From <cit.> we know that
  |R_1(x,y)|=2t. For all children of x and y that are obtained by
  i-point crossover, 1 ≤ i ≤ k with exactly i cuts, we have
  i possibilities for choosing the cuts along t-1 positions.  This
  amounts a total of t-1i possibilities. In 2 different choices
  for the ordering of parents. If t≤ k cuts may be placed
  simultaneously between any two positions in which x and y differ,
  i.e., i takes values from 0 to t-1. Thus r_k(t)=2 ∑_i=0^t-1t-1i = 2Φ_t-1(t-1)=2· 2^t-1 =2^t. For t>k the
  number of possible cuts is limited by k and hence r_k(t)=2 Φ_k(t-1).
  
Parts of this result were already observed by <cit.>. In
particular, r_1(t)=2t for t>1, r_2(t) = t^2-t+2 for t>2, 
r_k(k+1)=2^k+1, and r_k(k+2)=2^k+1-2. 

The latter equation shows that R_k-1(x,y) for d(x,y)=k+1 misses
exactly two points compared to R_k(x,y), i.e., R_k(x,y)∖
R_k-1(x,y)={a,b}. Thus we can conclude immediately that a=x
×_I y, b=y ×_I x with |I|=k.  Since every x,y, x≠
y, has a unique a,b with the above property, we obtain another simpler
proof of the Theorem <ref>.

From r_k(t)=2^t for t≤ k+1 and the fact that R_k(x,y) is
a hypercube K_2^t of dimension t for d(x,y)=t we immediately conclude
that R_k(x,y) is also a hypercube for t≤ k+1.

Let G be partial cube and let H be a graph obtained by contracting some
of the cuts of G, i.e. by forgetting some of the coordinates in binary
labelling of vertices. If H is isomorphic to some hypercube, then we say
that H is a cube minor of G.

 
  Consider R_k(x,y) as an induced subgraph of the boolean hypercube
  K_2^n, and suppose d(x,y)≥ k+1. Then the largest cube minors of
  R_k(x,y) are isomorphic to K_2^k+1.
 

  This is an immediate consequence of Lemma <ref> and 
  Theorem <ref>.
   

The Vapnik-Chervonenkis dimension (or VC-dimension) measures the
complexity of set systems. Originally introduced in learning theory by
<cit.>, it has found numerous applications e.g. in
statistics, combinatorics and computational geometry, see monograph edited
by <cit.>. Consider a base set X and family
ℋ⊆ 2^X. A set C⊆ X is shattered by
  ℋ if {Y∩ C| Y∈ℋ}=2^C. The VC-dimension
of ℋ is the largest integer d_VC such that there is a set
C of cardinality d_VC that is shattered by ℋ. For
ℋ=∅, d_VC= - 1 by
definition.

Clearly, X is shattered by ℋ=2^X, hence the VC-dimension of
the Boolean hypercube {0,1}^d is d. Now consider an even cycle
C_2t of length 2t, isometrically embedded into t dimensional
hypercube. It is not hard to check that the VC-dimension of C_2t is 2
for any t≥ 2. More generally, the VC-dimension of a partial cube G,
with d cuts, equals the dimension of the largest cube-minor in G,
because this is the largest cardinality of a set of coordinates that can be
shattered by the set of all d of cuts of G.



The VC-dimension of R_k(x,y) equals k+1 whenever d(x,y)>k. Otherwise 
the VC-dimension of R_k(x,y) equals d(x,y). 


  If d(x,y) ≤ k then R_k(x,y) induces graph isomorphic to
  d-dimensional hypercube, where d=d(x,y).  Let d=d(x,y). If d>k
  then we need to contract d-k-1 cuts (ignore the corresponding
  coordinates) to obtain a cube minor of dimension k+1.
   



§ TOPOLOGICAL REPRESENTATION OF THE K-POINT CROSSOVER OPERATORS



Oriented matroids <cit.> are an axiomatic combinatorial
abstraction of geometric and topological structures such as vector
configurations, (pseudo)hyperplane arrangements, convex polytopes, point
configurations in the Euclidean space, directed graphs, linear programs,
etc. They reflect properties such as linear dependencies, facial
relationship, convexity, duality, and have bearing on solutions of
associated optimization problems. Beyond their connection with many areas
of mathematics, the theory of oriented matroids has in recent years found
applications in diverse areas of science and technology, including
metabolic network analysis <cit.>, electronic circuits
<cit.>, geographic information science
<cit.>, and quantum gravity
<cit.>. 

In order to explore the relationships of k-point crossover operators and
oriented matroids it will be convenient to change the coordinates of the
vertices of the hypercube K_n^2. For the remainder of this section we
write + instead of 1 and - instead of 0 to conform with the
traditional notation in this field. Among several equivalent
axiomatizations of oriented matroids, the face or covector axioms best
captures the geometric flavour and thus is the most convenient one for our
purposes.

Let E be a finite set. A signed vector X on E is a 
vector (X_e: e∈ E) with coordinates X_e ∈{ +, 0, - }. 
The support of a sign vector X is the set 
X={e ∈ E  |  X_e ≠ 0}. The
composition X ∘ Y of two signed vectors X and Y is the
signed vector on E defined by (X ∘ Y)_e = X_e, if X_e ≠ 0,
and (X ∘ Y)_e = Y_e otherwise, and their difference set is  D(X, Y) = {e ∈ E  |  X_e  = - Y_e }. We denote by ≤ the product
(partial) ordering on {-,0,+}^E relative to the standard ordering 
- < 0 < + of signs. 

An oriented matroid M is ordered pair (E,ℱ)
of a finite set E and a set of covectors ℱ⊆{+,-,0}^E satisfying the following (face or covector) axioms: 


  (F0) 0=(0,0,…,0) ∈ℱ.

  (F1) If X ∈ℱ, then -X ∈ℱ.

  (F2) If X, Y ∈ F, then X ∘ Y ∈ℱ.

  (F3) If X, Y ∈ℱ and  e ∈ D(X,Y), 
      then there exists Z ∈ℱ such that Z_e = 0 and
      Z_f=(X ∘ Y)_f for all f ∈ E ∖ D(X, Y).


A simple example for an oriented matroid are the sign vectors of a
vector subspace. More precisely, consider a subspace V⊆ℝ^|E|, define, for every v∈ V, its sign vector s(v)
coordinate-wise by s_e(v)=(v_e) for all e∈ E, and denote by
ℱ the set of all sign vectors of V. Then M=(E, ℱ)
satisfies the axioms (F0)-(F3). Oriented matroids obtained from a vector
space in this manner are called representable or linear.

The set 𝒞⊂ℱ of non-zero covectors that are
minimal with respect to the partial order ≤ are called cocircuits or
vertices of M. The set 𝒯⊂ℱ of covectors
that are maximal with respect to ≤ are called topes of M.  The set
of cocircuits determines the set of covectors: every covector X ∈ℱ∖{0} has a representation of the form X= V_1∘
V_2 ∘…∘ V_k, where V_1, V_2, … V_k are cocircuits,
and V_1, V_2,… V_k ≤ X. Similarly, the topes determine the
oriented matroid: X is a covector if and only if its composition with any
tope is again a tope, i.e., ℱ= { X ∈{+,-,0}^E |∀
T ∈𝒯: X ∘ T ∈𝒯}.

M=(E,ℱ) is called uniform of rank r if the support
sets of cocircuits are exactly the subsets of E with r+1 elements.

The big face lattice ℱ is a lattice obtained by
adding the unique maximal element 1 to the partial order ≤
on ℱ. The rank of a covector X is defined as its height in
ℱ and rank of oriented matroid is the maximal rank of
its covectors.

 

As an example consider R_2(x,y) with d(x,y)=5. It can be verified that the
elements of R_2(,) are exactly the topes of the
oriented matroid corresponding to the Rhombododecahedron in Fig.<ref>.  Its big face lattice is shown in Figure
<ref>.



This observation can be generalized with the help of the following 


T ⊆{+,-}^X of VC-dimension d is the set of topes of 
a uniform oriented matroid M on X if and only if 
T = -T and |T| = 2Φ_d-1(|X|-1).



By Proposition <ref> and Theorems <ref> and 
<ref> this immediately implies

For x,y ∈{+,-}^X, with d(x,y)=|X|=n the elements of 
R_k(x,y) form the set of topes of a uniform oriented matroid 
M on X with VC-dimension k+1 and corank n-k-1.


One of the cornerstones of the theory of oriented matroids is the
Topological Representation Theorem, which connects oriented matroids with
pseudosphere arrangements, see Appendix A for detailed
definitions. Together with Theorem <ref>, it immediately
implies the following topological characterization of the recombination
sets of k-point crossover:

  For x,y ∈{+,-}^X, with d(x,y)=|X|=n, the recombination set
  R_k(x,y) can be topologically represented by a pseudosphere arrangement
  of dimension k, where the minimal elements in the big face lattice
  correspond to the intersections of exactly k pseudospheres, and there
  are 2nk-1 such intersections.

The significance of this result is that it provides a representation of
crossover operators in terms of topological objects. In order to illustrate
the usefulness of Theorem <ref>, we now turn to a full
characterization of the transit graphs of 2-point crossover operators.  The
smallest non-trivial examples are the graphs R_2(,)
in Fig. <ref> and
R_2(,) in Fig. <ref>.


 

  R_2(a,b) with d(a,b)=t > 3 induces antipodal planar quandrangulation,
  that is, a partial cube of diameter t with t^2-t+2 vertices, 2t^2-2t
  edges, t^2-t quadrangles, and all cuts of size 2t-2.


  Let |V|, |E|, |Q| and |C| denote number of vertices, edges,
  4-faces, and edges in a cut, respectively. From the definition of
  crossover operator, we can arbitrarily permute coordinates, hence it
  follows that each cut has the same number of edges, this justifies that
  we study |C|.  From Theorem <ref> it follows that vertices
  of R_2(a,b) form the set of topes of uniform oriented matroid of rank
  3 and corank t-3.  As shown by <cit.> and in the
  book by <cit.>, rank 3 oriented matroids can be represented
  by pseudocircle arrangement on 𝕊^2. The corresponding tope
  graph is therefore planar. Hence R_2(a,b) induces in particular a
  planar antipodal partial cube. Corank t-3 implies that each
  intersection of pseudocurves is the intersection of exactly two of
  them. Hence all faces of the dual – the tope graph – are 4-cycles,
  therefore R_2(a,b) induces planar quadrangulation. Moreover, each
  intersection of two pseudocircles corresponds to cocircuit. In uniform
  oriented matroid of corank t-3 there are exactly 2 tt-2
  cocircuits, which correspond to the 4-cycles in the dual graph.
 
  Quadrangulations are maximal planar bipartite graphs – no edge can be
  added so that graph remains planar and bipartite. Using Euler formula for
  planar graphs <cit.>, we obtain 
  |E|=2|V|-4. Theorem <ref>, furthermore, implies 
  |E|=2t^2-2t and thus |C|=|E|/t=2t-2.
  



As an example, Fig. <ref> shows the pseudocircle arrangement of
transit graph R_2(,) of
Fig.<ref> and its equivalent hyperplane
arrangement.

In order to get a better intuition on the structure of the graphs induced
by 2-point crossover operators, we finally derive their degree sequence.

  Let d(a,b)=t > 3. The degree sequence of a graph induced by R_2(a,b)
  equals (t,t,4,…,4,3,…,3), where there are t^2-3t vertices
  of degree 4 and 2t vertices of degree 3.


  W.l.o.g., let a=0… 0 and b=1 … 1. For any vertex c=x
  … xyx … x, x,y ∈{0,1} we have that c ∈ R_2(a,b),
  hence deg(a)=deg(b)=t. Let c ∈ R_2(a,b) ∖{a,b}. Then we
  have two cases:

  Case 1. c= xx … xxyy … yy and {x,y}=
  {0,1}. Then c has at most four neighbours in R_2(a,b): c_1=yx
  … xxyy … yy, c_2=xx … xxyy … yx , c_3=xx …
  xyyy … yy and c_4=xx … xxxy … yy. Since t > 3 it
  follows c also has at least three neighbours in R_2(a,b).

  Case 2. c= x … xxyy … yyxx … x and {x,y}=
  {0,1}. Then c has at most four neighbours in R_2(a,b): c_1=x
  … xxxy … yyxx … x, c_2=x … xyyy … yyxx …
  x , c_3=x … xxyy … yxxx … x and c_4=x … xxyy
  … yyyx … x. Since t > 3 it follows c also has at least
  three neighbours in R_2(a,b).

  Let x_3 and x_4 denote the number of vertices of degree 3 and 4
  respectively. By the handshaking lemma 2|E| = ∑_v ∈ V(G)
  deg(v). Therefore, it follows from arguments above and
  Theorem <ref> that
  
    4t^2 -4t    = 2t + ∑_v ∈ V(G) ∖{a,b} deg(v)
    
        4t^2 -6t    = 3x_3 + 4x_4

  Theorem <ref> also implies t^2-t = x_3+x_4. 
  Solving this system of linear equations yields 
  x_3=2t and x_4=t^2-3t.
   



§ CONCLUDING REMARKS


Crossover operators are a key ingredient in the construction of algorithms
in Evolutionary and Genetic Programming. Their purpose is to construct
offsprings that are a “mixture” of the two parental genotypes, an idea
that is captured well by the concept of transit functions. In this
contribution we have investigated in detail the transit sets of homologous
crossover operators for strings of fixed length and their combinatorial,
graph theoretic, and topological properties.

As shown by <cit.> 1-point crossover operators correspond to
circles, that is, rather simple 2-dimensional objects. For k>1 we have
shown that k-point crossover operators are of more complex nature and
correspond to higher dimensional objects, which is appropriately measured
by the VC-dimension. For the case of binary alphabets, we explored the
close connection with oriented matroids and found that the elements of
transit sets form the topes. Furthermore, there is an equivalent
characterization in terms of pseudosphere arrangements. Since string
recombination operators effectively only distinguishes whether a sequences
position is equal or different between the two parents, the results on the
graph-theoretical structures of the transit rests directly carry over to
arbitrary Hamming graphs.

Linear oriented matroids are exactly those that can be represented by
sphere arrangements, i.e., every member of such arrangement is
(d-1)-dimensional sphere in 𝕊^d, which is in turn equivalent
to the representation of oriented matroid by a central hyperplane
arrangement, e.g. their tope graphs are zonotopes. This suggest the
following open

  Are uniform oriented matroids corresponding to the k-point crossover
  operators realizable? In the case of positive answer, find equations
  describing the hyperplanes in the corresponding hyperplane arrangement.


The results presented here also suggest to consider transit sets of
recombination operators for state spaces other than strings. Natural
candidates are many crossover operators for permutation problems. A subset
of these was compared e.g. by <cit.> and <cit.> but
very little is known about the algebraic, combinatorial, and topological
properties. Interestingly, the 1-point crossover operator R_1 satisfies
all axioms except (B2) of the axioms characterizing the interval function
of an arbitrary connected graph. Nevertheless, there are striking
differences even though both functions induce the same convexity as noted
in Lemma <ref>.

Finally, recombination operators influence in a critical manner
they way how genetic information is passed down through the generalizations
in diploid populations. The corresponding nonassociative algebraic
structures so far have been studied mostly as generalizations of Mendel's
laws <cit.>, see also the books by
<cit.> and <cit.>. We suspect that a better
understanding of the structure of recombination operators will also be of
interest in this context.


  This work was supported in part by the Government of India, Department of
  Atomic Energy (grant no. 2/48(2)/2014/NBHM(R.P)-R&D II/14364 to MC),
  and the Deutsche Forschungsgemeinschaft within the EUROCORES Programme
  EUROGIGA (project GReGAS) of the European Science Foundation (grant no.  STA 850/11-1 to PFS).


mde      



  

§ APPENDIX A: PSEUDOSPHERE ARRANGMEMENTS


  Consider the d-dimensional sphere 𝕊^d in ℝ^d+1
  and the corresponding (d+1)-dimensional ball
  𝔹^d+1={(x_1,…,x_d+1) ∈ℝ^d+1 |  x^2_1
  + … + x^2_d+1≤ 1}, whose boundary surface is 𝕊^d.

  A pseudosphere S ⊂𝕊^d is a tame embedded
  (d-1)-dimensional sphere. Its complement in B^d consist of exactly
  two regions, hence S can be oriented, by labelling one region by
  S^+_e and the other by S^-_e. A pseudosphere arrangement
  𝒮={S_e  |  e∈ E} in the Euclidean space ℝ^d
  is a collection of (d-1)-dimensional pseudospheres on the
  d-dimensional unit sphere 𝕊^d, where the intersection of any
  number of spheres is again a sphere and the intersection of an arbitrary
  collection of closed sides is either a sphere or a ball, i.e., for all R
  ⊂ E holds
  
  
  (i) S_R=𝕊^d ∩_i∈ R S_i is empty or homeomorphic
    to a sphere.
  
  (ii) If e ∈ E and S_R ⊄S_e then S_R ∩ S_e is
    a pseudosphere in S_R, S_R ∩ S^+_e∅ and S_R ∩
    S^-_e∅.
  
  For a pseudosphere arrangement 𝒮, the position vector
  σ(x) of a point x ∈𝕊^d is defined as
  
    σ(x)_e=
        
          +,    for  x ∈ S^+_e 
    
          0,    for  x ∈ S^+_e 
    
          -,    for  x ∈ S^-_e
        .

  The set of all position vectors of 𝒮 is denoted by
  σ(𝒮). 

  A famous theorem due to <cit.> establishes an
  correspondence between oriented matroids and pseudosphere arrangement. 
  
  Topological Representation Theorem  Let M=(E,ℱ) be an oriented matroid of rank d. Then
    there exists a pseudosphere arrangement 𝒮 in 𝕊^d
    such that σ(𝒮)=ℱ. Conversely, if
    𝒮 is a pseudosphere arrangement in 𝕊^d, then
    (E,σ(𝒮)) is an oriented matroid of rank d.  
  A simple alternative proof was given by <cit.>.

  A pseudosphere arrangement naturally induces a cell complex on
  𝕊^d, whose partial order of faces corresponds precisely to the
  partial order ≤ on covectors of the corresponding oriented matroid.
  This fact serves as motivation for concept of covectors in the theory of
  oriented matroids.


