Zulip Chat Archive

Stream: graph theory

Topic: infinite union of graphs

Bhavik Mehta (Aug 21 2020 at 19:25):

Something interesting to think about: is there a nice way of doing this construction in Lean? For instance can you show that if G has no cycles of length four, then ext G is a friendship graph

Kyle Miller (Aug 21 2020 at 19:32):

What kind of union? A disjoint union, or a union of subgraphs within a particular universal graph?

Kyle Miller (Aug 21 2020 at 19:34):

Because, rather than defining subgraph G to be a bounded lattice, it could be defined to be a complete lattice, so then an infinite union would be the sup of an indexed family of subgraphs. (For example, G could be a complete graph on some given vertex type.)

Kyle Miller (Aug 21 2020 at 19:37):

What's ext G? (Is it something from Ramsey theory?)

Bhavik Mehta (Aug 21 2020 at 21:17):

Oh oops I meant to attach a picture - sorry

Bhavik Mehta (Aug 21 2020 at 21:18):


Bhavik Mehta (Aug 21 2020 at 21:19):

In particular in this setting when you're just given G, there's not an ambient graph in which all your subgraphs do form a lattice, so just taking sup like you mention isn't immediate

Kyle Miller (Aug 22 2020 at 04:04):

Having colimits of graphs like that would be nice, though in this case you could define ext G using a sup construction on subgraphs of the complete graph on the set of binary trees with leaves being labeled by vertices of G:

variables {α : Type u} [simple_graphs α]

inductive all_deriv_verts (G : α)
| incl (v : V G) : all_deriv_verts
| pair (v w : all_deriv_verts) : all_deriv_verts

def total (G : α) := complete_graph (all_deriv_verts G)

Here, total G is the graph that's universal.

Bhavik Mehta (Aug 22 2020 at 13:16):

I suspect you want pair to take a sym2 or finset of size 2 rather than an ordered pair, but yeah I can see that works

Kyle Miller (Aug 22 2020 at 16:56):

Oh, good catch

Last updated: Dec 20 2023 at 11:08 UTC