de Bruijn–Erdős theorem

E239169

The de Bruijn–Erdős theorem is a fundamental result in combinatorics and graph theory that relates finite and infinite structures, notably asserting that certain properties of infinite graphs or set systems are determined by their finite substructures.

All labels observed (5)

How this entity was disambiguated

Statements (45)

Predicate Object
instanceOf mathematical theorem ⓘ
theorem in combinatorics ⓘ
theorem in graph theory ⓘ
appliesTo hypergraphs ⓘ
simple graphs ⓘ
classification result about determination of infinite properties by finite substructures ⓘ
concerns chromatic number ⓘ
finite graphs ⓘ
graph coloring ⓘ
infinite graphs ⓘ
set systems ⓘ
field combinatorics ⓘ
graph theory ⓘ
generalizes finite graph coloring principles to infinite graphs ⓘ
hasConsequence coloring properties of infinite graphs are determined by their finite subgraphs ⓘ
many problems about infinite graphs reduce to problems about finite graphs ⓘ
hasProofMethod combinatorial argument ⓘ
compactness argument ⓘ
topological methods ⓘ
ultrafilter techniques ⓘ
hasVariant de Bruijn–Erdős theorem for hypergraphs ⓘ
de Bruijn–Erdős theorem for set systems ⓘ
implies chromatic number of an infinite graph equals the supremum of chromatic numbers of its finite subgraphs ⓘ
involvesConcept cardinality ⓘ
finite subgraph ⓘ
infinite graph ⓘ
proper vertex coloring ⓘ
isFundamentalIn structural graph theory ⓘ
theory of infinite graph colorings ⓘ
namedAfter Nicolaas Govert de Bruijn ⓘ
linked to: N. G. de Bruijn

Paul Erdős ⓘ
linked to: Pál Erdős
originalPublication N. G. de Bruijn and P. Erdős, A colour problem for infinite graphs and hypergraphs ⓘ
originalPublicationYear 1951 ⓘ
relatedTo Ramsey's theorem ⓘ
Tychonoff's theorem ⓘ
compactness theorem for first-order logic ⓘ
relates finite structures ⓘ
infinite structures ⓘ
statement Every infinite graph with finite chromatic number has a finite subgraph with the same chromatic number ⓘ
typeOfResult compactness-type theorem in combinatorics ⓘ
usedIn Ramsey theory ⓘ
combinatorial set theory ⓘ
extremal combinatorics ⓘ
infinite graph theory ⓘ
yearProved 1951 ⓘ

How these facts were elicited

Referenced by (5)

Full triples — surface form annotated when it differs from this entity's canonical label.

N. G. de Bruijn → notableWork → de Bruijn–Erdős theorem ⓘ
de Bruijn–Erdős theorem → hasVariant → de Bruijn–Erdős theorem for hypergraphs ⓘ
linked to: de Bruijn–Erdős theorem
de Bruijn–Erdős theorem → hasVariant → de Bruijn–Erdős theorem for set systems ⓘ
linked to: de Bruijn–Erdős theorem
Sylvester–Gallai theorem → generalizationOf → de Bruijn–Erdős theorem (incidence geometry) ⓘ
linked to: de Bruijn–Erdős theorem
Sylvester–Gallai theorem → relatedTo → Erdős–de Bruijn theorem on incidences ⓘ
linked to: de Bruijn–Erdős theorem