Computer Science/Discrete Mathematics Seminar I

For an undirected graph G=(V,E), let G^n denote the graph whose vertex set is V^n in which two distinct vertices (u_1, u_2, ... ,u_n) and (v_1, v_2, ... ,v_n) are adjacent iff for all i between 1 and n, u_i and v_i are either equal or adjacent. The Shannon capacity of G is the limit of the sequence (\alpha(G^n))^{1/n}, where \alpha(G^n) is the maximum size of an independent set of vertices in G^n. In the first part of the talk, I will sketch a proof showing that the Shannon Capacity of G can be far from any term of an arbitrarily long, yet fixed, prefix of this sequence. This is true even if this prefix shows a significant increase after which it stabilizes for a while. Next, motivated by questions in coding theory, I will discuss the Xor graph product, and investigate two new parameters of a graph, which relate to the independence numbers and clique numbers of its Xor powers. Joint work with Noga Alon.