首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Clique number of Xor products of Kneser graphs
Institution:Eötvös Loránd University, Pázmány Péter sétány 1/C, 1117 Budapest, Hungary
Abstract:In this article we investigate a problem in graph theory, which has an equivalent reformulation in extremal set theory similar to the problems researched in “A general 2-part Erd?s-Ko-Rado theorem” by Gyula O.H. Katona, who proposed our problem as well. In the graph theoretic form we examine the clique number of the Xor product of two isomorphic KG(N,k) Kneser graphs. Denote this number with f(k,N). We give lower and upper bounds on f(k,N), and we solve the problem up to a constant deviation depending only on k, and find the exact value for f(2,N) if N is large enough. Also we compute that f(k,k2) is asymptotically equivalent to k2.
Keywords:Extremal set theory  Intersecting families  Xor product
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号