Zoltán Füredi (Rényi Institute of Mathematics)
The clique number of Xor powers of Kneser graphs
*************************************************************************
Abstract: A Kneser graph G:=KG(N,k) has an N-element base set A, the vertex set of G consists of the k-element subsets of A, and a pair {U,V} forms an edge of G when its members are disjoint, U\cap V=\emptyset. Given two graphs G=(V(G), E(G)) and H=(V(H), E(H)) their Xor product G \cdot H is a graph with the vertex set V(G) \times V(H) and two vertices (g,h) and (g',h') are connected in G \cdot H if and only if:
or gg' is not an edge of G and hh' is an edge of H.
The Xor product is not as well understood as other graph products but there are a number of highly nontrivial results about it, e.g., by Alon and Lubetzky~2007 and by Thomason~1997. We investigate the clique number of Xor products of Kneser graphs. We also examine generalizations and propose problems.
This is joint work with A. Imolay and A. Schweitzer.
