Timeline for Embedding of graph classes
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 26, 2022 at 10:24 | comment | added | Ben Tom | In one of the comments above, I wrote about the decidability of $A$ and $B$. | |
| Feb 26, 2022 at 8:35 | comment | added | 喻 良 | How about $A[n]=\emptyset$ if the $n$-th Turing machine halts with input $n$, and $A[n]$is not empty otherwise. Then even for $(A, COM)$, the domain is undecidable. | |
| Feb 25, 2022 at 12:28 | comment | added | Ben Tom | This is not a problem because the domain of this function is decidable. | |
| Feb 25, 2022 at 11:15 | comment | added | 喻 良 | This is not even a total function. For example, what if $A[n]$ is empty for some $n$? | |
| Feb 23, 2022 at 16:48 | comment | added | Ben Tom | @LeechLattice , what if for any $G \in A[n]$ there is no $H \in B$ such that $G$ embeds in $H$? How does the machine know when to stop? | |
| Feb 23, 2022 at 16:39 | comment | added | LeechLattice | The machine can just enumerate all $n$-vertex graphs to find graphs that can play the role for $G$, and it can also enumerate graphs by increasing order of vertices to find which graph can play the role of $H$. | |
| Feb 23, 2022 at 16:32 | comment | added | Ben Tom | @LeechLattice , I need the machine to be able to recognize both $A$ and $B$. The fact that max does not affect computability is not entirely clear, because the machine needs to know which graphs from $A[n]$ it can take to test for the maximum. | |
| Feb 23, 2022 at 16:18 | comment | added | LeechLattice | How is the set $B$ given? The $\text{max}$ part is just finite and does not affect computability. | |
| Feb 23, 2022 at 13:07 | history | asked | Ben Tom | CC BY-SA 4.0 |