Suitable sets of permutations, packings of triples, and Ramsey's theorem

摘要

A set of N permutations of {1, 2, ..., v} is t-suitable, if each symbol precedes each subset of t - 1 others in at least one permutation. The extremal problem of determining the smallest size N of such sets for given v and t was the subject of classical studies by Dushnik in 1950 and Spencer in 1971. Colbourn recently introduced the concept of suitable cores as equivalent objects of suitable sets of permutations, and studied the dual problem of determining the largest v = SCN(t, N) such that a suitable core exists for given t and N. Chan and Jedwab showed that when N = left perpendicular t+1/2 right perpendicular inverted right perpendicular t+1/2 inverted left perpendicular the value of SCN (t, N) is asymptotically left perpendicular t/2 right perpendicular + 2 if l is a fixed integer. In this paper, we improve this result by showing that it is also true when l = 0(in t) using Ramsey theory. When v is bigger than left perpendicular t/2 right perpendicular + 2, we give new explicit constructions of suitable cores from packings of triples, and random constructions from extended Ramsey colorings. (C) 2019 Elsevier Ltd. All rights reserved.