2009/02/25 by Pierre Gillibert, Gillibert, Pierre, Friedrich Wehrung +1
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #General Mathematics (math.GM) #Logic (math.LO) #Mathematical and Theoretical Analysis #math.CO #math.GM #math.LO
paper · pdf · doi:10.48550/arxiv.0902.4448
14 pages, Combinatorica, to appear. A comment for version 1: the proof of Lemma 3.2 is valid in case Q is lower finite (general case unknown). As we deal mostly with lower finite posets, this oversight does not affect the rest of the paper
openalex publication_date 2009/02/25 · arxiv created 2010/05/28 · arxiv updated 2010/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We introduce an extension, indexed by a partially ordered set P and cardinal numbers k,l, denoted by (k,l)-->P, of the classical relation (k,n,l)--> r in infinite combinatorics. By definition, (k,n,l)--> r holds, if every map from the n-element subsets of k to the subsets of k with less than l elements has a r-element free set. For example, Kuratowski's Free Set Theorem states that (k,n,l)-->n+1 holds iff k is larger than or equal to the n-th cardinal successor l+n of the infinite cardinal k. By using the (k,l)-->P framework, we present a self-contained proof of the first author's result that (l+n,n,l)-->n+2, for each infinite cardinal l and each positive integer n, which solves a problem stated in the 1985 monograph of Erdös, Hajnal, Mate, and Rado. Furthermore, by using an order-dimension estimate established in 1971 by Hajnal and Spencer, we prove the relation (l+(n-1),r,l)-->2m, where m is the largest integer below (1/2)(1-2-r)-n/r, for every infinite cardinal l and all positive integers n and r with r larger than 1 but smaller than n. For example, (ℵ210,4,ℵ0)-->32,768. Other order-dimension estimates yield relations such as (ℵ109,4,ℵ0)--> 257 (using an estimate by Füredi and Kahn) and (ℵ7,4,ℵ0)-->10 (using an exact estimate by Dushnik).