Timeline for Non-definability of graph 3-colorability in first-order logic
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 19, 2023 at 20:37 | comment | added | H.C Manu | Oo, that's a clever little argument, thanks for the calrification @JoelDavidHamkins. | |
| Jul 19, 2023 at 20:34 | comment | added | Joel David Hamkins | @H.CManu If you refer to Emil's observation, it goes like this: the ultrapower of my bands of odd-length and the ultrapower of the even-sized bands both consist of continuum many $\mathbb{Z}$-chains sequences of my Giant's belt, so they are isomorphic as infinite graphs. But if 3-colorability were expressible for finite graphs, the even-sized factors would all satisfy the assertion, but the odd-sized factor not. So the ultrapower would satisfy it in the even case but not the odd case, contradicting that the two ultrapowers are isomorphic. | |
| Jul 19, 2023 at 20:19 | comment | added | H.C Manu | Sorry I know this should be obvious but I am not sure I understand. Given the fact that we are working with finite graphs, but the ultraproduct is made up of infinite graphs, how do we reach the conclusion of the argument? | |
| Jul 8, 2023 at 12:53 | comment | added | Joel David Hamkins | Thanks! I have fixed it. | |
| Jul 8, 2023 at 12:51 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 20 characters in body
|
| Jul 8, 2023 at 11:42 | comment | added | Andreas Blass | +1, but a quibble: "ultrapower" should be "ultraproduct". | |
| Jul 8, 2023 at 5:49 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 39 characters in body
|
| Jul 7, 2023 at 22:58 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
edited body
|
| Jul 7, 2023 at 22:52 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 33 characters in body
|
| Jul 7, 2023 at 22:40 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 562 characters in body
|
| Jul 7, 2023 at 21:32 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 6 characters in body
|
| Jul 7, 2023 at 21:21 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 670 characters in body
|
| Jul 7, 2023 at 21:19 | comment | added | Emil Jeřábek | Ah, yes, wheels. I couldn’t remember what the official name was. | |
| Jul 7, 2023 at 21:17 | comment | added | Joel David Hamkins | I see, bicycle wheels with an odd number of spokes! And that idea will generalize to every finite $n$. | |
| Jul 7, 2023 at 21:15 | comment | added | Emil Jeřábek | Btw, a perhaps easier way of going from 2-colourability to 3-colourability is to take the cycles and just add an extra vertex adjacent to all vertices of the cycle. This also generalizes to $k$-colourability for any constant $k\ge2$. | |
| Jul 7, 2023 at 21:12 | comment | added | Joel David Hamkins | Yes, I agree. Even when restricting to finite graphs, we cannot express it. | |
| Jul 7, 2023 at 21:07 | comment | added | Emil Jeřábek | Since the ultrapower of odd-sized bands and the ultrapower of even-sized bands are the same, this actually shows that no first-order sentence defines 3-colourability on finite graphs. | |
| Jul 7, 2023 at 21:04 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 1 character in body
|
| Jul 7, 2023 at 20:58 | history | answered | Joel David Hamkins | CC BY-SA 4.0 |