Hereditary rigidity, separation and density In memory of Professor I.G. Rosenberg - Combinatoire, théorie des nombres Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

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.
Fichier principal
Vignette du fichier
Final-Revision-H_M_P_T-31-03-2021.pdf (309.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03187290 , version 1 (31-03-2021)

Identifiants

Citer

Lucien Haddad, Masahiro Miyakawa, Maurice Pouzet, Hisayuki Tatsumi. Hereditary rigidity, separation and density In memory of Professor I.G. Rosenberg. ISMVL 2021, May 2021, Nursultan, Kazakhstan. ⟨10.1109/ISMVL51352.2021.00020⟩. ⟨hal-03187290⟩
28 Consultations
25 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More