Message Boards

GROUPS:

Antony Halim

[WSS20] Finding Conservation Laws in (Hyper)graph Rewritings

Antony Halim, Minerva Schools at Keck Graduate Institute

Posted 1 year ago

1519 Views

0 Replies

2 Total Likes

Follow this post

Abstract

Signs of conservation in hypergraph rewritings (model evolution) in the Wolfram Models may indicate conserved physical quantities, such as the baryon number. One approach to exploring these conservation laws is through checking for graph properties such as the graph properties of being Planar, Hamiltonian, or having no Self-Loops. Conservation of planarity, for example, can be checked using Wagner’s theorem by checking for the

3,3

and

graph minors, or using Kuratowski’s theorem by checking for the subgraphs that are subdivisions of

3,3

.Since we are dealing with graphs, the studied rules are the



rules (562 rules). The chosen initial conditions were randomly generated hypergraphs of 30 nodes and 60 edges (arity of two). The number of nodes was chosen such that it is one of the lowest bounds that can produce graphs that satisfy the tested properties trivially, e.g., planarity, due to the lack of enough nodes to form

3,3

graph minors, or subgraphs that are subdivisions of

3,3

. The hypergraphs and the initial conditions on which the rules were applied were chosen randomly rather than systematically; this was due to the enormous number of hypergraphs of the specified signature. The ratio of the number of edges to the number of nodes was chosen such that the outputs can maintain some of the graph properties and, at the same time, maintain some connectedness to avoid having all outputs extremely disconnected or split into numerous disconnected subgraphs that trivially satisfy the tested properties. The table of graphs to be tested consisted of each of the 562 rules applied to each of the randomly generated hypergraphs and initial conditions. The performed tests checked for whether the graphs were Planar, Bipartite, Connected, Acyclic, Hamiltonian, Simple, or had no Self-Loops.

Shownaboveisthesuccessiveapplicationofrule432,ofthe



rules,tooneoftheinitialconditions.Itcanbenoticedthatconnectednessispreserved.ThefirstapplicationoftheruleresultsinaHamiltoniangraph—indicatedinred—thathasnoSelf-Loops.Thus,connectednessispreserved.

Results

The testing approach was to collect together those graphs that satisfy a particular property, and then to test for other combinations of properties within that set of graphs.

Of the Connected graphs that were randomly generated, 0.17% were Hamiltonian, 12.88% were Loop-Free, 0.01% were Bipartite, 2.72% were Planar, and 0.87% were Simple. For each pair of these properties, the fraction of Connected graphs that simultaneously possessed that pair of properties is given in the table below.

Out[]=

	Hamiltonian	Loop-Free	Bipartite	Planar	Simple
Hamiltonian	0.0017	0.0008	0	0	0
Loop Free	0.0008	0.1288	0.0001	0.0097	0.0087
Bipartite	0	0.0001	0.0001	0.0001	0
Planar	0	0.0097	0.0001	0.0272	0.0026
Simple	0	0.0087	0	0.0026	0.0087

Loop Free & Bipartite & Planar: 0.0001
Loop Free & Simple & Planar: 0.0026

Of the Planar graphs that were randomly generated, 11.58% were Bipartite, 2.72% were Connected, 20.5% were Acyclic, 16.94% were Loop-Free, and 9.17% were Simple. For each pair of these properties, the fraction of Connected graphs that simultaneously possessed that pair of properties is given in the table below.

Out[]=

	Bipartite	Connected	Acyclic	Loop Free	Simple
Bipartite	0.1158	0.0001	0.0762	0.1158	0.0777
Connected	0.0001	0.0272	0	0.0097	0.0026
Acyclic	0.0762	0	0.205	0.0762	0.0762
Loop Free	0.1158	0.0097	0.0762	0.1694	0.0917
Simple	0.0777	0.0026	0.0762	0.0917	0.0917

Bipartite & Acyclic & Loop : 0.0762
Bipartite & Simple & Loop : 0.0777
Bipartite & Simple & Acyclic : 0.0762
Connected & Loop & Simple : 0.0026
Acyclic & Simple & Loop : 0.0762
Bipartite & Acyclic & Loop & Simple : 0.762

Of the Bipartite graphs that were randomly generated, 11.58% were Planar, 0.01% were Connected, 7.62% were Acyclic, 11.58% were Loop-Free, and 7.77% were Simple. For each pair of these properties, the fraction of Connected graphs that simultaneously possessed that pair of properties is given in the table below.

Out[]=

	Planar	Connected	Acyclic	Loop Free	Simple
Planar	0.1158	0.0001	0.0762	0.1158	0.0777
Connected	0.0001	0.0001	0	0.0001	0
Acyclic	0.0762	0	0.0762	0.0762	0.0762
Loop Free	0.1158	0.0001	0.0762	0.1158	0.0777
Simple	0.0777	0	0.0762	0.0777	0.0777

Planar & Acyclic & Loop : 0.0762
Planar & Acyclic & Simple : 0.0762
Planar & Simple & Loop : 0.0777
Acyclic & Loop & Simple : 0.0762
Planar & Acyclic & Loop & Simple : 0.0762

Of the Acyclic graphs that were randomly generated, 20.5% were Planar, 7.62% were Bipartite, 7.62% were Loop-Free, and 7.62% were Simple. For each pair of these properties, the fraction of Connected graphs that simultaneously possessed that pair of properties is given in the table below.

Out[]=

	Planar	Bipartite	Loop Free	Simple
Planar	0.205	0.0762	0.0762	0.0762
Bipartite	0.0762	0.0762	0.0762	0.0762
Loop Free	0.0762	0.0762	0.0762	0.0762
Simple	0.0762	0.0762	0.0762	0.0762

Planar & Bipartite & Loop Free : 0.0762
Planar & Bipartite & Simple : 0.0762
Planar & Loop Free & Simple : 0.0762
Bipartite & Loop Free & Simple : 0.0762
Planar & Simple & Loop Free & Bipartite : 0.0762

Of the Hamiltonian graphs that were randomly generated, 0.17% were Connected and 0.09% were Loop-Free. For each pair of these properties, the fraction of Connected graphs that simultaneously possessed that pair of properties is given in the table below.

Out[]=

	Connected	Loop Free
Connected	0.0017	0.0008
Loop Free	0.0008	0.0009

Of the Loop-Free graphs that were randomly generated, 16.94% were Planar, 11.58% were Bipartite, 12.88% were Connected, 7.62% were Acyclic, 0.09% were Hamiltonian, and 10.67% were Simple. For each pair of these properties, the fraction of Connected graphs that simultaneously possessed that pair of properties is given in the table below.

Out[]=

	Planar	Bipartite	Connected	Acyclic	Hamiltonian	Simple
Planar	0.1694	0.1158	0.0097	0.0762	0	0.0917
Bipartite	0.1158	0.1158	0.0001	0.0762	0	0.0777
Connected	0.0097	0.0001	0.1288	0	0.0008	0.0087
Acyclic	0.0762	0.0762	0	0.0762	0	0.0762
Hamiltonian	0	0	0.0008	0	0.0009	0
Simple	0.0917	0.0777	0.0087	0.0762	0	0.1067

Planar & Bipartite & Acyclic : 0.0762
Planar & Bipartite & Simple : 0.0777
Planar & Connected & Simple : 0.0026
Planar & Acyclic & Simple : 0.0762
Bipartite & Acyclic & Simple : 0.0762

Of the Simple graphs that were randomly generated, 9.17% were Planar, 7.77% were Bipartite, 0.87% were Connected, 7.62% were Acyclic, and 10.67% were Loop-Free. For each pair of these properties, the fraction of Connected graphs that simultaneously possessed that pair of properties is given in the table below.

Out[]=

	Planar	Bipartite	Connected	Acyclic	Loop Free
Planar	0.0917	0.0777	0.0026	0.0762	0.0917
Bipartite	0.0777	0.0777	0	0.0762	0.0777
Connected	0.0026	0	0.0087	0	0.0087
Acyclic	0.0762	0.0762	0	0.0762	0.0762
Loop Free	0.0917	0.0777	0.0087	0.0762	0.1067

Planar & Bipartite & Acyclic : 0.0762
Planar & Bipartite & Loop Free : 0.0777
Planar & Connected & Loop Free : 0.0026
Planar & Acyclic & Loop Free 0.0762
Bipartite & Acyclic & Loop Free : 0.0762
Planar & Acyclic & Loop Free & Bipartite : 0.0762

Conclusions & Recommendations

By analyzing which of the previous combinations of properties can lead to a graph that preserves Connectedness, and that does not get split into many subgraphs due to successive rule applications, we find that hypergraphs and rules combinations that give graphs that are both Hamiltonian and free of Self-Loops have always given outputs that preserve Connectedness. While the graphs that were only Hamiltonian had significantly high rates of preserving Connectedness, only the combination of the two properties, the graph being Hamiltonian and free of Self-Loops, solely had graphs that conserved Connectedness. It is important to note as well that many of the outputs that are preserving Connectedness converged to a fixed state after only one step, but some of the cases, like the one shown in the animation, did not show any convergence within the first twenty steps, and these are expected to be the intriguing cases to consider. It can also be noticed that these cases that preserve Connectedness do not all conserve the properties of the graph being Hamiltonian or having no Self-Loops.

The next step is to use a systematic approach to enumerate all hypergraphs of a similar signature then apply each of the



rules to each of the enumerated hypergraphs to make sure that there are no cases that give graphs that are both Hamiltonian and Self-Loop free while failing to preserve Connectedness. It is expected that the rules that preserve Connectedness and that do not converge quickly are the ones that can lead to interesting results.

Acknowledgements

I would like to thank my Mentor Matthew Szudzik, Stephen Wolfram, and the rest of the WSS staff for making this opportunity possible. Also, I would like to thank Professor Kiel Howe for his continuous help and support.

POSTED BY: Antony Halim

Answer

Reply to this discussion

Reply Preview

Attachments

Remove Add a file to this post

Follow this discussion

or Discard

Group Abstract

Feedback