by Tomás Feder
Interconnectedness is maintained through links. A basic question is how links are held together while the structure that these links maintain transforms itself. Another question is what properties of the objects linked are maintained through the link structure. Both questions relate to one another when we not only consider the notion that the structure transforms itself through time as the links are maintained, but also take into account the fact that different instantiations in time are also a single structure with links manifesting time, and it is not clear whether a causal link must be maintained through time as well.
A single linked structure holds objects together either directly or through a series of links. Each object manifests a series of qualities, and these qualities cannot differ too much among closely linked objects. A significant change in one of these objects forces such a change for closely related objects, so that the objects can remain linked. The fact that objects remain tied together through time is referred to as nonexpansiveness. This forces the structure to converge at a reasonable rate toward a stable configuration of qualities, or to reach a periodic configuration where the qualities permute themselves. While one can force the structure to a stable state or to a configuration of states with minimal number of varying qualities by a computation that stabilizes one quality at a time, the overall structure system will still tend to vary according to the laws described before.
These systems can be more complex when several time linked structures are involved. Here characterizing stable solutions depends on whether partial solutions can be understood in terms of pairs of elements at a time. The smallest example leading to intractability is a complete bipartite graph with two vertices in one side and three in the other side, with six edges. In general, the case of partial solutions understood in terms of a fixed number of elements at a time may increase in complexity as the fixed number grows, while for a single symmetric binary structure that is reflexive or irreflexive, such a full understanding of partial solutions is not needed to determine the existence of solutions, thus reducing the width of the problem, and seems to require the presence of some shortcuts or chords to achieve connectivity. In the reflexive case, the smallest chordal graph that can lead to intractability is a six vertex graph with a triangle and three edges coming out of the vertices of the triangle into the other vertices. In the irreflexive case, a cycle of length six gives intractability. For chordal instances, the permutation of qualities can lead to intractability.
The linking through time suggests only the ability of pairs of objects, one past and one present, to be so linked. When the causality of such links is lost, the nonexpansiveness transforms itself into a system allowing only certain kinds of exchanges to take place, as is manifest by systems with only a few possibilities for each underlying quality. Here the absence of equalities allows bipartite systems to converge. The structure becomes much more complex when either multiple possibilities or multiple qualities are allowed to interact. Even for the simplest kind of structures, an overly linked system shows considerable slow down in its ability to find a stable state among the possibilities for its qualities. The simplest example showing slow down has three elements and three colors of edges, each of which avoids one loop. Beyond the extreme situations, systems show both logical and group-theoretic implications. Thus computation links logical and mathematical structures to one another.
For a study of causal nonexpansiveness, see [1], and [2] with several superposed nonexpansive structures. For the role of chords and connectivity in reducing width, see [3], and for tractable and intractable cases with chords see [11]. To see what happens when causality is lost and replaced by exchanges, see [4], and [12] to see these systems converge in the absence of equalities or inequalities. For the increase in complexity when multiple qualities are allowed to interact as compared with the interaction of just pairs, see [5]. For a comparison of overly linked systems with systems with few links per object and few possibilities per quality, see [6]. For a study that does not manifest these extreme situations, see [7], and [8] for the logical implications, and [9], and [10], for the group-theoretic implications. Here two unary functions can manifest the full range of complexity [13]. For extensions to more complex quantification, see [14].
The Barnette paper [5] has ties to John Weilgart's language of space and its symbols. In this language, a triangle is the symbol for mind or spirit, selecting two of the three sides of a triangle is the symbol for man, a circle is the symbol for space and an oval is the symbol for time. In the Barnette paper, triangles and digons (corresponding to circles or ovals) are tied together in a tree structure, and the linking happens by selecting two of the three sides of a triangle to be linked. If the tree of triangles and digons meets itself without connecting, a quasi-tree is obtained. The basic structure formed by triangles around a point is a wheel. To allow the inclusion of digons, it sometimes happens that two digons are interconnected in such a way that the path joining them turns into triangles. In this case, the digons may be opened into triangles to the right or to the left. An interesting fact is that all of this happens in a reduced representation, so that the points forming triangles and digons must themselves be opened up to find the cycle traversing the entire structure.
From a logical point of view, one avoids diagonalization and undecidability by remaining within monadic questions avoiding negation and inequality. Although one may remove negation and inequality systematically, whether one can do this meaningfully or not remains undecidable, and one sometimes needs to reintroduce successor and negation for the computational process. Going from monadic to binary or unbounded logic allows for removing negation and inequality without avoiding diagonalization.
The computational approach applied to the logical structure underneath diagonalization leads to the group theoretic notion of a near subgroup, which has an indivisible radical of the group, and above it an odd order, a power of two order, and an odd order again, constituting the solvable part where most of the computation takes place, with a product of simple non-solvable groups at the top. For odd order elements, the computation uses a linking between products of elements and products of their inverses. The intermediate power of two and odd order layers constitute the section with most symmetry, known as strong near subgroups, where gyrating, or inverting without commuting, can take place. The simplest examples showing gyrating or inverting without commuting and having both the power of two and the odd layer are strong near subgroups with six elements.
For a study of Tom Etter's link systems in logic and physics, see the Boundary Institute . For essays on the interconnection of mathematics, physics and philosophy by Tom McFarlane, see Integral Science . The following articles can be found in the first author's page.
[1] T. Feder, Stable networks and product graphs.
[2] T. Feder, A dichotomy theorem on fixed points of several nonexpansive mappings.
[3] T. Feder and P. Hell, Width one and bounded strict width.
[4] T. Feder, Fanout limitations on constraint systems.
[5] T. Feder and C. Subi, On Barnette's conjecture.
[6] T. Feder and P. Hell, List constraint satisfaction and list partition.
[7] T. Feder and M. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory.
[8] T. Feder and M. Vardi, Homomorphism-closed vs. existential positive.
[9] T. Feder, Constraint satisfaction on finite groups with near subgroups.
[10] T. Feder, Strong near subgroups and left gyrogroups.
[11] T. Feder, P. Hell, S. Klein, L.T. Nogueira, and F. Protti, List partitions of chordal graphs.
[12] T. Feder and D. Ford, Classification of bipartite boolean constraint satisfaction through delta-matroid intersection.
[13] T. Feder, F. Madelaine and I. Stewart, Dichotomies for classes of homomorphism problems involving unary functions.
[14] T. Feder and P. Kolaitis, Closures and dichotomies for quantified constraints.