Constructions and nonexistence results for suitable sets of permutations

详细信息    查看全文

• 作者：Justin H.C. Chan ^jhc34@sfu.ca ; Jonathan Jedwab¹ ; ^jed@sfu.ca
• 关键词：Construction ; Extremal problem ; Nonexistence ; Ramsey's theorem ; Suitable array ; Suitable core
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：148
• 期：Complete
• 页码：183-196
• 全文大小：368 K
• 卷排序：148

文摘

A set of N   permutations of {1,2,…,v}{1,2,…,v} is (N,v,t)(N,v,t)-suitable   if each symbol precedes each subset of t−1t−1 others in at least one permutation. The central problems are to determine the smallest N for which such a set exists for given v and t, and to determine the largest v for which such a set exists for given N and t  . These extremal problems were the subject of classical studies by Dushnik in 1950 and Spencer in 1971. We give examples of suitable sets of permutations for new parameter triples (N,v,t)(N,v,t). We relate certain suitable sets of permutations with parameter t   to others with parameter t+1t+1, thereby showing that one of the two infinite families recently presented by Colbourn can be constructed directly from the other. We prove an exact nonexistence result for suitable sets of permutations using elementary combinatorial arguments. We then establish an asymptotic nonexistence result using Ramsey's theorem.