Cross t-intersecting integer sequences from weighted Erdos-Ko-Rado
Cross t-intersecting integer sequences from weighted Erdos-Ko-Rado
复制标题
来自加权 Erdos-Ko-Rado 的交叉 t 相交整数序列
DOI：
10.1017/s0963548313000138
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Norihide
中科院分区：
文献类型：
--
作者：
Tokushige;Norihide
设m，n，t为正整数。假设[m]n是m字母表上长度为n的序列的集合。如果任何两个序列a⊂A和b⊂B在至少t个位置匹配，我们称两个子集A∈[m]n和B∈[m]n交叉t-交。在这种情况下，证明了IF THEN|A|B|≤(Mn−t)2.我们从涉及交叉t-交子集族的ErdőS-Ko-Rado定理的加权形式得到了这一结果，并给出了相应的稳定性条件.我们的主要工具之一是由Friedgut[10]提出的求交矩阵的特征值法。
Let m,n and t be positive integers. Consider [m]n as the set of sequences of length n on an m-letter alphabet. We say that two subsets A⊂[m]n and B⊂[m]n cross t-intersect if any two sequences a∈A and b∈B match in at least t positions. In this case it is shown that if then |A||B|≤(mn−t)2. We derive this result from a weighted version of the Erdős–Ko–Rado theorem concerning cross t-intersecting families of subsets, and we also include the corresponding stability statement. One of our main tools is the eigenvalue method for intersection matrices due to Friedgut [10].