Tuesday, March 12, 2019

How beatiful is this stuff on matrixes and graphs ?

Yes I know that graphs are represented by incidence and adiacency matrixes. However I never realize how a matrix can be represented by bipartite (or multipartite graphs). My attention was brought to it by the Math3ma blog (by Tai Danae Bradley) which I follow with delight (I am not saying that I am understanding all I read there). In particular this blog post entitles "Viewing matrices and probability as graphs".

The figure above comes from that blog and explain the concept that a matrix can be represented by a bipartite graph. If you understand it, then you can click on the Figure and continue your reading at the original blog.
After that, I noticed that the matrix representation is actually quite concise. Is it the minimal (using less numbers, excluding indexes) representation of the graph ? And, viceversa, given a graph, can we partitions its nodes in  sets such that any node in a group is connected with nodes in the other groups, but not with those in the same group ? If we are able to do so, we can subsequently build the matrix representation of the graph, reverting the process used in figure. If our set of nodes in the graph is tripartite, then the resulting matrix will be three-dimensional and so on.

In 1D (on the line) the partition is obvious and  is a bi-partition.  In 2D, the problem seems to be necessary a qudri-partition, at least for those graphs that are grids (cw-complexes): in fact the problem is the same of that brought to the four color problem. What happens in 3D ?

P.S. - Recently (2019-07-16)I found this interesting paper.

No comments:

Post a Comment