×

zbMATH — the first resource for mathematics

The Erdős-Dushnik-Miller theorem for topological graphs and orders. (English) Zbl 0574.05045
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.

MSC:
05C99 Graph theory
05A05 Permutations, words, matrices
03E05 Other combinatorial set theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R.Bonnet (1973) On the cardinality of the set of initial intervals of a partially ordered set, Colloq. Math. Soc. Janos Bolyai 10, 189-198.
[2] R.Bonnet and M.Pouzet (1969) Extensions et stratifications d’ensembles dispersés, C. R. Acad. Sci. Paris 268, 1512-1515. · Zbl 0188.04203
[3] D.Duffus, M.Pouzet (and I.Rival (1981) Complete ordered sets with no infinite antichains, Discrete Math. 35, 39-52. · Zbl 0466.06002 · doi:10.1016/0012-365X(81)90200-4
[4] B.Dushnik and E. W.Miller (1941) Partially ordered sets, Amer. J. Math. 63, 600-610. · Zbl 0025.31002 · doi:10.2307/2371374
[5] P.Erdös and R.Rado (1956) A partition calculus in set theory, Bull. Amer. Math. Soc. 62, 427-489. · Zbl 0071.05105 · doi:10.1090/S0002-9904-1956-10036-0
[6] R. W.Hansell (1967) Monotone subnets in partially ordered sets, Proc. Amer. Math. Soc. 18, 854-858. · Zbl 0153.33202 · doi:10.1090/S0002-9939-1967-0215759-7
[7] J. L.Kelley (1955) General Topology, Van Nostrand, New York. · Zbl 0066.16604
[8] T.Jech (1978) Set Theory, Academic Press, New York. · Zbl 0419.03028
[9] L.Nachbin (1965) Topology and Order, Van Nostrand, Princeton, 122 pp. · Zbl 0131.37903
[10] M. Pouzet and N. Zaguia (1983) The deviation and the Krull dimension of a partially ordered set, Rapport laboratorie Algébre Ordinale, Lyon. (To appear in Discrete Math. with title: Dimension de Krull des ensembles ordonnés.)
[11] R.Rado (1954) Partial well ordering of sets of vectors, Mathematika 1, 89-95. · Zbl 0057.04302 · doi:10.1112/S0025579300000565
[12] J. C.Robson (1978) Well quasi ordered sets and ideals in free semigroups and algebras, J. Alg. 55, 521-535. · Zbl 0404.16010 · doi:10.1016/0021-8693(78)90235-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.