tag:blogger.com,1999:blog-3722233.post6268014219966280844..comments2023-06-01T23:08:19.877-05:00Comments on Computational Complexity: The Erdos- de Bruijn theoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-57088709968674603012012-03-01T12:32:53.451-06:002012-03-01T12:32:53.451-06:00This follows even from compactness of propositiona...This follows even from compactness of propositional calculus (aka zero-order logic).<br /><br />You define k variable symbols for each vertex in the graph. You add propositions asserting that exactly one holds for each vertex, as well as propositions for each edge and color.Davidhttps://www.blogger.com/profile/13818371550669837787noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26222248411945772282012-02-29T11:30:19.320-06:002012-02-29T11:30:19.320-06:00I often see such arguments phrased using König'...I often see such arguments phrased using König's Lemma that every finitely branching tree with an infinite number of nodes has an infinite branch (simple path starting at the root).<br /><br />In this case, the nodes of the tree are colorings. Level i represents all colorings of {1,...,i}. Node p at level i is a parent of node c at level i+1 if the colorings c and p agree on the colors of all nodes {1,...,i}.<br /><br />König's Lemma guarantees an infinite branch, which defines a single infinite coloring in the limit.<br /><br />There is an even shorter way to use compactness arguments that I have seen most often in the literature: "A lot of finite things exist with a property we want. By compactness, an infinite thing with the same property exists. QED"Dave Dotyhttp://www.dna.caltech.edu/~ddoty/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70653949820216571372012-02-29T11:12:10.094-06:002012-02-29T11:12:10.094-06:00Alternative proof, works in the uncountable case.
...Alternative proof, works in the uncountable case.<br /><br /> Consider the first order theory that has constants for each node on the graph, k unary predicates, statements that say that precisely one of the k predicates is true at every point, and statements that say for any two adjacent nodes of the graph that the corresponding constants don't have the same predicates true of both. This is consistent because every finite subtheory is consistent, hence by the completeness theorem it has a model. The model is a coloring.stuhttps://www.blogger.com/profile/05190631846507740664noreply@blogger.com