The Erdős-Dushnik-Miller theorem for topological graphs and orders

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.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: The Erdős-Dushnik-Miller theorem for topological graphs and orders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1063007)