The Erdős-Dushnik-Miller theorem for topological graphs and orders
type: Item
instance of: scholarly article
title: The Erdős-Dushnik-Miller theorem for topological graphs and orders
zbMATH Open document ID: 0574.05045
DOI: 10.1007/BF00383601
published in: Order
publication date: 1985-01-01T00:00:00Z
review text: 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\times 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\subseteq V\), there is a subset L'\(\subseteq L\) of the same cardinality \(| L'| =| L|\) such that the restriction \(G\upharpoonright 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\subseteq 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|)\leq | A|\), then some additional hypothesis seems to be required. We prove that, if the graph \(G\upharpoonright A\) is a comparability graph and A is a dense subset, then for any set \(L\subseteq V\) such that \(cf(| L|)>\omega\), there is a subset L'\(\subseteq L\) of size \(| L'| =| L|\) such that \(G\upharpoonright L'\) is complete. The condition \(cf(| L| >\omega\) is needed.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 03E05
zbMATH DE Number: 3916322
zbMATH Keywords: topological graph
zbMATH Keywords: topological space
zbMATH Keywords: complete graph
zbMATH Keywords: independent set
zbMATH Keywords: comparability graph
author: Eric C. Milner
author: Maurice Pouzet
MaRDI profile type: Publication
cites work: Q5581652
cites work: Complete ordered sets with no infinite antichains
cites work: Partially Ordered Sets
cites work: A partition calculus in set theory
cites work: Monotone Subnets in Partially Ordered Sets
cites work: Q3226265
cites work: Q3852172
cites work: Q5340517
cites work: Partial well‐ordering of sets of vectors
cites work: Well quasi-ordered sets and ideals in free semigroups and algebras
full work available at URL: https://doi.org/10.1007/bf00383601
OpenAlex ID: W2088409042
description: scientific article; zbMATH DE number 3916322