Essays, Posts & Presentations

Non-trivial homotopies of arbitrary hypergraphs and their solitons

Vladyslav Kuchkin

Author

Vladyslav Kuchkin

Title

Non-trivial homotopies of arbitrary hypergraphs and their solitons

Description

Study the graph homotopy

Non-trivial homotopies of arbitrary hypergraphs and their solitons

Vladyslav Kuchkin

Forschungszentrum Jülich, RWTH Aachen

Topological solitons (e.g. skyrmions) that exist in different branches of physics can effectively be described as cycle subgraphs of a hypergraph in the Wolfram model. The aim of this research is to develop a method to search for such cycles. As it turned out, the distribution of lengths of optimized cycles for a given graph contains important features about graph topology even if not all cycles are taken into account. The technique is similar to Monte-Carlo methods in physics and allows one to get reasonable results in graph exploration too. For the hypergraphs that contain a subgraph with non-trivial topology, the next step will be to study the evolution of the hypergraph under diverse rules and check the behaviour of the subgraph. The physically realistic cases correspond to the conservation of the homotopy group to which the hypergraph belongs.

Topological solitons in physics and in graph theory

Particles in modern physics often demonstrate the properties of topological solitons. They appear in experiments of inter-particle interactions that obey certain conservation laws and inspired scientists to reveal these intriguing connections. The idea that nuclei stability, or conservation of its baryonic charge, is akin to topological stability arises in Skyrm’s original paper [1]. Despite the fact that such a point of view is not very popular in modern high-energy physics, the main idea has been found to be useful in other branches of science. Magnetic solitons (skyrmions) that exist in chiral magnets and present well-localized whirls in ferromagnetic background can serve as a good example. In the continuum field theory, skyrmions are topological solitons that belong to

homotopy group. At the same time they live on the discrete lattice of magnetic material and due to this, it might be more reasonable to look at skyrmions from the side of discrete homotopy groups. The Wolfram model (WM) seems to be promising from this perspective because it considers a very general type of objects -- hypergraphs -- which additionally possess discrete topological properties [2]. Cycles of graphs in the WM may serve as analogues of the topological solitons in physics may serve . In this project, I concentrate mostly on S1 and S2 cycles in graphs [3].

S1 cycles represent one-dimensional loops that may contract into a point (see sphere) or may remain of finite size (see torus) depending on the graph topology -- trivial or non-trivial. Due to this, finding S1 cycles of the given graph is important from the point of view of the determination of its topology, which finally helps distinguish graphs of physics interest. S2 cycles are discrete analogues for two-dimensional surfaces (see sphere and torus). Finding such cycles is the same as figuring out polyhedral embedding for an arbitrary graph, which is an NP-complete problem, although a weak form of S2 -- so-called cellular embedding -- can be solved in linear time. The results presented below cover the following topics: 1) searching for S1 cycles on a square grid -- non-directed graph, 2) ways to generalize the approach to the hypergraph case, 3) exploring S2 cycles on some graphs.

Exploring S1 cycles of a graph as an optimization problem

For non-directed graphs, representing natural discretizations of arbitrary manifolds, it is easy to find all its cycles using the Wolfram Language (WL) function FindCycle. At the same time, the graphs of the most interest in WM are usually big and the brute force algorithm of considering all possible cycles does not seem to be effective. This problem can be solved by exploring only some subset of all cycles which are chosen randomly, since the statistical information of this subset often already contains the needed information about topological properties of the entire graph. From the physics perspective, such an approach is akin to Monte-Carlo methods [4]. To make the sampling more effective one can perform additional length optimization for every cycle from the subset. The technique for how this optimization can be accomplished is presented below.

2D square grid case

Let us consider a 2D grid graph (left); calling the function FindCycle allows us to get some cycle (right):

The cycle that FindCycle returns obviously can be optimized. As it turned out, in most cases it is enough to consider two simple rules. The first one is in removing three edges of a cycle and adding a new one:

-->

This one rule is not enough because it can not optimize rectangular graphs; due to this I also add the rule that inverts the corner:

-->

The algorithm that combines these two rules allows us to optimize lengths for a cycle on square grid graphs.

Examples

In addition to a 2D grid (left), the algorithm is applicable to different surface-like graphs (cylinder, cylinder with a hole, torus) that are shown below:

.Considering subsets of cycles for these graphs and performing optimization for each cycle, it is informative to look at the distribution of the lengths of optimized cycles. Using the WL function Histogram, one can visualize these distributions presented as probability densities:

The first spike on all histograms corresponds to a trivial cycle that for these particular cases coincides with the tessellation size -- 4 -- and can be contracted into a point. The 2D grid is topologically trivial because it has only cycles of this length. In the case of the cylinder, all nontrivial cycles have a length of 10.

For the cylinder with a hole, and for the torus, there are two types of nontrivial cycles of length 8 and 14, respectively.

. Additional spikes on the torus histogram do not have topological meaning and can disappear after performing more optimization steps. As we can see, even such a simple algorithm can give some useful information about graphs. Nevertheless, it has some limitations. For instance, it cannot optimize circle-like cycles. In its current form, the algorithm works only with square discretized surfaces and may fail if the graph has a large number of regions with some other tessellation. These problems can be solved and are subjects for further algorithm improvement. In the next section I consider the applicability of the algorithm for hypergraphs cases, which are the main object to study in WM.

S1 cycles on hypergraphs

The case of hypergraphs is more general due to the presence of hyperedges instead of edges, and can be thought of as a generalization of a directed graph. Although the algorithm discussed above is developed for non-directed graphs, it can be generalized straightforwardly.

Mapping between hypergraph and graph

The ResourseFunction HypergraphToGraph is useful because it performs the corresponding mapping between graphs while preserving some property of the hypergraph. Although in its standard implementation it creates graphs with a large number of edges, for my particular project, I have modified the use of the HypergraphToGraph function as is shown below:

In[]:=

<<SetReplace`r={{x,x,y},{x,z,u}}{{u,u,z},{y,v,z},{y,v,z}};hg=WolframModel[r,{{1,1,1},{1,1,1}},100,"FinalState"];g1=ResourceFunction["HypergraphToGraph"][hg];g2=ResourceFunction["HypergraphToGraph"][Flatten[If[Length[#]<3,{#},Partition[#,2,1]]&/@hg,1]];g3=Flatten[List[EdgeList[g2][[#,1]]EdgeList[g2][[#,2]]]&/@Range[Length[EdgeList[g2]]]];{HypergraphPlot[hg],g1,g2,Graph[g3]}

Out[]=





The first graph is the hypergraph (hg) from the Notable Universe Models list, the second one (g1) is its mapping obtained via the HypergraphToGraph function, the third is my modification mapping (g2) and the fourth is its non-directed version (g3).The final non-directed graph is simple to analyze with the algorithm shown above, although some information about its cycles may not be of interest from the point of view of the original hypergraph. Due to this an additional check has to be performed to figure out whether the cycle of such a non-directed graph corresponds to some cycle of the hypergraph.

Inflation-like soliton

In the case of the hypergraph shown above, the S1 cycle on its growing part represents the inflation-like soliton. It can be easily found for projection graph (g2) using FindCycle function with an additional constraint -- the sum of its vertices values has to be maximal. The graph evolution below shows how this soliton transforms while the hypergraph grows:





Graphs with S2 cycles

Since polyhedral embedding is an NP-complete problem, it is reasonable to use less precise methods that will be more computationally economical and at the same time be able to catch some useful information regarding the presence of non-trivial S2 cycles in the graph. Intuitively it is clear that the presence of an S2 cycle leads to the presence of a gigantic number of S1 cycles in the graph, though many of them are contractable. The straightforward exploration of all such S1 cycles again does not seem to be reasonable. As it turns out, the algorithm used above for optimizing S1 cycles can give certain hints about whether a graph can have S2 cycles. As has been mentioned above, the algorithm will not work properly for circular cycles, but at the same time, there are graphs containing S2 cycles for which having a big number of such non-optimized S1 cycles can serve as good evidence of the presence of a higher homotopy group.

Sphere

An example of the S2 cycle is the graph obtained as a discretization of a sphere. The circular S1 cycle that can not be more optimized using the algorithm above is shown in red:

Excluding trivial cycles of size 4 and 3 (near sphere poles), the distribution of optimized S1 cycle lengths is:

Torus with a sphere

Adding two additional vertices to the torus graph leads to new S2 cycles appearing in it. The vertices that belong to the smallest S2 cycle are shown in red:

Again excluding S1 cycles of trivial size, the distribution of the lengths has the form:

It is interesting that in both cases (sphere and torus with a sphere), the calculated histograms contain many additional cycles that may be related to the presence of S2 cycles in the initial graph. The connection between S1 and S2 cycles is direct. Assuming that the graph contains an S2 cycle means that the set of edges of S2 can be presented as a non-intersecting union of S1 cycles of the graph where every edge of an S1 cycle appears in exactly two sets. The example below demonstrates how it works. For the graph hg = {12,13,14,15, 2 3, 24,25, 34,36, 45,56, 61} (left), one can find an S2 cycle {12, 2 3, 13, 34, 24,14} (right) that is equivalent to the union {12, 2 3, 31} ⋃ {23, 34, 42} ⋃ {12, 24, 41} ⋃ {13, 34, 41}:

Therefore, analyzing S1 cycles of minimal length allows reconstruction of the S2 cycle if the graph contains one. The generalization of this definition of S2 for the case of directed graphs and hypergraphs has to take into account the edge directedness when constructing the non-intersecting union.

Concluding remarks

In this project, I have studied S1 and S2 cycles in non-directed graphs and their relation to topological solitons in physics. It has been shown that for the graph with square tessellation, the length optimization algorithm of the S1 cycle can be effectively used to determine the presence of non-trivial S1 cycles and even give some hints regarding presence of S2 cycles. The method I use allows one to find the graph homotopy group by analyzing optimized length distribution histograms, taking into account a randomly chosen subset of S1 cycles. The algorithm has been tested for graphs with square tessellation and requires additional improvement for working with graphs of arbitrary tessellation. Additionally, the further development of the project can be done in a few independent directions: 1) Study of graphs and hypergraphs belonging to higher homotopy groups. 2) Developing algorithms for effective searching of S2 and higher order cycles in graphs. 3) Exploring the connection between graphs with non-trivial topology and topological solitons in physics.

Complete project work

Skyrmion plot

In[]:=

Sk1=SliceVectorPlot3D

{2y,-2x,-1+

}

,z==0,{x,-3,3},{y,-3,3},{z,-3,3},VectorStyle"Arrow3D",VectorColorFunctionFunction[{x,y,z,vx,vy,vz,n},ColorData["ThermometerColors"][vz]],PlotLegendsAutomatic,VectorPoints12;Sk2=SliceVectorPlot3D[{y,-x,z},

==1,{x,-1,1},{y,-1,1},{z,-1,1},VectorStyle"Arrow3D",VectorColorFunctionFunction[{x,y,z,vx,vy,vz,n},ColorData["ThermometerColors"][z]],PlotLegendsAutomatic];{Sk1,Sk2}



GetRandomCycle[hg_]:=Module[{l,rv,time},time=0.01;l=0;While[l==0,rv=RandomChoice[VertexList[hg]];l=Length[TimeConstrained[FindCycle[{hg,rv}],time]];];FindCycle[{hg,rv}]]

which is based on the standard WL function FindCycle. The latter is called with two arguments hg and randomly chosen vertex, rv. If FindCycle can not find the cycle going through the vertex rv faster than for 0.01 sec, the new value for rv is generated and the whole precede is repeated.
The algorithm for optimization of the S1 cycle length consists of two rules described above. Function RemoveEdge is called with arguments hg, cycle c, and p -- the edge index of the cycle

In[]:=

RemoveEdge[hg_,c_,p_]:=Module[{cycle,i1,i2,P1,P2,v},v=Flatten[c][[p]];i1=Flatten[Position[Transpose[Position[Flatten[c],v[[1]]]][[2]],2]][[1]];i2=Flatten[Position[Transpose[Position[Flatten[c],v[[2]]]][[2]],1]][[1]];P1=Transpose[Position[Flatten[c],v[[1]]]][[1,i1]];P2=Transpose[Position[Flatten[c],v[[2]]]][[1,i2]];cycle=Join[{Flatten[c][[P1]]},{Flatten[c][[p]]},{Flatten[c][[P2]]}];If[Length[Position[EdgeList[hg],cycle[[3,2]]cycle[[1,1]]]]>0||Length[Position[EdgeList[hg],cycle[[1,1]]cycle[[3,2]]]]>0,cycle={Join[Complement[Flatten[c],cycle],{cycle[[1,1]]cycle[[3,2]]}]},cycle=c];cycle]

The function finds indices for two neighbour vertices, P1 and P2, to the edge with index p. Then it checks whether three edges (p and two of its neighbours) can be removed and substituted with a single edge connecting vertices with indices P1 and P2. If it is possible it returns the corresponded shorten cycle, otherwise, it returns the initial cycle.
The function CornerInvert is called with the same input parameters

In[]:=

CornerInvert[hg_,c_,p_]:=Module[{p1,P1,cycle1,u1,u2,q1,q2,u},v=Flatten[c][[p]];p1=Position[Position[Flatten[c],v[[1]]],2];P1=Position[Flatten[c],v[[1]]][[Flatten[p1][[1]],1]];cycle1=Join[{Flatten[c][[P1]]},{Flatten[c][[p]]}];u1=Flatten[c][[P1,1]];u2=Flatten[c][[p,2]];Position[EdgeList[hg],u1];Position[EdgeList[hg],u2];q1=Transpose[Position[EdgeList[hg],u1]][[1]];q2=Transpose[Position[EdgeList[hg],u2]][[1]];q1=EdgeList[hg][[#]]&/@q1;q2=EdgeList[hg][[#]]&/@q2;q1=Complement[q1,{q1[[Flatten[Position[q1,v[[1]]]][[1]]]]}];q2=Complement[q2,{q2[[Flatten[Position[q2,v[[1]]]][[1]]]]}];u=Intersection[VertexList[q1],VertexList[q2]];If[Length[u]0,cycle=c,u=u[[1]];cycle2={u1u,uu2};If[Length[Position[c,u]]0,cycle={Join[Complement[Flatten[c],cycle1],cycle2]},cycle=c];];cycle]

It checks whether edges with index p and previous to it can be substituted with two other edges. If the graph hg contains such edges, the function returns the updated cycle, otherwise the initial one.
The following function goes over all possible values of edge index p and makes sure that one of the two functions above returns the new cycle

In[]:=

MakeOneStep[hg_,c_]:=Module[{l1,l2,index},l1=Length[Flatten[c]];index=SelectFirst[Range[l1],Length[Flatten[RemoveEdge[hg,c,#]]]!=l1&];If[MissingQ[index],cycle=CornerInvert[hg,c,RandomChoice[Range[1,Length[Flatten[c]]]]],cycle=RemoveEdge[hg,c,index]];cycle]

The function MakeNSteps calls function MakeOneStep num times if the length of the cycle does not exceed 4.

In[]:=

MakeNSteps[hg_,c_,num_]:=Module[{cycle,i},cycle=c;i=1;While[i≤num&&Length[Flatten[cycle]]>4,cycle=MakeOneStep[hg,cycle];i++];cycle]

To optimize a few cycles I use the following function

In[]:=

OptimizeNCycles[hg_,num_,steps_]:=Module[{lengths},lengths=Table[Length[Flatten[MakeNSteps[hg,GetRandomCycle[hg],steps]]],num];lengths]

It randomly picks up num cycles using GetRandomCycle function. Each of them is optimized by function MakeNSteps, the variable steps is the number of callings function MakeOneStep. The final output is the list of lengths of the optimized cycles.

Example of optimizing one S1 cycle

Nx=8;Ny=10;hg=GridGraph[{Nx,Ny}];bc=Flatten[List[Nx(Ny-1)+##]&/@Range[1,Nx]];hg=Join[EdgeList[hg],bc];c=FindCycle[hg,{22}];(*c=GetRandomCycle[hg];*)HighlightGraph[hg,PathGraph[Flatten[c]],VertexLabelsNone];c1=MakeNSteps[hg,c,100];HighlightGraph[hg,PathGraph[Flatten[#]]]&/@{c,c1}

Out[]=





Example of optimizing many S1 cycles

In[]:=

Nx=8;Ny=10;hg=GridGraph[{Nx,Ny}];bc=Flatten[List[Nx(Ny-1)+##]&/@Range[1,Nx]];hg=Graph[Join[EdgeList[hg],bc]];data=OptimizeNCycles[hg,20,200]

Out[]=

{4,4,4,4,10,4,4,10,10,4,10,4,4,4,4,4,4,4,4,10}

In[]:=

Histogram[Select[data,#>2&],{1},"Probability"]

Out[]=

Inflation-like soltion

To find all S1 cycles for a hypergraph I use the following function

In[]:=

findCycleOfHypergraph[hg_]:=Module[{chg=0}, g=Flatten[If[Length[#]<3,{#},Partition[#,2,1]]&/@hg,1];g2D=ResourceFunction["HypergraphToGraph"][g];cycle=FindCycle[g2D,Infinity,All];chg=Table[If[Length[Intersection[EdgeList[ResourceFunction["HypergraphToGraph"][Partition[hg[[i]],2,1]]],cycle[[j]]]]>0,hg[[i]],Nothing],{j,1,Length[cycle]},{i,1,Length[hg]}];chg]

The function that provides inflation-like soliton evolution is

In[]:=

plotHyperGraphCycles[num_]:=Module[{h},r={{x,x,y},{x,z,u}}{{u,u,z},{y,v,z},{y,v,z}};hg=WolframModel[r,{{1,1,1},{1,1,1}},num,"FinalState"];hgCycle=findCycleOfHypergraph[hg];s=Sum[k,{k,Flatten[#]}]&/@hgCycle;pos=Flatten[Position[s,Max[s]]][[1]];h=HypergraphPlot[hg,GraphHighlighthgCycle[[pos]],VertexLabelsNone];h]plotHyperGraphCycles[#]&/@Range[20,40,5]

Visualisation S2 cycle

In[]:=

PlotHighlight[hg_,hgs_]:=Module[{hg1,hgs1},hg1=Table[{EdgeList[hg][[i]][[1]],EdgeList[hg][[i]][[2]]},{i,1,Length[EdgeList[hg]]}];hgs1=Table[{hgs[[i,2]],hgs[[i,1]]},{i,1,Length[hgs]}];(*hgs1=Table[{EdgeList[hgs][[i]][[1]],EdgeList[hgs][[i]][[2]]},{i,1,Length[EdgeList[hgs]]}];*)HypergraphPlot[hg1,"ArrowheadLength"->0,VertexSize->0.02,GraphHighlightJoin[hgs,hgs1],VertexLabelsNone]]

In[]:=

hg={12,13,14,15,23,24,25,34,36,45,56,61};hgs={12,23,13,34,24,14};PlotHighlight[hg,hgs]

Out[]=

Keywords

◼

Topological soliton

◼

Graph homotopy

Acknowledgment

I would like to acknowledge Stephen Wolfram for defining for me this project, Sam Whittington and Jonathan Gorard for supervision work, Max Piskunov, Carlos Muñoz and Hatem Elshatlawy for useful advice and help concerning Wolfram Language.

References

◼

Skyrme T.H.R. A Non-Linear Field Theory, Proc. R. Soc. Lond. A 260, 127 (1961).

◼

Wolfram S. A Class of Models with the Potential to Represent Fundamental Physics (2020). ArXiv:2004.08210 [Gr-Qc, Physics:Hep-Th, Physics:Math-Ph]. http://arxiv.org/abs/2004.08210

◼

Tucker, Thomas W., Gross, Jonathan L. Topological Graph Theory. United States: Dover Publications, 2001.

◼

David P. Landau and Kurt Binder. A Guide to Monte Carlo Simulations inStatistical Physics. Cambridge University Press, 4 edition, 2014.

Cite this as: Vladyslav Kuchkin, "Non-trivial homotopies of arbitrary hypergraphs and their solitons" from the Notebook Archive (2021), https://notebookarchive.org/2021-07-6167th2

Non-trivial homotopies of arbitrary hypergraphs and their solitons

Topological solitons in physics and in graph theory

Exploring S1 cycles of a graph as an optimization problem

2D square grid case

Examples

​S1 cycles on hypergraphs

Mapping between hypergraph and graph

Inflation-like soliton

Graphs with S2 cycles

Sphere

Torus with a sphere

Concluding remarks

Complete project work

Skyrmion plot

Construction of graphs

​2D grid

Cylinder

Torus

Sphere

​Cylinder with a hole

​Torus with a sphere

​S1 cycles optimization

​Example of optimizing one S1 cycle

​Example of optimizing many S1 cycles

​Inflation-like soltion

​Visualisation S2 cycle

Keywords

Acknowledgment

References

S1 cycles on hypergraphs

2D grid

Cylinder with a hole

Torus with a sphere

S1 cycles optimization

Example of optimizing one S1 cycle

Example of optimizing many S1 cycles

Inflation-like soltion

Visualisation S2 cycle