4
$\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 '13 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$ – Martin Brandenburg Sep 8 '13 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$ – Hans-Peter Stricker Sep 9 '13 at 9:21
  • $\begingroup$ @Martin: This question is for motivation: math.stackexchange.com/questions/488700/… $\endgroup$ – Hans-Peter Stricker Sep 9 '13 at 19:08
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$ – Martin Brandenburg Sep 9 '13 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 '13 at 22:37
  • $\begingroup$ In ACC these are called indiscrete objects. $\endgroup$ – Martin Brandenburg Sep 10 '13 at 7:13
  • $\begingroup$ @ZhenLin thanks for the correction, I'll edit the answer. $\endgroup$ – Giorgio Mossa Sep 10 '13 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$ – Peter Heinig Jun 28 '17 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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