Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: line graphs

Daniel Plácido (May 01 2021 at 04:00):

Today I was reading about the line graph of a graph. This construction takes a graph $G$ and creates a graph whose nodes are the edges of $G$. I'm pretty convinced that this is an endofunctor $\mathsf{Graph}\to\mathsf{Graph}$ defined by sending $s,t:E\rightrightarrows V$ to the legs of this pullback:

Then the universal maps define the action on morphisms, and also by universality we get associativity, unitality, etc.

Is there any categorical way of going "the other way around"? The answer is no, since there's this Whitney's isomorphism theorem:

If the line graphs of two connected graphs are isomorphic, then the underlying graphs are isomorphic, except in the case of the triangle graph $K_3$ and the claw $K_{1,3}$, which have isomorphic line graphs but are not themselves isomorphic.

Can this be """fixed""" in any way, as in making a functor taking a line graph and reconstructing (approximately?) the original graph?

John Baez (May 01 2021 at 04:30):

What you're saying sounds interesting, but your picture isn't visible for me so I can't really understand what the "line graph" is.

Oscar Cunningham (May 01 2021 at 06:32):

For $s$ and $t$ to make sense do we have to be thinking about the version of 'line graph' that works for directed graphs? I think for the definition here https://en.wikipedia.org/wiki/Line_graph#Line_digraphs the diagram would be the pullback of $s$ and $t$ themselves.

John Baez (May 01 2021 at 14:24):

Okay, that definition looks good. For category theorists a graph (also called a directed multigraph or quiver) is a pair of functions $s, t: E \to V$. Taking the pullback of these we get the set of length-two paths, and this pullback has two maps to $E$. So, we get a new graph, the line graph, where the set of vertices is $E$ and the set of edges is the set of length-two paths.

John Baez (May 01 2021 at 14:27):

So yes, one question is whether there's a version of Whitney's isomorphism theorem for quivers: the original version is for graph theorists' graphs (also called simple graphs).

Oscar Cunningham (May 01 2021 at 15:13):

Another question we could ask is whether the line-graph functor is an adjoint.

It's definitely not a right adjoint since it doesn't preserve the terminal object (the point gets sent to the empty graph).

If it's a left adjoint, with right adjoint $U$, then we would have $V_{U(G)} = \mathrm{Hom}(1,U(G)) = \mathrm{Hom}(F(1),G) = \mathrm{Hom}(0,G) = 1$ and $E_{U(G)} = \mathrm{Hom}(\bullet\to\bullet,U(G)) = \mathrm{Hom}(F(\bullet\to\bullet),G) = \mathrm{Hom}(1,G) = V_G$. So then maps $H\to U(G)$ would just be arbitrary functions $E_H\to V_G$, which is very different from $F(H)\to G$.

So no adjoints.

Spencer Breiner (May 01 2021 at 16:06):

Oscar Cunningham said:

It's definitely not a right adjoint since it doesn't preserve the terminal object (the point gets sent to the empty graph).

Are you sure? Terminal object in graphs has a loop $\ell$, so the line graph of 1 looks to me like it is terminal : $\{\ell\circ\ell\}\rightrightarrows\{\ell\}$

Oscar Cunningham (May 01 2021 at 16:08):

Ooh, good point!

Daniel Plácido (May 01 2021 at 16:27):

John Baez said:

your picture isn't visible for me

sorry, here it is image.png

Daniel Plácido (May 01 2021 at 16:28):

Oscar Cunningham said:

the diagram would be the pullback of $s$ and $t$ themselves.

as Osscar noticed :)

Oscar Cunningham (May 01 2021 at 16:52):

Now I think there is a right adjoint. Given a graph $G$, define $R(G)$ by starting with an independent arrow for each vertex of $G$ and then for each arrow in $G$ quotient together the target of the arrow corresponding to its source with the source of the arrow corresponding to its target. I think that in other words this is just the pushout of $s$ and $t$.

Oscar Cunningham (May 01 2021 at 16:55):

Also I found an example of the line graph construction not being reversible. The graph with vertices $a$ and $b$ with two arrows between them has the same line graph as the graph with an arrow from $a$ to $b$ and an arrow from $c$ to $d$.

Joe Moeller (May 03 2021 at 13:58):

I'm about to read this thread, but before I do, I'll just do a shameless self-plug for something related. In my paper Noncommutative network models, I use Kneser graphs (a cousin to line graphs) to describe some algebraic properties I wanted a categorical gizmo to have. One thing I show is that the assignment of the kneser graph $KG_{n,k}$ to a set of size $n$ gives a lax symmetric monoidal functor $KG_{-,k} \colon (\mathsf{FinInj}, +) \to (\mathsf{SimpGrph}, +)$. Sorry if this is too diverting!

John Baez (May 03 2021 at 16:21):

Indeed, this discussion of line graphs made me think of Kneser graphs, and you.