A semidefinite programming approach to a cross-intersection problem with measures

• 成果类型: Article
• 署名作者: Suda, Sho; Tanaka, Hajime; Tokushige, Norihide
• 署名单位: Aichi University Education; Tohoku University; University of the Ryukyus
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1106-3
• 发表日期: 2017
• 页码: 113-130
• 关键词: erdos-ko-rado; THEOREM; families

摘要

We present a semidefinite programming approach to bound the measures of cross-independent pairs in a bipartite graph. This can be viewed as a far-reaching extension of Hoffman's ratio bound on the independence number of a graph. As an application, we solve a problem on the maximum measures of cross-intersecting families of subsets with two different product measures, which is a generalized measure version of the ErdAs-Ko-Rado theorem for cross-intersecting families with different uniformities.