Timeline for Which graphs are Cayley graphs?
Current License: CC BY-SA 3.0
15 events
when toggle format | what | by | license | comment | |
---|---|---|---|---|---|
S Apr 11, 2017 at 14:04 | history | suggested | Mike Pierce | CC BY-SA 3.0 |
Mathjaxxed and reformatted
|
Apr 11, 2017 at 14:03 | review | Suggested edits | |||
S Apr 11, 2017 at 14:04 | |||||
Feb 7, 2011 at 14:14 | comment | added | Emil Jeřábek | The condition that all vertices have the same degree is $\Pi^0_2$: for every vertices $x,y$ and every finite sequence of distinct vertices $z_1,\dots,z_n$ pointing to $x$, there exists a finite sequence of distinct vertices $w_1,\dots,w_n$ pointing to $y$, and mutatis mutandis for the out-degrees. The condition that a fixed vertex has finite degree is easily seen to be $\Sigma^0_2$. Altogether, the condition for recognition of finite-degree Cayley graphs is $\mathcal B(\Pi^0_2)$ (Boolean combination of $\Pi^0_2$-conditions; indeed, a difference of two such). | |
Feb 12, 2010 at 15:50 | comment | added | François G. Dorais | One strategy is to come up with a group G = (omega,) such that the growth rates of the functions f_a(m) = max(a*0,...,am) is very high when a is not the identity, but the Cayley graph is still computable. This looks plausible since forgetting the labels prevents computing the growth rates f_a. | |
Feb 12, 2010 at 15:33 | comment | added | Joel David Hamkins | Suppose we try at least to prove it is non-arithmetic, by finding a simple class of graphs, such that the question of whether they are Cayley or not codes arithmetic truth? If the sequence of graphs was arithmetic, then the condition of being Cayley could not be. | |
Feb 12, 2010 at 15:25 | comment | added | François G. Dorais | My usual approach to proving Sigma^1_1 completeness is to first find a good ordinal rank on the complement so I can get a good handle. There are some candidates (involving trees of approximations of the sequence E_i that I described in another comment) but, so far, they all seem difficult to play with... | |
Feb 12, 2010 at 15:10 | comment | added | Joel David Hamkins | Thanks very much, François! Now, let's figure out the countably generated case. I am thinking it may be complete Sigma^1_1, which would be a negative answer, in the sense that it would mean that the easiest way to say a countable graph Gamma is a Cayley graph is to say that there is a group presentation for which it is the Cayley graph. | |
Feb 12, 2010 at 14:52 | comment | added | François G. Dorais | ... in order to tell when the node has 0, 1, or 2 successors. The same happens here. If you have an effective bound on the neighbors of each vertex, then the equal degree condition becomes much simpler. | |
Feb 12, 2010 at 14:50 | comment | added | François G. Dorais | Side note: The way the equal degree condition makes the complexity go up one notch may seem unusual, but this is actually very common. Another example of this happens with König's Lemma. It is true that every infinite recursive subtree of $2^{<\omega}$ has a low branch, but this is not true that every infinite recursive subtree of $\omega^{<\omega}$ where each node has at most two successors. Indeed, there is such a recursive subtree of $\omega^{<\omega}$ where every branch computes the jump! The reason is essentially the same, you first need to find a bound on the successors of a node... | |
Feb 12, 2010 at 14:48 | comment | added | Joel David Hamkins | I guess this degree-matching requirement can be simplified to Sigma^0_3. You just say: there is k such that 0 points at k vertices and for any k+1 many arrows, they don't point all at the same vertex, and whenever k vertices point at v and w is a vertex, then there are k arrows pointing at w (and silarly for out-degree). This makes the condition Sigma^0_3 altogether. | |
Feb 12, 2010 at 14:34 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
corrected Sigma^0_3 to Sigma^0_4; added 64 characters in body
|
Feb 12, 2010 at 14:23 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 77 characters in body
|
Feb 12, 2010 at 14:17 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
Added tree argument details
|
Feb 12, 2010 at 13:31 | history | edited | Joel David Hamkins | CC BY-SA 2.5 |
added 131 characters in body
|
Feb 12, 2010 at 13:17 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |