Timeline for Deciding homomorphic images of De Bruijn graphs
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 12, 2023 at 14:38 | comment | added | Ville Salo | Yeah, this agrees with my intuition. But I haven't done an argument of this type in the one-sided setting, so I'm not sure on the details of consistently picking which part is repeated. | |
| Aug 12, 2023 at 14:19 | comment | added | Sam van G | Looking at the proof of your Theorem 1, I think that, in the setting of our given graph $G$, "suitably repeatable part" could mean the following: for any finite word $w \in 2^*$, write $H(w)$ for the relation on vertices of $G$ defined by $u H(w) v$ iff there is a path in $G$ from $u$ to $v$ labeled by $w$. Then a finite factor $w$ of $y \in 2^\omega$ is suitable if $H(w)$ is an idempotent relation. Does that fit with your intuitions? | |
| Aug 12, 2023 at 7:14 | comment | added | Sam van G | For the remainder of your comments, we will need a while to think about it and read your work. It would be great if these methods can help solve it. | |
| Aug 12, 2023 at 7:12 | comment | added | Sam van G | Thanks for this! First, you’re right that it was ambiguous, we strictly speaking only need to decide whether or not there exists a homomorphism, but typically think about deciding the existence of surjections (which clearly suffices - not completely sure about the other direction though so I edited the question to be less ambiguous). | |
| Aug 12, 2023 at 5:12 | history | answered | Ville Salo | CC BY-SA 4.0 |