Can anyone name a undecidable problem that is genuinely graph-related? (Genuine means: not a standard one in graph's disguise.)
$\begingroup$
$\endgroup$
5
asked Jan 8, 2010 at 10:56
-
$\begingroup$ genuinely graph-related = first arisen in graph theory $\endgroup$– Hans-Peter StrickerCommented Jan 8, 2010 at 11:28
-
$\begingroup$ I don't know that the term "genuinely graph-related" is well-defined. $\endgroup$– Qiaochu YuanCommented Jan 8, 2010 at 16:46
-
$\begingroup$ Sorry, = was intended to mean "is intended to mean". $\endgroup$– Hans-Peter StrickerCommented Jan 8, 2010 at 17:24
-
5$\begingroup$ This is NOT a definition of "Sorry,", by the way. $\endgroup$– Hans-Peter StrickerCommented Jan 8, 2010 at 17:26
-
$\begingroup$ Whether two graphs are quantum isomorphic... $\endgroup$– JP McCarthyCommented Feb 10 at 17:48
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
5
From a MathSciNet search:
Földes, Stéphane; Steinberg, Richard A topological space for which graph embeddability is undecidable. J. Combin. Theory Ser. B 29 (1980), no. 3, 342--344.
From the introduction: ``From Edmonds' permutation theorem and a generalization due to Stahl, it follows that graph embeddability is decidable for all surfaces, orientable as well as nonorientable. We show the existence of a topological space $\hat G$ such that there is no algorithm to decide whether a finite graph is embeddable in $\hat G$. In fact, $\hat G$ will be a path-connected subspace of the real plane.''
answered Jan 8, 2010 at 13:37
-
1$\begingroup$ Thanks! (How can such graph properties be characterized? Concerning the existence of another structure (graph, topological space or whatever) and a specific mapping/function: is there a standard name for such properties?) $\endgroup$ Commented Jan 8, 2010 at 13:49
-
$\begingroup$ @HS: if you like an answer, please upvote it. You currently have 50% more questions than upvotes. $\endgroup$ Commented Jan 8, 2010 at 14:05
-
$\begingroup$ Done! (But please note, that I accepted an answer to almost all of my questions. Isn't an upvote included in accepting an answer?) $\endgroup$ Commented Jan 8, 2010 at 14:22
-
$\begingroup$ No, I don't believe it is. I have seen accepted answers with 0 upvotes. Anyway, you currently have 13 questions and 9 upvotes, which seems a little stingy. $\endgroup$ Commented Jan 8, 2010 at 14:35
-
1$\begingroup$ OK, I didn't know and will do better in the future! $\endgroup$ Commented Jan 8, 2010 at 14:47
$\begingroup$
$\endgroup$
My favorite undecidable problem in graph theory is the following: given a finite set of graphs $L$, is there a graph $G$ such that the neighborhood of each vertex in $G$ is isomorphic to a graph in $L$.
For a proof see: Peter M. Winkler. Existence of graphs with a given set of r-neighborhoods Journal of Combinatorial Theory, Series B, Volume 34, Issue 2, April 1983, Pages 165-176. (I am fairly sure this result is older, but that's the best I can do now.
answered Jan 8, 2010 at 19:49
$\begingroup$
$\endgroup$
3
With a different notion of undecidability, the following is another example. Ramsey's theorem says that if you 2-colour the edges of a countably infinite graph then there will be an infinite set of vertices such that all the edges between them have the same colour. A natural question one might then ask is whether if a graph with uncountably many vertices is 2-coloured you can find a subset of the vertices of the same size as the vertex set of the whole graph such that all edges inside the subset have the same colour. It turns out that you cannot necessarily do so unless the cardinality is enormous. Cardinalities that work are called weakly compact, and their existence is independent of ZFC. (This is the definition of "weakly compact" but there are many equivalent ways of defining them.)
-
$\begingroup$ @gowers: by "undecidability", do you mean that the answer may depend on which system of set theory is in force? $\endgroup$– EmilCommented Jan 8, 2010 at 19:02
-
$\begingroup$ This reminds me of the "chromatic number of the plane" problem: en.wikipedia.org/wiki/Hadwiger%E2%80%93Nelson_problem $\endgroup$– EmilCommented Jan 8, 2010 at 19:03
-
$\begingroup$ Yes, I was using it as a synonym for "independent", as the sometimes is used that way. $\endgroup$– gowersCommented Jan 9, 2010 at 9:12