• Calendar

December 11, Tuesday
12:00 – 13:00

Graph products are a basic combinatorial object, introduced by Alfred Whitehead and Bertrand Russell in their 1912 Principia Mathematica. They are widely studied and used in applications in different fields, for example information theory, and hardness of approximation. In the first part of the talk, motivated by a problem in communication, we present a new type of graph product, which we call the Bi-partite Graph Product, or BGP for short. We characterize the spectrum of the BGP, and derive two results: an edge discrepancy result, and a new explicit construction of a co-spectral graph family. In the second part of the talk we show how to use the well-known Tensor graph product to obtain a family of uniquely k-colorable graphs. Our main tool of analysis is Connelly's condition in Rigidity Theory combined with an explicit construction and algebraic calculations of the rigidity stress matrix. Based on joint works with Michael Langberg and Igor Park.