Timeline for Equality-preserving embeddings of finite trees
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 5, 2014 at 15:29 | comment | added | Tony Huynh | I think the BQO may be true but is likely intractable with the current machinery. For example, I tried to prove just the WQO using the main result from Graph Minors XXIII, and couldn't quite get it to work. It might be that one has to redo the argument from Graph Minors XXIII, which is a bit complicated. So, it looks like this result is closer to WQO graphs than WQO trees. That's why I say BQO is likely intractable. | |
| Jun 3, 2014 at 11:04 | comment | added | M Carl | You are quite right, my approach would also force different labels to be mapped to different labels, which I explicitely didn't ask for. I will have a look at RSXXIII. Does anybody have an intuition on the bqo part of the question? Is it merely a variant of the analogue for trees or rather untractable? I understand that the finite graphs are expected to be bqo under minors (possibly also immersion?), but that this is a deep open question. | |
| Jun 2, 2014 at 13:55 | comment | added | Tony Huynh | I am not sure this will work since we actually want the trees to be topological minors of each other. If you apply the usual graph minor theorem to your auxiliary graphs, it might be that one tree embeds as a minor in another tree, and this isn't what we want. I think the way to get around this is to use the fact that graphs are WQO under immersion. This is proved in Graph Minors XXIII. Note that in Graph Minors XXIII, it is shown that graphs with WQO labels are WQO, but the notion is a bit different than what is required here. | |
| Jun 2, 2014 at 10:18 | review | First posts | |||
| Jun 2, 2014 at 10:19 | |||||
| Jun 2, 2014 at 10:03 | history | answered | GabrielG | CC BY-SA 3.0 |