Hereditary rigidity, separation and density In memory of Professor I.G. Rosenberg
Résumé
We continue the investigation of systems of hereditarily rigid relations started in Couceiro, Haddad, Pouzet and Schölzel [1]. We observe that on a set V with m elements, there is a hereditarily rigid set R made of n tournaments if and only if m(m − 1) ≤ 2 n. We ask if the same inequality holds when the tournaments are replaced by linear orders. This problem has an equivalent formulation in terms of separation of linear orders. Let h Lin (m) be the least cardinal n such that there is a family R of n linear orders on an m-element set V such that any two distinct ordered pairs of distinct elements of V are separated by some member of R, then ⌈log 2 (m(m − 1))⌉ ≤ h Lin (m) with equality if m ≤ 7. We ask whether the equality holds for every m. We prove that h Lin (m+1) ≤ h Lin (m)+1. If V is infinite, we show that h Lin (m) = ℵ0 for m ≤ 2 ℵ 0. More generally, we prove that the two equalities h Lin (m) = log2(m) = d(Lin(V)) hold, where log 2 (m) is the least cardinal µ such that m ≤ 2 µ , and d(Lin(V)) is the topological density of the set Lin(V) of linear orders on V (viewed as a subset of the power set P(V × V) equipped with the product topology). These equalities follow from the Generalized Continuum Hypothesis, but we do not know whether they hold without any set theoretical hypothesis.
Domaines
Mathématique discrète [cs.DM]
Origine : Fichiers produits par l'(les) auteur(s)