Graph Product Powers [Graph Theory]

This video covers graph product powers (an iterated binary graph operation), specifically those built off the 4 most common products: Cartesian, Tensor, Strong, and Lexicographic graph products. We cover the sizes and limit-densities of these product powers as well.
Join my channel to get benefits, such as early access, Discord server, and priority video suggestions:
/ @vitalsine

[@jvarunkumar]

Thanks for the video. Can you shed some light on the intuition regarding the information conveyed/captured by say the 3rd strong product of some graph G? Are there some interesting properties of these k^th strong powers of a graph?

[@VitalSine]

Hmm, that's a great question. The k-th strong product has applications to information theory, see: en.wikipedia.org/wiki/Shannon_capacity_of_a_graph. A communications channel can be represented by a (confusion) graph whose vertices are the elements of your alphabet, adjacent when they can be confused for each other. Independent sets are codewords that cannot be confused for each other, and k-th product powers and limits of product powers come into the definition of Shannon capacity.

[@jvarunkumar]

@@VitalSine Thank you for the response. If a unweighted undirected graph G is given as an adjacency matrix A, then B=A^k ( boolean matrix multiplication performed k times over A) has 1 for B[u][v], if there is a path of length at most k , between u and v. Is there something similar to infer from this kth strong product or cartesian product or tensor product?

[@VitalSine]

​@@jvarunkumar Yes, there is a similar insight from kth strong product in the information theory example. The independence number of the kth strong product, is the maximum number of codewords of length k formed from your alphabet (vertices in the initial graph) that you can use without confusion. This is all using the interpretation of a vertex in the k-th strong product as a codeword of length k from the alphabet = vertices of the initial graph. Good question for cartesian/tensor products. Nothing comes to mind right now regarding applications of the k-th product power for cartesian/tensor products, but I'm sure there could be applications similar to the Shannon capacity example for strong products. Something to think about is that k-th product powers are about relating tuples of vertices to each other, so if you have some objects (ex. an alphabet of symbols), some way those objects are related together (ex. symbols that can be confused for each other are "related") and a way of "concatenating" those objects (ex. concatenation of symbols to form codewords), then a k-th product power could make sense in that application for describing how concatenations relate to each other (ex. how codewords of length > 1 can be confused with each other). The strong product adjacency rules encode the way that length-k codewords being confused for each other works (sharing some symbols in the same positions and having the rest of the positions with symbols different but confusable with each other). Cartesian/tensor product don't encode that, instead the Cartesian product encodes: (one position has symbols confusable with each other, the rest of the positions have the same symbols) , and Tensor product encodes (all positions have symbols different but confusable with each other).

[@VitalSine]

@@jvarunkumar A paper you may be interested in, it discusses an application of cartesian product powers: arxiv.org/abs/1506.08564