Timeline for Is every path with this property shorter than another path with the same endpoints?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 1, 2021 at 13:27 | history | edited | user44143 | CC BY-SA 4.0 |
added 880 characters in body
|
| Feb 28, 2021 at 12:06 | comment | added | fedja | @domotorp Each octopus should have at least 2 legs, so $n\ge 2m$. ($m$ is the number of octopuses). You are right about 12321-dead end, of course :-) | |
| Feb 28, 2021 at 8:27 | comment | added | Martin Rubey | I think you should mention that the graph obtained from the path by joining a vertex $u_0$ to $v_0$ and $v_5$, a vertex $u_1$ to $v_2$ and $v_6$, a vertex $u_2$ to $v_3$ and $v_8$ and a vertex $u_3$ to $v_1$, $v_4$ and $v_7$, does not allow a longer path visiting all of $v_0,\dots,v_8$. I assumed that one could strengthen the conjecture this way, but as you discovered, this is not possible. Also, this seems to be the smallest example. | |
| Feb 28, 2021 at 3:23 | history | rollback | user44143 |
Rollback to Revision 2
|
|
| Feb 28, 2021 at 3:22 | comment | added | user44143 | @mathworker21, you are right -- I was looking for examples that hit all the vertices in the original path. I will revert | |
| Feb 28, 2021 at 3:19 | comment | added | mathworker21 | @MattF. your counterexample is not a counterexample. consider the path 0-->1-->2-->x-->6-->5-->4-->3-->y-->8 , where x,y are vertices outside the path. | |
| Feb 28, 2021 at 2:47 | comment | added | user44143 | @fedja, you motivated me to look further and I found something interesting! | |
| Feb 28, 2021 at 2:46 | history | edited | user44143 | CC BY-SA 4.0 |
found counterexample
|
| Feb 27, 2021 at 21:35 | comment | added | domotorp | @fedja Also 123212-dead end is already bad, because you can jump to the second 1, go back to the first 2, then jump to the last 2. | |
| Feb 27, 2021 at 21:29 | comment | added | domotorp | @fedja After successfully deciphering your notation, I feel like you assume that for every $v_i$ there is a unique $u$ satisfying the condition, but there might be more. Because of this I don't think $m\ge 4$ implies $n\ge 8$ without a further argument. | |
| Feb 27, 2021 at 16:43 | comment | added | fedja | You don't need Mathematica for that much: when we have $m$ "octopuses" whose legs we connect by a path, we need to have at least $2m$ and at most $m^2-m$ total legs. For $m\le 3$, the verification by hand is easy: no number should repeat and no pair should repeat even with skip of 1 in one of the pairs. So we can start only as 12131-dead end, 1231-dead end or 123212-dead end. Thus $m\ge 4$, so $n\ge 8$. I believe that I have checked that $m=4$ doesn't work either (so $n\ge 10$) but I need to recheck it to claim it for sure. In general I do not know a fast algorithm. | |
| Feb 26, 2021 at 8:59 | history | edited | user44143 | CC BY-SA 4.0 |
testing paths where u can connect any number of v's, including some connecting 4 v's in the n=7 case
|
| Feb 25, 2021 at 17:38 | comment | added | mathworker21 | This is great, thanks!! | |
| Feb 25, 2021 at 17:35 | history | answered | user44143 | CC BY-SA 4.0 |