The chain covering number of a poset with no infinite antichains

Uri Abraham; Maurice Pouzet

doi:10.5802/crmath.511

Combinatoire

The chain covering number of a poset with no infinite antichains
[Le nombre de chaînes recouvrant un ensemble ordonné sans antichaînes infinies]

Uri Abraham ¹ ; Maurice Pouzet ^2,³

¹ Math & CS Dept., Ben-Gurion University, Beer-Sheva, 84105 Israel
² ICJ, Mathématiques, Université Claude-Bernard Lyon1, 43 bd. 11 Novembre 1918, 69622 Villeurbanne Cedex, France
³ Mathematics & Statistics Department, University of Calgary, Calgary, Alberta, Canada T2N 1N4

Comptes Rendus. Mathématique, Volume 361 (2023), pp. 1383-1399.

Résumé
Abstract

Le nombre de recouvrement par chaînes d’un ensemble ordonné $P$ (poset), noté $Cov (P)$ , est le plus petit nombre de chaînes nécessaires pour recouvrir $P$ . Pour un cardinal donné $ν$ , on donne une liste de posets $Q$ de nombre de recouvrement par chaînes $ν$ telle que pour tout poset $P$ sans antichaîne infinie, $Cov (P) \geq ν$ si et seulement si $P$ contient une copie d’un membre de la liste. Cette liste est constituée de posets de cardinal $ν$ , elle a deux éléments si $ν$ est un cardinal successeur, à savoir ${[ν]}^{2}$ et son dual, et quatre éléments si $ν$ est un cardinal limite avec $cf (ν)$ faiblement compact. Pour $ν = ℵ_{1}$ , une liste a été donnée par le premier auteur ; sa construction a été étendue par F. Dorais à tout cardinal successeur infini $ν$ .

The chain covering number $Cov (P)$ of a poset $P$ is the least number of chains needed to cover $P$ . For an uncountable cardinal $ν$ , we give a list of posets of cardinality and covering number $ν$ such that for every poset $P$ with no infinite antichain, $Cov (P) \geq ν$ if and only if $P$ embeds a member of the list. This list has two elements if $ν$ is a successor cardinal, namely ${[ν]}^{2}$ and its dual, and four elements if $ν$ is a limit cardinal with $cf (ν)$ weakly compact. For $ν = ℵ_{1}$ , a list was given by the first author; his construction was extended by F. Dorais to every infinite successor cardinal $ν$ .

Reçu le : 2023-04-03
Révisé le : 2023-06-08
Accepté le : 2023-06-09
Publié le : 2023-10-31

DOI : 10.5802/crmath.511

Classification : 03E05, 06A07

Affiliations des auteurs :

Uri Abraham ¹ ; Maurice Pouzet ^{2, 3}

Licence :

CC-BY 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{CRMATH_2023__361_G8_1383_0,
     author = {Uri Abraham and Maurice Pouzet},
     title = {The chain covering number of a poset with no infinite antichains},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {1383--1399},
     publisher = {Acad\'emie des sciences, Paris},
     volume = {361},
     year = {2023},
     doi = {10.5802/crmath.511},
     language = {en},
}

TY  - JOUR
AU  - Uri Abraham
AU  - Maurice Pouzet
TI  - The chain covering number of a poset with no infinite antichains
JO  - Comptes Rendus. Mathématique
PY  - 2023
SP  - 1383
EP  - 1399
VL  - 361
PB  - Académie des sciences, Paris
DO  - 10.5802/crmath.511
LA  - en
ID  - CRMATH_2023__361_G8_1383_0
ER  -

%0 Journal Article
%A Uri Abraham
%A Maurice Pouzet
%T The chain covering number of a poset with no infinite antichains
%J Comptes Rendus. Mathématique
%D 2023
%P 1383-1399
%V 361
%I Académie des sciences, Paris
%R 10.5802/crmath.511
%G en
%F CRMATH_2023__361_G8_1383_0

Uri Abraham; Maurice Pouzet. The chain covering number of a poset with no infinite antichains. Comptes Rendus. Mathématique, Volume 361 (2023), pp. 1383-1399. doi : 10.5802/crmath.511. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.5802/crmath.511/

Bibliographie
Cité par

[1] Uri Abraham A note on Dilworth’s theorem in the infinite case, Order, Volume 4 (1987) no. 2, pp. 107-125 | DOI | MR | Zbl

[2] Uri Abraham; Robert Bonnet; Wiesław Kubiś Poset algebras over well quasi-ordered posets, Algebra Univers., Volume 58 (2008) no. 3, pp. 263-286 | DOI | MR | Zbl

[3] Roland Assous; Maurice Pouzet Jónsson posets, Algebra Univers., Volume 79 (2018) no. 3, 74 | DOI | MR | Zbl

[4] Robert Bonnet On the cardinality of the set of initial intervals of a partially ordered set, Infinite sets, Keszthely, 1973 (NATO ASI Series. Series C. Mathematical and Physical Sciences), Volume 3, North-Holland, Amsterdam, 1975, pp. 189-198 | Zbl

[5] Robert P. Dilworth A decomposition theorem for partially ordered sets, Ann. Math., Volume 51 (1950), pp. 161-166 | DOI | MR | Zbl

[6] François G. Dorais Another note on Dilworth’s theorem in the infinite case (2008) (7 pp., https://www.dorais.org/assets/pdf/abraham.pdf)

[7] François G. Dorais A note on conjectures of F. Galvin and R. Rado, Can. Math. Bull., Volume 56 (2013) no. 2, pp. 317-325 | DOI | MR | Zbl

[8] Ben Dushnik; Edwin W. Miller Partially ordered sets, Am. J. Math., Volume 63 (1941), pp. 600-610 | DOI | MR | Zbl

[9] Roland Fraïssé Theory of relations, Studies in Logic and the Foundations of Mathematics, 145, North-Holland, 2000 (with an appendix by Norbert Sauer) | MR | Zbl

[10] Eric C. Milner; Maurice Pouzet On the cofinality of partially ordered sets, Ordered sets (Banff, Alta., 1981) (NATO ASI Series. Series C. Mathematical and Physical Sciences), Volume 83, Reidel, Dordrecht-Boston, Mass., 1982, pp. 279-298 | DOI | MR | Zbl

[11] Eric C. Milner; Maurice Pouzet Antichain decompositions of a partially ordered set, Sets, graphs and numbers (Budapest, 1991) (Colloquia Mathematica Societatis János Bolyai), Volume 60, North-Holland, 1992, pp. 469-498 | MR | Zbl

[12] Eric C. Milner; Karel Prikry The cofinality of a partially ordered set, Proc. Lond. Math. Soc., Volume 46 (1983) no. 3, pp. 454-470 | DOI | MR | Zbl

[13] Micha A. Perles On Dilworth’s theorem in the infinite case, Isr. J. Math., Volume 1 (1963), pp. 108-109 | DOI | MR | Zbl

[14] Maurice Pouzet Ensemble ordonné universel recouvert par deux chaines, J. Comb. Theory, Ser. B, Volume 25 (1978) no. 1, pp. 1-25 | DOI | MR | Zbl

[15] Maurice Pouzet Parties cofinales des ordres partiels ne contenant pas d’antichaine infinie (1980) (unpublished)

[16] Richard Rado Theorems on intervals of ordered sets, Discrete Math., Volume 35 (1981), pp. 199-201 | DOI | MR | Zbl

[17] Stevo Todorčević On a conjecture of R. Rado, J. Lond. Math. Soc., Volume 27 (1983) no. 1, pp. 1-8 | DOI | MR | Zbl

[18] Stevo Todorčević Conjectures of Rado and Chang and cardinal arithmetic, Finite and infinite combinatorics in sets and logic (Banff, AB, 1991) (NATO ASI Series. Series C. Mathematical and Physical Sciences), Volume 411, Kluwer Academic Publishers, 1993, pp. 385-398 | DOI | MR | Zbl

[19] Stevo Todorčević Combinatorial dychotomies in set theory, Bull. Symb. Log., Volume 17 (2011) no. 1, pp. 1-72 | DOI | MR | Zbl

[20] Elliot S. Wolk On decompositions of partially ordered sets, Proc. Am. Math. Soc., Volume 15 (1964), pp. 197-199 | DOI | MR | Zbl

Cité par Sources :

Commentaires - Politique

Ces articles pourraient vous intéresser

Automaticité des ordinaux et des graphes homogènes

Christian Delhommé

C. R. Math (2004)

Ordres indécomposables critiques

Imed Zaguia

C. R. Math (2008)

Monotonicity and complete monotonicity for continuous-time Markov chains

Paolo Dai Pra; Pierre-Yves Louis; Ida Minelli

C. R. Math (2006)