Timeline for MSO2-expressible graph properties unexpressible in MSO1
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3, 2017 at 21:16 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 244 characters in body
|
| Jan 3, 2017 at 19:44 | comment | added | Emil Jeřábek | Yes, I think that should work. I have meanwhile had the coffee, and figured the following alternative way: there is an even-length path from $u$ to $v$ iff there is a partition of $V(G)$ in two disjoint sets $A$ and $B$ such that $u,v\in A$, and there is a walk from $u$ to $v$ alternating between $A$ and $B$; the latter amounts to the connectivity of $u$ and $v$ in the graph $H$ with $V(H)=A$, and $\{x,y\}\in E(H)$ iff $\exists z\in B\,(\{x,z\},\{y,z\}\in E(G))$. (Odd-length paths are similar.) This is expressible in $\mathrm{MSO}_1$. | |
| Jan 3, 2017 at 18:43 | comment | added | Tony Huynh | Yes, I want the path to be simple, but you did get me thinking. It seems like the partition formula might work in $\mathsf{MSO}_1$. If we consider a shortest length odd path, then the formula is something like there are disjoint subsets $A,B$ such that $u \in A, v \in B$, $u$ is adjacent to exactly one vertex in $B$, $v$ is adjacent to exactly one vertex in $A$, each vertex in $A$ (other than $u$) is adjacent to exactly two vertices in $B$, and each vertex in $B$ (other than $v$) is adjacent to exactly two vertices in $A$. | |
| Jan 3, 2017 at 17:58 | comment | added | Emil Jeřábek | Never mind, I think I need more coffee. | |
| Jan 3, 2017 at 16:56 | comment | added | Tony Huynh | @EmilJeřábek If by $G^2$ you mean the graph with the same vertex set as $G$ and where $u$ and $v$ are adjacent in $G^2$ if they are at distance at most $2$ from each other in $G$, then the iff does not hold. For example, $G$ is a subgraph of $G^2$. Putting edges if the vertices are at distance exactly $2$ will not work either. For example, consider the complete graphs. | |
| Jan 3, 2017 at 16:20 | comment | added | Emil Jeřábek | I may be missing something, but there is an even-length path between $u$ and $v$ in $G$ iff there is a path between $u$ and $v$ in $G^2$, and the latter is FO definable in $G$, which should give an $\mathrm{MSO}_1$ expression. The case of odd-length paths is similar. | |
| Jan 3, 2017 at 11:44 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 24 characters in body
|
| Jan 3, 2017 at 11:28 | comment | added | Dušan Knop | I would only add to your example with path that for the set P the graph G[P] must be connected as otherwise it is possible to cheat using disconnected cycles. But this is only minor correction. | |
| Dec 22, 2016 at 22:22 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 776 characters in body
|
| Dec 22, 2016 at 11:06 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 36 characters in body
|
| Dec 22, 2016 at 11:03 | history | undeleted | Tony Huynh | ||
| Dec 22, 2016 at 11:01 | history | edited | Tony Huynh | CC BY-SA 3.0 |
added 36 characters in body
|
| Dec 22, 2016 at 10:44 | history | deleted | Tony Huynh | via Vote | |
| Dec 22, 2016 at 10:40 | history | answered | Tony Huynh | CC BY-SA 3.0 |