Timeline for Is every path with this property shorter than another path with the same endpoints?
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 4, 2021 at 17:45 | comment | added | Zach Hunter | outstanding! everything in proof checks out to me, including that the primitive block satisfies its necessary conditions. I am quite shocked that by allowing only a single $u\in V\setminus V_0$ to have degree 3, that there exists a counterexample. I honestly thought the variant with octopi would be true! | |
| Mar 4, 2021 at 17:09 | comment | added | fedja | @MartinRubey Well, it was you who requested such an example. ;-) Thanks anyway! | |
| Mar 4, 2021 at 16:48 | comment | added | Martin Rubey | I am too tired to check, and I guess that the universe is already too old to check, too. Congratulations! | |
| Mar 4, 2021 at 15:50 | history | edited | fedja | CC BY-SA 4.0 |
edited body
|
| Mar 4, 2021 at 15:39 | comment | added | fedja | @MattF OK, look at the monster your little baby graph finally grew into :-). | |
| Mar 4, 2021 at 15:38 | history | edited | fedja | CC BY-SA 4.0 |
added 8216 characters in body
|
| Mar 4, 2021 at 1:47 | comment | added | fedja | @MartinRubey More precisely, the primitive block is 0121345*5407372 and the key properties are that you cannot traverse it from the beginning to the end in a longer way than the honest direct path but also you cannot reach * from 0 executing all available jumps (at least one jump has to be skipped). If you could confirm that these two properties hold (I checked them by hand too but I could mistake), I'll post the rest :-) | |
| Mar 4, 2021 at 1:17 | comment | added | fedja | @MartinRubey It looks like it exists: I used the computer to find a primitive building block of length 15 which, if I don't mistake, can be used to construct another intermediate building block, which can be used to construct a final building block, which can be plugged into the Matt F. construction instead of $aa\dots aa*A$ but I need to verify the details before posting. The number of vertices you obtain this way is astronomical... | |
| Mar 3, 2021 at 14:35 | comment | added | Zach Hunter | @MartinRubey, I don't think the methods here can easily be extended to produce a counter-example for the case you mention. indeed, in the paragraph which starts "It is funny that..." fedja says that he had previously tried to get the method to work in your case, but there seems to be an obstruction. nevertheless, I think it would be very interesting to see this final case be resolved. computationally I know it has been verified up to at least 20 vertices. | |
| Mar 3, 2021 at 14:05 | comment | added | Ville Salo | Shouldn't upvote before checking but I'm just so happy to see this that I can't help myself... | |
| Mar 3, 2021 at 8:02 | comment | added | Martin Rubey | I wonder whether such a construction also exists if vertices in $V_1$ may only be incident to a single vertex $u\not\in V_1$. This would be a 'set partition' analogue of @domotorp's proof. | |
| Mar 3, 2021 at 2:10 | comment | added | Mike | It is a great picture too by the way, I can see from that how you modified Matt J's graph to get the desired construction. | |
| Mar 3, 2021 at 2:04 | comment | added | Mike | @fedja I do see it now. I had used Matt J's comments--and your conversation w him in the comments, to figure out that this was your construction, but without that I would have not been able to see it at all. The picture is beautiful and is illustrative and shows the idea of the construction, but it probably would also be really helpful for other readers if you also were to write out the construction as in the one of Matt J's comments. It's a very nice construction in your answer! | |
| Mar 3, 2021 at 1:47 | comment | added | fedja | @Mike I see that you have been already helped but I still added a picture in the hope that it will help some other confused soul :-) | |
| Mar 3, 2021 at 1:46 | history | edited | fedja | CC BY-SA 4.0 |
added 286 characters in body
|
| Mar 3, 2021 at 0:29 | comment | added | Mike | Looks very interesting! Nice! | |
| Mar 2, 2021 at 23:30 | comment | added | Zach Hunter | taking $G$ to Matt F's almost counterexample, we must have that $\phi(p)$ is the path with no jumps, and then some local analysis finishes the proof. | |
| Mar 2, 2021 at 23:29 | comment | added | Zach Hunter | we then establish a coloring $c$ on our subdivided path so that $c(v_i) = i$, $c(v_{i,1}) =i$, and $c(v_{i,j} = i-1$ if $j \neq 1$. for any path $p = w_0,..., w_k$ from $v_0$ to $v_n$, we notice there will never be $x<y<z$ such that $w_x,w_y,w_z$ are in our path, and $c(w_x) = c(w_z) \neq c(w_y)$. we can use these coloring to establish a map $\phi$ from $v_0-v_n$-paths on our modified graph to $v_0-v_n$-paths on the original $G$, and note that $\phi(p)$ must visit each vertex in $G$. | |
| Mar 2, 2021 at 23:20 | comment | added | Zach Hunter | alternatively, I would try to think of it as starting with $G,P$, and then subdividing each edge of $P$ a number of $N$ times. for each edge $e = (v_i,v_{i+1})$, we label the new vertices left to right, as $v_{i,1},..., v_{i,N}$. for each $0\le i< n-2$, and $1<j\le N$, we add a common neighbor $u'$ connecting $v_{i,j}$ and $v_{i+1,1}$. all vertices besides $v_{0,1}$ and $v_{n-1,j}$ for $1<j \le N$ have a common neighor. we then essentially contract those vertices away to get the construction. | |
| Mar 2, 2021 at 23:19 | comment | added | Mike | I see it now, going through it, looks interesting. But...it is hard to see how that construction in Matt F's comment, corresponds to the answer above | |
| Mar 2, 2021 at 23:04 | comment | added | Zach Hunter | have you looking at the second graph in Matt F's comment? I think trying to draw that (well a simplified version of it) on paper should make the construction clear. | |
| Mar 2, 2021 at 23:02 | comment | added | Mike | Or even how many vertices are in this construction | |
| Mar 2, 2021 at 22:57 | comment | added | Mike | I'm not sure what you mean by block, the notation $aa\ldots a*A$, etc | |
| Mar 2, 2021 at 22:54 | comment | added | fedja | @Mike Erm,,, What part is not clear? (I mean, rewriting the entire post into the comment box will hardly answer your question, will it?) | |
| Mar 2, 2021 at 22:48 | comment | added | Mike | So...what is the construction again? | |
| Mar 2, 2021 at 18:59 | comment | added | Zach Hunter | ah yes! I feel so stupid, I though about similar methods so much but somehow missed this. beautiful! | |
| Mar 2, 2021 at 18:11 | comment | added | fedja | @MattF. Exactly. | |
| Mar 2, 2021 at 18:06 | history | edited | fedja | CC BY-SA 4.0 |
added 2 characters in body
|
| Mar 2, 2021 at 17:42 | comment | added | user44143 | So in my notation, the setup would be not $$\{\{0,5\}, \{1,4,7\}, \{2,6\}, \{3,8\}\}$$ but instead something such as$$\{\{099,599\},\{199,499,799\},\{299,699\},\{399,899\},\\ \{000,100\}\ldots\{098,100\},\ \{101,200\}\ldots\{198,200\},\ \{201,300\}\ldots\{298,300\},\ \\ \{301,400\}\ldots\{398,400\},\ \{401,500\}\ldots\{498,500\},\ \{501,600\}\ldots\{598,600\},\ \\ \{601,700\}\ldots\{698,700\},\ \{701,800\}\ldots\{798,800\},\ \{801,900\}\ldots\{898,900\}\}$$ | |
| Mar 2, 2021 at 17:27 | history | answered | fedja | CC BY-SA 4.0 |