Timeline for Universal graph
Current License: CC BY-SA 4.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23 at 21:15 | comment | added | Florian Lehner | @CommandMaster The answer to your question about a locally finite universal graph is Corollary 3.2 in my paper "A note on classes of subgraphs of locally finite graphs" linked below Fedor Petrov's answer. There even is a locally finite graph which contains all graphs of maximum degree $d$ as induced subgraphs. | |
| Jan 23 at 1:19 | history | became hot network question | |||
| Jan 22 at 23:07 | comment | added | Fedor Petrov | Ah, I see, the spheres sizes are bounded by an a priori sequence and the edges are only between neighbour spheres or inside the same sphere. | |
| Jan 22 at 22:51 | comment | added | Anton Petrunin | @NoahSchweber Noach, could you restore your construction of locally finite universal graph? | |
| Jan 22 at 22:39 | comment | added | Anton Petrunin | @FedorPetrov One can embed $n$-balls inductively into $G_n$. | |
| Jan 22 at 21:46 | comment | added | Fedor Petrov | I am happy even if $G_{n+1}\setminus G_n$ is connected to the whole $G_{n}\setminus G_{n-1}$, since we do not need induced embeddings and the degrees are still finite. But how to embed an arbitrary graph of degree 3 here? | |
| Jan 22 at 21:39 | comment | added | Anton Petrunin | @FedorPetrov he constructs a sequence of graphs $G_0\subset G_1\subset\dots$ Each vertex in $G_{n+1}\setminus G_n$ corresponds to a three-vertex subset in $G_n\setminus G_{n-1}$ and connected to its three-vertex subset. | |
| Jan 22 at 21:20 | comment | added | Fedor Petrov | I try to understand the deleted anser by Noah and do not succeed. How to make Rado construction locally finite? For me it seems crucial to add new and new edges from the same vertex. | |
| Jan 22 at 20:39 | comment | added | Anton Petrunin | @CommandMaster This was done by Noah Schweber in his deleted answer. (It was a modification of the Rado-graph construction.) | |
| Jan 22 at 20:34 | vote | accept | Anton Petrunin | ||
| Jan 22 at 19:51 | answer | added | Fedor Petrov | timeline score: 19 | |
| Jan 22 at 19:14 | comment | added | Daniel Weber | Do you know how to do this with all degrees $< \infty$ (that is, a locally finite graph)? | |
| Jan 22 at 19:01 | comment | added | Ben Johnsrude | @CommandMaster we aren't assuming that the graphs are finite, so there are uncountable many graphs we need to embed in $U$. | |
| Jan 22 at 19:00 | comment | added | Daniel Weber | Why can't you take all finite graphs with degrees $\leq 3$ and put them in a long chain with maximum degree 4? | |
| Jan 22 at 18:46 | comment | added | Anton Petrunin | @Ben if we consider graphs with marked vertices and assume that embedding maps marked vertex to the marked vertex, then "yes". In this case it is enuf to do finite graphs. | |
| Jan 22 at 18:46 | comment | added | Noah Schweber | @BenJohnsrude Nope: let $G$ be the successor graph on the naturals and $H$ the successor graph on the integers. | |
| Jan 22 at 18:45 | comment | added | Sam Hopkins | @BenJohnsrude: that's obviously not true without some further assumptions on $G$ and $H$. For example, let $G$ be the disjoint union of countably many copies of all finite paths, and let $H$ be the infinite path. | |
| Jan 22 at 18:43 | comment | added | Ben Johnsrude | If $G,H$ are graphs such that $G$ contains an embedded copy of every finite subgraph of $H$, does this imply that $G$ contains an embedded copy of $H$? This sounds like a compactness theorem-type of statement. If that's true, we only need to arrange for $G$ to contain all finite $H$, which is easy to do. | |
| Jan 22 at 18:40 | comment | added | Anton Petrunin | @CorentinB NOT induced. | |
| Jan 22 at 18:37 | comment | added | Corentin B | Which notion of subgraph / embedding are you considering? Induced or not? Equivalently, should every edge between vertices in the image « come from » an edge in the embedded subgraph? | |
| Jan 22 at 18:35 | comment | added | Noah Schweber | Dangit, I had stuff to do today ... | |
| Jan 22 at 18:32 | comment | added | Ben Johnsrude | Not Noah, but if you fix a starting vertex $v$ and, at step $i$, collect all neighbors of the vertices you have so far, then you will exhaust the graph in countably-many steps with only finitely many vertexes added at each step. EDIT: If I'm not mistaken, the same argument establishes countability if you only assume that each vertex has finite degree. | |
| Jan 22 at 18:31 | comment | added | Alessandro Codenotti | Ah, that's interesting, is there an easy argument to see that must be the case? @NoahSchweber | |
| Jan 22 at 18:30 | comment | added | Noah Schweber | @AlessandroCodenotti Nope - every connected bounded-degree graph is countable (I made exactly this mistake, multiple times, earlier). | |
| Jan 22 at 18:19 | comment | added | Noah Schweber | If I write enough things fast enough, one of them will eventually be true. | |
| Jan 22 at 18:19 | comment | added | Anton Petrunin | @NoahSchweber you are very fast, now I do not see a way to fix it. | |
| Jan 22 at 18:14 | history | edited | YCor |
edited tags
|
|
| Jan 22 at 18:10 | vote | accept | Anton Petrunin | ||
| Jan 22 at 18:16 | |||||
| Jan 22 at 17:42 | comment | added | Anton Petrunin | @SamNead yes, it is fixed now. | |
| Jan 22 at 17:41 | history | edited | Anton Petrunin | CC BY-SA 4.0 |
added 25 characters in body
|
| Jan 22 at 17:40 | comment | added | Sam Nead | Is there some assumption of connectedness on the sources or target? | |
| Jan 22 at 17:16 | history | asked | Anton Petrunin | CC BY-SA 4.0 |