On Numbers and Graphs - Quantum Calculus

We have calculated with graphs from the very beginning: Humans computed with pebbles like in this scene of the `Clan of the Cave Baer` (1986)) or with line graphs when writing with tally sticks (see this lecture). In all of these cases, the addition of graphs is the disjoint union which serves a nice monoid like the natural numbers. It can be extended to networks: just taking the disjoint union of networks gives an addition. The Tukey Tally computation comes to mind as well as how nature writes information onto DNA by adding graphs (networks of amino acids). Also, the Khipu language is a language in which graphs are used for computations, and the addition there given by adding knotted pieces to an already given knot can be seen as an arithmetic too.
From a topological side there is an addition dual to the disjoint union: It is the join operation. We take the disjoint union of the graphs and connect then all vertices of the first graph with vertices of the second. There is even a compatible multiplication there: build the Cartesian product of the vertices of the individual graphs, then connect two pairs if the projection to at least one of the projected graphs is connected.
Historically, the join appeared first in the work of Alexander Zykov, the multiplication (in a dual form) appeared first in the work of Gert Sabidussi. Unfortunately, no picture appears to be known of Alexander Zykov (googling leads to a Ice hockey player). But Gert Sabidussi is a contemporary mathematician who works at the university of Montreal. There is an nice biographical notes about Gert Sabidussi which contains details like that he often drove with Einstein in the bus in Princeton and had the shared the office with Benoit Mandelbrot or that he gave a talk in 1958 at an AMS meeting, where 2 people were present, one among them Branko Gruenbaum. Back to the story. We prove the following theorem:

Theorem: The Zykov-Sabidussi ring can be completed to become a Banach algebra.

What makes it possible is that the clique number c(G) of a graph is compatible with arithmetic: c(G+H)=c(G)+c(H) and c(G*H)=c(G) c(H). Maybe it is best to look at the Document: On Numbers and Graphs [PDF] and the slides: And here is the Mathematica code included in the paper

NormalizeGraph[s_]:=Module[{e,v,e2,vl,nn,r,V1=VertexList[s],e1=EdgeRules[s],ss},
 e2={};Do[If[Not[e1[[k,1]]==e1[[k,2]]],e2=Append[e2,e1[[k]]]],{k,Length[e1]}]; e1=e2;
 vl=VertexList[s]; nn=Length[vl];r=Table[vl[[k]]->k,{k,nn}];e=e1 /. r; v=V1 /. r;
 UndirectedGraph[Graph[v,e]]];
CliqueNumber[s_]:=Length[First[FindClique[s]]];

ZykovJoin[ss1_,ss2_] := Module[{s1,s2,v1, v2, n1, n2, e1, e2,v,e},
   s1 = NormalizeGraph[ss1]; s2 = NormalizeGraph[ss2];
   v1 = VertexList[s1];      n1 = Length[v1]; v2 = VertexList[s2]+n1;n2=Length[v2];
   e1 = EdgeList[s1];        e2 = EdgeList[s2];
   e1 = If[Length[e1]==0,{},Table[e1[[k,1]] -> e1[[k, 2]], {k, Length[e1]}]];
   e2 = If[Length[e2]==0,{},Table[e2[[k,1]]+ n1->e2[[k,2]]+n1,{k,Length[e2]}]];
   v = Union[v1, v2]; e = Flatten[ Union[{e1, e2, Flatten[Table[
        v1[[k]] -> v2[[l]], {k, Length[v1]}, {l, Length[v2]}]]}]];
   NormalizeGraph[UndirectedGraph[Graph[v, e]]]];
ZykovJoin[ss1_,ss2_,ss3_]:=ZykovJoin[ss1,ZykovJoin[ss2,ss3]];

ZykovProduct[s1_,s2_]:=Module[{v1,v2,e1,e2,v,e={}},
  v1 = VertexList[s1];        v2 = VertexList[s2];
  e1 = Union[EdgeList[s1]];   e2 = Union[EdgeList[s2]];
  e1 = Table[Sort[{e1[[k,1]], e1[[k,2]]}], {k, Length[e1]}];
  e2 = Table[Sort[{e2[[k,1]], e2[[k,2]]}], {k, Length[e2]}];
  v = Partition[Flatten[Table[{v1[[k]],v2[[l]]},{k,Length[v1]},{l,Length[v2]}]],2];
  Do[Do[Do[e = Append[e, {e1[[k, 1]], v2[[m]]} -> {e1[[k, 2]], v2[[l]]}],
      {k,Length[e1]}], {m,Length[v2]}], {l,Length[v2]}];
  Do[Do[Do[e = Append[e, {v1[[m]], e2[[k,1]]} -> {v1[[l]], e2[[k,2]]}],
      {k,Length[e2]}], {m,Length[v1]}], {l,Length[v1]}];
  NormalizeGraph[UndirectedGraph[Graph[v,e]]] ];
ZykovProduct[s1_,s2_,s3_]:=ZykovProduct[s1,ZykovProduct[s2,s3]]; GC=GraphComplement;
StrongProduct[s1_,s2_]:=NormalizeGraph[GC[ZykovProduct[GC[s1],GC[s2]]]];
AdditivePrimeQ[s_]:=ConnectedGraphQ[GraphComplement[s]];

ErdoesRenyi[M_,p_]:=Module[{q,e,a},V=Range[M];e=EdgeRules[CompleteGraph[M]]; q={};
  Do[If[Random[] P≤ p,q=Append[q,e[[j]]]],{j,Length[e]}];UndirectedGraph[Graph[V,q]]];

s1=ErdoesRenyi[8,0.4]; s2=ErdoesRenyi[9,0.5]; s3=ErdoesRenyi[10,0.4];
s23=ZykovJoin[s2,s3]; p13=ZykovProduct[s1,s3]; p12=ZykovProduct[s1,s2];
A=ZykovProduct[s1,s23];    B=ZykovJoin[p12,p13];

Print["Distributivity: ",IsomorphicGraphQ[A,B]];
Print["Multiplicativity: ",CliqueNumber[p12]==CliqueNumber[s1]*CliqueNumber[s2]];
Print["Additivity: ",CliqueNumber[s23]==CliqueNumber[s2]+CliqueNumber[s3]];
Print["Additive primes: ",Table[AdditivePrimeQ[CycleGraph[k]], {k, 3, 7}]];

Author: oliverknill