de Bruijn–Erdős theorem

E239169

mathematical theorem theorem in combinatorics theorem in graph theory

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.

Try in SPARQL Jump to: Surface forms Statements Referenced by

All labels observed (3)

Label	Occurrences
de Bruijn–Erdős theorem canonical	1
de Bruijn–Erdős theorem for hypergraphs	1
de Bruijn–Erdős theorem for set systems	1

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 self-linksurface differs ⓘ surface form: de Bruijn–Erdős theorem for hypergraphs de Bruijn–Erdős theorem self-linksurface differs ⓘ surface form: 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	N. G. de Bruijn ⓘ surface form: Nicolaas Govert de Bruijn Pál Erdős ⓘ surface form: Paul 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 theorem for products of compact spaces ⓘ surface form: 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

The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.

Instruction

You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10.

# Requirements
- If you don't know the subject at all, return an empty list.
- If the subject is not a named entity, return an empty list.
- Include at least one triple where predicate is "instanceOf".
- Do not get too wordy.
- Separate several objects into multiple triples with one object.

Input

Subject: de Bruijn–Erdős theorem
Description of subject: 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.

Referenced by (3)

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 self-linksurface differs ⓘ

this entity surface form: de Bruijn–Erdős theorem for hypergraphs

de Bruijn–Erdős theorem → hasVariant → de Bruijn–Erdős theorem self-linksurface differs ⓘ

this entity surface form: de Bruijn–Erdős theorem for set systems