Timeline for Subset of edges of graph touching all vertices such that all paths consist of at most two edges
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 16, 2012 at 9:38 | comment | added | Fred.Fred | ...unless there is a leaf in level 1, in that case we just connect all leaves with r and do not choose any x1. We get a bunch of cut off trees for which we use recursion. For the tree "under" x1 (if it was chosen), we connect all leaves to x1 and remove all other edges under x1 and again use recursion for the cut off trees. Seems promising ? (edited) | |
| Aug 16, 2012 at 9:27 | comment | added | Fred.Fred | Aaron: That's a great idea! By Zorn's Lemma, every connected graph $G$ has a spanning tree $T$, i.e. a subgraph connecting all vertices of $G$ which is a tree. So it seems that we can work with just trees. Now we can choose a root $r$ and recursively define level function $l: T \rightarrow Ordinals$ by putting $l(r)=0,l(x)=l(y)+1$ if we already know $l(y)$ and there is an edge between $x$ and $y$ which is well-defined in trees. Suppose that $T$ has more than one vertex. Than there is at least one vertex $x_1$ of level 1, we add edge $(r,x_1)$ and remove all other edges in level 1. (cont..) | |
| Aug 16, 2012 at 8:04 | comment | added | Gerhard Paseman | Here is an example that (almost) makes my head hurt. Let X be the set of real numbers. Let Y be the set of cocountable sets of reals. Let x iin y mean there is an edge between x in X and y in Y. How do we handle such a beast? Gerhard "Needs To Go To Sleep" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 7:21 | comment | added | Gerhard Paseman | I think you have a nice reduction of the problem to bipartite graphs. It might be time to read what Igor Rivin suggested. Gerhard "Ask Me About System Design" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 7:13 | comment | added | Gerhard Paseman | Also, in the leaf case, how do we get only stars and not, say bipartite graphs with cycles? Gerhard "Back To The Stick Figures" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 7:07 | comment | added | Gerhard Paseman | Here is something to think about. Use your same construction iin both cases. In the leafless case, you end up with many stars as well as some with longer branches. The result should be an possibly infinite tree with maximal path length 4, since you added back some edges. Now run your algorithm again on that infinite tree. Gerhard "Hope THIS Makes It Work" Paseman, 2012.08.16 | |
| Aug 16, 2012 at 7:02 | comment | added | Aaron Meyerowitz | Yes, that is a problem. I'll think about it. I wonder if one can remove a maximal non-disconnecting set of edges to get a tree and then take it from there. | |
| Aug 16, 2012 at 7:00 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 1055 characters in body
|
| Aug 16, 2012 at 5:13 | comment | added | Gerhard Paseman | I am concerned that there will still be an isolated vertex in the limit because it is connected to uncountably many vertices with label 1, and it "never gets its turn." Perhaps you can tell me more about when such a vertex will be processed? (Basically I am worried about the no leaf process continuing infinitely often and affecting a certain unfortunate vertex.) Perhaps this combined with a well ordering argument might work? Gerhard "Ask Me About System Design" Paseman, 2012.08.15 | |
| Aug 16, 2012 at 4:31 | history | edited | Aaron Meyerowitz | CC BY-SA 3.0 |
added 353 characters in body
|
| Aug 16, 2012 at 4:21 | history | answered | Aaron Meyerowitz | CC BY-SA 3.0 |