Sometimes ignorance really is bliss.
If I had normal mathematical training, I would probably know the answers to some of the questions that have been puzzling me lately. But I would have missed the fun of figuring out the answers for myself.
Consider a relation R on some domain, and consider its transitive closure R*. Or, for some purposes, consider its positive transitive closure R+.
Now, sometimes when one is interested both in R and in R*, it seems convenient to have R be as small as it is possible to make it, as long as the transitive closure remains the same. So if there are any ‘redundant’ members of R — members that we can remove without changing R*, we would like to remove them. Since this operation feels like the opposite of transitive closure, I have privately called it “transitive aperture” since I first encountered it nine or ten years ago.
Given two relations R and R’, R’ is a transitive aperture of R if and only if R’ is a subset of R and R’* = R*. R’ is a minimal transitive aperture of R if and only if R’ has no subset R” such that R”* = R’* = R*.
For example: consider the < (less-than) relation on integers. It’s clear (a) that the transitive closure of < is < itself, and (b) that the successor relation on integers (1 = succ(0), 2 = succ(1), etc.) has the same transitive closure. It’s also clear (intuitively — I haven’t tried a proof) that if you omit anything from the successor relation, its transitive closure won’t be <, so the successor relation is apparently a minimal transitive aperture of <.
Now, in all the examples I’ve thought of so far, it’s been obvious both how to calculate the minimal transitive aperture of a given relation, and that there was only one.
But I’ve been asking myself several questions recently. Can I define the notion of minimal transitive aperture cleanly? Does every relation have one? Is it unique? I.e., does every relation have exactly one? Is there an algorithm for finding a minimal transitive aperture for an arbitrary relation?
I spent some time thinking about this today, while driving to Santa Fe and back, and I believe I know some of the answers. I think the definition above is clean and precise. And I think it’s obvious that there’s an algorithm for finding all minimal transitive apertures for any finite relation. (It’s finite, right? Take all the subsets and see if they are (a) a transitive aperture of R and (b) a minimal transitive aperture — if R is finite, then R has a finite number of subsets, so the algorithm will terminate. I didn’t say it was fast, I just said there’s an algorithm.) I don’t know whether there’s an algorithm for infinite relations. And it’s clear that for some relations, there is more than one minimal transitive aperture. But I don’t have time tonight to sketch any of this. I shouldn’t be writing this in the first place, I should be packing for a trip, but I wanted to get at least the formulation of the problem down.
The idea can also be formulated in terms of graphs. Take any directed graph G; you have a set of nodes and a relation on that set. Take the transitive closure of that relation, and draw another graph T with the same set of nodes as G, and arcs representing the transitive closure of the arcs of G. Call T the transitive closure of G, or the reachability graph of G. (For any two nodes n and m, there is an arc from n to m in T if and only if m is reachable from n in G.) A transitive aperture of G is a digraph with the same set of nodes, a subset of G’s arcs, and the same reachability graph.
It’s clear, as I say, that there can be multiple minimal apertures that have the same transitive closure. Any graph of three nodes a, b, c with a cycle among all three nodes a → b → c → a will do to show this: its transitive closure is a complete graph of three nodes. But a → c → b → a has the same transitive closure. QED.
So it’s clear that for digraphs with cycles, there may be multiple minimal transitive apertures.
And for acyclic digraphs?