Zulip Chat Archive

Stream: graph theory

Topic: category of graphs


view this post on Zulip Jalex Stark (Aug 29 2020 at 21:50):

@Alena Gusakov and I started trying to define this together, but we detoured into doing Scott's lftcm exercises and don't have a definition

view this post on Zulip Jalex Stark (Aug 29 2020 at 21:50):

I think there is a category file in branch#hedetniemi ?

view this post on Zulip Jalex Stark (Aug 29 2020 at 21:53):

oh, maybe I'm wrong, they do have this, though

def as_graph (C) [category_theory.category C] : directed_multigraph C :=
{ edge := λ x y, x  y }

view this post on Zulip Aaron Anderson (Aug 29 2020 at 21:53):

There are a few different definitions?

view this post on Zulip Aaron Anderson (Aug 29 2020 at 21:53):

In your attempts so far, are the morphisms homomorphisms or embeddings?

view this post on Zulip Kyle Miller (Aug 29 2020 at 21:53):

I think that's the definition that takes a category and reinterprets it as a directed multigraph

view this post on Zulip Kyle Miller (Aug 29 2020 at 21:54):

it's like the inverse of has_hom (but not quite)

view this post on Zulip Jalex Stark (Aug 29 2020 at 21:54):

the category of homormorphisms is more interesting

view this post on Zulip Kyle Miller (Aug 29 2020 at 21:56):

@Aaron Anderson in your definition of embedding, why did you make it so that image must be an induced graph? I haven't checked, but I don't think that's what a monomorphism would be given your definition of a homomorphism.

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:00):

The real reason is that that's the definition of an embedding from model theory, but I can think of a few justifications

view this post on Zulip Kyle Miller (Aug 29 2020 at 22:03):

It's not what I would expect from the word 'embedding'. I'd like to be able to define a path as an embedding of a path graph, for example. What's a use of your definition of an embedding with respect to graph theory?

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:07):

When showing the random graph is unique, you use an increasing chain of partial embeddings between two random graphs, and you want this definition

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:08):

Sometimes you do want an embedding to have to be an isomorphism onto its image

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:08):

According to nLab, my definition corresponds to a "regular mono"

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:08):

And they philosophically say "A monomorphism is regular if it behaves like an embedding."

view this post on Zulip Kyle Miller (Aug 29 2020 at 22:15):

I guess the analogue in topology is that this is the difference between a smooth embedding and an injective smooth map. I tend to think of graphs as being topologically realized, which means arbitrary subdivisions of edges are equivalent, at least as far as maps are concerned. However, if you cannot subdivide edges, then as a simplicial map the embedding really would need to have an image that's an induced subgraph. (Topologically, you want the simplicial image to have a regular neighborhood. Injective graph homomorphisms don't have these in general.)

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:16):

It's probably worth noting the nlab's definition of the category of graphs as well: https://ncatlab.org/nlab/show/category+of+simple+graphs

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:18):

Although there's also: https://ncatlab.org/nlab/show/the+category+of+simple+graphs+from+a+graph-theoretic+perspective

view this post on Zulip Kyle Miller (Aug 29 2020 at 22:22):

Something I'd like to be true is that if GG' is a subgraph of GG, then there is some notion of an embedding GGG' \hookrightarrow G.

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:23):

"monos in SimpGph are simple graph maps that are injective on vertices and edges,"

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:24):

Pretty sure this matches what you want?

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:25):

Yeah, I’d be in favor of having bundled monos and regular monos, but I prefer the regular monos get the name and symbol of embeddings.

view this post on Zulip Kyle Miller (Aug 29 2020 at 22:25):

Yeah, exactly. I believe that regular monomorphisms are useful, too, but I'd like to make sure that there is notation for monomorphisms.

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:26):

In the category theory library, neither of these are bundled (which I think is a good thing) and they're all typeclasses (which I think might be a bad thing)

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:26):

I can certainly see the value of bundling them for graphs though

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:26):

It’s also nice that the regular mono version is available as an abbreviation

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:27):

I do add those abbreviations in #3946

view this post on Zulip Aaron Anderson (Aug 29 2020 at 22:28):

Cycling this thread back around, I’d be happy to help define the category, as I think I understand how bundled categories work

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:29):

I wonder how horrible it'd be to define the category of graphs like this instead: https://ncatlab.org/nlab/show/category+of+simple+graphs#properties_of_

view this post on Zulip Jalex Stark (Aug 29 2020 at 22:30):

so eventually we will have a theorem like

\forall \iota, (Graph.hom_of_embedding \iota).is_mono

?

view this post on Zulip Jalex Stark (Aug 29 2020 at 22:30):

uh, i hope you don't mean defining it via theorem 3.1

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:31):

I do mean that, but I'm not seriously suggesting it as the definition

view this post on Zulip Jalex Stark (Aug 29 2020 at 22:31):

got it

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:31):

I think I do basically have all the language and theory built up to prove most of that though

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:32):

I expect it won't give results which aren't easier to prove directly but still!

view this post on Zulip Jalex Stark (Aug 29 2020 at 22:33):

I'm in favor of the goal "prove all of the theorems on the nlab page for which mathlib already has the categorical definitions"

view this post on Zulip Jalex Stark (Aug 29 2020 at 22:34):

and I think the same goal with "mathlib" replaced by "bhavik's topos repo" is interesting but I don't know enough math to contribute at all :sweat_smile:

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 22:35):

Haha, entirely reasonable! Unless someone else is interested in helping me do it or there's a result which people who don't care about categories want out of it, I don't think I'll get to it any time soon either :)

view this post on Zulip Jalex Stark (Aug 29 2020 at 23:32):

Oh, i just noticed what you said on the other topic about requiring reflexivity. The most natural category of graphs in my mind allows self-loops but doesn't force them. The graph with a single vertex and a single edge is a terminal object.

view this post on Zulip Jalex Stark (Aug 29 2020 at 23:33):

But I want to express the property "G is not 3-colorable" as "G does not have a homomorphism to K_3", so I don't want K_3 to be pointed (where by "pointed" i mean "have a map from the terminal object", idk if that is a standard terminology)

view this post on Zulip Bhavik Mehta (Aug 29 2020 at 23:41):

Yeah there's sometimes friction between the 'natural' category and the one with lots of good categorical properties

view this post on Zulip Alena Gusakov (Aug 30 2020 at 01:53):

Hope I didn't miss anything earlier about this - is there a reason why we're not defining things in a way similar to monoids, e.g. having simple_graph be a class and having bundled structure graph_hom? I'm running into some issues with trying to define the category of simple graphs cause I can't seem to bundle things in a way where we can derive stuff.

view this post on Zulip Aaron Anderson (Aug 30 2020 at 01:54):

So the basic idea is that we sometimes want to study multiple graphs on the same type

view this post on Zulip Aaron Anderson (Aug 30 2020 at 01:55):

And so we can’t just have a type with an instance on it, because multiple non-equal instances are hard to juggle between

view this post on Zulip Aaron Anderson (Aug 30 2020 at 01:55):

But somehow they pulled that off with topological_space, where sometimes it’s an instance, and sometimes it’s not

view this post on Zulip Alena Gusakov (Aug 30 2020 at 01:55):

Ohhhh okay gotcha. Sorry, I think I did actually have that conversation with someone and forgot about it

view this post on Zulip Aaron Anderson (Aug 30 2020 at 01:57):

We should probably study the topology library and see if we maybe could get away with graph instances sometimes after all

view this post on Zulip Bhavik Mehta (Aug 30 2020 at 02:11):

I think it might be worth looking at options which don't use bundled then because it's designed for when the structure is a typeclass

view this post on Zulip Kyle Miller (Aug 30 2020 at 02:53):

There's nothing that says the class has to be associated to a type, by the way -- it's just that most algebraic objects tend to be referred to by their carrier type. You can associate it to the VVPropV \to V \to \mathrm{Prop} relation if you wanted. (See the graph defs thread from today.) There is a very strong case to be made the adjacency relation is the graph.

I think with topological spaces, most of the time the underlying set has a natural topology, so it still makes sense for a typeclass even if you need the occasional escape hatch. I don't think anyone ever refers to the vertex set of a graph and assumes it has an associated graph structure.

But, if you insist on typeclasses on the vertex type, the trick you can do is something like this:

@[irreducible] def complete_graph (V : Type*) := V

instance {V : Type*} : simple_graph (complete_graph V) := sorry

but then you'd have to deal with the fact that the adjacency relation is defined on complete_graph V rather than V itself.

view this post on Zulip Kyle Miller (Aug 30 2020 at 04:28):

Given what @Bhavik Mehta pointed out on ncatlab, maybe this is a reasonable definition of the category? Regarding what @Jalex Stark was saying about colorability, it seems like you can define the notion of local injectivity (a function is locally injective if whenever f(v) = f(w), then v is not adjacent to w), and then a proper coloring is a locally injective graph homomorphism to a complete graph.

import category_theory.category
import tactic

open category_theory

universes u v w

structure simple_graph :=
(V : Type u)
(adj' : V  V  Prop)
(symm' : symmetric adj' . obviously)
(refl' : reflexive adj' . obviously)

namespace simple_graph

abbreviation adj {G : simple_graph.{u}} (u v : G.V) : Prop := G.adj' u v

infix ~ := adj
-- or infix ` ~g ` : 40 := adj

end simple_graph

@[ext]
structure hom (G : simple_graph.{u}) (G' : simple_graph.{v}) :=
(to_fun : G.V  G'.V)
(map_adj :  v w : G.V⦄, v ~ w  to_fun v ~ to_fun w)

instance (G : simple_graph.{u}) (G' : simple_graph.{v}) : has_coe_to_fun (hom G G') :=
⟨_, hom.to_fun

def hom.id (G : simple_graph.{u}) : hom G G :=
{ to_fun := id,
  map_adj := by tidy }

section hom

variables {G : simple_graph.{u}} {G' : simple_graph.{v}} {G'' : simple_graph.{w}}

def hom.trans (f : hom G G') (f' : hom G' G'') : hom G G'' :=
{ to_fun := f'  f,
  map_adj := by { intros v w h, repeat { rw function.comp_app }, exact f'.map_adj (f.map_adj h) } }

def hom.locally_injective (f : hom G G') : Prop :=  v w : G.V⦄, f v = f w  ¬(v ~ w)

end hom

instance : has_hom (simple_graph.{u}) :=
{ hom := hom }

instance : category_struct (simple_graph.{u}) :=
{ id := hom.id,
  comp := @hom.trans }

instance : category (simple_graph.{u}) :=
{ }

def complete_graph (V : Type u) : simple_graph.{u} :=
{ V := V,
  adj' := λ v w, true }

/--
A coloring of the graph G by colors from α.
-/
structure coloring (G : simple_graph.{u}) (α : Type v) :=
(f : hom G (complete_graph α))
(proper : f.locally_injective)

view this post on Zulip Kyle Miller (Aug 30 2020 at 04:30):

I tried being a little careful about universes, allowing a homomorphism to go between graphs in different universes. The category itself only has graphs all in the same universe.

view this post on Zulip Kyle Miller (Aug 30 2020 at 04:31):

Anyway, this category supports homomorphisms to edge contractions, which is kind of nice.

view this post on Zulip Kyle Miller (Aug 30 2020 at 04:35):

(For subgraphs, you could define a category of subgraphs for each graph (morphisms are the poset of inclusions), then for each morphism in the category get an induced functor between subgraph categories. There'd also be the inclusion functor from a subgraph category back to the graph category, each morphism in the image being monic.)

view this post on Zulip Kyle Miller (Aug 30 2020 at 04:39):

Oh, I made a mistake with the definition of locally injective, and probably other things. I'm not used to the adjacency relation being reflexive!

One thing to remember is that you'd need the definition for neighbor_set to account for reflexivity:

variables {G : simple_graph.{u}}

def neighbor_set (v : G.V) : set G.V := {w : G.V | v ~ w  v  w}

def closed_neighbor_set (v : G.V) : set G.V := {w : G.V | v ~ w}

view this post on Zulip Kyle Miller (Aug 30 2020 at 04:59):

Another option is to define graphs as irreflexive symmetric relations then define homomorphisms in terms of the reflexive closure of the relation:

import category_theory.category
import tactic

open category_theory

universes u v w

structure simple_graph :=
(V : Type u)
(adj' : V  V  Prop)
(symm' : symmetric adj' . obviously)
(irrefl' : irreflexive adj' . obviously)

namespace simple_graph

abbreviation adj {G : simple_graph.{u}} (u v : G.V) : Prop := G.adj' u v

infix ~ := adj
-- or infix ` ~g ` : 40 := adj

abbreviation rel (G : simple_graph.{u}) (u v : G.V) : Prop := u ~ v  u = v

variables {G : simple_graph.{u}}

def neighbor_set (v : G.V) : set G.V := {w : G.V | v ~ w}

def closed_neighbor_set (v : G.V) : set G.V := {w : G.V | G.rel v w}

end simple_graph

@[ext]
structure hom (G : simple_graph.{u}) (G' : simple_graph.{v}) :=
(to_fun : G.V  G'.V)
(map_adj :  v w : G.V⦄, G.rel v w  G'.rel (to_fun v) (to_fun w))

instance (G : simple_graph.{u}) (G' : simple_graph.{v}) : has_coe_to_fun (hom G G') :=
⟨_, hom.to_fun

def hom.id (G : simple_graph.{u}) : hom G G :=
{ to_fun := id,
  map_adj := by tidy }

section hom

variables {G : simple_graph.{u}} {G' : simple_graph.{v}} {G'' : simple_graph.{w}}

def hom.trans (f : hom G G') (f' : hom G' G'') : hom G G'' :=
{ to_fun := f'  f,
  map_adj := by { intros v w h, repeat { rw function.comp_app }, exact f'.map_adj (f.map_adj h) } }

def hom.locally_injective (f : hom G G') : Prop :=  v w : G.V⦄, f v = f w  ¬(v ~ w)

end hom

instance : has_hom (simple_graph.{u}) :=
{ hom := hom }

instance : category_struct (simple_graph.{u}) :=
{ id := hom.id,
  comp := @hom.trans }

instance : category (simple_graph.{u}) :=
{ }

def complete_graph (V : Type u) : simple_graph.{u} :=
{ V := V,
  adj' := ne }

/--
A coloring of the graph G by colors from α.
-/
structure coloring (G : simple_graph.{u}) (α : Type v) :=
(f : hom G (complete_graph α))
(proper : f.locally_injective)

view this post on Zulip Bhavik Mehta (Aug 30 2020 at 13:32):

Kyle Miller said:

(For subgraphs, you could define a category of subgraphs for each graph (morphisms are the poset of inclusions), then for each morphism in the category get an induced functor between subgraph categories. There'd also be the inclusion functor from a subgraph category back to the graph category, each morphism in the image being monic.)

I'd hope also that the standard subobject lattice (as a poset) in the category would be the same as the poset of subgraphs as well, and the subobject lattice of an object in a category should be coming to mathlib in the next few days

view this post on Zulip Bhavik Mehta (Aug 30 2020 at 13:33):

Kyle Miller said:

There's nothing that says the class has to be associated to a type, by the way -- it's just that most algebraic objects tend to be referred to by their carrier type. You can associate it to the VVPropV \to V \to \mathrm{Prop} relation if you wanted. (See the graph defs thread from today.) There is a very strong case to be made the adjacency relation is the graph.

I think with topological spaces, most of the time the underlying set has a natural topology, so it still makes sense for a typeclass even if you need the occasional escape hatch. I don't think anyone ever refers to the vertex set of a graph and assumes it has an associated graph structure.

But, if you insist on typeclasses on the vertex type, the trick you can do is something like this:

@[irreducible] def complete_graph (V : Type*) := V

instance {V : Type*} : simple_graph (complete_graph V) := sorry

but then you'd have to deal with the fact that the adjacency relation is defined on complete_graph V rather than V itself.

Yeah, I don't think in this context it's a great idea to have typeclasses on the vertex type, which I think is an argument against using the bundled API rather than an argument for a different def of graphs or anything like that - the bundled category design is intended for algebraic structures like you mention, which are set up in a different way to this

view this post on Zulip Jalex Stark (Aug 31 2020 at 16:02):

Jalex Stark said:

But I want to express the property "G is not 3-colorable" as "G does not have a homomorphism to K_3", so I don't want K_3 to be pointed (where by "pointed" i mean "have a map from the terminal object", idk if that is a standard terminology)

if G and H have no points, then there's a natural bijection between between points of the exponential object GH G^H and actual morphisms HG H \to G

view this post on Zulip Kyle Miller (Aug 31 2020 at 19:37):

Regarding that ncatlab post @Bhavik Mehta pointed out, it's worth knowing that this is the 1-dimensional version of the category of simplicial complexes. A map of simplicial complexes is a function on vertex sets that sends simplices to simplices, but these simplices might be collapsed in different ways. For edges (1-simplices), they can either be sent to other edges or collapsed to a vertex (a 0-simplex).

Thinking forward to graphs as being 1-skeleta of arbitrary simplicial complexes, it is probably worth defining homomorphisms this way. (Plus you get that nice characterization of graph minors as being subquotients.)

view this post on Zulip Kyle Miller (Aug 31 2020 at 19:41):

Aaron Anderson said:

Yeah, I’d be in favor of having bundled monos and regular monos, but I prefer the regular monos get the name and symbol of embeddings.

Regarding this, I've created a topic about (regular) monomorphisms: https://leanprover.zulipchat.com/#narrow/stream/116395-maths/topic/embeddings.20and.20hook.20arrow.20notation.3A.20%28regular%29.20monomorphisms

It would be nice to match the way notation works in other parts of mathlib for this, if there's any precedent.

view this post on Zulip Kyle Miller (Aug 31 2020 at 19:48):

It might make sense using unadorned hook arrows for embeddings, but, for example, Lee's smooth manifolds book uses the hook arrow for smooth inclusion maps, and uses the word "embedding" as a modifier.

view this post on Zulip Aaron Anderson (Aug 31 2020 at 19:52):

I've pulled the graph maps out of my PR so we can keep discussing here.

view this post on Zulip Aaron Anderson (Aug 31 2020 at 19:54):

It seems that for topological purposes, it may just be better if we take the definition of a graph to be reflexive, instead of irreflexive, but for combinatorial purposes, we probably still want the usual edge-number formulas and stuff to be true.

view this post on Zulip Aaron Anderson (Aug 31 2020 at 19:56):

However, for those topological purposes, we'd probably rather be thinking about simplicial complexes anyway, and sometimes requiring they be only have 0 and 1 dimensional simplices.

view this post on Zulip Aaron Anderson (Aug 31 2020 at 19:57):

Is perhaps the solution to have the current irreflexive definition of graph, with its current definition of hom, as one category, and when we want to talk about that graph topologically, we use a function/functor from graphs to simplicial complexes, where there are a few more maps?

view this post on Zulip Kyle Miller (Aug 31 2020 at 19:58):

I tried out the reflexive version, and I kept getting confused because I kept forgetting the relation no longer corresponded to edges... This only really helps make the definitions of homomorphisms easier -- for this category it might be better to define it in terms of the reflexive closure of the relation.

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:00):

Though, it might be better still to define it like

structure hom G G' :=
(to_fun : V G -> V G')
(map_prop : forall (v w : V G), v ~ w -> (f v = f w \/ f v ~ f w))

since having the reflexive closure on the L.H.S. of the implication is unnecessary. This matches the simplicial complex map definition.

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:03):

The fact that minors are subquotients using this hom definition is compelling, I think

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:05):

Do you know if there are any reasons to use the rel_hom-with-irreflexive-adjacency definition?

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:08):

Mostly for studying colorability

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:08):

that's really the only context where I've thought much about graph homomorphisms

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:09):

and tbh I think pretty much every definition we mention is going to be implemented eventually, it's just an issue of coming up for a name for each of the 18 categories we're gonna have

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:10):

locally injective homomorphisms cover that case, at least

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:10):

I haven't been able to determine whether that counts as an immersion or not

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:10):

What do you mean by locally injective?

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:11):

I mean

def locally_injective (f : hom G G') := forall (v w : V G), v ~ w -> f v != f w

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:12):

it seems somewhat useful in other contexts, too, like for walks of length n. It's a locally injective homomorphism of a path graph with n edges

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:13):

But anyway, I think I'd rather have irrefl_hom and refl_hom, with better names, and then have a theorem that says that a refl_hom is an irrefl_hom iff it's locally injective that have the definition of irrefl_hom be a function with the property v ~ w -> (f v = f w \/ f v ~ f w) /\ f v != f w

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:17):

As I view irrefl_hom as more basic, I'm inclined to call that just hom with the nomenclature ->g, and call the refl_hom something like top_hom or continuous or something, with a different nomenclature, but I really don't care what the nomenclature is at the end of the day.

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:20):

Do you view it to be more basic because it's slightly easier to define? Maybe it's because you're thinking of it as being a homomorphism of models of graphs?

I'm having a hard time seeing it being that useful for anything other than graph coloring, and even for graph coloring I'd be more inclined to define graph colorings as their own thing since it's just a function that sends adjacent vertices to non-equal elements.

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:21):

It seems like a lemma that graph colorings correspond to (locally injective) homomorphisms to complete graphs

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:27):

I view it as more basic because

  • I'm used to model theory
  • For multigraphs, it coincides with a pair, consisting of a vertex map and an edge map, which agree
  • The only applications that I personally have thought about in any depth are coloring and walks, and those use it
  • I've looked up a few internet sources (although none seem authoritative), and all of them use the irreflexive definition, except for nLab, mentions the irreflexive definition as standard before deciding they'd rather study the reflexive version

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:28):

@Jalex Stark, I have it in my head that you've spent some time getting comfortable with graph homomorphisms. Do you have a good source that could help us?

view this post on Zulip Jalex Stark (Aug 31 2020 at 20:29):

I think I spent a long time with uh chapter 8? Of godsil's algebraic graph theory

view this post on Zulip Jalex Stark (Aug 31 2020 at 20:31):

And asked a lot of dumb questions to william ballinger

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:46):

Jalex Stark said:

And asked a lot of dumb questions to william ballinger

Really the best way to learn any subject

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:47):

Godsil also uses the irreflexive definition. I think it's standard for combinatorial settings, where the reflexive definition is standard for topological settings, so I really think those are not so much the "homomorphisms" of graph theory as the "continuous maps" of graph theory

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:47):

Ok, thanks for expanding on your inclinations.

Re model theory: it might be that the definition of a simple graph we have matches intuition but is the wrong structure, so the notion of a homomorphism might need to be non-standard.

Re multigraphs: there's a case to be made that they should be set up to allow edge contractions, but I don't have any idea how to do that cleanly. (I know how to do it, but no one, including me, would like using it.)

If I'm not mistaken, while graph minors are subquotients in the ncatlab category, they are also quotients of subobjects in the irrefl category. Edge contractions could correspond to a span of maps, rather than being a map itself.

Re walks: I see value in making a length-n walk be exactly a homomorphism from an n-edge path, which unfortunately fails with this ncatlab definition of homomorphism. (But for colorings, I'm not convinced homomorphisms to complete graphs are the basic definition. That's not to say I don't see the utility; just that defining homomorphisms only for the sake of colorings doesn't seem right)

I'm mostly undecided one way or the other at this point. I think if we can verify that graph minors are quotients of subobjects in the irrefl category (pretty sure it's true), then I'm satisfied.

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:48):

Also, if we ever want to define graphs that have loops as actual information, and talk about homomorphisms in their context, I think the irreflexive one makes a lot more sense

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:49):

I don't think we have to really pick one, we just call one the category of graphs with homomorphisms, and one the category of graphs with continuous maps.

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:49):

It matters for which gets the simpler notation

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:50):

And also, if it turned out we might only use one of them, that'd keep maintenance down

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:54):

We could define them both with rel_hom, that might keep maintenance down... but the only way to find out if we only want to use one of them is to start using them

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:55):

Is the irrefl category an actual separate category, or is it merely the ncatlab category with the additional constraint that maps are locally injective?

view this post on Zulip Kyle Miller (Aug 31 2020 at 20:56):

It's true, we'd need to use both to really know.

view this post on Zulip Aaron Anderson (Aug 31 2020 at 20:57):

It is indeed a subcategory of the refl category. I've also yet to see a source that defines graph homomorphisms as the refl definition without first pointing out that there's a choice.

view this post on Zulip Kyle Miller (Aug 31 2020 at 21:00):

Yeah, I meant that as a design question. If one is a subcategory of the other, is it worth having both as separate definitions? I imagine many homomorphisms will be injective, where the distinction doesn't matter.

view this post on Zulip Kyle Miller (Aug 31 2020 at 21:01):

(I'm pretty sure I was wrong about graph minors being the same as quotients of subobjects. They are quotients of subobjects, but not conversely.)

view this post on Zulip Kyle Miller (Aug 31 2020 at 21:02):

Anyway, if there is a precedent to studying the category from the irreflexive relation, then it seems reasonable just defining homomorphisms that way. If anyone proves an excluded minors theorem at some point, this could be revisited.

view this post on Zulip Aaron Anderson (Aug 31 2020 at 21:04):

Kyle Miller said:

Yeah, I meant that as a design question. If one is a subcategory of the other, is it worth having both as separate definitions? I imagine many homomorphisms will be injective, where the distinction doesn't matter.

Well, the continuous definition will be in mathlib sooner or later, as a full subcategory of simplicial sets


Last updated: May 08 2021 at 21:09 UTC