Introduction to Combinatorial Species
This post will provide readers with a general idea of what species is and how it is being used for graphs and permutations. Essentially, species exist to facilitate the abstract study of structures on (finite) sets, such as graphs and permutations.
We will use the following background material:
Categories: A category is a collection of objects and maps between them. Examples of categories include groups, rings, sets, and topological spaces.
Functor: A functor is a map between categories. For example, a functor might replace topological spaces with groups.
Species: Let B be the category of finite set, with the morphism within the category be the bijection of these sets, a species is a functor such that
We will provide some examples below to make the concept less abstract and easier to perceive. For the purpose of this post, we will mainly focus on species for graphs and permutations.
# The Species of Graphs
We will be writing "Species of Graphs" as "Gra". This is a functor, from finite sets to finite sets. Gra will take a finite set
When a functor acts on morphisms, the definition gives:
# Example on Graph Structure
We will provide an example with 3 edges:
Now the question is, how many ways can we construct a graph structure out of this? The graphs below showcased the result:
We can also express these structures using another notation where
# Example on Morphism of Graph
To see how the above structure can be relabled into:
# The Species of Permutations
We will be writing "Species of Permutations" as "Perm". Perm will take a finite set u, and output the set of all permutations on u:
Essentially what this definition is saying is that the output for such finite set would be the set of all permutation structures on u, or simply all the bijections.
A Perm of a bijection from one set to another set can be expressed as:
We put a question mark because we do not have information on the bijection of v. Therefore, we will be use a diagram chase to find that bijection. Here is the information that we have already obtained:
Therefore, to get from V to V we could follow the map counterclockwise. We define
# Example on Permutation
# Example on Morphism of Permutation
Such example is quite similar to the bijection between finite sets for graph.
So that concludes our brief introduction of species, specifically for graphs and permutations. Later on we will talk about species addition, multiplication, and definitely some other interesting topics in random permutations. Thanks for reading!