Talk:De Bruijn–Erdős theorem (graph theory)

De Bruijn–Erdős theorem (graph theory) has been listed as one of the Mathematics good articles under the good article criteria. If you can improve it further, please do so. If it no longer meets these criteria, you can reassess it.
Review: January 15, 2019. (Reviewed version).

A fact from De Bruijn–Erdős theorem (graph theory) appeared on Wikipedia's Main Page in the Did you know column on 24 July 2011 (check views). The text of the entry was as follows:

Did you know... that the De Bruijn–Erdős theorem may be used to extend the four-color theorem from finite planar graphs to planar graphs with infinitely many vertices?

A record of the entry may be seen at Wikipedia:Recent additions/2011/July.

Wikipedia

A second "De Bruijn–Erdős theorem"[edit]

There's another "De Bruijn–Erdős theorem" that comes up occasionally in incidence geometry. It essentially states that a configuration of n points in the projective plane, not all on a line, span at least n distinct lines. The result is from the following paper:

de Bruijn, N. G.; Erdős, P. (1948), "A combinatioral [sic] problem" (PDF), Indagationes Mathematicae, 10: 421–423

I plan to add to this article a mention of this soon (but I'm too tired tonight). Jwesley₇₈ 07:38, 3 April 2010 (UTC)[reply]

I think there should be separate articles for the two theorems. In books like A Course in Combinatorics by van Lint and Wilson this is the only De Bruijn–Erdős theorem mentioned (and proved).Kope (talk) 12:38, 3 April 2010 (UTC)[reply]

Yes, it's definitely the lesser known of the two. The theorem I'm referring to is discussed in Section 2.2, which is titled "The de Bruijn–Erdos Theorem, of the book "Combinatorics of Finite Geometries" by L. M. Batten. (You can see the table of contents here.) Do you think the title of the new (02:40, 4 April 2010 (UTC)) article should be De Bruijn–Erdős theorem (incidence geometry)? Jwesley₇₈ 17:37, 3 April 2010 (UTC)[reply]

I created an article for the other theorem here: De Bruijn–Erdős theorem (incidence geometry) Jwesley₇₈ 17:15, 4 April 2010 (UTC)[reply]

Rename to "de Bruijn–Erdős theorem (graph theory)"[edit]

For sake of symmetry with its companion article "de Bruijn–Erdős theorem (incidence geometry)", I propose this article be renamed to "de Bruijn–Erdős theorem (graph theory)". Anyone object? or have an better name? Jwesley₇₈ 23:42, 4 April 2010 (UTC)[reply]

Fine, other possibilites are "de Bruijn–Erdős theorem (infinite graph theory)", "de Bruijn–Erdős theorem (infinite graphs)". Kope (talk) 06:37, 5 April 2010 (UTC)[reply]

Proof via Zorn's lemma[edit]

The proof via Zorn's lemma was actually given by Lajos Pósa, as Soifer remarks in his book. It is unpublished, but Lovász wrote it up in his book Combinatorial Problems and Exercises. I think that the first to come up with that proof was Gabriel Dirac, he did not publish it either, but wrote it up in his Ph. D. thesis. Kope (talk) 05:43, 6 April 2010 (UTC)[reply]

Other proofs by ultrapowers and ultrafilters[edit]

Does the treatment given in this dissertation by one of Sabidussi's graduate students add sufficiently to Luxemburg's to merit inclusion?? 128.172.67.235 (talk) 18:39, 12 August 2016 (UTC)[reply]

Sentence needs expanation[edit]

Next sentence is unclear....

This follows immediately (what follows?)

from the definition of a strongly compact cardinal κ

as being a cardinal

such that every collection of formulae of infinitary logic

each of length smaller than κ,

that is satisfiable for every subcollection of fewer than κ formulae,

is (what is satisfiable???) globally satisfiable.

Jumpow (talk) 22:09, 16 May 2017 (UTC)[reply]

I added some indentation to your listing. The collectionion of formulae is "what is satisfiable". "What follows" is the sentence having this footnote. —David Eppstein (talk) 05:39, 17 May 2017 (UTC)[reply]

Thanks, now I understood. Jumpow (talk) 19:47, 23 May 2017 (UTC)[reply]

Suggestions[edit]

I was thinking about reviewing the good article nomination, but decided against it, because I don't really have any experience with math articles on Wikipedia. But I thought I might put in my two cents anyhow.

"It is a special case of the compactness theorem of Kurt Gödel stating that a set of first-order sentences has a model if and only if every finite subset of it has a model." I'm not sure this is true. Or at least I don't see how the theorem can be proved using the compactness of first-order logic. It can, however, be easily proved using the compactness of propositional logic.

Reading the article, I felt like there were a few things that could be made more accessible by providing a little more detail. For example, I think the counterexample to the theorem in models of set theory without choice could be made more easily understandable. I don't understand math without the axiom of choice, so that part I won't comment on. But maybe the argument why the graph G can be two-colored with the axiom of choice can be made clearer. Why do two vertices in G that differ by an even integer multiple of the square root of two plus a rational number require the same color? Why is the graph formed by contracting each equivalence class to a single vertex an infinite matching?

Other than that, I thought it was really interesting and well-written article. Thanks,--Carabinieri (talk) 16:36, 23 May 2018 (UTC)[reply]

Thanks! I added both a reference for the connection to first-order compactness and a second reference that explains which first-order structures are intended. As for the counterexample, I think it was explained wrong. (The vertices require the same color if we are to 2-color the graph, but we never said we were trying to 2-color it before the assertion that they require the same color.) I've rewritten that part. —David Eppstein (talk) 06:04, 24 May 2018 (UTC)[reply]