An infinite combinatorial statement with a poset parameter

Combinatorica, 31(2) (2011), 183-200
http://dx.doi.org/10.1007/s00493-011-2602-y

We introduce an extension, indexed by a partially ordered set P and cardinal numbers ?,?, denoted by (?,<?)?P, of the classical relation (?,n,?)?? in infinite combinatorics. By definition, (?,n,?)?? holds if every map F: [?] n ?[?]<? has a ?-element free set. For example, Kuratowski’s Free Set Theorem states that (?,n,?)?n+1 holds iff ? ? ? +n , where ? +n denotes the n-th cardinal successor of an infinite cardinal ?. By using the (?,<?)?P framework, we present a self-contained proof of the first author’s result that (? +n ,n,?)?n+2, for each infinite cardinal ? and each positive integer n, which solves a problem stated in the 1985 monograph of Erd?s, Hajnal, Máté, and Rado. Furthermore, by using an order-dimension estimate established in 1971 by Hajnal and Spencer, we prove the relation TeX , for every infinite cardinal ? and all positive integers n and r with 2?r<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).