Timeline for Applications of infinite graph theory
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2017 at 19:26 | comment | added | Peter Heinig | Also, it is not inconceivable a priori that $P(n)$ is eventually inconsistent in the sense that there is an $n_0$ such that for each $n >n_0$ the statement $\neg P(n)$ is a validity on the class of all undirected simple graphs. Henson's proof shows that this is not so: the infinite graphs show that one also cannot prove the (sort of) stronger conjectures $C(P(5))$, $C(P(6))$, ... , all of which are open afaik, in the above elementary way. | |
| Jun 9, 2017 at 19:12 | history | edited | Peter Heinig | CC BY-SA 3.0 |
Corrected not-incorrect but smaller-than-necessary range of parameters$n$ for which $C(P(n))$ is known to be true. In the text, as usual, $4=\{0,1,2,3\}$.\}
|
| Jun 9, 2017 at 18:08 | history | edited | Peter Heinig | CC BY-SA 3.0 |
added 155 characters in body
|
| Jun 9, 2017 at 18:01 | comment | added | Peter Heinig | And, explicitly, because of $P(4)=F\wedge E(4)$, a first-order proof of $E(4)\Rightarrow\neg F$, i.e., a proof that the property being triangle-freeness-preservingly-$4$-e.c. implies the existence of a triangle, would be a proof that $P(4)$ is simply inconsistent (and hence that $C(P(4))$ would be true for the strong reason that there does not exist any graph with $P(4)$, not only no finite one). The infinite models tell you that it is not that easy. | |
| Jun 9, 2017 at 17:56 | history | edited | Peter Heinig | CC BY-SA 3.0 |
Improved readability, as requested in a comment.
|
| Jun 9, 2017 at 17:35 | comment | added | Peter Heinig | And the negation of the first-order property in italics, while not a validity on the class of all (simple undirected) graphs, may be a validity on the class of all finite graphs. This is the open conjecture. | |
| Jun 9, 2017 at 17:30 | comment | added | Peter Heinig | And, in short, what the infinite graphs do for your is that they rule out the a priori possibility that the first-order property being triangle-free and being triangle-freeness-preservingly-4-existentially-closed is outright inconsistent. If you write out the latter property (the one in italics) in first-order logic, it is sufficiently complex that it seems fair to say that it is not humanly possible to tell right away whether it may just be inconsistent, i.e., that its negation be a validity on the class of all graphs. The infinite models show that it is not inconsistent. | |
| Jun 9, 2017 at 17:28 | comment | added | Peter Heinig | @MattF.: $C(P)$ was not claimed to be a first-order statement. You are right that it is not. But the point is somewhere else. As to the clarification you request: $C(P)$ means, well, what it says. In the example, it means: "there does not exist any finite graph which has the first-order property being triangle-free and being triangle-freeness-preservingly-$4$-existentially-closed". It is not known afaik whether this conjecture is true. | |
| Jun 9, 2017 at 17:23 | history | edited | Peter Heinig | CC BY-SA 3.0 |
deleted 35 characters in body
|
| Jun 9, 2017 at 16:35 | comment | added | user44143 | In the first paragraph, "there does not exist a finite graph satisfying P" is not even a statement of first-order logic, so I would clarify what you mean by a conjecture of that form. | |
| Jun 9, 2017 at 15:29 | history | answered | Peter Heinig | CC BY-SA 3.0 |