# Graph colourings and Hedetniemi’s conjecture II: universal colouring

In my previous post, I stated the recently disproved Hedetniemi’s conjecture on colourings of product graphs (see this post for my conventions on graphs). In the next few posts, I will explain some of the ideas of the proof from an algebraic geometer’s perspective.

Lemma. Let be a graph. Then there exists an -colouring on such that for every graph and every -colouring on , there is a unique morphism such that .

Proof. By this post, we have the adjunction

(1)

In particular, the identity gives an -colouring under this adjunction. If is any other graph, (1) gives a bijection between morphisms and -colourings of , which by naturality of (1) is given by .

Corollary. To prove Hedetniemi’s conjecture, it suffices to treat the ‘universal’ case , for every and every loopless graph .

Proof. Suppose by contradiction that there is a counterexample , i.e. there are loopless graphs and such that

(2)

Then there exists an -colouring , so the lemma gives a map such that . This forces since an -colouring on induces an -colouring on by pullback. Thus, (2) implies

showing that is a counterexample as well.

Corollary. Hedetniemi’s conjecture is equivalent to the statement that for any loopless graph and any , either or admits an -colouring.

Example. By the final example of my previous post and the proof of the first corollary above, the cases are trivially true. We can also check this by hand:

• If does not have a -colouring, then it has an edge. Then has no edges by construction, since has no edges. See also Example 2 of this post.
• If does not have a -colouring, then it has an odd cycle . We need to produce a -colouring on . Choose identifications and with adjacencies . Consider the map

To show this is a graph homomorphism, we must show that for adjacent we have . If two maps are adjacent, then for adjacent we have . Taking shows that , so

since is odd.

The case is treated in [EZS85], which seems to be one of the first places where the internal Hom of graphs appears (in the specific setting of ).

References.

[EZS85] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4. Combinatorica 5.2, p. 121–126 (1985).

# Internal Hom in the category of graphs

In this earlier post, I described what products in the category of graphs look like. In my previous post, I gave some basic examples of internal Hom. Today we will combine these and describe the internal Hom in the category of graphs.

Definition. Let and be graphs. Then the graph has vertices , and an edge from to if and only if implies (where we allow as usual).

Lemma. If , , and are graphs, then there is a natural isomorphism

In other words, is the internal Hom in the symmetric monoidal category .

Proof. There is a bijection

So it suffices to show that is a graph homomorphism if and only if is. The condition that is a graph homomorphism means that for any , the functions have the property that implies . This is equivalent to for all and all . By the construction of the product graph , this is exactly the condition that is a graph homomorphism.

Because the symmetric monoidal structure on is given by the categorical product, it is customary to refer to the internal as the exponential graph .

Example 1. Let be the discrete graph on a set . Then is the complete graph with loops on the set . Indeed, the condition for two functions to be adjacent is vacuous since has no edges.

In particular, any function is a graph homomorphism. Under the adjunction above, this corresponds to the fact that any function is a graph homomorphism, since is a discrete graph.

Example 2. Conversely, is discrete as soon as has an edge, and complete with loops otherwise. Indeed, the condition

can only be satisfied if , and in that case is true for all and .

In particular, a function is a graph homomorphism if and only if either or has no edges. Under the adjunction above, this corresponds to the fact that a function is a graph homomorphism to if and only if has no edges, which means either or has no edges.

Example 3. Let be the discrete graph on a set with loops at every point. Then is the -fold power of . Indeed, the condition that two functions are adjacent is that for all , which means exactly that for each of the projections .

In particular, graph homomorphisms correspond to giving graph homomorphisms . Under the adjunction above, this corresponds to the fact that a graph homomorphism is the same thing as graph homomorphisms , since is the -fold disjoint union of .

Example 4. Let be the terminal graph consisting of a single point with a loop (note that we used instead for in this earlier post). The observation above that also works the other way around: . Then the adjunction gives

This is actually true in any symmetric monoidal category with internal hom and identity object . We conclude that a function is a graph homomorphism if and only if has a loop at . This is also immediately seen from the definition: has a loop at if and only if implies .

Example 5. Let and be the complete graphs on and vertices respectively. Then has as vertices all -tuples , and an edge from to if and only if when . For example, for we get an edge between and if and only if and .

# Internal Hom

This is an introductory post about some easy examples of internal Hom.

Definition. Let be a symmetric monoidal category, i.e. a category with a functor that is associative, unital, and commutative up to natural isomorphism. Then an internal Hom in is a functor

such that is a left adjoint to for any , i.e. there are functorial isomorphisms

Remark. In the easiest examples, we typically think of as ‘upgrading to an object of ‘:

Example. Let be a commutative ring, and let be the category of -modules, with the tensor product. Then with its natural -module structure is an internal Hom, by the usual tensor-Hom adjunction:

The same is true when is the category of -bimodules for a not necessarily commutative ring .

However, we cannot do this for left -modules over a noncommutative ring, because there is no natural -module structure on for left -modules and . In general, the tensor product takes an -bimodule and a -bimodule and produces an -bimodule . Taking gives a way to tensor a right -module with a left -module, but there is no standard way to tensor two left -modules, let alone equip it with the structure of a left -module.

Example. Let . Then is naturally a set, making it into an internal Hom for :

When is the categorical product , the internal (if it exists) is usually called an exponential object, in analogy with the case above.

Example. Another example of exponential objects is from topology. Let be the category of locally compact Hausdorff topological spaces. Then the compact-open topology makes into an internal Hom of topological spaces. (There are mild generalisations of this beyond the compact Hausdorff case, but for an arbitrary topological space the functor does not preserve colimits and hence cannot admit a right adjoint.)

Example. An example of a slightly different nature is chain complexes: let be a commutative ring, and let be the category of cochain complexes

of -modules (meaning each is an -module, and the are -linear maps satisfying ). Homomorphisms are commutative diagrams

and the tensor product is given by the direct sum totalisation of the double complex of componentwise tensor products.

There isn’t a natural way to ‘endow with the structure of a chain complex’, but there is an internal Hom given by

with differentials given by

Then we get for example

since a morphism is given by an element such that , i.e. , meaning that is a morphism of cochain complexes.

Example. The final example for today is presheaves and sheaves. If is a topological space, then the category of abelian sheaves on has an internal Hom given by

with the obvious transition maps for inclusions of open sets. This is usually called the sheaf Hom. A similar statement holds for presheaves.

# Limits in the category of graphs

This is a first post about some categorical properties of graphs (there might be a few more).

Definition. For us, a graph is a pair where is a set and is a collection of subsets of of size or . An element with is called an edge from to , and a singleton is a loop at (or sometimes an edge from to itself). If , it is customary to write and .

A morphism of graphs is a map such that for all . The category of graphs will be denoted , and will be called the forgetful functor.

Example. The complete graph on vertices is the graph where and is the set of -element subsets of . In other words, there is an edge from to if and only if .

Then a morphism is exactly an -colouring of : the condition for forces whenever and are adjacent. Conversely, a morphism to a graph without loops is exactly an -clique in : the condition that has no loops forces for .

Lemma. The category has and the forgetful functor preserves all small limits.

Proof. Let be a functor from a small category , and let be the limit of the underlying sets, with cone maps . We will equip with a graph structure such that the maps for are morphisms and then show that the constructed is a limit of in .

To equip with an edge set , simply let be the set of of size or such that for all . Then this clearly makes into a graph such that the are graph morphisms for all . Moreover, these maps make into the limit cone over : for any other cone , the underlying maps factor uniquely through by the definition of , and the construction of shows that is actually a morphism of graphs .

Remark. Note however that does not create limits. On top of the construction above, this would mean that there is a unique graph structure on such that is a cone over . However, there are many such structures on , because we can remove edges all we want (on the same vertex set ).

Example. As an example, we explicitly describe the product of two graphs and : by the lemma its vertex set is . The ‘largest graph structure’ such that both projections and are graph morphisms is given by if and only if and and . This corresponds to the structure found in the proof of the lemma.

For a very concrete example, note that the product of two intervals/edges is a disjoint union of two intervals, corresponding to the diagonals in . This is the local model to keep in mind.

The literature also contains other types of product graphs, which all have the underlying set . Some authors use the notation for the categorical product or tensor product we described. The Cartesian product is defined by , so that the product of two intervals is a box. The strong product is the union of the two, so that the product of two intervals is a box with diagonals. There are numerous other notions of products of graphs.

Remark. Analogously, we can also show that has and preserves all small colimits: just equip the set-theoretic colimit with the edges coming from one of the graphs in the diagram.

Example. For a concrete example of a colimit, let’s carry out an edge contraction. Let be a graph, and let be an edge. The only way to contract in our category is to create a loop: let be the one-point graph without edges, and let be the maps sending to and respectively. Then the coequaliser of the parallel pair is the graph whose vertices are , where is the equivalence relation if and only if or , and whose edges are exactly the images of edges in . In particular, the edge gives a loop at the image .

Remark. Note that the preservation of limits also follows since has a left adjoint: to a set we can associate the discrete graph with vertex set and no edges. Then a morphism to any graph is just a set map .

Similarly, the complete graph with loops gives a right adjoint to , showing that all colimits that exist in must be preserved by . However, these considerations do not actually tell us which limits or colimits exist.

# Epimorphisms of groups

In my previous post, we saw that injections (surjections) in concrete categories are always monomorphisms (epimorphisms), and in some cases the converse holds.

We now wish to classify all epimorphisms of groups. To show that all epimorphisms are surjective, for any strict subgroup we want to construct maps to some group that differ on but agree on . In the case of abelian groups this is relatively easy, because we can take to be the cokernel, the quotient map, and the zero map. But in general the cokernel only exists if the image is normal, so a different argument is needed.

Lemma. Let be a group homomorphism. Then is an epimorphism if and only if is surjective.

Proof. We already saw that surjections are epimorphisms. Conversely, let be an epimorphism of groups. We may replace by its image in , since the map is still an epimorphism. Let be the coset space, viewed as a pointed set with distinguished element . Let be the set “ with the distinguished point doubled”, and write and for these distinguished points.

Let be the symmetric group on , and define homomorphisms by letting act naturally on the copy of in (for ). Since the action of on fixes the trivial coset , we see that the maps agree. Since is an epimorphism, this forces . But then

showing that is surjective (and a fortiori ).

Note however that the result is not true in every algebraic category. For example, the map is an epimorphism of (commutative) rings that is not surjective. More generally, every localisation is an epimorphism, by the universal property of localisation; these maps are rarely surjective.

# Concrete categories and monomorphisms

This post serves to collect some background on concrete categories for my next post.

Concrete categories are categories in which objects have an underlying set:

Definition. A concrete category is a pair of a category with a faithful functor . In cases where is understood, we will simply say is a concrete category.

Example. The categories of groups, of topological spaces, of rings, and of -modules are concrete in an obvious way. The category of sheaves on a site with enough points is concrete by mapping a sheaf to the disjoint union of its stalks (the same holds for any Grothendieck topos, but a different argument is needed). Similarly, the category of schemes can be concretised by sending to , where is the contravariant power set functor.

Today we will study the relationship between monomorphisms and injections in :

Lemma. Let be a concrete category, and let be a morphism in . If is a monomorphism (resp. epimorphism), then so is .

Proof. A morphism in is a monomorphism if and only if the induced map is injective. Faithfulness implies that the vertical maps in the commutative diagram

are injective, hence if the bottom map is injective so is the top. The statement about epimorphisms follows dually.

For example, this says that any injection of groups is a monomorphism, and any surjection of rings is an epimorphism, since the monomorphisms (epimorphisms) in are exactly the injections (surjections).

In some concrete categories, these are the only monomorphisms and epimorphisms. For example:

Lemma. Let be a concrete category such that the forgetful functor admits a left (right) adjoint. Then every monomorphism (epimorphism) in is injective (surjective).

Proof. If is a right adjoint, it preserves limits. But is a monomorphism if and only if the square

is a pullback. Thus, preserves monomorphisms if it preserves limits. The statement about epimorphisms is dual.

For example, the forgetful functors on algebraic categories like , , and have left adjoints (a free functor), so all monomorphisms are injective.

The forgetful functor has adjoints on both sides: the left adjoint is given by the discrete topology, and the right adjoint by the indiscrete topology. Thus, monomorphisms and epimorphisms in are exactly injections and surjections, respectively.

On the other hand, in the category of Hausdorff topological spaces, the inclusion is an epimorphism that is not surjective. Indeed, a map to a Hausdorff space is determined by its values on .

# Classification of compact objects in Top

In my previous post, I showed that compact objects in the category of topological spaces have to be finite. Today we improve this to a full characterisation.

Lemma. Let be a topological space. Then is a compact object in if and only if is finite discrete.

This result dates back to Gabriel and Ulmer [GU71, 6.4], as was pointed out to me by Jiří Rosický in reply to my MO question and answer of this account (of which this post is essentially a retelling). Our proof is different from the one given in [GU71], instead using a variant of an argument given in the n-Lab.

Before giving the proof, we construct an auxiliary space against which we will be testing compactness. It is essentially the colimit constructed in the n-Lab, except that we swapped the roles of and (the reason for this will become clear in the proof).

Definition. For all , let be the topological space , where the nonempty open sets are given by for . They form a topology since

Define the map by

This is continuous since equals if and if . Let be the colimit of this diagram.

Since the elements map to the same element in , we conclude that is the two-point space , where the map is the second coordinate projection. Moreover, the colimit topology on is the indiscrete topology. Indeed, neither nor are open.

Proof of Lemma. If is compact, then my previous post shows that is finite. Let be any subset, and let be the indicator function . It is continuous because has the indiscrete topology. Since is a compact object, has to factor through some . Let be the first coordinate projection, i.e.

Let be a number such that for all ; this exists because is finite. Then , which shows that is open. Since was arbitrary, we conclude that is discrete.

Conversely, every finite discrete space is a compact object. Indeed, any map out of is continuous, and finite sets are compact in .

[GU71] Gabriel, Peter and Ulmer, Friedrich, Lokal präsentierbare Kategorien. Lecture Notes in Mathematics 221. Springer-Verlag, Berlin-New York, 1971. DOI: 10.1007/BFb0059396.

# Compact objects in the category of topological spaces

We compare two competing notions of compactness for topological spaces. Besides the usual notion, there is the following:

Definition. Let be a cocomplete category. Then an object is compact if commutes with filtered colimits.

Exercise. An -module is compact if and only if it is finitely generated.

We want to study compact objects in the category of topological spaces. One would hope that this corresponds to compact topological spaces. However, this is very far off:

Lemma. Let be a compact object. Then is finite.

Proof. Let be the set with the indiscrete topology, i.e. . It is the union of all its finite subsets, and this gives it the colimit topology because a subset is open if and only if its intersection with each finite subset is. Indeed, if were neither nor , then there exist with and . But then is not open, because inherits the indiscrete topology from .

Therefore, if is a compact object, then the identity map factors through one of these finite subsets, hence is finite.

However, the converse is not true. In fact the indiscrete space on a two element set is not a compact object, as is explained here.

Corollary. Let be a compact object. Then is a compact topological space.

Proof. It is finite by the lemma above. Every finite topological space is compact.

Originally, this post relied on the universal open covering of my previous post to show that a compact object in is compact; however the above proof shows something much stronger.

# A fun example of a representable functor

This post is about representable functors:

Definition. Let be a functor. Then is representable if it is isomorphic to for some . In this case, we say that represents .

Exercise. If such exists, then it is unique up to unique isomorphism.

Really one should encode the isomorphism as well, but this is often dropped from the notation. By the Yoneda lemma, every natural transformation is uniquely determined by the element of corresponding to the identity of .

When is a natural isomorphism, the corresponding element is called the universal object of . It has the property that for every and any , there exists a unique morphism such that .

Example. The forgetful functor is represented by . Indeed, the natural map

is an isomorphism. The universal element is .

Example. Similarly, the forgetful functor is represented by . The universal element is .

A fun exercise (for the rest of your life!) is to see whether functors you encounter in your work are representable. See for example this post about some more geometric examples.

The main example for today is the following:

Lemma. The functor that associates to a topological space its topology is representable.

Proof. Consider the topological space with topology . Then there is a natural map

Conversely, given an open set , we can associate the characteristic function . This gives an inverse of the map above.

The space we constructed is called the Sierpiński space. The universal open set is .

Remark. The space represents the data of open sets for : for any continuous map , we have , where . If denotes the complementary open, then the form a cover of if and only if . This corresponds to the statement that lands in .

Thus, the open cover is the universal open cover, i.e. for every open covering there exists a unique continuous map such that .

# Sites without a terminal object

Let be a site with a terminal object . Then the cohomology on the site is defined as the derived functors of the global sections functor . But what do we do if the site does not have a terminal object?

The solution is to define as , where denotes the structure sheaf if is a ringed site. If is not equipped with a ring structure, we take to be the constant sheaf ; this makes into a ringed site.

Lemma. Let be a site with a terminal object . Then the above definitions agree, i.e.

Proof. Note that , since any map can be uniquely extended to a morphism of (pre)sheaves , and conversely every such morphism is determined by its map on global sections. The result now follows since and are defined as the derived functors of and respectively.

Remark. From this perspective, it seems quite magical that for a sheaf of -modules on a ringed space , the cohomology groups and agree. It turns out that this is true in the setting of ringed sites as well; see Tag 03FD.

So why is this useful? Let’s give some examples of sites that do not have a terminal object.

Example. Let be a group scheme over . Then we have a stack of -torsors. The objects of are pairs , where is a -scheme and is a -torsor over . Morphisms are pairs making the diagram

commutative. This forces the diagram to be a pullback, since all maps between -torsors are isomorphisms.

The (large) Zariski site on is defined by declaring coverings to be families such that is a Zariski covering (and similarly for the étale and fppf sites).

Now does the category have a terminal object? This would be a -torsor such that every other -torsor admits a unique map to it, realising as the pullback of along . But this object would exactly be the classifying stack , which does not exist as a scheme (or algebraic space). The fact that a terminal object does not exist is the whole reason we need to define it as a stack in the first place!

Example. Let be a variety in characteristic ; for simplicity, let’s say . Then consider the crystalline site of . Roughly speaking, its objects are triples , where is an open immersion, is a thickening with a map to , and is a divided power structure on the ideal sheaf (with a compatibility condition w.r.t. ). There is a suitable notion of morphisms.

This site does not have a terminal object, basically because there are many thickenings on with the respective compatibilities. (I am admittedly no expert, and it could very well be true that this is not 100% correct. However, I am certain that the crystalline site in general does not have a terminal object.)