Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
I am not sure if there is a way to consistently define a directed version of $K_n$ for every $n$. – Tunococ Sep 8 '13 at 12:25
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? – Martin Brandenburg Sep 8 '13 at 14:18
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"? – Hans Stricker Sep 9 '13 at 9:21
@Martin: This question is for motivation:… – Hans Stricker Sep 9 '13 at 19:08

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?

share|cite|improve this answer
Interesting. Discrete objects are introduced in Definition 8.1 of ACC. – Martin Brandenburg Sep 9 '13 at 21:49
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.) – Zhen Lin Sep 9 '13 at 22:37
In ACC these are called indiscrete objects. – Martin Brandenburg Sep 10 '13 at 7:13
@ZhenLin thanks for the correction, I'll edit the answer. – Giorgio Mossa Sep 10 '13 at 10:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.