Long Finite Sequences

详细信息    查看全文

• 作者：Friedman ; Harvey M.
• 刊名：Journal of Combinatorial Theory, Series A
• 出版年：2001
• 出版时间：July, 2001
• 年：2001
• 卷：95
• 期：1
• 页码：102-144
• 全文大小：280 K

文摘

Let k be a positive integer. There is a longest finite sequence x₁, …, x_n in k letters in which no consecutive block x_i, …, x_2i is a subsequence of any later consecutive block x_j, …, x_2j. Let n(k) be this longest length. We prove that n(1)=3, n(2)=11, and n(3) is incomprehensibly large. We give a lower bound for n(3) in terms of the familiar Ackermann hierarchy. We also give asymptotic upper and lower bounds for n(k). We view n(3) as a particularly elemental description of an incomprehensibly large integer. Related problems involving binary sequences (two letters) are also addressed. We also report on some recent computer explorations of R. Dougherty which we use to raise the lower bound for n(3).