5
$\begingroup$

In the category of (finite) simple graphs with graph homomorphisms $\mathsf{SimpGph}$, (how) can the complete graphs $K_n$ be characterized by genuinely categorical means? Are they somehow "distinguished" categorically?

Miscellaneous findings so far:

  • $\mathsf{SimpGph}$ has only the null graph $K_0$ as its initial object (from which one cannot construct other graphs) and no terminal object at all.

  • When loops are allowed the single-vertex-with-one-loop-graph is terminal, but it is not the complete graph $K_1$.

  • The digraph $\circ\!\!\rightarrow\!\!\circ$ of two vertices with a single arrow between them (something like the directed version of $K_2$) gives rise to a functor category which is essentially the category of all digraphs.

$\endgroup$
4
  • $\begingroup$ I am not sure if there is a way to consistently define a directed version of $K_n$ for every $n$. $\endgroup$
    – Tunococ
    Sep 8, 2013 at 12:25
  • $\begingroup$ Why all these "categorical characterization of Bla" questions? Of course I have also asked this a couple of times on mathoverflow, but this was always motivated to prove some kind of rigidity theorem. What's the purpose of defining complete graphs categorically? And what does this mean at all? $\endgroup$ Sep 8, 2013 at 14:18
  • $\begingroup$ I found your MO question on the rigidity of the category of schemes where you write "[...] that a category is rigid if every object can be defined in a categorical way". What did you have in mind with "defined in a categorical way"? $\endgroup$ Sep 9, 2013 at 9:21
  • $\begingroup$ @Martin: This question is for motivation: math.stackexchange.com/questions/488700/… $\endgroup$ Sep 9, 2013 at 19:08

1 Answer 1

4
$\begingroup$

From the definition a simple graph is a set with a symmetric-reflexive relation, and since we are considering finite graph we deal with finite sets. Then there's a trivial functor $U \colon \mathbf{SimpGrp} \to \mathbf{FinSet}$, where $\mathbf{FinSet}$ is the category of finite sets and function between them, sending every graph in its undeliing set and every graph morphism in its underlining function. Such a functor is faithfull so gives the structure of a concrete category.

Now a $K_n$ is just a indiscrete object in the sense of the Abstract and concrete categories, i.e. is object in $\mathbf{SimpGrp}$ such that for every other graph $X$ and every function $f \colon U(X) \to U(K_n)$ there's always a (unique) lift $\tilde f \colon X \to K_n$ in $\mathbf{SimpGrp}$ such that $U(\tilde f)=f$.

Is this satisfying?

$\endgroup$
5
  • $\begingroup$ Interesting. Discrete objects are introduced in Definition 8.1 of ACC. $\endgroup$ Sep 9, 2013 at 21:49
  • 3
    $\begingroup$ Your second paragraph is incorrect: $K_n$ is a codiscrete object. (The discrete graph on a set of vertices is, of course, the one with no edges.) $\endgroup$
    – Zhen Lin
    Sep 9, 2013 at 22:37
  • $\begingroup$ In ACC these are called indiscrete objects. $\endgroup$ Sep 10, 2013 at 7:13
  • $\begingroup$ @ZhenLin thanks for the correction, I'll edit the answer. $\endgroup$ Sep 10, 2013 at 10:04
  • $\begingroup$ Just to amplify the above comments: the complete graph can also be called a cofree object in a usual sense: it can be characterized as the representing object of the presheaf determined by a certain forgetful functor $U$, showing that this $U$ has a right-adjoint. (Incidentally, this $U$ has a left-adjoint $L$, too; $L$ sends a set to the "edge-free" graph with that vertex-set.) $\endgroup$ Jun 28, 2017 at 19:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .