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 Kneser graphs. Denote this number with . We give lower and upper bounds on , and we solve the problem up to a constant deviation depending only on k, and find the exact value for if N is large enough. Also we compute that is asymptotically equivalent to . |
| |
Keywords: | Extremal set theory Intersecting families Xor product |
本文献已被 ScienceDirect 等数据库收录! |
|