Eigen-species

The title of this post is half-serious: it is designed to catch attention, but I think there are interesting things lurking here which deserve more exploration.

Species

A species describes a class of objects built on finite sets, in a “functorial” way, in the sense that any bijection between finite sets induces a bijection between the objects constructed on those sets. In category language, it is a functor from the category of finite sets and bijections to itself.

Two examples to start with: the species Set, which is the identity; and the species Graph, which constructs all the graphs on the input set.

Substitution

I will be concerned with the important object of substitution of species. If A and B are species, where B builds nothing on the empty set, then A[B] is the species for which an object on a set X is constructed as follows: partition X into non-empty parts in any manner; put a B-structure on each part; and put an A-structure on the set of parts.

For example, if CGraph is the species of connected graphs, then Set[CGraph] = Graph, where = is interpreted rather loosely. This simply says that an arbitrary graph is a disjoint union of connected graphs, with no structure on the set of components.

Substitution into Set is commonly referred to as the exponential principle. The exponential generating function for the labelled objects in Set is just the exponential function, so substitution of a species into Set corresponds to taking the exponential of its (labelled) counting series.

Groups

My main interest is that an oligomorphic permutation group G gives rise to a species: it preserves a canonical relational structure (consisting of all the G-invariant relations made up of tuples of distinct elements); and on a finite set, the species builds all the relational structures embeddable in this canonical structure.

In the group case, substitution of species corresponds to wreath product of permutation groups.

In order to arise from the group case, we require two conditions on the species:

  • It should be hereditary, that is, closed under taking substructures: the structure induced on a subset by any object in the species should also belong to the species. Many important species satisfy this.
  • It should have the amalgamation property: two structures can be amalgamated over (at least) a common substructure. This is a much more restrictive condition.

Then Fraïssé’s Theorem guarantees the existence of a countable homogeneous structure whose substructures are precisely those in the given class. All numerical data (numbers of labelled and unlabelled structures, cycle index) are then associated with a group, the automorphism group of the countable homogeneous structure.

The groups associated with the species Set and Graph are the symmetric group of countable degree and the automorphism group of the random graph, respectively.

Since connected graphs are not hereditary, the equation relating graphs to connected graphs is not mirrored by a group.

An example

I am interested in equations like A[B] ≈ 2B. So A is thought of as an operator, and B an “eigenspecies” for it. The 2 can be interpreted in the sense that the counting function for labelled objects in the species (or the cycle index of the species, in Joyal’s sense) is doubled; or, more elaborately, that objects in the substituted species are “doubled” copies of objects in B.

The approximation comes because very often there is only one A-structure on a 1-element set, in which case the A[B]-structures and B-structures on a 1-element set are equinumerous. So I will require the doubling only for sets with more than one element.

For example, what would Set[B] ≈ 2B (in this sense) mean? We would need a class of objects so that, on any set of size larger than 1, exactly half of the objects are connected. So the exponential generating function B(x) for labelled structures in B will satisfy exp(B(x)) = 2B(x)−1.

There is such a class, namely Nfree, the class of N-free graphs, those which do not contain a path of length 3 as induced subgraph. This important class has many names (for example, cographs), and many characterisations. In particular,

  • it is the smallest class containing the 1-vertex graph and closed under the operations of complementation and disjoint union;
  • an N-free graph with more than 1 vertex is connected if and only if its complement is disconnected.

A better example

The reason this example is unsatisfying is that it doesn’t come from a group. There is no countable homogeneous N-free graph, or (said another way) the class of finite N-free graphs does not have the amalgamation property.

But this can be rectified, as was done by Jacinta Covington in her thesis.

To see what is involved, let us see how amalgamation fails. Let a,b,c be three non-adjacent vertices, x a vertex joined to a and b (but not c), and y a vertex joined to b and c (but not a). If we try to amalgamate {a,b,c,x} with {a,b,c,y}, we cannot identify x and y because of their different adjacencies within {a,b,c}; and either joining or not joining a and b results in a path of length 3.

So we need a rule which says that, in any independent set of size 3, external vertices joined to two vertices in the independent set must always be joined to the same pair. So the third vertex must be “distinguished” in some way. Dually, in a triangle, we must distinguish a vertex as the possible single neighbour of an external vertex.

Consider 3-vertex subsets of an N-free graph. In such a set containing one or two edges, there is clearly a distinguished vertex. If the set has no edges, or three edges, there is no vertex obviously distinguished, but as we have seen, there must be a rule which does distinguish one if amalgamation is to be restored. Thus, we need to add a ternary relation which distinguishes one point from each triple of distinct points, so that if the 3-set contains one or two edges, the relation distinguishes the same point as the graph structure does.

One type of structure in which every 3-set has a distinguished vertex is LeavesBTree, the set of leaves of a binary tree. Of any three leaves, two are related to one another more closely than either is related to the third. (So, for example, among {human, chimpanzee, gorilla}, it is the gorilla which is distinguished.)

Now Covington’s work shows that this is exactly the kind of relation required to restore the amalgamation property for N-free graphs. We have:

  • LeavesBTree has the amalgamation property;
  • The class Nfree+ of N-free graphs possessing also the ternary structure of leaves in a binary tree, so that the vertex distinguished by the ternary relation on a 3-set containing one or two edges agrees with the one distinguished by the graph structure, has the amalgamation property.

In particular, there is a countable universal N-free graph which is homogeneous when the ternary relation is added. (We call such a structure homogenizable.) This graph is connected with diameter 2. Paradoxically, although the complement of a finite connected N-free graph is disconnected, the complement of Covington’s graph is connected; indeed, the graph is isomorphic to its complement.

Let CNfree+ denote the species of connected N-free graphs enriched with the ternary relation. In a disconnected N-free graph, the ternary relation corresponding to possible added points in an extension is unchanged if points are replaced by others in the same connected component. So there is a LeavesBTree relation on the set of connected components. This with a little further argument shows that LeavesBTree[CNfree+] = Nfree+ ≈ 2CNfree+. So CNfree+ is an eigenspecies for LeavesBTree.

However, connected graphs are not hereditary, so this situation is not yet supported by a group. Something different is required.

Since no finite N-free graph is self-complementary, the orbits on finite subgraphs (with more than one vertex) of Covington’s graph come in complementary pairs. The two objects in a pair have the same ternary relation, and make identical contributions to the enumeration or cycle index of the species. So if Nfree* denotes the species of complementary pairs of finite N-free graphs, then we have

LeavesBTree[Nfree*] = Nfree+ ≈ 2Nfree*,

where all three species in the equation are realised by oligomorphic groups. (The group of the pair of graphs contains the group of Covington’s graph as a subgroup of index 2.)

The automorphism group of Covington’s graph is primitive, while the wreath product is imprimitive. So the orbit counts and cycle indices associated with oligomorphic groups are not able to determine primitivity in general.

And finally

There is a nice description of the set of N-free graphs homogenenized by the leaves of a given binary tree. Colour the non-leaves of the binary tree black and white in any manner; then join two leaves if their common ancestor is coloured black.

Jan Hubička and Jarik Nešetřil discovered that Covington’s construction is not an accident: under rather mild conditions a structure can be homogenized. (However, we do not know conditions to ensure that a finite number of additional relations suffice; this is one of the big open problems in the area!) So there must be many more interesting phenomena to discover here.

Also, much less is known about Covington’s graph than about the analogous cases of the random graph and Henson’s Kn-free graphs. A topic surely worth exploring.

Questions like those in this post can be explored at the level of counting functions, by asking what it means for a formal power series to be doubled (apart from the constant term) by substitution into another given series, for example. Having worked out which series has this property, one can attempt to identify it using the On-line Encyclopedia of Integer Sequences. In this way, web browsing could become serious mathematical research!

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in exposition and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s