Timeline for Is there an algorithm that finds the forbidden minors?
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 5, 2018 at 1:13 | comment | added | Thomas Klimpel | @domotorp The minimal set of excluded minors for the union has been shown to be computable in 2008: logic.las.tu-berlin.de/Members/Kreutzer/Publications/… | |
| Nov 4, 2018 at 19:43 | comment | added | domotorp | I see - well, I'm not desperate to know the answer, just I got surprised and became curious... | |
| Nov 4, 2018 at 14:45 | comment | added | Thomas Klimpel | @domotorp I agree, good point. I do have some ideas for such examples, but I have the impression that the growth rate of all my examples (which basically try to play with "grid" dimension) will stay within ELEMENTARY. However, I believe that if I wanted to invest time into those questions, then I should first do a literature study about what happened in the years 2000-2018, perhaps by looking at papers that quote the papers that I know about, or by looking at later publications of the authors which worked on those questions. | |
| Nov 3, 2018 at 22:12 | comment | added | domotorp | This last part is quite interesting. If understand well, this implies the following. For a graph family $\mathcal G$, denote by $m(\mathcal G)$ the size of the largest forbidden minimal minor. Let $f(n)=\max \{m(\mathcal G_1 \cup \mathcal G_2)\mid m(\mathcal G_1),m(\mathcal G_2)\le n\}$. Then there is no known recursive upper bound for $f(n)$. Do you know some examples that show that $f(n)$ grows very fast? | |
| Nov 3, 2018 at 22:01 | vote | accept | domotorp | ||
| Nov 3, 2018 at 16:58 | history | answered | Thomas Klimpel | CC BY-SA 4.0 |