Timeline for Graph properties: definability and decidability
Current License: CC BY-SA 2.5
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jan 10, 2011 at 13:49 | answer | added | Łukasz Grabowski | timeline score: 2 | |
| Jan 9, 2011 at 18:52 | comment | added | gowers | The point I'm making is that pretty well anything that's undefinable can be turned into an undefinable graph property. So as far as I can see the question doesn't turn in any interesting way on the fact that it is posed for graph properties. | |
| Jan 9, 2011 at 17:53 | comment | added | Hans-Peter Stricker | @Timothy: It's the same as yours, and of course, "has edge-density at most p" isn't definable, when p isn't. What I wanted to say was, that it's a question about graphs, nevertheless. | |
| Jan 9, 2011 at 16:44 | comment | added | gowers | What is your definition of "graph property"? The one I'm familiar with is "subset of the set of all graphs that's isomorphism invariant" (and here I'm talking about finite graphs). If the real number p isn't definable, then neither is the graph property "has edge-density at most p". It's definable in terms of p, but p isn't definable so that doesn't help much. | |
| Jan 9, 2011 at 11:43 | comment | added | Hans-Peter Stricker | @Timothy: Why not? What you describe is just a richer language, allowing to define properties that depend on real-valued parameters. | |
| Jan 9, 2011 at 8:44 | comment | added | gowers | Is this really a question about graphs? For instance, take the property "has edge-density at most p". This will be definable if and only if the real number p is (between 0 and 1 and) definable. | |
| Jan 9, 2011 at 2:25 | answer | added | David Harris | timeline score: 3 | |
| Jan 9, 2011 at 1:25 | answer | added | user5810 | timeline score: 3 | |
| Jan 9, 2011 at 0:59 | history | edited | Hans-Peter Stricker | CC BY-SA 2.5 |
added 2 characters in body
|
| Jan 9, 2011 at 0:07 | comment | added | Hans-Peter Stricker | Good questions. Is there any chance to have a complete list of them, each with a definite list of answers, thus specifying all conceivable languages? | |
| Jan 9, 2011 at 0:04 | comment | added | Andrés E. Caicedo | What requirements do you ask of a language? Does it need to have a countable vocabulary? Is its syntax recursive? What requirements do you ask of its semantics? | |
| Jan 8, 2011 at 23:40 | history | edited | Hans-Peter Stricker | CC BY-SA 2.5 |
added 144 characters in body; added 1 characters in body; edited tags
|
| Jan 8, 2011 at 23:31 | history | asked | Hans-Peter Stricker | CC BY-SA 2.5 |