Duality

This is the lecture note for a micro-seminar of ChatGPT.

Today we discuss dualities in combinatorial objects.

Dualities arise naturally from the more basic notion of involutions. An involution is a function $f : X \to X$ such that $f \circ f = {id}_{X}$ . So, we start by looking at the most basic involution in mathematics:

φ \mapsto \neg φ .

This simple involution gives us the most basic duality in mathematics: De Morgan's law.

φ \land ψ = \neg (\neg φ \lor \neg ψ) .

Other kinds of duality arise by creating a connection between objects with $φ$ and objects with $\neg φ$ . My favourite example is Dilworth's theorem, where $φ$ is "pairwise comparable" i.e. a chain and $\neg φ$ is "pairwise not comparable" i.e. an antichain.

Many dualities takes this form of a min-max relation. Classic examples include Menger's theorem, where $φ$ is "connected" and $\neg φ$ is "cut set", and similarly max-flow min-cut theorem. I want to mention here a (perhaps) lesser-known theorem of this kind:

Strong Duality Theorem in Linear Programming. If the two optimization problems

\begin{aligned} maximize & c^{⊤} x \\ subject to \\ A x \leq b \\ x \geq 0 \end{aligned}

and

\begin{aligned} minimize & b^{⊤} y \\ subject to \\ A^{⊤} y \leq c \\ y \geq 0 \end{aligned}

are both feasible and bounded, then their optimal values are equal.

There are many involutions happening in this theorem: $A \mapsto A^{⊤}$ , $x \mapsto - x$ , etc. Maybe an interesting question to ask here is: is there a systematic way of joining multiple simple involutions / dualities into one big duality theorem?

This reminds me about the following theorem in game theory:

The Minimax Theorem of Games. Any finite matrix game of two players has an optimal mixed strategy; i.e. for any matrix $A$ and vectors $x$ and $y$ which all coordinates add up to $1$ , we have

max_{x} min_{y} x^{⊤} A y = min_{y} max_{x} x^{⊤} A y .

This is actually a special case of the fundamental theorem of games, or more commonly known as the Nash equilibrium.

General Duality

Whitney Duality: Planar Graphs and Vector Spaces

When talking about dualities, we would think of dual graphs of planar graphs. The (geometric) dual graph has all faces of a planar graph as vertices, and two vertices are adjacent if and only if the corresponding faces are adjacent. We now concentrate on the interesting properties of dual graphs. Consider a cycle in the original graph. What does it correspond to? At least, in most reasonable cases, it's a bond in the dual graph.

This actually reminds us of another important duality, that of vector spaces: the orthogonal subspace. (The cycle space is orthogonal to the bond space.)

It seems that we can combine the two ideas into one general duality. Here's what we do. We define the code $C (G)$ of a graph $G$ to be the vector space over $F_{2}$ spanned by rows of the incidence matrix of $G$ . Examples: the code of a cycle consists of all words with even weight; the code of a tree consists of all words. We define two graphs $G$ and $H$ to be (Whitney) dual, if $C (G)$ is orthogonal to $C (H)$ .

It is easy to check that geometric dual of a planar graph is also a Whitney dual, so Whitney dual is a generalization of geometric dual.

...Or not. The fact is, in some sense, Whitney duality is equivalent to geometric duality. The value of Whitney duality is that it gives us a nice description of planarity through pure combinatorial / algebraic language:

Theorem. A graph is planar if and only if it has a Whitney dual.

We postpone the proof of this theorem, and continue to find some connections between geometric dual graphs. An interesting observation is that a connected planar graph don't separate the plane if and only if it's a tree. This gives us the insight that the dual of a tree subgraph is the complement of a tree. We quickly realize that this could be the defining property of a dual graph.

We take the following attemption: we call two connected graphs $G$ and $H$ dual, if there is a bijection $φ$ from $E (G)$ to $E (H)$ , such that for every spanning tree $T \subseteq G$ , $E (H) ∖ φ (T)$ is a spanning tree of $E (H)$ .

How does this relate to other objects? Let's take a closer look to the notion of a "tree", or more generally, a "forest". We enumerate some of its most basic and most important properties here.

It tries to avoid a certain kind of substructure, or in this case, a cycle.
Any two maximal forest has the same number of edges.

A corollary of the first property is:

Any subset of a forest is still a forest.

The second property comes from a more basic fact:

Any non-maximal forest can be extended to a maximal forest. Actually for any selected maximal forest $F$ we can extend only using edges from $F$ .

Does that sound like something else?

A linearly independent set.

Any subset of a linearly independent set is still linearly independent.
Any non-maximal linearly independent set can be extended to a maximal linearly independent set. Actually for any selected maximal linearly independent set $B$ we can extend only using vectors from $B$ .

Audiences with certain knowledge will realize that we're actually dealing with matroids.

Matroids: General Independence and Duality

A matroid is a pair $(E, I)$ with $E$ a finite set and $I \subseteq 2^{E}$ , such that

$\emptyset \in I$ .
If $I_{2} \subseteq I_{1} \in I$ , then $I_{2} \in I$ .
If $I_{1}, I_{2} \in I$ , and $| I_{1} | < | I_{2} |$ , then there is a $e \in I_{2} ∖ I_{1}$ such that $I_{1} \cup e \in I$ .

Elements in $I$ are called independent sets. One quickly realizes that we can study maximal independent sets instead of general independent sets. A maximal independent set is called a base.

All bases has the same cardinality.

Remember the generalization of dual graphs using the concept of trees? It basically says that: the image of a base is the complement of a base.

Let $M$ be a matroid on a finite set $E$ , and $B$ the set of bases of $M$ . Then there is another matroid $M^{*}$ on $E$ , such that the set of bases of $M^{*}$ is exactly ${E ∖ B : B \in B}$ . $M^{*}$ is called the dual matroid of $M$ .

Category Theory: Duality of Universal Constructs

Before going into the fascinating theory of matroids, let's take a brief look at category theory.

If one want to construct a set that contains every element from set $A$ and set $B$ , but without overlapping, one has two choices: take the cartesian product $A \times B$ , and take the disjoint union $A ⊔ B$ . These two concepts are closely related, or even dual, in a category-theoretic view.

Given two functions $f, g : A \to B$ . If we want to make $f$ and $g$ be "equal" in some sense, there are two ways of doing this: 1) only consider those $a \in A$ such that $f (a) = g (a)$ ; 2) consider $B$ modulo a equivalence relation defined by $f (a) \sim g (a)$ . These two actions might seem dual; actually it's like the same kind of action, but done to $A$ and $B$ , respectively. We will see that this intuition is true.

We first think of how to define a Cartesian product of $A$ and $B$ , without every touching the actual elements of sets. We might think of the projection maps $π_{A}$ and $π_{B}$ , with $π_{A} (a, b) = a$ and $π_{B} (a, b) = b$ . One attempt to define products might be a set $P$ such that there exists $π_{A}$ and $π_{B}$ :

\begin{matrix} A & \overset{π_{A}}{\leftarrow} & P & \overset{π_{B}}{\to} & B \end{matrix}

The problem is $P$ might be too large, containing unnessecary elements, or too condensed, failing to include all elements. We want $P$ to be the most free set satisfying this. In category theory this kind of freeness is often expressed by the Universal Mapping Property:

Definition of the product. The product of $A$ and $B$ is an object $P$ , universal with two projection maps $π_{A} : P \to A$ and $π_{B} : P \to B$ , i.e. for any $Z$ with $ψ_{A} : Z \to A$ and $ψ_{B} : Z \to B$ , there is a unique $u$ such that $ψ_{A} u = π_{A}$ and $ψ_{B} u = π_{B}$ .

The dual of this definition turns out to be simple enough: reverse every arrow.

Definition of the coproduct. The coproduct of $A$ and $B$ is an object $P$ , universal with $π_{A} : A \to P$ and $π_{B} : B \to P$ .

\begin{matrix} A & \overset{π_{A}}{\to} & P & \overset{π_{B}}{\leftarrow} & B \end{matrix}

One can check that coproducts in $Sets$ is simply the disjoint union, explaining the "similarities" between Cartesian product and disjoint union.

We now turn to the second example, which is actually the notion of an equalizer.

Definition of the equalizer. Given two arrows $f, g : A \to B$ , an equalizer is an object $E$ together with an arrow $q : E \to A$ , universal such that $f q = g q$ .

\begin{matrix} E & \overset{q}{\to} & A & \to_{g}^{f} & B \end{matrix}

And, without surprises:

Definition of the coequalizer. Given two arrows $f, g : A \to B$ , a coequalizer is an object $E$ together with an arrow $q : B \to E$ , universal such that $q f = q g$ .

\begin{matrix} A & \to_{g}^{f} & B & \overset{q}{\to} & E \end{matrix}

These structures actually all belongs to a even more general class: limits and colimits. We will not go into category theory that much, and we now return to matroid theory.

More Matroid Theory

Our attention to matroid theory today will be restricted to duality. We recall the definition of a dual matroid:

Definition of a dual matroid. Let $M$ be a matroid, $B$ be the set of its bases, and $B^{*} = {E ∖ B : B \in B}$ . Then $B^{*}$ is the set of bases of another matroid $M^{*}$ , called the dual matroid of $M$ .

Furthur discussion are postponed to the following lectures.