ISSN:
1572-9273
Keywords:
04A20
;
Topological graph
;
complete graph
;
independent set
;
ordered set
;
comparability graphy
;
ideal
;
topological space
;
Krull dimension
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract A topological graph is a graph G=(V, E) on a topological space V such that the edge set E is a closed subset of the product space V x V. If the graph contains no infinite independent set then, by a well-known theorem of Erdös, Dushnik and Miller, for any infinite set L⊑V, there is a subset L′⊑L of the same oardinality |L′| = |L| such that the restriction G ↾ L′ is a complete graph. We investigate the question of whether the same conclusion holds if we weaken the hypothesis and assume only that some dense subset A⊑V does not contain an infinite independent set. If the cofinality cf (|L|)〉|A|, then there is an L′ as before, but if cf (|L|)〈-|A|, then some additional hypothesis seems to be required. We prove that, if the graph G↾A is a comparability graph and A is a dense subset, then for any set L⊑V such that cf (|L|)〉ω, there is a subset L′⊑L of size |L′|=|L| such that G↾L′ is complete. The condition cf (|L|)〉ω is needed.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00383601
Permalink
