This is a quick post for all of my non-Brasilian colleagues who are interested in learning about the research community here. My student Paulo Vitor Macedo Dias has put together a Brasilian Category Theory website. This is meant to be a repository for all things category theory in Brasil: we want to compile lists of events, researchers, research labs, as well as outreach material and research blogs.
A central goal of the project is to build and maintain a comprehensive, up-to-date list of researchers. This is genuinely important: having a clear picture of who is working with category theory—broadly understood, in any area where it plays a role—helps strengthen the community, makes collaboration easier, and increases the visibility of Brasilian research both locally and internationally. We want this list to include everyone, from established researchers to students, and from pure category theorists to those who use category-theoretic ideas in adjacent fields.
We also strongly encourage Brasilians working abroad to register themselves. The Brasilian category theory community extends well beyond the country’s borders, and making those connections visible is an important part of the project.
If you would like your information to appear on the website, you can follow the simple instructions available on the page. You can register either by making a pull request or simply by sending an email to categoriasbrasil@gmail.com.
In the email, please include:
Full name or laboratory name
Institutional affiliation (university, institute, etc.)
Link to your Lattes CV and/or personal website
Main research areas in Category Theory
(Optional) A profile photo or laboratory logo
(Optional) Any additional information you find relevant
The platform is open to everyone, and contributions are very welcome. In particular, anyone can write a blog post by simply submitting a pull request (see the instructions here: https://categorias-brasil.github.io/blog/como-contribuir/).
We are rather excited about the blog section. One of our goals is to create a lively and accessible stream of posts about current research, expository topics, and connections to other areas. If you are a researcher, consider writing a short post explaining your work, sharing an idea, or giving context to a recent result. It doesn’t have to be long or overly formal: clarity and enthusiasm are far more important.
We would also like to make a special call to undergraduate students. You are warmly encouraged to contribute outreach-style posts that explain concepts from category theory in simple, intuitive language. Writing these kinds of posts is a great way to solidify your own understanding while helping others enter the subject. Even explaining a single definition or example can make a real difference.
Our hope is that this website becomes not just a directory, but a genuine hub for interaction—helping people discover each other’s work, fostering collaborations, and making the Brasilian category theory community more visible internationally.
And if you’re part of the community in any way, add yourself, write something and encourage others to do the same. Let’s build our community together!
I’ve been thinking about time-varying graphs, where the vertices and edges may come and go as time hikes forward, for a while now. As part of my PhD thesis, Kitty Meeks and I defined a measure of structural complexity of temporal graphs which turned out to have lots of algorithmic applications (it even won the best paper award IWOCA!) but, despite these successes, there was something that bugged me: I still wasn’t sure what a temporal graph actually was!
So here’s the deal. In the temporal graph literature, they often speak about temporal graphs as being sequences of graphs, called snapshots, which represent how a graph might change with time. My question was: why is this a temporal graph and not just a sequence fo graphs? What part of the mathematical structure should compel me to think of this data as temporal? From my perspective this is where this whole project started. My coauthors — Wilmer Leal, James Fairbanks, Martti Karvonen & Frédéric Simard — certainly had different and complementary motivations, but I won’t speak on their behalf: get in touch with them, they’re all lovely and really smart!
The issue of making sense of what temporal data should be is rather complicated, as it turns out. I remember sitting in a little hippie tea shop in Gainesville discussing what time ought to be and what it really means for something to be temporal. We ended up agreeing with St. Augustine: what makes data temporal is that it is ‘in the memory’. By this we mean that temporal data should be all about snapshots, yes, but also about the memories between snapshots. This suggests that a key difference between temporal data and a mere indexed sequence of mathematical objects is that it is telling a story — there is a narrative arc.
So that’s what Wilmer, James, Martti, Frédéric and I did: we made the memory an explicit part of the data. We built on Schultz, Spivak and Vasilakopoulou’s sheaf-theoretic take on dynamical systems and provide a unified definition of time-varying data that works for basically any kind of mathematical object. We call these narratives — sheaves (or co-sheaves) over a category of intervals of time. When given as sheaves, we call them persistent narratives and we think of them as remembering what parts of the data persist over time. When given as co-sheaves, we call them cumulative narratives and we think of them as remembering all of the data we’ve seen so far.
One of our main contributions is to show that the way to record your temporal data really matters: although there are canonical functors \(\mathfrak{K}\) and \(\mathfrak{P}\) that let us transform persistent narratives into cumulative ones and vice-versa, these do not yield an equivalence of categories and thus information might be lost in these conversions. The good news is that the two functors \(\mathfrak{K}\) and \(\mathfrak{P}\) form an adjunction, so this loss of information is in some sense canonically trackable.
Another main contribution of ours is to distill desiderata for a theory of temporal data, which I’ll outline below.
(D1): (Categories of Temporal Data) Any theory of temporal data should define not only time-varying data, but also appropriate morphisms thereof.
(D2): (Cumulative and Persistent Perspectives) In contrast to being a mere sequence, temporal data should explicitly record whether it is to be viewed cumulatively or persistently. Furthermore there should be methods of conversion between these two viewpoints.
(D3): (Systematic ‘Temporalization’) Any theory of temporal data should come equipped with systematic ways of obtaining temporal analogues of notions relating to static data.
(D4): (Object Agnosticism) Theories of temporal data should be object agnostic and applicable to any kinds of data originating from given underlying dynamics.
(D5): (Sampling) Since temporal data naturally arises from some underlying dynamical system, any theory of temporal data should be seamlessly interoperable with theories of dynamical systems.
Our paper goes into all of these details and explains how our theory of narratives ticks the box of each desideratum. If you’re interested to learn more, you can check it out here or, as I recently found out, you can watch some videos on YouTube: our paper is now included as part of a course given by Nathaniel Osgood at the University of Saskatchewan. Thanks Nate!
That’s all for today. It’s always nice to celebrate when a paper gets accepted and to take the time to thank my wonderful coauthors and all the people who’ve helped along the way!
I guess it’s official: as of today I am a professor at the Institute for Mathematics and Statistics at the Univesity of São Paulo (USP)!
This is what I would’ve written last semester, when I started my new job. But as many can imagine, moving to another continent can be a little distracting. Now I’m back, focused, basking in the sunshine and recovering from my first Carnaval.
Other than sharing this news, this post was intended to be a short announcement of the “III Encontro Brasileiro em Teoria das Categorias“. Brasil has a vibrant (applied) category theory community and it has so far been a very welcoming space. If you are interested, feel free to get in touch with the organizers.
After being quiet for a little while, I can reassure that more posts will come soon — this time from below the equator.
Emilio Minichiello recently gave a woderful talk at the at the New York City Category Theory Seminar all about some results of mine (joint with Ernst Althaus, Daniel Rosiak and James Fairbanks) concerning dynamic programming and sheaves. Since many students and colleagues have asked me for recordings of my lectures on this subject and since I invariably turn up empty handed and covered in chalk, I’m very excited to now be able to point everyone to Emilio’s talk. If you’re interested, you can find the recording here.
Let \(G\) be a finite group, for uniformly and independently chosen elements \(x\) and \(y\) in \(G\), what the the probability that \(x\) and \(y\) commute?
In other words we ask: what is the value of $$\mathsf{ds}_G(xy= yx) := \frac{|\{(x,y) \mid x, y \in G \text{ and } xy = yx\}|}{|G|^2}?$$
The answer is well-known: either \(G\) is Abelian, in which case \(\mathsf{ds}_G(xy= yx) = 1\), or \(G\) is not Abelian and one has \(\mathsf{ds}_G(xy= yx) \leq 5/8\).
Framing this result a bit more conceptually, it is asking: how close can a group be to being Abelian without actually being Abelian? Clearly one can ask this kind of question about any mathematical structure and indeed this falls into the more general setting of determining the degree of satisfiability of some property \(p\) in some finite structure \(M\); in other words one asks: “what is the probability that uniformly chosen elements of \(M\) satisfy \(p\)?” Formally it is defined as follows.
Def: Take a first-order language \(\mathcal{L}\), a finite \(\mathcal{L}\)-structure \(M\), and an \(\mathcal{L}\)-formula \(\varphi(x_1,\dots,x_n)\) in \(n\) free variables. We call the quantity $$ \frac{ | \{ (a_1, \dots, a_n) \in M^n \mid \varphi(a_1, \dots, a_n) \} | }{ | M | ^n }$$ the degree of satisfiability of the formula \(\varphi\) in the structure \(M\), and denote it \(\mathsf{ds}_M(\varphi)\). One says that a formula \(\varphi\) has finite satisfiability gap \(\varepsilon\) for \(0 < \varepsilon < 1\) if for all \(M\) either \(\mathsf{ds}_M(\varphi\) = 1\) or \(\mathsf{ds}_M(\varphi) \leq 1 – \varepsilon\).
For groups there are many results establishing such finite satisfiability gaps. Some of these were developed by my friend Zoltan in his paper “Degree of Satisfiability of Some Special Equations” which is also where the terminology “degree of satisfiability” comes from. But what’s particularly interesting is the sheer quantity of known gap results (see our paper for pointers for further reading); indeed, as of now, the existence of an equation in the language of group theory that does not have finite satisfiability gap remains open. This is even in the case of equations in only one free variable; for example only partial results about finite satisfiability gaps are known for the equation \(x^p = 1\) for any \(p\) at least five.
Why Heyting Algebras?
Having said all this, it looks like the story for groups gets quite hard rather fast, so what about other structures? This is exactly what Zoltan asked me when he approached me about working on this topic. We studied Heyting Algebras and hopefully you’re now asking yourself: “why Heyting algebras?”. The answer is that the choice was motivated by both practical concerns and philosophical ones. On the practical side, Zoltan suspected that interaction of algebraic and order-theoretic structure would be helpful for our purposes; this was overwhelmingly true. On the philosophical side, studying degree of satisfiability in Heyting algebras lets us shed light on anti-exceptionalism: this is the contention that logic itself should be accepted, rejected and revised according to the same standards as other theories in science. In other words one should attempt to disprove the validity of a given logical system by searching for empirical evidence that falsifies a true statement in that logic.
Now the question is: suppose you wanted to test whether we should reason about the universe using classical or intuitionistic logic, what would do? Even if you only find evidence for classical logic (i.e. you find that all of your experiments so far agree with with what one would expect in classical logic), that doesn’t equip you with any sense of how likely it is for you to never encounter a situation in which one must think intuitionistically, but not classically. But this is where degree of satisfiability can be useful. Suppose you knew that there is an equation \(\varphi = \top\) which is tautological in classical logic, but not intuitionistically. If we know that \(\varphi = \top\) has finite satisfiability gap \(\varepsilon\), then, as we examine the universe, collecting data about the validity of the equation \(\varphi = \top\) as we go, and, because this equation has finite satisfiability gap, we can quantify how likely it is that the following two assertions hold simultaneously: (1) so far, all of our data points satisfy \(\varphi = \top\) (which, recall, is a classical principle) while (2) the universe we inhabit exhibits evidence against classical logic (i.e. there exist data points which do not satisfy \(\varphi = \top\)).
Some examples of classical principles (i.e. formulae that are tautological if and only if the logical system we inhabit is the classical one) include:
\(x \lor \neg x = \top\) (i.e. the law of excluded middle)
\(\neg \neg x = x\) (i.e. double negation elimination) and
\( x \to y = \neg x \lor y\) (i.e. material implication).
So do there exist classical principles which have finite satisfiability gap? And what does this have to do with Heyting Algebras?
Surprisingly the short answer is yes! This is part of what we show in our paper. But, before I spoil the fun, let’s answer the second question: we care about Heyting algebras because they are to intuitionistic logic what Boolean algebras are to classical logic. Formally this is what I mean:
(1) a propositional formula \(\varphi\) is provable in classical logic precisely if, for every Boolean algebra \(B\), one has that \(B \models (\varphi = \top)\) and
(2) a propositional formula \(\varphi\) is provable in intuitionistic logic precisely if, for every Heyting algebra \(H\), one has that \(H \models (\varphi = \top)\).
These two two statements mean that we can think about all of this wonderful business of anti-exceptionalism in very mathematically concrete terms; we ask: are there any classical principles (such as the ones I listed above) which have finite satisfiability gap in Heyting algebras?
To understand what this means, note that, if the answer were no, then this would mean that it’s essentially hopeless to try to empirically assert the validity of classical logic over intuitionistic logic. This is because, for any classical principle \(\varphi\) , there would be Heyting algebras \(H\) (plausible models of the logical structure of the universe we inhabit) in which the classical principle does not hold (i.e. \(H\) is not Boolean), but where the probability of satisfying the equation \(\varphi = \top\) is arbitrarily high when one samples points from \(H\) independently at random.
Fascinatingly, it turns out that this is not the case! Indeed we showed that the law of excluded middle does have finite satisfiability gap (this is the theorem below) and moreover, with much more effort, one can suitably extend this result to infinite Heyting algebras.
Theorem [B. , Kocsis]: for any heyting algebra \(H\), either \(H\) is Boolean (in which case \(\mathsf{ds}_H(x \lor \neg x = \top) = 1\)) or one has that \(\mathsf{ds}_H(x \lor \neg x = \top) \leq 2/3\).
We prove many more results, for instance we show that, although double negation elimination also is a classical principle, it does not have finite satisfiability gap. In other words, there are Heyting algebras which are not Boolean, but in which double negation elimination holds with arbitrarily high probability!
This is the starting point for another one of our results which yields a complete classification of all the one-variable equations of Heyting algebras in terms of their degree of satisfiability.
Theorem [B., Kocsis]: An equation \(\varphi(p)\) in one free variable has finite satisfiability gap precisely if it is equivalent to one of the following: \(p = \top\), \(\neg p = \top\) or \(p \lor \neg p = \top\).
Where to next?
This project was incredibly fun particularly because it involved a blend of combinatorics (e.g. to prove that material implication has no gap), lattice theory and logic. Furthermore, the results are very encouraging compared to the case of finite groups, so perhaps there is a big untold story lurking here in the realms of lattice theory. I wonder what we might uncover next…
Recently I have been thinking a lot about pullbacks of graphs and it really is frustrating at times because they’re much harder to think about compared to colimits. It turns out that there is an obvious (in hindsight) reason for this and I thought it would be nice to tell you about it.
While thinking of limits of graphs, I’ve been progressively roping more and more people into joining me in this game. First I started with my undergraduate student Mansi Pai and then I got Will Turner into it too. Both of them (like every other person I play these games with) observe very quickly that, although it’s very visually simple to think of taking colimits of graphs, limits, the dual operation, are much harder to think about. It turns out that you can see why very easily once you know a fact and a vibe:
Fact. spans of finite sets are \(\mathbb{N}\)-valued matrices.
Vibe. prime factorization is “hard” to do.
Now I put “hard” in quotes above because, as you probably know, nobody really knows which complexity class PrimeFactorization really ought to be in (although we all suspect it to be NP-intermediate). Either way though, since we base lots of cryptography on the fact that prime factorization is difficult to do, I think it’s fair for me to say that it’s a “hard problem” for the purposes of this post.
Now what about the fact I mentioned? Well, as the nlab will tell you, Spans in FinSet are \(\mathbb{N}\)-valued matrices : a span \(X_1 \leftarrow M \rightarrow X_2\) of finite sets, is a matrix with \(|X_1|\) rows, \(|X_2|\) columns and where the \((x_1, x_2)\)-entry (for \((x_1, x_2) \in X_1 \times X_2\)) is given by the cardinality of the fiber over the two elements \(x_1\) and \(x_2\) (i.e. the cardinality of the set \(\{m \in M \mid f_i(m) = x_i \text{ for } i \in \{1,2\}\) where \(f_1\) and \(f_2\) are the legs of the span above).
In any category \(\mathsf{C}\) with pullbacks, you can define the category \(\mathsf{Span}(\mathsf{C})\) of spans in \(\mathsf{C}\). This has as objects those of \(\mathsf{C}\) and as arrows the spans in \(\mathsf{C}\). Composition is done by pullback as follows: given two composable morphisms \((M, m_1, m_2) \colon X_1 \to X_2\) and \((N, n_1, n_2) \colon X_2 \to X_3\) as drawn below,
we form their composite by taking the pullback of \(m_2\) and \(n_1\) yielding the red span shown below.
Now, given what I just told you about thinking of matrices as spans, it should be natural to wonder whether the category \(\mathsf{Span}(\mathsf{FinSet})\) represents. It turns out that it can be thought of as the category having natural numbers as objects and matrices as morphisms which compose via matrix multiplication.
But then, armed with this fact and the fact that integer factorization is hard, it should be obvious that writing a graph as a limit of prime factors (where I mean “prime” in terms of being written as pullbacks) should be hard: if you could do that, then you would also have a way of factorizing matrices; but then you could factorize \(1 \times 1\) matrices. In other words, limits of graphs are hard to think about because integers are hard to factorize.
During Thanksgiving week I went to Wytham Abbey, a manor house in Oxfordshire where the “Workhop on Non-Compositionality in Complex Systems” was taking place. The workshop (organized by Matteo Cappucci and Jules Hedges) was centered around four papers that covered the theme of compositional patterns and emergence therein. I wrote one of them (the one on Structured Decompositions which I authored with Zoltan Kocsis and Jade Master) and you can find the other three here: 1, 2, 3. It was a truly lovely week of research in beautiful frescoed rooms warmed by fireplaces that Fabrizio would diligently keep burning at their maximum capacity.
While I was there, I worked with Fabrizio Genovese, Caterina Puca and Daniel Rosiak on some ideas that Daniel, James Fairbanks and I had been throwing around for a while, namely: “can you use cohomology to detect the failures of compositionality of a computational problem?” This ended up requiring us to spend a week computing in a frenzy, but the outcome amounted to many deep observations that we’re still trying to digest fully. The goal of this blog post is to just explain why I (really I should say “we“) think that cohomology is the right tool for making sense of emergence.
Computational Problems as Presheaves
I like to think of computational problems as presheaves assigning a set of solutions (i.e. a solution space) to each object \(c\) in some category of inputs. For example consider the “fruit fly” of computational complexity theory: the \(k-\texttt{VertexCover}\) problem. It is the decision problem that asks whether a given graph \(G\) contains a vertex subset \(S\) of size at most \(k\) (some given integer) such that the removal of \(S\) from \(G\) yields an edgeless graph. An example of a graph with a vertex cover of size two is shown below (pick \(\{b,d\}\) as the vertex cover).
You can encode this problem as a presheaf \(\mathcal{V}_k \colon \mathsf{Grph}^{op}_{mono} \to \mathsf{Set}\) which is a “functor by pullback” acting on objects as follows: $$\mathcal{V}_k \colon G \mapsto \{S \subseteq G \mid |S| \leq k \text{ and } G – S \text{ edgeless}\}.$$ (Note that you really need to start with the category of graphs and monomorphisms if you want this to actually be functorial since otherwise the size of the vertex covers might blow up when you pull them back along arbitrary morphisms.)
An Example: Solving Vertex Cover by Dynamic Programming on a Decomposed Graph.
Suppose we’re given a graph \(G\) and a cover of \(G\) (i.e. a structured decomposition) consisting of a collection \((U_i)_{i \in I}\) of subgraphs of \(G\) whose colimit is \(G\). Can we solve \(k-\texttt{VertexCover}\) on the instance \(G\) by only computing locally on the pieces \((U_i)_{i \in I}\) of the cover?
The answer is yes and you’ll see why in moment. But I’m not going to bother telling you the whole solution because it’s more complicated than it needs to be and it would obfuscate the point I’m trying to make. Instead, I’ll tell you an easier story: rather than considering any cover \((U_i)_{i \in I}\), we’ll only focus on path decompositions. Intuitively a path decomposition is a cover where each open \(U_i\) has non-empty intersections with \(U_{i-1}\) and \(U_{i+1}\) and empty intersection otherwise. More precisely, a path decomposition of a graph \(G\) is a diagram that looks like a sequence of monic spans whose colimit is \(G\). For example a path decomposition into \(n\) pieces \(U_1, U_2, \dots, U_n\) might look like $$U_1 \hookleftarrow U_{1, 2} \hookrightarrow U_2 \hookleftarrow U_{2,3} \hookrightarrow U_3 \dots U_{n-1} \hookleftarrow U_{n-1, n} \hookrightarrow U_n.$$
So how might we solve \(k-\texttt{VertexCover}\) by dynamic programming on a path decomposition?
To see how to do this, let’s start with an even easier presheaf, namely the one that takes a graph to all of its vertex covers without any size restrictions. Let’s call this \(\mathcal{V} \colon \mathsf{Grph}^{op}_{mono} \to \mathsf{Set}\). This presheaf is actually a sheaf, meaning that, if we are given a vertex cover \(S_i\) in \(U_i\), say and a vertex cover \(S_j\) in \(U_j\), then we can always construct a unique vertex cover \(S\) on the union (pushout) of \(U_i\) and \(U_j\) which restricts to \(S_i\) (resp. \(S_j\)) on \(U_i\) (resp. \(U_j\)) whenever \(S_i |_{U_i \cap U_j} = S_j |_{U_i \cap U_j}\) (i.e. whenever the two vertex covers agree over the intersection \(U_i \cap U_j\)).
The fact that \(\mathcal{V}\) is a sheaf has profound algorithmic consequences (which you can read about in my paper with Ernst Althaus, James Fairbanks and Daniel Rosiak) which let us design fast dynamic programming algorithms. In this concrete case the dynamic programming algorithm to decide if \(\mathcal{V}(G)\) is empty (i.e. \(G\) is a no-instance) or not goes as follows.
– You start with the given path decomposition $$U_1 \hookleftarrow U_{1, 2} \hookrightarrow U_2 \hookleftarrow U_{2,3} \hookrightarrow U_3$$ of the input graph \(G\) (for simplicity let’s assume we only have three opens).
– Then you apply \(\mathcal{V}\) to this decomposition to get the following diagram of sets: $$\mathcal{V}(U_1) \hookrightarrow \mathcal{V}(U_{1, 2}) \hookleftarrow \mathcal{V}(U_2) \hookrightarrow \mathcal{V}(U_{2,3}) \hookleftarrow \mathcal{V}(U_3)$$
which represents the local solution spaces \(\mathcal{V}(U_i)\) and their restriction maps to the pairwise intersections.
– Now we compute the pullback \(\mathcal{V}(U_1) \times_{\mathcal{V}(U_{1, 2})} \mathcal{V}(U_2)\) and we remove from \(\mathcal{V}(U_1)\) and \(\mathcal{V}(U_2)\) any element which is not in the range of the legs of the pullback cone.
– Finally repeat the previous step for \(\mathcal{V}(U_2)\) and \(\mathcal{V}(U_3)\) and answer “NO” if any of sets associated to \(U_1\), \(U_2\) or \(U_3\) after this process of filtering are empty.
Since \(\mathcal{V}\) is a sheaf, it’s not too hard to see that this algorithm is correct (for an actual statement of the algorithm I sketched above and its proof of correctness in a much more general case, see our paper). Furthermore this algorithm is fast since it takes time at most \(2^{2k} \cdot n\) where \(n\) is the number of pieces in the path decompsotion (in the example above we had \(n = 3\)).
At this point one might ask whether this same approach might work if we replace the presheaf \(\mathcal{V}\) with the one we actually care about, namely \(\mathcal{V}_k\). Unfortunately this doesn’t work and it fails because \(\mathcal{V}_k\) is not a sheaf. To see why, observe that, although we might have two vertex covers \(S_i\) and \(S_j\) of size at most \(k\) on some opens \(U_i\) and \(U_j\), even if we have that \(S_i |_{U_i \cap U_j} = S_j |_{U_i \cap U_j}\), we are not guaranteed that the union \(S_i +_{S_i |_{U_i \cap U_j}} S_j\) has size at most \(k\).
Now staring at this, one might get the feeling that this is the only way in which the \(k-\texttt{VertexCover}\) problem fails to be compositional, but how can we make this intuition precise?
Čech Cohomology for Vertex Cover
To study the failures of compositionality of the \(k-\texttt{VertexCover}\) problem, we’ll first need to set ourselves up for some cohomology. First of all, consider the nerve
of the path decomposition. We will use define the following augmented complex
where \(F\) to denotes the functor obtained by composing \(\mathcal{V}_k\) with the free Abelian group functor and where the coboundary maps are given by $$ \delta^{-1} \colon \bigl (s \in \mathcal{V}_k(G) \bigr) \mapsto \bigl (s|_{U_i})_{i \in I} \quad \text{ and } \quad \delta^n \colon s \mapsto \sum_{j = 0}^{n} (-1)^j F(d_{n,i})(s). $$
As usual we will define the \(n\)-th cohomology group \(H^n\) as the quotient \(H^n := \ker \delta^n / \text{im} \delta^{n-1}\). Now notice that, if \(F\) were a sheaf, then \(H^0\) as defined with respect to this augmented complex would be trivial. To see this, observe that \(\ker \delta^0\) is generated exactly by the matching families of the sheaf and thus, if \(F\) were a sheaf, then each matching family would lift to a unique global section (i.e. each matching family would be in the image of \(\delta^{-1}\)). For a presheaf which refuses to be a sheaf (such as our \(F\) as we just defined it above), however, \(H^0\) is generated exactly by those families of local vertex covers, which, despite being in pairwise agreement, fail to lift to global solutions.
This is wonderful: what we just did was deduce that the obstructions to compositionality are given by the generators of \(H^0\). But what does this mean concretely? And does this agree with our intuition that the only way in which \(\mathcal{V}_k\) fails to be compositional is that local vertex covers may glue into vertex covers that are too large (i.e. they exceed our budget of \(k\) vertices)?
It’s time to compute!
Let’s make this a small example. Take \(k = 2\) and let \(G\) be a four-cycle with vertices \(a,b,c,d\) and let’s consider a path decomposition of \(G\) into two parts \(U_1\) and \(U_2\) where \(U_1\) is the two-edge path \(d-a-b\) and \(U_2\) is the two-edge path \(d-c-b\). Now enumerate the local vertex covers of size at most \(2\); these are (below I’m dropping parentheses, so read \(a\) as \(\{a\}\) and \(ab\) as \(\{a,b\}\) etc.):
Since \(U_{12}\) consists solely of the vertices \(b\) and \(d\) (and no edges), we have that \(\mathcal{V}_2(U_{12}) = \{\emptyset, b, d\}\) and hence the matching familes are
while, since \(\mathcal{V}_2(G) = \{ac, bd\}\), we have
$$\text{im} \delta^{-1} = \{(a,c), (bd, bd)\}.$$
Thus we have that \(H^0\) has two generators (namely these are \((ab, bc)\) and \((ad, dc)\)) which correspond precisely to those local vertex covers which agree on the intersection, but whose union is too large!
Does this work this nicely for other problems?
The answer is a resounding yes! If you want to try it out, I suggest you try the \(k-\texttt{CycleTransversal}\) problem which asks to find a set \(S\) of vertices whose removal from the host graph \(G\) renders it a forest. This too can be cast as a presheaf by pullback and this too refuses to be a sheaf. The interesting thing is that, if you try to compute \(H^0\) for this presheaf on the same graph and cover described in the previous example, you’ll end up with three generators: two of them will describe issues relating to the size of the glued solutions (just like in the case of vertex cover) but the third one is different, it describes the fact that two local cycle covers can agree, but their gluing can fail to cover all the global cycles!
Looking ahead
Ideally it would be wonderful if we could make use of the information of \(H^0\) to automatically come up with dynamic programming algorithms. I have many ideas of how to do this and, based on my ongoing work with Spencer Breiner, Matteo Cappucci, James Fairbanks and Daniel Rosiak, I think these are all very promising. However, for now it’s unclear whether we can actually turn this cohomological information into a practical tool for designing combinatorial algorithms. On the bus ride from Wytham Abbey to Heathrow airport, I was told that cohomology groups are sheaves. If that’s true, then I have some good news for us all… but I’m having a hard time hunting down the precise result. If anyone knows about this, please reach out, I’d love to know the details!
You asked: “[w]hat is the analog of tree-width for finite permutation groups? This should have an answer. And the answer should be fairly obvious/deducible (Cf Grothendieck) from the right abstract point of view.“
This blog post is part of my correspondence with Mike Fellows. I’m posting it here for three reasons: (1) I needed LaTeX support (email just wouldn’t cut it), (2) the discussion is of general interest and (3) my answer involves notes that I had been intending to share on this blog for a while.
I think the answer should be structured co-decompositions. They’re things that look like this:
Let me explain.
You start by taking a tree \(T\) and you assign:
to each node \(t \in VT\) a (finite) group \(G_t\)
to each edge \(e = st \in ET\) a (finite) group \(G_e\) and a pair of surjective group homomorphism \(f_s^e \colon G_s \to G_e\) and \( f_t^e \colon G_t \to G_e\).
You call this resulting structure a tree co-decomposition of a group \(G\) if \(G\) arises by recursively taking fibered products of the groups assigned to the nodes of \(T\) over the groups assigned to the edges of \(T\).
For anyone reading who might not recall, what a fibered product is, here’s the definition: “a fibered product (or pullback) of two group homomorphisms \(f_1 \colon G_1 \to H\) and \(f_2 \colon G_2 \to H\) is the subgroup of \(G_1 \times G_2\) given by the elements \(\{(x,y) \mid f_1(x) = f_2(y)\}\).)
Now you might ask: “why on earth is this an analogue of tree-width for groups?“
The short answer is that the structure I defined above is an instance of a structured decomposition. These are category-theoretic generalizations of graph decompositions that I introduced a little while ago with Zoltan Kocsis and Jade Master. You can read about them in one of my older blog posts or in our paper. Since structured decompositions generalize tree decompositions of graphs, structured decompositions of groups are the natural group-theoretic analogue of graph decompositions.
But now I’m expecting some hesitation in you: I started off by saying that structured co-decompositions were the right choice, but then I spoke about structured decompositions without the “co“. So you’re probably asking yourself: “why the ‘co‘? What does that even mean?”
It’s a great question. First off let’s talk about what the “co” is doing. As usual in category theory, sticking a “co” in front of a word indicates that we’re invoking categorical duality. In this particular case we’re invoking duality on the category of objects we’re wanting to decompose: a structured co decomposition of groups is a structured decomposition in \(\mathsf{Grp}^{op}\) (i.e. the category you get by inverting the domain and codomain of all the morphisms in the category of groups and group homomorphisms). Since I didn’t give the actual category theoretic definition of a structured decomposition in this post, perhaps it’s best to unpack things a little.
First of all, what’s a structured decomposition of groups? Well, it turns out (as I found about a year after Zoltan, Jade and I wrote our paper) that group-valued structured decompositions were already studied by Hyman Bass and Jean-Pierre Serre under the name of graphs of groups. These are useful tools in geometric group theory and are defined as follows: you pick a graph \(G\) and you assign groups to each of its vertices and edges and then you assign injective group homomorphisms \(G_e \to G_x\) from each edge-group \(G_e\) to each vertex-group \(G_x\) whenever \(x\) is a vertex incident with \(e\). You’ll notice that this is exactly what you get when you “flip the directions of all the edges” in the definition I gave at the beginning of this post.
So why am I not advocating to use graphs of groups (i.e. structured decompositions of groups) as analogues of tree decompositions for graphs? There are two reasons, let me explain.
First of all, Mike, you’re asking about decomposing finite groups. And if you want to do this, graphs of groups just won’t cut it: you say that a group \(G\) is decomposed by a group-valued structured decomposition \(d\) if the colimit of \(d\) is \(G\). (Sacrificing a bit of formality in favor of more group-theoretic terminology, a colimit of groups is what you get when you do a bunch of free products with amalgamation.) So why is this not what we want? Well because in general colimits of finite groups are infinite.
However, if you start with finite groups and you take limits (think “fibered products”) then you end up with a finite group. This is the first reason why structured co-decompositions of groups are better group-theoretic analogues of (tree) graph decompositions of groups.
The second reason for preferring co-decompositions has to do with the kinds of applications we might have in mind. You and I like algorithms, obviously, and I’m guessing you’re asking about group decompositions because you have some neat algorithmic tricks lurking in your mind… so let me give just a hint as to why I suspect co-decompositions are the right choice in this setting.
The first thing to have in mind is my paper with Ernst Althaus, Daniel Rosiak and James Fairbanks about solving decision problems that are encoded as sheaves. The idea is that a computational problem should be a contravariant functor from your category of inputs (e.g. Graphs) to your category of solution spaces (e.g. Sets): the functor maps each input to its set of solutions. Mike this is the stuff I spoke about at FPT fest in Norway (for anyone else reading this, you can see a recording of a more category-theoretic version of the talk on YouTube).
(Note: the organizers forgot to share my screen for the first couple of minutes of the recording, so, if the video seems weird to you at the beginning, just have some patience, it’ll get sorted out after a few minutes of me talking.)
The reason the contravariance is relevant to us is that, if you think of solution spaces not as sets, but instead as groups (where the idea is to exploit the symmetries in the solution space), then computational problems naturally take graph decompositions to co-decompositions of groups!
I have a lot more to say, about this. For instance one important thing I’d like to highlight is that I think that, although group decompositions are interesting, I think that groupoid decompositions are more interesting still. There are many reasons to say this (ranging from the deeply philosophical, to the very practical), but I guess that the one-liner idea is that encoding graph isomorphism as a contravariant functor naturally lands you in groupoids, not in groups…
…unfortunately Mike I’m about to be late for the category theory class I’m teaching, so I have to wrap up this post and perform a disappearing act. I’ll talk to you soon (and thanks for putting up with my slow reply; life’s been hectic lately!)
Sometimes in math things sound obviously true and that’s exactly how it turns out. Other times, you’re less lucky. Today was one of those days. In this post we’ll see that, although \(\mathsf{Grph}\) is adhesive, \(\mathsf{Grph}^{op}\) isn’t.
For a while now, Will Turner and I have been working both with adhesive categories and with \(\mathsf{Grph}^{op}\). As is often the case, if you’re holding a nail-shaped thing in one hand and hammer-shaped thing in the other, you might think that they might go together well. That’s what we did. In the back of our minds there was this little harmless assumption that \(\mathsf{Grph}^{op}\) was adhesive. The proof of this “fact” was one of those “to-dos” that I was saving for a rainy day. The trouble is that there aren’t that many rainy days in Florida, so I never checked it until today when Will found a little counterexample to a conjecture we had made. It turns out that \(\mathsf{Grph}^{op}\) isn’t adhesive and in fact neither is \(\mathsf{Set}^{op}\) (and hence no copresheaf category is!).
So what’s the plan? Well, we’re going to think about co-adhesive categories: i.e. any category \(\mathsf{C}\) such that \(\mathsf{C}^{op}\) is adhesive. I’ll remind you what an adhesive category is and then I’ll prove that \(\mathsf{Set}\) isn’t co-adhesive. It’ll be real short and easy. I’m writing this mostly for me so that I never make the same mistake twice.
Df: an adhesive category is a category \(\mathsf{C}\) in which:
all pushouts of monomorphims exist,
all pullbacks exist and
all monic pushout squares as Van Kampen.
What does Van Kampen mean? A pushout square
is Van Kampen if, whenever we are given a commutative square sitting above it (i.e. the given pushout square is the bottom face) as in the following diagram
then, if back faces are pullback squares, then the front faces are pullbacks if and only if the top face is a pushout.
If adhesive categories seem mysterious to you, don’t worry. The definition scares a lot of people at first sight. But adhesive categories are very nice and in fact most of the nice categories you know and love are adhesive: \(\mathsf{Set}\) is adhesive, any copresheaf category is adhesive (such as graphs, Petri nets, simplicial sets, hypergraphs, databases) and any small topos is adhesive too. Surprisingly (at least for me) it turns out that \(\mathsf{Set}^{op}\) isn’t adhesive.
Prop: \(\mathsf{Set}\) is not coadhesive.
Proof: we have to show that \(\mathsf{Set}^{op}\) is not adhesive. Since \(\mathsf{Set}\) has all pushouts and pullbacks, the problem must lie with the Van Kampen squares. So take the following pushout square in \(\mathsf{Set}^{op}\) (I’ll draw it as a pullback square in \(\mathsf{Set}\) because it’s easier to think about that way).
And take any cube sitting above it as in the definition of a Van Kampen square (again notice that everything will look upside-down because we’re dualizing everything).
This cube has the pullback square we started with as its bottom face and it’s generated by taking pushouts starting with the red function \(f\) defined as \(f = \{(xa,a_x),(xb, b_x), (ya, y’), (yb, y’)\}\). It is easy to verify that, although all of the side faces of the cube are pushouts, the top face is not a pullback. Thus \(\mathsf{Set}\) is not co-adhesive, as desired.
So there you go. It turns out as usual that it’s the “easy things” that bite you. It turns out that categorical duality continues to be difficult to think about. And it turns out that I have little intuition as to which categories can be both adhesive and co-adhesive! If you know of any examples please do get in touch with me!
Towards the end of May I visited Johannes Carmesin‘s group at the University of Birmingham. I was there to work with Will Turner on obstructions to compositionality and their categorification.
I had an absolute blast. Will and I proved a bunch of new results and this post is about one of them: I’ll tell you how to deifne tree decompositions in terms of lattices of subgraphs. I think that it’s a cute result in of itself, but also that it will have profound consequences in the future. If you’re interested, Will has written a pair of posts about separations and fracturings of objects of a category; you can read about these things on his blog here and here.
The post should be relatively self-contained and it’ll consist of three main parts. First I’ll start by explaining tree decompositions at a high level and I’ll define them in terms of structured decompositions. (I’ll do this for two reasons: this more abstract definition is cleaner and we’ll need it later anyway.) Then I’ll explain our result for graphs and finally I’ll note how this generalizes to all kinds of other cool categories.
1. Tree decompositions
Tree decompositions (and the associated notion of tree-width) are fundamental tools in structural graph theory. Roughly they witness the global connectivity of a graph: in order to make sense of how connected a graph is, you don’t simply want a single vertex cut, but instead you need many such cuts which are nicely nested. Here’s an example.
A tree decomposition (below) of a graph (above). The tree decomposition specifies how to split the graph into small components in a tree-like ways (i.e. via a series of nested vertex cuts). Source: wikipedia
The tree-width of a graph measures how “decomposable” a given graph is; it is defined for a graph \(G\) as the minimum over all tree decompositions of \(G\) of the maximum size of the constituent parts of the decomposition.
Tree decompositions have been around for a while now. To the best of my knowledge they were first introduced by Bertelé and Brioschi in 1972 and then independently defined by Halin in 1976 and then by Robertson and Seymour in 1986. It’s interesting to see the same notion redefined multiple times (well, actually tree-width has many more cryptomorphic definitions, but we won’t get into that here..) and with three different mathematical goals: the first was focused on algorithmic compositionality, the second was interested in graph invariants similar to Hadwiger’s number and the modified chromatic and connectivity numbers and the third was motivated by topological questions (namely Wagner’s conjecture – which is now a Theorem!).
As I promised you earlier, I’ll give you a definition of tree decompositions now, but I’ll do it in terms of structured decompositions. These are much more general, but they require a little category theory to state properly. Don’t worry though: I’ll give the definition in such a way that you won’t need to know any category theory (at least not until section 3 of this post).
A monic structured decomposition is a bit like a generalized graph: it consists of a collection of objects of a category (think graphs or sets) and a collection of monic spans acting as generalized relations between the objects (FYI, for graphs, a monic span is just a pair of injective graph homomorphisms which have the same domain). Here’s a picture of a structured decomposition of graphs.
Df. Fix a graph \(G\) and a category \(\mathsf{C}\). A \(C\)-valued structured decomposition of shape \(G\) is a functor \(d\) of the form $$d \colon \int G \to \mathsf{C}$$ where \(\int G\) is the category obtained from \(G\) by making a the vertices and the edges of \(G\) into objects of \(\int G\) and which has a morphism from each edge-object to both of its endpoints (and identity arrows, naturally). For any vertex \(v\) and any edge \(e = xy\) in \(G\), we call the object \(d(v)\) a bag of \(d\), we call the object \(d(e)\) an adhesion of \(d\) and we call the span \(d x \leftarrow d e \rightarrow d y\) an adhesion span in \(d\). We say the decomposition is monic if \(d(f)\) is a monomorphism for each morphism \(f\) in it’s domain. Suppose \(\mathsf{C}\) has colimits, then, given an object \(c \in \mathsf{C}\), we say that
(D) the decomposition \(d\) decomposes \(c\) if \(\mathsf{colim}(d) = c\).
If you don’t know what a colimt is, don’t worry: just think about it as “gluing”. For instance the colimit of a monic span \(G_1 \leftarrow H \rightarrow G_2\) of graphs is the graph obtained by gluing \(G_1\) to \(G_2\) along their shared subgraph \(H\) (specifically we glue thew two graphs along the images of \(H\) under \(f_1\) and \(f_2\) where these are the morphisms in the span.).
Since I’ll be only speaking about monic decompositions in this post, I’ll drop the adjective and simply refer to a monic structured decomposition as a structured decomposition (or even just “decomposition”).
With this definition in mind, what’s a tree decomposition?
A tree decomposition is a tree-shaped \(\mathsf{Gr}\)-valued structured decomposition (where \(\mathsf{Gr}\) is the category of reflexive, simmetric graphs).
P.S. I don’t really care which category of graphs you choose, as long as it’s defined as a C-set category, everything I’ll tell you below will work.
Just to make sure we’re on the same page, let me spell out what a tree decomposition of a graph \(G\) is. You start with a tree \(T\), then you build a category \(\int T\) from it by making a span for each edge of \(T\) (as I explained ealier). Here’s a picture.
I added colors so it’s easier to see which span comes from which graph.
Then you choose a graph for each object of \(\int T\) and an injective graph homomorphism for each morphism of \(\int T\); i,e. you define a functor \(d \colon \int T \to \mathsf{Gr}\). This is a tree decompostion, but we only say that it decomposes the graph \(G\) if, when we glue together all of the graphs in the bags of the decomposition along the shared subgraphs in the adhesions, we obtain the graph \(G\).
2. Tree Decompositions via Lattices
Fix a graph \(\Gamma\) throught this section. To any such graph we can associate a poset \(\mathsf{Sub} \Gamma\) whose elements are subgraphs of \(\Gamma\) ordered by inclusion. Formally this is a special case of subobject poset \(\mathsf{Sub} c\) which is a construction which works on any category \(\mathsf{C}\) and for any object \(c\) therein. It’s defined as the category consisting of the following data:
Objects: these are monomorphisms \(d \to c\) into \(c\).
Morphism: these are commutative triangles of monos.
Notice that for graphs, the subobject poset comes equipped with infima and suprema and these distribute over eachother. In other words, this means that \(\mathsf{Sub} \Gamma\) is a distributive lattice. This is all we need to get the definition of a tree decomposition in terms of the subobject lattice.
Df. let \(\delta \colon \Delta \to \mathsf{Sub} \Gamma\) be a subposet of \(\mathsf{Sub} \Gamma\). We call \(\delta\) a weak tree pre-arrangement if for all \(x, y, z \in \Delta\) the following holds:
(WTPR) if \(\delta x \land \delta y \neq \bot\) and \(\delta y \land \delta z \neq \bot\) then \(\delta x \land \delta y \land \delta z = \delta x \land \delta z\).
We say that \(\delta\) is a weak tree arrangement if it is a pre-arrangement which also satisfies the following condition:
(TR) for all \(x \in \mathsf{Sub} \Gamma\), there exists a subposet \(\delta’ \colon \Delta’ \to \Delta\) such that \(x \leq \bigvee_{x’ \in \Delta’} \delta \delta’ x’\).
Admittedly, since we’re in a lattice, condition (TR) might look weird since taking \(x = \top\) implies that \(\top \leq \bigvee_{y’ \in \Delta’} \delta \delta’ y’ \leq \bigvee_{y \in \Delta} \delta y\) and hence that \(\bigvee_{y \in \Delta} \delta y = \top\) (in other words it says that we chose a bunch of subgraphs whose union is the whole graph… compare this to condition (D) of the definition of a structured decomposition). I stated point (TR) in this obfuscated way because I’m hoping to something neat with it in the future, so don’t worry about it. Anyway, after all this, here’s the proof I promised you.
Proposition. Given any tree decomposition \(\tau \colon \int T \to \mathsf{Gr}\) of a graph \(\Gamma\), the bags of \(\tau\) determine a weak tree arrangement. Conversely, every weak tree arrangement of \(\Gamma\) determines a tree decomposition.
Proof. Take any three bags \(\tau x, \tau y, \tau z\) in \(\tau\). Notice that the fact that \(\mathsf{colim} \tau = \Gamma\) (together with the observation that, given any diagram of monos in the category of graphs, its colimit cocones also consists of monos) implies that \(\tau x, \tau y, \tau z\) are subobjects of \(\Gamma\). Now suppose that \(\tau x \land \tau y \neq \bot\) and \(\tau y \land \tau z \neq \bot\). Clearly we always have that \(\tau x \land \tau y \land \tau z \leq \tau x \land \tau z\), so we have to show that, if \(w \in \tau x \land \tau z\), then we also have \(w \in \tau y\). To see this, observe that, since \(T\) is a tree and since \(\mathsf{colim} \tau = \Gamma\), the only way to have \(\tau x \land \tau y \neq \bot\) and \(\tau y \land \tau z \neq \bot\) is for \(y\) to lie on the unique path from \(x\) to \(z\) in \(T\) (if not, then you’d get a cycle). But then notice, since \(\mathsf{colim} \tau = \Gamma\), we must have \(w \in \tau y\) as deisred.
For the converse direction, take a weak tree arrangement \(\delta \colon \Delta \to \mathsf{Sub} \Gamma\). The naïve approach is to just make a structured decomposition for \(\Gamma\) by taking pairwise intersections between the elements of the tree ararngement (notice, as we did earlier, that condition (TR) implies condition (D)). However, if you do this, you’ll likely end up with a structured decomposition $$d_0 \colon \int G_0 \to \mathsf{Gr}$$ which isn’t tree-shaped. We’ll see that this is just a superficial issue since there is a way of “uncycling” the decomposition in what follows (this will then conclude the proof). Suppose we have elements \(x_1, \dots, x_n\) in \(\Delta\) which give rise to a cycle in \(d\); i.e. such that \( x_n \land x_1 \neq \bot \) and \( x_i \land x_{i+1} \neq \bot \) for all \(1 \leq i < n\). Then obseve that condition (WTPR) implies that \(\delta x_i \land \delta x_j = \delta x_k \land \delta x_\ell\) for all distinct \(x_i, x_j, x_k\) and with \(x_\ell\) distinct from \(x_k\). Thus we have shown that \(x_i \land x_j = \bigwedge_{k \in \{1, \dots, n\}} x_k\) (for dinstinct \(x_i, x_j\)) and thus that any cycle in \(d\) actually also contains a wheel where the spokes are centered at \(\bigwedge_{k \in \{1, \dots, n\}} x_k\). We will use this to make a new decomposition \(d_1\) from \(d_0\) as follows. Let \(G_1\) be the graph obtained from \(G_0\) (where \(G_0\) is the shape graph of \(d_0\)) by removing all the edges joining any two vertices in the cycle \(x_1 \dots x_n\) we were just considering and then adding a star centered at a new vertex \(w_1\) and with \(x_1, x_2, \dots, x_n\) as its leaves. Thus define \(d_1 \colon \int G_1 \to \mathsf{Gr}\) by letting \(d_1(x) = d_0(x)\) for all \(x \in G_1 \cap G_2\) and setting \(d_1(w) = \bigwedge_{k \in \{1, \dots, n\}} x_k\) and associating to each edge \(wx_i\) of the star centered at \(w\) the trivial adhesion \(\bigwedge_{k \in \{1, \dots, n\}} x_k \leftarrow \bigwedge_{k \in \{1, \dots, n\}} x_k \hookrightarrow x_i\). From what we argued before (namely that \(x_i \land x_j = \bigwedge_{k \in \{1, \dots, n\}} x_k\)) we have that \(\mathsf{colim} d_1 = \mathsf{colim} d_0 = \Gamma\). The plan is to show that \(G_1\) has strictly fewer cycles than \(G_0\); the result will then follow since it implies that by continuing this process \(d_0, d_1, \dots \) we will eventually (in a finite number of steps since \(G_0\) is finite) reach a acyclic decomposition, as desired (note that I’m not distinguishing between trees and forests..). This is the following claim.
Claim: let \(H\) be the graph obtained from \(G\) by replacing a clique on the vertices \(x_1, \dots, x_n\) with a star with center \(w\) and leaves \(x_1, \dots, x_n\). Then there is an injection \(|\{C \mid C \text{ is a cycle in } H\}| < |\{C \mid C \text{ is a cycle in } G\}|.\) Proof: There is an injection $$f \colon \{C \mid C \text{ is a cycle in } H\} \hookrightarrow \{C \mid C \text{ is a cycle in } G\}$$ defined as follows. For any cycle \(C\) in \(H\), if \(C\) uses no edges of the star centered at \(w\), then \(C\) is also a cycle in \(G\) so let \(f\) take \(C\) to `itself’ in \(G\). Otherwise, \(C\) must use precisely two edges of the star — w.l.o.g. let these be \(x_1 w\) and \(w x_2\) — so, since \(x_1, \dots, x_n\) was a clique in \(G\), we can map the cycle \(C\) the cycle \(C – \{x_1 w, w x_2\} +\{x_1x_2\}\). Completing the proof, observe that some cycles of \(G\) (e.g. those that more than one edge of the clique on the vertices \(x_1, \dots, x_n\) ) are not in the image of the injection \(f\). Thus \(|\{C \mid C \text{ is a cycle in } H\}| < |\{C \mid C \text{ is a cycle in } G\}|\), as desired.
My sense of aethetics tell me that it would be ideal if we could change the definition of a weak tree (pre-) arrangement so as to make sure that it consist of a downwards-closed sub poset. It turns out this is possible (giving rise to what I’ll call tree pre-arrangements and tree arrangements) so I’ll include this definition below.
Df. let \(\delta \colon \Delta \to \mathsf{Sub} \Gamma\) be a downwards-closed subposet of \(\mathsf{Sub} \Gamma\). We call \(\delta\) a tree pre-arrangement if for all \(x, y’, z \in \Delta\) the following holds:
(TPR) if \(\delta x \land \delta y’ \neq \bot\) and \(\delta y’ \land \delta z \neq \bot\) then for all maximal \(y \geq y’\) in \(\Delta\) we have that \(\delta x \land \delta y \land \delta z = \delta x \land \delta z\).
We say that \(\delta\) is a tree arrangement if it is a pre-arrangement which also satisfies the following condition:
(TR) for all \(x \in \mathsf{Sub} \Gamma\), there exists a subposet \(\delta’ \colon \Delta’ \to \Delta\) such that \(x \leq \bigvee_{x’ \in \Delta’} \delta \delta’ x’\).
That is to say that weak tree pre-arrangements are just the maximal elements of tree pre-arrangements as is noted below.
Prop. tree (pre-) arrangements are exactly the downwards-closures of weak tree (pre-) arangments.
Proof: Let \(\delta \colon \Delta \to \mathsf{Sub}\Gamma\) be a weak tree (pre-) arrangement. Clearly, if \(\bigvee_{x \in \Delta} \delta x = \top\), then this also holds for the downwards closure of \(\delta\) and vice-versa. Thus all we need to show is that condition (WTPR) in a weak tree pre-arrangement is equivlaent to condition (TPR) in a tree pre-arrangement; however, this is immediate since condition (TPR) is saying exactly that the collection of maximal elements in \(\delta\) satisfy condition (WTPR) (because tree pre-arrangements are downwards closed).
3. A small note on generalizing these ideas
Notice that the only assumptios we used above were:
that pushouts of monos exist and are monos
that the subobject lattice has pullbacks (i.e. that pullbacks of monos exist)
that, taking the supremum in the subobject lattice to be defined as a pushout over a pullback of monos, the lattice becomes a distributive lattice.
With a list of requirements like this, my friend Paweł Sobociński would imediately exclaim: “you shouldn’t be working with graphs, you should be working with adhesive categories”. Obviously Paweł would be correct in saying this and indeed averything I just mentioned works in any adhesive category.
