#  Polychrony as chinampas

Eric Dolores-Cuenca a,∗,
Jose Antonio Arciniega-Nevárezb,∗∗,
Anh Nguyenc,
Amanda Yitong Zoud,
Luke Van Poperingg,e,
Nathan Crockg,
Gordon Erlebachere,
Jose L. Mendoza-Cortesf,∗∗∗

###### Abstract

We study the flow of signals through paths with the following condition: a
node emits a signal if two incoming signals from other nodes arrive
coincidentally or if it receives an external stimuli. We apply our study to
count and describe families of polychrony groups on a line and we introduce
triangular sequences.

a Yonsei University, Seodaemun-gu, Seoul, Korea.
b División de Ingenierías, Campus Guanajuato, Universidad de Guanajuato,
Guanajuato, Gto., México.

c Drexel University, Philadelphia, PA, United States.

d University of Michigan, Ann Arbor, MI, United States.

e Department of Scientific Computing, Florida State University, Tallahassee,
FL,

United States.

f Department of Chemical Engineering & Materials Science, Michigan State
University, East Lansing, MI, United States.
g NewSci Labs, Tallahassee, FL, United States.

*<EMAIL_ADDRESS>
**<EMAIL_ADDRESS>
***<EMAIL_ADDRESS>(ORCID: 0000-0001-5184-1406)

##  1  Introduction

Given a fixed directed graph, we assume that signals propagate throughout the
edges following their orientation. When several signals coincidentally reach a
vertex, a built-in condition determines whether it will react by firing
signals. This is an example of a signal-flow graph, a concept developed by
Samuel Mason and Claude Shannon ([15, 17]). If the condition is linear in the
intensity of the input signals, the graphs are called linear signal-flow
graphs. Nonlinear signal-flow graphs are used to study circulatory regulation
[12], to design automatization of non linear data converters [11] and to
analyze the problem of inverting a system consisting of nonlinear and time
varying components [5].

In this paper, we study the following nonlinear condition:

  * •

Every signal has intensity one.

  * •

Every vertex has a threshold of intensity two.

  * •

If a vertex receives coincidentally signals of intensity higher than the
threshold, the vertex fires a signal through each of its outgoing edges.

In [13] a polychrony group defines a group of neurons, called primary neurons,
that fire at specific times leading to more neurons firing, called secondary
neurons. As a result, a cascade occurs when the number of primary neurons is
below the number of secondary neurons. We study the general phenomena of
polychronization as non-linear signal-flow graph for the case of the graphs
$1\rightarrow 2\rightarrow 3\rightarrow\cdots\rightarrow n$.

One of our goals is to characterize those polychrony groups that lead to
cascades. A second goal is to count families of cascades. We also explain the
algebraic structure of cascades using the language of categorical network
models [3], and the theory of cellular automata. More specifically, we employ
rule 192 [19] but we allow initial conditions to occur at different times.

Following the above introduction, Section 2 reviews required concepts from
graph theory. In Section 3, we study the case of path networks with unital
intensity, threshold two and only a single outgoing edge. Our main results are
Theorem 3.6 and Proposition 3.9. As a consequence of our work we solve a few
enumerations of polychrony groups. In Section 3.4, we describe algorithms to
answer questions about cascades. For example given a path and a set of
external stimuli,

  * •

Will a fixed vertex be activated at a particular time?

  * •

Can we reconstruct all vertex that will be activated?

Triangular sequences play an important role in the enumeration of chinampas.
We discuss this role, and related open problems in Section 4. In Subsection
5.1, we explain the algebraic structure of cascades by using the language of
Network Models. Then we describe possible future work in Section 6.5. Code is
available at https://github.com/mendozacortesgroup/chinampas/.

##  2 Base and activation diagrams

In this chapter we review the notion of a covering graph to represent the flow
of signals in a network. We translate the problem of characterizing our
nonlinear signal-flow graphs into the problem of coloring covering graphs.

###  2.1 Base diagram

Consider the set of non-negative integers $\mathbb{N}$. For a directed graph
$A$, we denote the set of vertices and edges of $A$, respectively by $V(A)$
and $E(A)$. We define a base diagram of $A$ as the pair $(B,p)$ where $B$ is a
directed graph with set of vertices $V(B)=V\times\mathbb{N}$ and, given any
edge $e:m\rightarrow n$ of $E(A)$ labeled by $t\in\mathbb{N}$ and any
$i\in\mathbb{N}$, we define an edge $e_{i}\in E(B)$ as
$e_{i}:(m,i)\rightarrow(n,{i+t})$ between the vertices $(m,i),(n,{i+t})$ of
$V(B)$ ( see Figure 1). The function $p:B\rightarrow A$ is the projection
defined by $(m,i)\mapsto m$, and the image of every edge
${(m,i)\rightarrow(n,{i+t})}$ under $p$ defines the edge $e:m\rightarrow n$ of
$E(A)$ with label $t$.

$b$$a$$(a,0)$$(b,0)$$(a,1)$$(b,1)$$(a,2)$$(b,2)$$(a,3)$$(b,3)$$2$$1$$1$ Figure
1: Below: A signal-flow graph $A$. Above: The corresponding base diagram $B$.

A singleton $u$ is a graph with one vertex and one self-edge with label $1$.
The label represents the time that a signal takes to travel from source to
target. A path of length $l$, denoted by $path(l)$, is a directed graph with
vertices $\\{1,2,\cdots,l\\}$, where each vertex has a self-edge, while each
vertex $i<l$ has one outgoing edge to vertex $i+1$. Any edge has label $1$.
For example, see the bottom left of Figure 2. A cycle of length $l$, denoted
by $cyc(l)$, is a path with vertices in the set $\\{1,2,\cdots,l\\}$, but the
vertex $l$ has one outgoing edge to the vertex $1$ with label $1$. In other
words, a cycle is a closed path. The graphs $u$, $path(l)$, and $cyc(l)$
induce the base diagrams $\tilde{u}$, $tellis(l)$, and $cylinder(l)$, for
examples see Figure 2.

$k$$3$$2$$1$$1$$2$$3$$k$$1$$2$$3$$k$$1$$2$$3$$k$$...$$...$$...$$...$$...$$...$$...$$...$$...$$...$
(a) A $path(l)$ and its corresponding base diagram $tellis(l)$.

$k$$3$$2$$1$$1$$2$$3$$k$$1$$2$$3$$k$$1$$2$$3$$k$$...$$...$$...$$...$$...$$...$$...$$...$$...$$...$$...$
(b) A $cyc(l)$ and its corresponding base diagram $cylinder(l)$.

Figure 2: Directed labeled graphs and their base diagrams

###  2.2 Activation diagram

In the sequel, we consider graphs where every vertex has one self edge, one
outgoing edge, and every edge is consider with travel time 1, unless otherwise
stated. Given a base diagram, as an initial condition we select a subset of
vertices and call them the set of primary vertices. An activation diagram
$(B,S)$ is a base diagram $B$ and a subset $S$ of primary vertices of $V(B)$.

A secondary vertex with coordinates $(r,t)$ is a vertex in which each one of
$(r,t-1)$ and $(r-1,t-1)$ is either a primary vertex or a secondary vertex. To
any activation diagram we associate the activation graph, the underlying
colored graph in which primary and secondary vertices are black and the
remaining vertices are white. To illustrate activation diagrams we only draw
vertices that are either primary or secondary and avoid the others in the base
diagram. See Figure 3.

Figure 3:  Left: Activation diagram. Right: Corresponding activation graph.

######  Example 2.1.

Let $P=path(l)$ and $B=tellis(l)$ be as described before. Fix a vertex
$v_{i}\in P$, and consider the initial conditions
$S=\\{(v_{i+k},t)\\}_{k=0,1,\cdots,l-1}\subset B$ of consecutive vertices with
the same time. The set $S$ is determined by the initial vertex $v_{i}$ of the
path $P$, its length $l$ and a fixed time $t\in\mathbb{N}$. We call pyramid to
the activation diagram $(B,S)$ and denote it by $pyramid(l,i,t)$. In Figure 4,
it is illustrated the activation diagram $pyramid(3,i,t)$ of a path of length
$3$.

$(i+2,t)$$(i,t)$$(i+1,t)$$(i+1,t+1)$$(i+2,t+1)$$(i+2,t+2)$ Figure 4: A ring
indicates the primary vertices, there are 3 secondary vertices forming a
pyramid.

######  Remark 2.2.

Suppose we have an activation diagram in which there is a $pyramid(l,i,t)$
with an extra primary vertex $(i-1+s,t+s)$ where $0\leq s\leq l-1$. The vertex
affects $pyramid(l,i,t)$ by activating the vertices in the diagonal
$\\{(i-1+k,t+k)\leavevmode\nobreak\ |\leavevmode\nobreak\ k=s+1,\cdots,l)\\}$.
On other hand if the extra primary vertex is localized in $(i+l+1,t+s)$, where
$0\leq s\leq l-1$, then the vertical line $\\{(i+l+1,t+k)\leavevmode\nobreak\
|\leavevmode\nobreak\ k=s+1,\cdots,l\\}$ is activated, see Figure 5.

Figure 5: Effect of adding a primary vertex to a pyramid.

By a path of secondary vertices from $(i,t)$ to $(j,s)$ we mean a sequence
$(i_{0},t_{0}),(i_{1},t_{1}),\cdots,(i_{k},t_{k})$ with first point
$(i_{0},t_{0})$ $=$ $(i,t)$ and final point $(i_{k},t_{k})$ $=$ $(j,s)$, such
that there is an edge between two consecutive vertices. Here the edges are
considered ignoring the direction. Edges go from $(i,t)$ to $(i,t+1)$ and from
$(i,t)$ to $(i-1,t-1)$.

We restrict our study to activation diagrams where every primary vertex
contributes to the activation of at least one secondary vertex. A redundant
activation diagram occurs when a primary vertex is also a secondary vertex.
See Figure 6.

Figure 6:  In this activation graph, there is a primary vertex that is also a
secondary vertex.

An activation diagram $C$ is connected if the secondary vertices of the
corresponding activation graph form a connected undirected graph. As an
example, Figure 3 and Figure 4 are connected activation diagrams. Figure 7 is
not a connected activation diagram.

Figure 7: An example of an activation diagram that is not connected.

###  2.3 Base diagrams as a model of a network

We adopt the convention of [4]: the network, node, link combination often
refers to real systems… In contrast, we use the terms graph, vertex, edge when
we discuss the mathematical representation of these networks. Our networks are
such that there exist nodes $p$ firing due to external stimuli and nodes $s$
firing when the sum of input signals from other nodes exceed their own
thresholds. Our goal is the study of cascades, that is, networks whose number
of nodes $s$ are greater or equal to nodes $p$. We translate this to a base
diagram $(B,P:B\mapsto A)$: a node $p$ firing due to external stimuli at time
$t$ in the network corresponds to a primary vertex $(p,t)$ of $V(B)$ and a
node $s$ firing as a consequence of the signals of other nodes corresponds to
a secondary vertex in $V(B)$. In this way, a cascade in a network corresponds
to an activation diagram. The activation diagram of Figure 3 has as underlying
network a cascade.

Table 1 resumes the relation between the definitions of networks and the
corresponding definitions of base diagrams. Terms on the left relate to
Network theory, the term immediate to the right is the equivalent concept in
base diagrams.

Network Base diagram External stimuli Primary vertex (Network, external
stimuli) Activation Diagram (AD) Cascade AD with more or equal secondary
vertices than primary ones

Table 1: Equivalent definitions between networks and base diagrams.

##  3 Chinampas

In a cellular automata [19], three consecutive colored (black and white) cells
determine the color of the middle cell in the next iteration. In particular,
we are interested in the rule 192. The rule dictates cell $C$ will be black if
$C$ and the one to the left were black at the previous iteration, see Figure
8.

Figure 8:  Rule 192. We consider the vertical axis as time, and activated
vertex are black while inactive vertex are white.

In Figure 9, the vertical axis is the time and we think of the yellow blocks
as the stimuli to keep alive the automatas of the game of life [9]. The lowest
row represents an automata that survived for three units of time under rule
192. The next row shows three automatas that survived four units of time, then
we have six automatas that survived five units of time, and finally, we have
twelve automatas that survived six units of time.

Figure 9: Cellular automatas with less than six external stimuli.

We now proceed to study cascades on networks as the evolution of cellular
automatas where we fix the external stimuli and apply rule 192 to evolve the
cells. We will use the language of graph theory that we have developed in the
previous section.

In Subsection 3.1, we give a topological description of an arbitrary cascade
in terms of activation diagrams provided the network is a path. After that, we
count a couple of families of polycrhony groups using Lemma 3.13 and Lemma
3.14. The Subsection 3.4 contains algorithms to identify if a fixed vertex
will be activated at a particular time.

Given an activation diagram, the profit is equal to the number of secondary
vertices minus the number of primary vertices. The profit measures the maximum
number of extra vertices that are activated as a consequence of the topology
of the graph. A connected non redundant activation diagram is a chinampa if
its profit is grader or equal to zero. An example of chinampa is ilustrated in
Figure 10. The simplest chinampa, in the sense it involves the least number of
vertices, is a $pyramid(3,i,t)$ as in Figure 4. The name is due to the
similarity of the figures with a Mexican agricultural technique that uses soil
to grow crops on a lake. We imagine that chinampas have crops above the soil,
and underneath there are roots. There is no control on the size of the roots,
all we can say is that they are all pushed by the water in the same direction.

The profit defines a fuction from the set of chinampas to non negative
integers, we denote by $profit(C)$ the profit of a chinampa $C$.

Figure 10: A chinampa.

###  3.1 The topological description of a chinampa.

We describe chinampas over a $path(l)$. For this goal, we will give a
decomposition of a chinampa into pyramids. Remember that we defined
$pyramid(l,i,t)$ as an activation diagram $(B,S)$ where the primary vertices
$S$ are consecutive and have the same time. We extend the definition of
pyramid to the activation diagram $(B,S)$ in which $S$ contains secondary
vertices. So, in chinampa $C$ of Figure 11, we have two pyramids
$pyramid(3,i,t)$ and $pyramid(3,i+2,t+2)$ where the vertex $(i+2,t+2)$ is a
secondary vertex.

Figure 11: $pyramid(3,i,t)$ and $pyramid(3,i+2,t+2)$, with $(i+2,t+2)$ a
secondary vertex, form a chinampa.

Note that a pyramid has only one secondary vertex at the top, we call it
pyramidion. If $P_{1}=(B,S_{1})$ and $P_{2}=(B,S_{2})$ are pyramids in a
chinampa, we say that pyramid $P_{2}$ is staking into pyramid $P_{1}$ if the
pyramidion of $P_{2}$ is an secondary vertex of $P_{1}$ other than the
pyramidion of $P_{1}$, and $P_{2}$ is not contained in $P_{1}$.

Remark 2.2 shows that the activation diagram of a $path(l)$ is of the form a
$pyramid(k,i,t)$ together with primary vertices at the right or at the left of
$pyramid(k,i,t)$. We will see that an activation diagram is a sequence of
staked pyramids.

######  Remark 3.1.

Consider two pyramids $pyramid(l_{1},i,t)$ and $pyramid(l_{2},i+l_{1},t)$. The
pair of primary vertices $(i+l_{1},t)$ and $(i+l_{1}+1,t)$, activate
$(i+l_{1}+1,t+1)$ which is not part of any of the two pyramids. By Remark 2.2
the entire diagonal to which the vertex belongs is activated, as well as the
vertical line $\\{(i+l_{1}+1,t+k)\\}_{k\in\\{1,\cdots,l_{1}+1\\}}$, etc.
Therefore, we end up with $pyramid(l_{1}+l_{2},i,t)$. The argument works for
two pyramids $pyramid(l_{1},i,t)$ and $pyramid(i+l_{1}+k,i,t)$ separated by
activated vertices $\\{(i+l_{1}+j,t)\leavevmode\nobreak\ |\leavevmode\nobreak\
1\leq j\leq k\\}$. So, in such cases, instead of considering several small
adjacent pyramids, we always consider only the biggest pyramid that includes
the small adjacent pyramids.

######  Proposition 3.2.

There exist only one pyramidion with maximum time in a chinampa. We call it
spike.

###### Proof.

Suppose $(i,t)$ and $(j,t)$ with $i<j$ are pyramidia with maximum time. By
connectedness there is a path from $(i,t)$ to $(j,t)$ with only secondary
vertices. Each vertex on the path has time lower or equal to $t$. Starting
from the vertices with lower time, we use Remark 3.1 until we reach those
vertices with time $t$. At each step we conclude that all vertices above and
between those in the path are secondary vertices. Then those vertices between
$(i,t)$ and $(j,t)$ are activated, meaning that $(i,t)$ and $(j,t)$ are not
pyramidion. A contradiction. ∎

######  Remark 3.3.

If $(i,t)$ and $(j,t)$ are activated vertices connected by a path of activated
vertices with time lower or equal than $t$, the argument in the proof of
Proposition 3.2 shows that both of them are in a pyramid whose pyramidion has
time greater than $t$. As a consequence, if two pyramids $P_{1}$ and $P_{2}$
can be staked under a given $P$, then the pyramid $P_{1}$ cannot be adjacent
to $P_{2}$, since by Remark 3.1, we would instead stack the biggest pyramid
that includes both $P_{1}$ and $P_{2}$.

The activation diagram of Figure 12, is not a chinampa. Assume $t$ is the
minimum time of the primary vertices. Then $pyramid(2,i,t)$ and
$pyramid(2,i+2,t)$ are adjacent, so they are in $pyramid(4,i,t)$. Which means
that the vertex in the middle will be secondary vertex, contrary to the non
redundancy requirement.

Figure 12: This activation diagram is not a chinampa, the copies of
$pyramid(2,i,t)$ at the bottom are next to each other, as a consequence all
vertices in the hole are internally activated.

######  Remark 3.4.

Another consequence of Remark 2.2 is that a chinampa has no activated vertex
located at the right of the spike. If the spike is $(i,t)$ then all activated
vertices are of the form $(j,t^{\prime})$ with $j\leq i$ and $t^{\prime}<t$.

Now we shall give an order to the pyramids in a chinampa.

######  Proposition 3.5.

In a chinampa, there exist a unique $pyramid(l,i,t)$ with $l\geq 3$ of maximum
time. We call it top pyramid.

###### Proof.

Start with the spike $(i,t)$. If this is the pyramidion of a $pyramid(l,i,t)$
with $l\geq 3$ we are done. If not, then we have a sequence of
$pyramid(2,i,t)$ stacked into each other. But the chinampa has profit grader
or equal than zero, so eventually we will find $pyramid(l,i,t)$ with $l\geq
3$. Let top pyramid be the first instance found with this strategy. There is
no other pyramid $pyramid(l^{\prime},i^{\prime},t^{\prime})$ with
${l^{\prime}}>2,{t^{\prime}}\geq t$ since by connectedness and remark 3.1, we
would conclude that there is a bigger pyramid containing both top pyramid and
$pyramid(l^{\prime},i^{\prime},t^{\prime})$, which contradicts that top
pyramid is the first instance found. ∎

######  Theorem 3.6 (Topological classification of Chinampas).

Any Chinampa can be described as a sequence of pyramids stacked into each
other.

###### Proof.

We showed that in a chinampa there is a unique top pyramid Proposition 3.5.
This top pyramid is stack into a sequence of $pyramid(2,i,t)$ unless the spike
belongs to the top pyramid Proposition 3.2. Any other
$pyramid(n,i^{\prime},t^{\prime})$, $n\geq 3$ must have $t^{\prime}<t$ Remark
3.4. Pyramids are connected, and this is only possible if they are stacked
into each other. ∎

The average chinampa is described in Figure 13.

Figure 13:  Standard example of a chinampa. Left: Zooming out, the possible
configurations can be represented as stacking of pyramids. Right: Zooming in,
we see a detail of the activation graph, lines on the left figure are found to
be groups of activated vertices.

We define an abstract pyramid $pyramid(l)$ as an activated diagram without
neither initial vertex and initial time. In a $pyramid(l)$, we always consider
that the vertices at the bottom are primary vertices. A $pyramid(l)$ turns in
a $pyramid(l,i,t)$ if it is placed in a base diagram, that is, if we chose an
initial vertex $i$ and a time $t$.

Consider a chinampa $C$. Let $\mathbf{P}$ be the set of $pyramid(l)$, one for
each staking $pyramid(l,i,t)$ in the chinampa $C$. We recover the chinampa by
staking abstract pyramids from the set $\mathbf{P}$. We associate to any
$P\in\mathbf{P}$ the corresponding pyramidion. If the pyramidion of $P$
belongs to the pyramid $Q$, we call $Q$ the parent of the pyramid $P$. Note
that, after stacking, some primary vertices of the parent become secondary
vertices.

We describe an algorithm to create the list $\mathbf{P}$, we can use Breadth
First Search (BFS) or Depth First Search (DFS) [7]. Algorithm 1 is the
pseudocode of an implementation of BFS. In this algorithm the pyramidion and
the parent of $P$ are attached to $P$ as $P.pyramidion$ and $P.parent$
respectively.

Data: A Chinampa

Result: A Unique factorization

$Pyramid_{0}$ = pyramid whose pyramidion is the spike.;

Cache = [$Pyramid_{0}$];

factorization = [ ];

while Cache != [ ] do

init = pop(Cache);

/* compare the vertices of init with pyramidion */

for $v$ in $V(init)$ do

if $v$==init.pyramidion then

continue;

else if there is $P\in\mathbf{P}$ with $P.parent==init$ and $P.pyramidion==v$
then

Add $P$ to Cache

end for

factorization.append(init)

end while

return factorization

Algorithm 1 Factorization via BFS

######  Remark 3.7.

The vertices in a pyramid have an order, for example the dictionary order
starting in the top, and from left to right. Provided a fixed order on
abstract pyramids, as the one described above, our algorithm is deterministic.
So, we consider the returned list as a factorization of the chinampa in terms
of pyramids.

###  3.2 Profit

In the context, there will be not confusion between pyramid and abstract
pyramid, so some times, we call both of them pyramids. From now on, we
construct chinampas by the staking process. Remember that we do not allow
staking two pyramids one inside of the other, neither one adjacent to the
other, and some primary vertices in the abstract pyramid turn into secondary
vertices when we stake a pyramid.

Let $P_{1}$ and $P_{2}$ be two abstract pyramids and let $C$ be the chinampa
obtained by staking $P_{1}$ into $P_{2}$. We define the intersection
$P_{1}\cap P_{2}$ of two abstract pyramids $P_{1}$ and $P_{2}$ as the abstract
pyramid with activated vertices the intersection of the activated vertices of
$P_{1}$ and $P_{2}$. By definition of abstract pyramid, if a vertex is primary
in one and secondary in the other then the vertex is primary in $P_{1}\cap
P_{2}$. If the intersection of two pyramids is only one point, we assume a
profit of $-1$. We have the following result for vertical staking.

######  Lemma 3.8.

Let $C$ be a chinampa obtaned by vertical staking of two abstract piramids
$P_{1}$ and $P_{2}$. The profit function satisfies

$profit(C)=profit(P_{1})+profit(P_{2})-profit(P_{1}\cap P_{2}).$

###### Proof.

Suppose pyramid $P_{1}$ is above $P_{2}$, then the abstract pyramid
$P_{3}=P_{1}\cap P_{2}$ is again a pyramid. Let $n_{1}$, $n_{2}$ and $n_{3}$
be the number of primary vertices of $P_{1}$, $P_{2}$ and $P_{3}$
respectively. Then the $n_{3}$ primary vertices of $P_{1}$ turns into
secondary vertices in $C$, therefore the number of primary vertices of $C$ are
given by

$(n_{1}-n_{3})+n_{2},$

Even more, let $m_{1}$, $m_{2}$ and $m_{3}$ be the number of secondary
vertices of $P_{1}$, $P_{2}$ and $P_{3}$ respectively, then the number of
secondary vertices of $C$ are

$(m_{1}+n_{3})+m_{2}-(m_{3}+n_{3}).$

Therefore the results follows. ∎

Note that arguments in the proof of Lemma 3.8 are standard and can be used to
prove the following proposition.

######  Proposition 3.9.

Let $C$ be a chinampa with set of abstract pyramids $\mathbf{P}$. The profit
function satisfies the inclussion-exclussion principle

$profit(C)=\\\
\sum_{P\in\mathbf{P}}profit(P)-\sum_{P_{1},P_{2}\in\mathbf{P}}profit(P_{1}\cap
P_{2})+\sum_{P_{1},P_{2},P_{3}\in\mathbf{P}}profit(P_{1}\cap P_{2}\cap
P_{3})\pm\cdots.$ (1)

There are two was of staking a $pyramid(2)$ into another $pyramid(2)$. By
Equation (1) stacking $pyramid(2)$ into a chinampa does not changes the
profit. We show that the profit function is non decreasing.

######  Lemma 3.10.

Let $C$ be a chinampa with profit $n$. Staking a $pyramid(l,i,t)$ with $l\geq
3$ into $C$ creates a chinampa $C^{\prime}$ with profit $m>n$.

###### Proof.

Assume that we stack $pyramid(l,i,t)$ into $C$. Locally, the $pyramid(l,i,t)$
is staking in a pyramid $P$ of $C$. So that primary vertices of $P$ with time
$t+s$ with $0<s<l$ are replaced by secondary vertices, see Figure 14. The
number of primary vertices of $C$ increases by $l-(l-s)=s$ but the number of
secondary vertices increases by $(l-1+l-2+...+l-s)$ because staking only
affects the vertices of $P$. The result follows since $l\geq 3$ implies
$(l-1+l-2+...+l-s)>s$. ∎

Figure 14: A $pyramid(l,i,t)$ with $l=4$ is stack into $C$, in this example
two primary vertex of $C$ at $t+2$ become secondary.

######  Remark 3.11.

Staking one pyramid of length three and several pyramid of length two returns
a chinampa of profit zero. Conversely, by Lemma 3.10, if we have a chinampa of
profit zero, it must the result of staking one pyramid of length three and
some pyramids of length two. Similarly, a chinampa of profit $1$ has two
copies of pyramid of length three and some copies of pyramid of length two.
For profit $2$ we can have either a $pyramid(4)$ and several $pyramid(2)$
stack on/below it, or three $pyramid(3)$ and several $pyramid(2)$.

In general, a chinampa of profit $k$ is made by staking $\\{pyramid(l_{i})\\}$
so that they satisfy Equation (1). We know that
$profit(pyramid(l))=\frac{l(l-3)}{2}$, it is less or equal to $k$ by Lemma
3.10. This gives a bound on the largest pyramid contained in a chinampa in
terms of the profit of the chinampa

$l_{i}\leq\frac{3+\sqrt{9+8k}}{2},$ (2)

for all $l_{i}.$

###  3.3 Combinatorial description of chinampas of profit 0 and 1

Our purpose is to find the number of chinampas inside of $pyramid(n)$. A
general chinampa can always be considered as part of an $pyramid(n)$, see
Remark 3.4. So, consider $P=pyramid(n)$ in $tellis(n)$. We define

$ch[n;(2,a_{2}),(3,a_{3}),\dots,(k,a_{k})]$

to be the number of all chinampas contained in $P$ and obtained by staking
$a_{i}$ copies of $pyramid(i)$, where $2\leq i\leq k$.

######  Example 3.12.

It is clear that $ch[n;(n,1)]=1$, $ch[n+k;(n,k+1)]=2^{k}$ for $k\geq 0$, and

$ch[n;(2,n-1)]=2^{n-2}$ (3)

From now on, we will omit the terms corresponding to $pyramid(2)$ from the
notation, but not from the calculations, so:

$ch[n;(2,1),(n-1,1)]=ch[n;(n-1,1)].$

In Figure 15, we depict three of the elements singled out by $ch[4;(3,1)]$.
The three chinampas of profit 0 that have a $pyramid(3)$ at the top.

Figure 15: Three chinampas of profit 0 that have a $pyramid(3)\,$ on the top.

In order to count the number of chinampas of profit zero inside of an instance
of $pyramid(n)$, we consider the formal series

$\sum_{n}ch[n+3;(3,1)]\frac{x^{n}}{n!}.$

Following [18, Section 2.3], we use the calculus of formal exponential
generating functions to determine all coefficients. Note that
$ch[n+3;(3,1)]=0$ for $n<0$.

We will use the fact that the equation

$p(x)=2\int p(x)dx+f(x)e^{2x}+h(x)$

has solution

$p(x)=\frac{d}{dx}\left(e^{2x}\int f(x)+h(x)e^{-2x}dx\right).$ (4)

######  Lemma 3.13.

In $pyramid(n+3)$, for non negative integer $n$, there are $(2+3n)2^{n-1}$
possible chinampas of profit 0. More over, these numbers are given by the
coefficients of the generating function:

$\sum_{n=0}^{\infty}ch[n+3;(3,1)]\frac{x^{n}}{n!}=(3x+1)e^{2x}.$

###### Proof.

Remember that according to Remark 3.11 a chinampa of profit zero has only one
staked $pyramid(3)$. First, we can count explicitly the number of chinampas in
$pyramid(n+3)$ when $pyramid(3)$ is at the top of $pyramid(n+3)$, for each non
negative integer $n$ there is $3(2^{n-1})$ possible chinampas with this
supposition. This is because for each element of Figure 15, we create new
elements by stacking a sequence of $pyramid(2)$ below the element. Therefore,
the result follows by Equation (3). The rest of chinampas in $pyramid(n+3)$
are those in which $pyramid(3)$ is not the top. Those are $2ch[n-1+3;(3,1)]$,
since the $pyramid(3)$ is inside of one of the two subpyramids
$pyramid(n-1+3)$: one given by ignoring the main diagonal of $pyramid(n+3)$ or
the other by ignoring the right vertical column of $pyramid(n+3)$.

Therefore, for $n>0$:

$ch[n+3;(3,1)]=2ch[n-1+3;(3,1)]+3(2^{n-1}).$

Now, define

$p(x)=\sum_{n=0}^{\infty}ch[n+3;(3,1)]\frac{x^{n}}{n!}.$

So

$\displaystyle p(x)$
$\displaystyle=\sum_{n=0}^{\infty}ch(n+3,(3,1))\frac{x^{n}}{n!}$
$\displaystyle=1+2\sum_{n=1}^{\infty}ch(n-1+3,(3,1))\frac{x^{n}}{n!}+\sum_{n=0}^{\infty}3(2^{n-1})\frac{x^{n}}{n!}$
$\displaystyle=2\int{p(x)dx}+\frac{3e^{2x}-1}{2}$

Using Equation (4) and the condition $ch[3;(3,1)]=1$ we obtain

$\displaystyle\sum_{n=0}^{\infty}ch[n+3;(3,1)]\frac{x^{n}}{n!}$
$\displaystyle=(3x+1)e^{2x}$
$\displaystyle=\sum_{n=0}^{\infty}(2+3n)2^{n-1}\frac{x^{n}}{n!}$

∎

######  Lemma 3.14.

For a non negative integer $n$, chinampas of profit one have the generating
function

$\sum_{n=0}^{\infty}ch[n+4;(3,2)]\frac{x^{n}}{n!}=(9x^{2}+18x+4)\frac{e^{2x}}{2}.$

###### Proof.

A chinampa of profit one can only be formed by two copies of $pyramid(3)$ and
chains of $pyramid(2)$ as shown in Remark 3.11. Define the formal series

$q(x)=\sum_{n=0}^{\infty}ch[n+4;(3,2)]\frac{x^{n}}{n!},$

and consider the cases:

  * •

no one of the $pyramid(3)$ is at the top, then we have two subpyramids as in
the previous lemma, so we count $2ch[n+3;(3,2)].$

  * •

one $pyramid(3)$ is at the top, then the remaining $pyramid(3)$ can be put in
$2ch[n+3;(3,1)]$ ways on the two subpyramids. However, the two subcases have
$ch[n+2;(3,1)]$ common terms as shown in Figure 16. Then the correct number is
$2ch[n+3;(3,1)]-ch[n+2;(3,1)]$.

Figure 16: We represent the two subpyramids. If we stack onto pyramid(3) in
the intersection of those regions, it will be appear on both subpyramids.

We conclude that, for each non negative integer $n$:

$ch[n+4;(3,2)]=2ch[n+3;(3,2)]+2ch[n+3;(3,1)]-ch[n+2;(3,1)].$

Then using the generating series $p(x)$ found in Lemma 3.13 we compute:

$\displaystyle q(x)$ $\displaystyle=$
$\displaystyle\sum_{n=0}^{\infty}ch[n+4;(3,2)]\frac{x^{n}}{n!}$
$\displaystyle=$ $\displaystyle
2\sum_{n=1}^{\infty}ch[n+3;(3,2)]\frac{x^{n}}{n!}+2\sum_{n=0}^{\infty}ch[n+3;(3,1)]\frac{x^{n}}{n!}-\sum_{n=1}^{\infty}ch[n+2;(3,1)]\frac{x^{n}}{n!}$
$\displaystyle=$ $\displaystyle 2\int q(x)dx+2(3x+1)e^{2x}-\int(3x+1)e^{2x}dx$
$\displaystyle=$ $\displaystyle 2\int q(x)dx+\frac{18x+9}{4}e^{2x}$

Solving Equation (4) we obtain

$\displaystyle\sum_{n=0}^{\infty}ch[n+4;(3,2)]\frac{x^{n}}{n!}$
$\displaystyle=$ $\displaystyle\frac{9+2c+36x+18x^{2}}{4}e^{2x}$

We compute $ch[4;(3,2)]=2$ to conclude that

$\sum_{n=0}^{\infty}ch[n+4;(3,2)]\frac{x^{n}}{n!}=(4+18x+9x^{2})\frac{e^{2x}}{2}.$

∎

###  3.4 Algorithms for activated vertices

We describe an algorithm to

  * •

construct cascades,

  * •

predict if a vertex is activated at a given time in a cascade.

####  3.4.1 Building cascades

Instead of working at the level of networks and computing each secondary
vertex that appears in a cascade, we work at the level of chinampas. Following
ideas from dynamical programming, we compute the pyramids that are part of the
chinampas.

We remind the reader that we assume each $pyramid(l)$ have a natural order on
its vertices by time and then from left to right, so that the pyramidion is
the first element.

Input: An ordered list of primary vertices $PV$.

Result: A list of pyramids;

listOfPyramids = $[\,]$;

interval.t= PV[0].time, interval.lP=PV[0].position,
interval.rP=PV[0].position;// time, left pos,right pos

for vertex in $PV[1:]$ do

if vertex.time == interval.t and vertex.position = interval.rP+1 then

interval.rP = vertex.position

else

listOfPyramids.append(interval);

interval.t=vertex.time, interval.lP=vertex.position,
interval.rP=vertex.position;

end if

end for

listOfPyramids.append(interval);

pastPyramids = copy(listOfPyramids);

for interval in ListOfPyramids do

for lowerPyramid in pastPyramids do

deltaT=(interval.t-lowerPyramid.t);

if lowerPyramid.t+(lowerPyramid.rP-lowerPyramid.lP) $<$interval.t then

pastPyramids.remove(lowerPyramid)

else if lowerPyramid.t$>$interval.t +interval.rP-interval.lP then

break

else if interval.lP==lowerPyramid.rP+1 then

interval.lP=lowerPyramid.lP+deltaT

else if interval.rP==lowerPyramid.lP+deltaT-1 then

interval.rP=lowerPyramid.rP

end if

end for

end for

listOfPyramids = removeDuplicates(listOfPyramids); // see Algorithm 3

return listOfPyramids

Algorithm 2 $buildPyramids$

Fix a chinampa with a known set of primary vertices. We sort the primary
vertices by the time of occurrence and then by the label of the vertices. To
every sequence of $n$ consecutive primary vertices, having the same time $t$,
we assign a new structure called an interval. An interval only remembers the
coordinates $(n,t)$ of the first and last primary vertices. We assign to the
set of intervals the order inherited by the set of primary vertices. The order
is determined by the left vertex in the interval.

To the interval with lowest time, assuming it has $l$ consecutive vertices, we
associate a $pyramid(l)$. An iterative process to build the cascade goes as
follows. Given the next interval, assuming it has $l_{k}$ consecutive
vertices, we check if the first or the last term are next to a pyramid
previously built. If so, we extend the interval to include those secondary
vertex in the pyramid that have the same time as the interval. After we growth
the interval from $l_{k}$ to $l_{k}+d_{k}$, we now assign to the interval the
$pyramid(l_{k}+d_{k})$, see Algorithm 2. The auxiliary Algorithm 3 removes
duplicates.

Let $n$ be the number of primary vertices, $n_{0}=int(n/2)$. To compute the
time complexity of Algorithm 2 we analyze the best and worst case scenario.
The best case scenario is when the vertices are all part of the base of a
pyramid, in that case the time complexity is $O(n)$. The worst case scenario
is when we have $n_{0}$ copies of $pyramid(n_{0})$, concatenated in a way that
two consecutive pyramids share the maximum area possible. The time complexity
of the algorithm in this case is $(n_{0}(n_{0}-1)/2)^{2}=O(n^{2})$, because
the double loop runs $1+2+3+\cdots+n_{0}-1$ times.

Input: An ordered list of intervals $listOfPyramids$;

Result: An ordered list of intervals without intersection;

dynamicCopy=copy(listOfPyramids);

previous = dynamicCopy[0];

index = 1;

for walker in $listOfPyramids[1:]$ do

if previous.rP==walker.lP-1 and previous.t==walker.t then

previous.rP=walker.rP dynamicCopy=dynamicCopy[:index]+dynamicCopy[index+1:];

else

previous =dynamicCopy[index];

index = index+1;

end if

end for

return dynamicCopy

Algorithm 3 $removeDuplicates$

####  3.4.2 Will a vertex be activated?

Now to find if a vertex is activated, we need to check if a vertex is inside
of a pyramid. In other words, we need to verify for each pyramid if the vertex
satisfy the inequalities required to be in the region determined by the
corners of the pyramid. See Algorithm 4 of time complexity $O(n)$ in the best
case and $O(n^{2})$ in the worst case (because it calls Algorithm 2). For an
implementation of this algorithms see
https://github.com/mendozacortesgroup/chinampas/.

Input: A vertex $(n,t_{0})$, a list of primary vertices $PV$.

Result: Boolean explaining if the vertex $n$ will be activated at time
$t_{0}$;

if $(n,t_{0})$ in $PV$ then

return True ;

end if

orderedListOfPyramids = $buildPyramids(PV)$;

for pyramid in orderedListOfPyramids do

deltaT=($t_{0}-pyramid.t$);

if $pyramid.lP+deltaT\leq n\leq pyramid.rP$ and $pyramid.t\leq t_{0}\leq
n-pyramid.lP+pyramid.t$ then

/* $(n,t_{0})$ in a pyramid */

return True;

else if $pyramid.t>t_{0}$ then

break;

end if

end for

return False;

Algorithm 4 $will\\_vertex\\_be\\_activated$

##  4 Triangular sequences

The problem of finding all chinampas of profit bigger than two is still open.
Our techniques to count the chinampas of profit cero and one cannot be adapted
to this case as it misses a big family of elements, see Remark 3.11. In this
section we propose an intermediate step, we introduce triangular sequences.

We study chinampas obtained by stacking several $pyramid(2)$ below
$pyramid(n)$ for $n\geq 4$. We call roots those sequences of $pyramid(2)$
stacked onto each other. Note that $pyramid(n)$ with $n\geq 4$ can have more
than one root. For simplicity we assume that we have $pyramid(n)$ with $n=3K$
and $K\in\mathbb{N}$. Also we assume that all roots have the same number $R$
of $pyramid(2)$.

######  Example 4.1.

Consider the two extreme cases on $pyramid(6)$ whose roots are portrayed on
Figure 4. To the left the roots only go down, while on the figure of the right
the roots move to the left.

&

Figure 17:  Roots on $pyramid(6)$, here we display all activated vertices
except those above the primary vertices of $pyramid(6)$

Given $K$ and $R$, we define a $KR$–triangular sequence as a bisequence
$\\{s_{i}^{j}\\}$ where the coefficients are integers and they satisfy the
constrains:

$\scriptsize\begin{array}[]{ccccccccccccc}K+R&&K+R-1&&&&K+i&&&&K+2&&K+1\\\
\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
s_{R}^{R}&>&s_{R-1}^{R-1}&>&\cdots&>&s_{i}^{i}&>&\cdots&>&s_{2}^{2}&>&s_{1}^{1}\\\
\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
R&&s_{R}^{R-1}&>&\cdots&>&s_{i+1}^{i}&>&\cdots&>&s_{3}^{2}&>&s_{2}^{1}\\\
&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
&&R-1&&&&\vdots&&&&\vdots&&\vdots\\\
&&&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
&&&&\cdots&>&s_{R}^{i}&&\cdots&>&s_{j+1}^{2}&>&s_{j}^{1}\\\
&&&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
&&&&&&i&&&&\vdots&&\vdots\\\
&&&&&&&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
&&&&&&&&&&s_{R}^{2}&>&s_{R-1}^{1}\\\
&&&&&&&&&&\rotatebox[origin={c}]{90.0}{$\leq$}&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
&&&&&&&&&&2&&s_{R}^{1}\\\ &&&&&&&&&&&&\rotatebox[origin={c}]{90.0}{$\leq$}\\\
&&&&&&&&&&&&1\end{array}$ (5)

######  Remark 4.2.

The particular relation $s_{j}^{i}>s_{j-1}^{i-1}$ will prevent redundancy on
the roots.

######  Proposition 4.3.

Consider the chinampas with $n=3K$ roots each root with $R$ copies
$pyramid(2)$. The number of $KR$–triangular sequences $\\{s^{i}_{j}\\}$ counts
the number of possible roots on $pyramid(n)$ with the previous conditions.

###### Proof.

Given the $KR$–triangular sequence $\\{s_{j}^{i}\\}$ and consider a
rectangular board $B$ of $(K+R)$ columns and $R$ rows.

For the first step, we put a white mark on the cell of $B$ given by the
intersection of row 1 and column $s^{1}_{1}$. In step 2, we put a white mark
on the cell intersection of row 2 and column $s^{1}_{2}$ and another white
mark on the cell intersection of row 2 column $s^{2}_{2}$. The step $i$ ask us
to put marks on cells $(i,s_{j}^{i})$ with $j\leq i$. Now for each $i$, we
take the $i$ row, and we color with black all cells in the columns $1$ to
$n+i$ that are not white.

To recover the roots of $pyramid(n)$, we substitute each black colored cell by
3 consecutive cells: one white and two black. Black colored cells are the
activated vertices the root of $pyramid(n)$. The fact that each of the
sequences $\\{s^{i}_{j}\\}_{j}$ is decreasing translated into the movement to
the left of roots. The condition $s_{j}^{i}>s_{j-1}^{i-1}$ appears because the
roots can only move one unit to the left. The map that sent one black block
into a white block with two black blocks prevents redundancy. This assignment
can be verified to be an isomorphism. ∎

Figure 18: The corresponding Triangular sequences come from counting blocks.

######  Example 4.4.

We look at the white spaces as in Figure 18. They correspond to the roots of
Figure 4.

According to Proposition 4.3 the sequences corresponding to the left of Figure
18 are

$\begin{array}[]{cccc}&&&s_{1}^{1}\\\ &&s_{2}^{2}&s_{2}^{1}\\\
&s_{3}^{3}&s_{3}^{2}&s_{3}^{1}\\\
s_{4}^{4}&s_{4}^{3}&s_{4}^{2}&s_{4}^{1}\end{array}=\begin{array}[]{cccc}&&&3\\\
&&4&3\\\ &5&4&3\\\ 6&5&4&3\end{array}$

and for the right

$\begin{array}[]{cccc}&&&s_{1}^{1}\\\ &&s_{2}^{2}&s_{2}^{1}\\\
&s_{3}^{3}&s_{3}^{2}&s_{3}^{1}\\\
s_{4}^{4}&s_{4}^{3}&s_{4}^{2}&s_{4}^{1}\end{array}=\begin{array}[]{cccc}&&&1\\\
&&2&1\\\ &3&2&1\\\ 4&3&2&1.\end{array}$

###  4.1 Methods to compute triangular sequences

We used the equivalent description of a $KR$–triangular sequence with
$s_{R}^{1}\geq 1$ and $K+2R-1\geq s_{R}^{R}$. Take a KR–triangular sequence as
in (5), add one to those elements in the second row $\\{s^{i}_{i+1}\\}_{1\leq
i\leq R-1}$; add two to elements in the third row $\\{s^{i}_{i+2}\\}_{1\leq
i\leq R-2}$. Continue until we add $R-1$ to the last row $\\{s^{1}_{R}\\}$.
The resultant sequence is denoted by $T_{R,n}$. Each step preserves the
horizontal inequalities and transforms the vertical relations into strict
inequalities.

We use the software Mathematica [20] and the calculus of species (see [18], or
[6]) in our experiments with triangular sequences.

  * •

Fix $R$ and the line $L_{2R-1}$ with $2R-1$ points. We count all possible ways
to label points in the line preserving the order, and using numbers from $1$
to $n$. Call this number $p_{n}$. We can verify the identity $\sum
p_{n}x^{n}=\frac{x^{2R-1}}{(1-x)^{2R}}$.

  * •

We compute symbolic sums over all possible ways to assign values with numbers
from one to $n$ to the points in $T_{R,n}$. Call this $q_{n}$. We aim to find
$\sum q_{n}x^{n}$. This step is computationally demanding and can only be done
for small $R$.

  * •

Divide $q_{n}$ by $p_{n}$ and call this $c_{n}$. The fact that $p_{n}|q_{n}$
was proved for $R=3$ in [2].

  * •

We want to obtain the generating series of $\\{q_{n}\\}$, so we interpret
$c_{n}$ as the result of applying a differential operator to $\sum
p_{n}x^{n}=\frac{x^{2R-1}}{(1-x)^{2R}}$:

    * –

Expand the $c_{n}$ as a polynomial in $n$ and interpret any instance of
$n^{k}$ as the differential operator $(x\frac{d}{dx})^{k}.$

    * –

Apply the differential operator to $\frac{x^{2R-1}}{(1-x)^{2R}}$ to obtain the
generating series $\sum q_{n}x^{n}$.

####  4.1.1 Generating functions of triangular sequences

  * •

If $R=3$ then
$\frac{(1+x)x^{5}}{(1-x)^{7}}=x^{5}+8x^{6}+35x^{7}+112x^{8}+294x^{9}+672x^{10}+$
$+1386x^{11}+2640x^{12}+4719x^{13}+8008x^{14}+13013x^{15}+O(x^{16}),$

  * •

if $R=4$ then
$\frac{(1+5x+5x^{2}+x^{3})x^{7}}{(1-x)^{11}}=x^{7}+16x^{8}+126x^{9}+672x^{10}+$
$+2772x^{11}+9504x^{12}+28314x^{13}+75504x^{14}+184041x^{15}+O(x^{16}),$

  * •

if $R=5$ then
$\frac{(1+16x+70x^{2}+112x^{3}+70x^{4}+16x^{5}+x^{6})x^{9}}{(1-x)^{16}}=x^{9}+32x^{10}+$
$+462x^{11}+4224x^{12}+28314x^{13}+151008x^{14}+674817x^{15}+O(x^{16}),$

  * •

if $R=6$ then
$\frac{(1+42x+539x^{2}+2948x^{3}+7854x^{4}+10824x^{5}+7854x^{6}+2948x^{7}+539x^{8}+42x^{9}+x^{10})x^{11}}{(1-x)^{22}}=$
$+x^{11}+64x^{12}+1716x^{13}+27456x^{14}+306735x^{15}+O(x^{16}),$

  * •

if $R=7$ then
$\frac{(1+99x+3129x^{2}+44739x^{3}+336819x^{4}+1450761x^{5}+3753841x^{6}+5999851x^{7}}{(1-x)^{29}}+$
$+\frac{5999851x^{8}+3753841x^{9}+1450761x^{10}+336819x^{11}+44739x^{12}+3129x^{13}+99x^{14}+x^{15})x^{13}}{(1-x)^{29}}=$

$x^{13}+128x^{14}+6435x^{15}+O(x^{16}).$

Expanding those series, the coefficient of $x^{k+1}$ is the number of
$KR$–triangular sequences.

A pdf with our calculations can be seen at:
https://github.com/mendozacortesgroup/chinampas

##  5 Generalization

###  5.1 Network Models

Here we want to explain the algebraic structure of cascades via chinampas. As
a consequence we learn how to code this family of non linear signal flow
graphs. Rather than using matrices, it is more natural to use union of sets.
This section uses category theory [10], and follows closely the work of [3].

The category $S$ has objects $\mathbf{n}=\\{1,2,\cdots,n\\}$, and every
morphim $\mathbf{n}\to\mathbf{m}$ is a bijection. There is a product $+$ and a
braiding $B_{n,m}$ making $S$ a strict symmetric monoidal category (see for
instance [3, § 2]).

A one-colored network model is a lax symmetric monoidal functor $F\colon
S\rightarrow Monoids$ (for the definition see [3, § 2]). We shall build a one-
colored network model $F$ from a chinampa. For this goal we use the
caracterization of lax symmetric monoidal functor given in [3, Theorem 2.3].

For any natural $n$ define

$F(n)=\\{\text{finite set of primary vertices in a $tellis(n)$}\\},$

and

$F(0)=\emptyset.$

we denote by $e_{n}\in F(n)$ the $tellis(n)$ with empy set of primary vetices.

We define

  1. 1.

a family of overlaying functions $\cup:F(n)\times F(n)\rightarrow F(n)$ given
by union of primary vertices,

  2. 2.

an action of the group of permutations $S_{n}$ on $F(n)$ by permuting the
first coordinate of any vertex,

  3. 3.

a family of disjoint union functions $\sqcup:F(n)\times F(m)\rightarrow
F(n+m)$ given by maping the primary vertices $(i,t)\in F(n)$ into $(i,t)\in
F(m+n)$ and the primary vertices $(i,t)\in F(m)$ into $(i+n,t)\in F(n+m)$

The overlaying functions $\cup$ from point 1 induce a product so $F(n)$ is a
monoid.

######  Example 5.1.

To understand the action of the permutation group consider
$\\{(1,0),(2,0),(3,0),(4,2)\\}\in F(4)$, this is a chinampa. The permutation
$\sigma(1)=1$, $\sigma(2)=4$, $\sigma(3)=2$, $\sigma(4)=3$ results in a non
connected redundant activation diagram
$\sigma(\\{(1,0),(2,0),(3,0),(4,2)\\})=\\{(1,0),(4,0),(2,0),(3,2)\\}$ as in
Figure 19.

Figure 19: Left: A base diagram $d=\\{(1,0),(2,0),(3,0),(4,2)\\}\in F(4)$.
Right: $\sigma(d)\in F(4)$ where $\sigma(1)=1$, $\sigma(2)=4$, $\sigma(3)=2$,
$\sigma(4)=3$.

To understand the operation $\sqcup$ consider
$d=\\{(1,0),(2,0),(3,0),(2,2)\\}\in F(3)$ and $f=\\{(1,0),(2,0)\\}\in F(2)$,
then $d\sqcup f=\\{(1,0),(2,0),(3,0),(2,2),(4,0),$ $(5,0)\\}\in F(5)$ as in
Figure 20.

Figure 20: Given $d=\\{(1,0),(2,0),(3,0),(2,2)\\}\in F(3)$ and
$f=\\{(1,0),(2,0)\\}\in F(2)$ then $d\sqcup
f=\\{(1,0),(2,0),(3,0),(2,2),(4,0),(5,0)\\}\in F(5)$.

To understand the operation $\cup$ consider
$d=\\{(1,0),(2,0),(3,0),(2,2),(4,3)\\}\in F(4)$ and
$f=\\{(1,0),(2,0),(3,0),(4,2)\\}\in F(4)$, then $d\cup
f=\\{(1,0),(2,0),(3,0),$ $(2,2),(4,2),(4,3)\\}\in F(4)$ as in Figure 21.

Figure 21: Given $d=\\{(1,0),(2,0),(3,0),(2,2),(4,3)\\}\in F(4)$ and
$f=\\{(1,0),(2,0),(3,0),(4,2)\\}\in F(4)$, then $d\cup
f=\\{(1,0),(2,0),(3,0),(2,2),(4,2),(4,3)\\}\in F(4)$.

######  Proposition 5.2.

The family $F$ defines a functor $F\colon S\to Monoid$ so, it is a one-colored
network model.

###### Proof.

We show that $F$ together with the functions $\cup$, $\sqcup$ and $B_{n,m}$
satisfy [3, Theorem 2.3].

By definition, $e_{n}$ is the unit of $\cup$ and $e_{0}$ is the unit of
$\sqcup$. Both $\cup$ and $\sqcup$ are associative. The units satisfy
$e_{n}\sqcup e_{m}=e_{n+m}$. The action of $S_{n}$ on $F(n)$ is permuting the
labels of the vertices and this action is distributive with respect $\cup$.
More over, the unity $e_{n}$ is a fixed point under this action. The operation
$\cup$ is distributive with respect $\sqcup$.

If $g\in F(n)$, $h\in F(m)$, $\sigma\in S_{n}$ and $\tau\in S_{m}$, by
definition $(\sigma+\tau)(g\sqcup h)$, is $(\sigma+\tau)(r)=\sigma(r)$ if
$r\leq n$ and $(\sigma+\tau)(r)=n+\tau(r)$ otherwise. In other words, on the
copy of $F(n)\subset F(n+m)$ we have the action of $\sigma$ and on the copy of
$F(m)\subset F(n+m)$ we have the action of $\tau$, then $(\sigma+\tau)(g\sqcup
h)=\sigma g\sqcup\tau h$.

Finally, $B_{m,n}(h\sqcup g)$ is $g$ on the first $n$ and then $h$ on
$\\{n+1,\cdots,n+m\\}$, that is $B_{m,n}(h\sqcup g)=g\sqcup h$. ∎

The theory of operads [14] introduces the language to study composition of
operations. An operad $O$ consist of a set $O(n)$ of $n$-ary operations for
every $n$. For every partition
$n_{1},n_{2},\cdots,n_{k},n=\sum_{i=1}^{k}n_{i}$, we have composition maps

$O(n_{1},n_{2},\cdots,n_{k};n)=\\{O(n_{1})\times O(n_{2})\times\cdots\times
O(n_{k})\rightarrow O(n)\\}.$

The composition is associative, there is a unit element in $O(1)$. The
permutation group $S_{n}$ acts on $O(n)$, and composition commutes with the
action of the group. Those actions represent the permutation of inputs.

For a one-colored network model $F$, there is an associated a network operad
$op(\int F)$ [3, Definition 7.2]. For our purposes we will only use the
explicit description

$op\int F(n_{1},\cdots,n_{k};n)=S_{n}\times F(n),n=\sum n_{i},$

where $F$ is the one-colored network model of Proposition 5.2.

If we interpret $op(\int F)$ as operations, what sets accept these operations?
Given a set $X$ there is a canonical operad $End_{X}$ of endomorphisms. Where

$End_{X}(n)=\\{X^{n}\rightarrow X\\}$

and $End_{X}(n_{1},\cdots,n_{k};n)$ are the set composition of functions. A
$op(\int F)$-algebra is a set $X$ and a map between operads $op(\int
F)\rightarrow End_{X}$. That is, a family of maps

$op\left(\int F\right)(n)\times X^{n}\rightarrow X$

with compatibility conditions.

There is always a canonical $op\int F$–algebra $A_{F}$ which is defined by
$A_{F}(n)=F(n)$. Given $(\sigma,g)\in op\int F(n_{1},\cdots,n_{k};\sum
n_{i}),$ and $\\{h_{i}\in A_{F}(n_{i})\\}_{i=1,\cdots,k},$ the action of the
operad $op\int F$ is given by

$\alpha(\sigma,g)(h_{1},\cdots,h_{k})=\sigma(h_{1}\sqcup\cdots\sqcup
h_{k})\cup g\in A_{F}(\sum n_{i}).$

Unwrapping the definitions, we relabel the elements of
$h_{1}\sqcup\cdots\sqcup h_{k}$ to obtain primary vertices of $tellis(\sum
n_{i})$. We apply the permutation $\sigma$ to obtain
$\sigma(h_{1}\sqcup\cdots\sqcup h_{k})$ and we overlay the output with $g$.

Consider the function of sets

$proy:A_{F}(n)\to\\{\text{disjoint union of activation graphs on
$tellis(n)$}\\}$

defined on elements as follows. For $h\in A_{F}(n)$, a finite set of primary
vertices in $tellis(n)$, $proy(h)$ adds secondary vertices to $h$ from down to
top, and then removes redundancies to obtain a union of activation graphs.
This map is well defined as it can be described as coloring black all
activated vertex. We also define the function

$incl:\\{\text{disjoint union of activation graphs on $tellis(n)$}\\}\to
A_{F}(n)$

that only keeps (non redundant) primary vertices. The action of the
permitation group does not preserve the chinampa structure, since it can add
redundancies. That is why $incl$ and $proy$ are morphisms of sets.

An arbitrary element in $A_{F}(n)$ can be written as union of terms whose
image under $proy$ are connected activation graphs.

######  Lemma 5.3.

Define $e=incl\circ proy$, then $e$ is idempotent and $proy$ is a retraction,
that is $e^{2}=e,proy\circ incl=id$.

Note that for $a,b,c\in A_{F},$

$e(e(a\cup b)\cup c)=e(a\cup e(b\cup c))=e(a\cup b\cup c).$

However $e(a)\cup e(b)\not=e(a\cup b).$ Every element of $A_{F}$ can be
retracted into a disjoint union of chinampas or union of points. For every
chinampa $C$, the preimage $proy^{-1}(C)$ contains all equivalent ways to
select primary vertex ending with the same activation graph.

######  Remark 5.4.

At the level of networks, among all possible ways to obtain the same
polycrhony group $e$ selects the external stimuli in the signal-flow diagram
without redundancy.

We built a one-colored network model $F$ to describe the algebraic structure
of a cascade. An element of $F(n)$ can be written in terms of the monoidal
operation in several ways, as union of its subsets.

######  Remark 5.5.

We started this project trying to code polycrhony groups. By using the
language of operads we conclude that to simulate polychrony groups we need to
code the monoidal operation of union of sets.

In Subsection 3.1, we restricted the algebraic structure to vertical stacking
in order to count connected non redundant elements called chinampas. This is
possible because vertical stacking admits a unique factorization, see
Algorithm 1.

Assume now that we restrict the nodes that can react to external stimuly in a
network. Either by adding inhibitions or assuming the node is damaged at a
particular time. Select $m$ vertices, and $n$ primary vertices of $tellis(k)$.
Only the $m$ vertices can change color and become primary or secondary
vertices. This defines an elementary net system, a kind of Petri Net [16] in
which the set of transitions are the $m$ chosen vertices, each with two places
going in and two going out, see Figure 22.

States are the $n$ marks, and our transition functions are the $m$ vertices.
When more than two marks are on the same vertex $v$, two marks are distributed
via $v$’s outgoing edges.

$x$$II$$II$$IIx$$I$$II$$I$$IIx$$I$$I$$I$ Figure 22: The five marks $I$
represent the states, and our transition functions are the vertices, except
for the vertices marked with an $x$ which cannot fire. The vertical axis is
time.

##  6 Future Work

Consider a simulation of neural activity. Assume that a set of neurons form a
path. Section 3.1 describes the possible diagrams of activation using the
staking of pyramids. It is not necessarily to compute all possible
interactions between signals, as the basis of the pyramids determine all
vertices activated. From Proposition 5.2 and Remark 5.5, we can use the
language of category theory to simplify the code required. A simulation of
neural activity requires to extend our work to more general networks.

Up to this point every network satisfy the following hypothesis: every vertex
has at most one edge towards itself and at most one edge towards a different
vertex, every signal has intensity one and the threshold is two for all
vertices. We also require chinampas to be non redundant connected activation
diagram with profit grader than zero, and we restricted networks to the case
of paths.

In this section, we will describe broadly the effect of relaxing the main
hypothesis of this paper. For each new network we associate the correspond
covering graph and activation diagram following the same definition as in
Section 2.2.

###  6.1 Rooted Tree Networks

Consider that the network is a rooted tree with the direction going to the
root. On each segment between branching points or between a leaf and a branch,
we have a path, and so the corresponding cascades on the path can be study
with chinampas, see Figure 23.

Figure 23: Interaction at branching points. Below: we see the network, a
rooted tree. Above: we see copies of pyramid that can be replaced by other
chinampas. On the branching points signals from different branches interact.

On a path, every secondary vertex correspond to a node in the network that was
previously a primary vertex. This happens because in the network, the vertex
needed a self signal in order to fire. By allowing branching points we have a
new situation in which a vertex is activated after receiving several signals
from different incoming edges. This process creates regions of purely
secondary vertex. Those regions resemble neurons that do not interact with
external stimuli, only with other neurons.

###  6.2 Chinampas with infinite profit

In this section we describe chinampas on networks that are cycles. Having
feedback allows chinampas that do not stop as we see in algorithm 5. This
algorithm works even if:

  * •

the vertices has several outgoing edges,

  * •

the labels are different,

  * •

the intensities are different,

  * •

the thresholds are different.

Assume we have a subset of vertices $S\subset A$ where every vertex $n$
receive as many incoming signals as the threshold of $n$. For such $S$, one
way to obtain an infinite cascade is by activating every element of $S$ for a
long period of time. This is known as a synfire chain [1], an activation
diagram where all vertices are activated at the same time.

We introduce a more efficient algorithm than the synfire chain, and we will
prove that the algorithm returns a cascade. For example, we can activate all
vertices at the times $0$, $1$ as in Figure 24 (right) and obtain a finite
cascade. We can also activate all vertices at times $0$, $1$, $2$ to obtain an
infinite cascade. Instead the algorithm is used in Figure 24 (left) and
returns an infinite cascade with 7 primary vertex.

Figure 24: (Left) From the lemma it follows that we only need to activate
seven vertices to obtain an infinite cascade, as all vertices are activated
for all times bigger than 2. (Right) Finite cascade obtained by activating
every vertices at time 0 and time 1 (Synfire). To obtain an infinite cascade
activating every vertices at the same time we will need to activate all
vertices at time 0,1 and 2.

Given a pair of connected vertices $m,n$ we denote by $e_{m,n}$ the edge from
$m$ to $n$, and we denote by $time(e_{m,n})$ the time it takes the signal to
go from vertex $m$ to vertex $n$.

Data: vertices in $S$, labeled edges between vertices in $S$ satisfying
conditions of Lemma 6.1

Result: Infinity cascade

$temp\\_list=[\leavevmode\nobreak\ ]$;

for every $n\in S$ do

/* consider the maximum time among the edges leaving $n$ */

$m_{n}=max\\{time(e_{n,n_{i}})$ for $e_{n,n_{i}}\in$Edges(A)$,n_{i}\in S\\}$;

$temp\\_list.append(m_{n})$;

end for

Set $M=max(temp\\_list)$;

/* by construction $M-time(e_{n^{\prime},n^{\prime\prime}})\geq 0$ for all
${n^{\prime},n^{\prime\prime}}\in S$. */

Activate each element $n\in S$ from time $M-m_{n}$ to time $M$;

return M

Algorithm 5 Efficient construction of infinity cascades

######  Lemma 6.1.

Sufficient conditions to existence of infinite cascades on the activation
diagram $A$. Suppose that $S\subset$ vertices($A$) satisfies the following
condition, for every $n\in S$ :

  1. 1.

there are $n_{1},n_{2},\cdots,n_{k_{s}}\in S$ so that $e_{n_{i},n}\in$
Edges($A$),

  2. 2.

the sum of the intensity of the signals sent by $\\{n_{i}\\}_{1\leq i\leq
k_{s}}$ is bigger or equal than the threshold of $n$.

Then $S$ admits at least one infinite cascade.

###### Proof.

Let $M$ be the output of Algorithm 5. We show that by activating all vertices
in $S$ at the correct time period, periodicity assure us the vertices will
keep on activating themselves.

We proceed by induction to show that all vertices are activated on the time
$M+i$ for all $i\in N$. Note that at time $M+0$ every vertices is activated,
and each vertex receives enough signals to reach the threshold by hypothesis.

Lets assume that from time $M$ to time $M+i,$ every edge in $S$ is activated.
We want to prove that from time $M$ to $M+i+1$ every edge is activated.

Consider $n_{0}\in S$ and we will study all incoming edges to $n_{0}$. Let
$n_{k}\in S$ be connected to $n_{0}$. If $time(e_{n_{k},n_{0}})\leq i+1$ then
$n_{k}$ was activated by other vertices during the period $[M,M+i]$ by
hypothesis. If $time(e_{n_{k},n_{0}})>i+1$ then we activated $n_{k}$ at time

$M+i+1-time(e_{n_{k},n_{0}})=M-(time(e_{n_{k},n_{0}})-(i+1))>M-time(e_{n_{k},n_{0}})>M-m_{n_{k}}$

because by hypothesis we activated $n_{k}$ from time $M-m_{n_{k}}$ to time
$M$. We conclude that $n_{0}$ is activated as all incoming edges were
activated at the correct time. Since $n_{0}$ is arbitrary, every element of
$S$ is activated at time $M+i+1$. This concludes the induction step.

After a while, the subsequent activated vertices will be more than the initial
activated vertices and we will have a cascade. ∎

Not every network admits infinite chinampas, for example $paths(n)$.

###  6.3 Signals with integer intensity

We first describe the situation in which intensity of signals can be $1$ or
$-1$. An inhibition is a vertex that sends signals with negative intensity.
Accepting vertices that send inhibitory signals, means that chinampas with
infinite profit can be stop and that our pyramids can have holes (see Figure
25).

Figure 25: Below: a network. Top: a chinampa with infinite profit. Middle: a
chinampa with inhibited vertices. The infinite chinampa is now finite, the
chinampas over paths interact in new ways.

All our algorithms need to be adapted in order to work with inhibitions. To be
precise, we need to modify the line in which we determine if a vertex receives
enough signals.

Infinite chinampas can be stop by the inhibitions at branching points. Knowing
the initial inhibitions beforehand can help adapt Algorithm 5 to find infinite
cascades, or to control the total profit.

If the signals have integer intensities, among the increase on complexity of
the diagrams, a remarkable effect can occur: a vertex can reactivate itself
until an inhibition stops it.

###  6.4 Multiple outgoing edges

Several outgoing edges with label bigger than one allow us to have chinampas
on different scales. If the self edges have different times then there is time
interaction of those different cascades as in Figure 26.

Figure 26: By allowing the edges to have label different to one we can have
different cascades interacting on the same vertices as in the first two
vertices of the figure, if the self edges of the last 3 vertices have label 4,
then we will have a cascade of infinite profit.

Of special importance are $n$-clique, the graph with $n$ vertices all of them
connected to each other, in which all the edge’s labels are the same. Assume
that all vertex have a common threshold. To initiate an infinite cascade we
apply external stimuli to any random set of vertex with more elements than the
threshold. See Figure 27.

Figure 27: Assuming the threshold is two and intensity one. Four signals
create an infinite cascade.

###  6.5 Triangular Sequences

The theory of species [6] is not general enough to find the remaining
generating series of triangular sequences. The reason is that our enumeration
problems are topological in nature, they depend not only on the number of
points but on the shape of the figure. Generating functions coming from
Species depend only on the number of terms. The next task would be to count
chinampas of arbitrary profit.

Consider the number of all labeling functions $q_{n}=|\\{f:n\mapsto
T_{R,n}\\}|$ that are order preserving. In [2] it is shown that

$\frac{q_{n}}{{\binom{2R-1}{n}}}\in\mathbb{N}$

for $R=3$. For higher $R$ this is still an open question.

###  6.6 Sparse recurrent neural networks

The difference between Synfire chains and chinampas is that we do not
necessarily activate the nodes at the same time. Fully connected recurrent
neural networks can be seen as examples of Synfire chains. Perhaps the study
of chinampas can be used to understand sparse objects in Machine Learning such
as the lottery-ticket-winners [8], or a network that receives different data
at different states. We can consider a sparse neural network that is required
to have certain predictions at different layers. This would require to modify
the loss function to measure how far are those intermediate predictions from
the intended value in a way compatible with back propagation.

## Acknowledgement

We thank Jade Master for a clarification on the relationship between petri
nets and chinampas.

  * •

Cellular automata draws were made using http://madebyevan.com/fsm/.

  * •

Figure 9 was made with https://playgameoflife.com/.

The first author has received funding from the National Research Foundation of
Korea (NRF) grant funded by the Korea government (MSIT) (No.
2020R1C1C1A0100826).

## Glossary

## References

  * [1] Moshe Abeles  “Local Cortical Circuits”  Springer-Verlag Berlin Heidelberg, 1982  DOI: https://doi.org/10.1007/978-3-642-81708-3
  * [2] Jose Antonio Arciniega-Nevarez and Eric Dolores-Cuenca  “Power series represented by Posets”, 2021  arXiv:2105.06633 [math.CO]
  * [3] John C. Baez, John Foley, Joe Moeller and Blake S. Pollard  “Network Models”  In Theory and Applications of Categories, 2020, pp. 700–744
  * [4] A.L. Barabási  “Network Science”  Cambridge University Press, 2016  DOI: https://doi.org/10.1098/rsta.2012.0375
  * [5] Thomas A. Baran  “Inversion of nonlinear and time-varying systems”  In Digital Signal Processing and Signal Processing Education Meeting (DSP/SPE) IEEE, 2011, pp. 283–288  DOI: https://doi.org/10.1109/DSP-SPE.2011.5739226
  * [6] François Bergeron, Gilbert Labelle and Pierre Leroux  “Combinatorial Species and Tree-like Structures”, Encyclopedia of Mathematics and its Applications  Cambridge University Press, 1997  DOI: https://doi.org/10.1017/CBO9781107325913
  * [7] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein  “Introduction to Algorithms, Third Edition”  The MIT Press, 2009
  * [8] Jonathan Frankle and Michael Carbin  “The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks”  In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019 OpenReview.net, 2019  URL: https://openreview.net/forum?id=rJl-b3RcF7
  * [9] Martin Gardner  “Mathematical Games - The Fantastic Combinations of John Conway’s New Solitaire Game ’Life”’  In Scientific American, 1970, pp. 070–120  DOI: https://doi.org/10.1038/scientificamerican1070-120
  * [10] S.. Gelfand and Yu.. Manin  “Methods of homological algebra / S.I. Gelfand and Yu. I. Manin”  Springer, 2002  DOI: https://doi.org/10.1007/978-3-662-12492-5
  * [11] J. Guilherme, N.. Horta and J.. Franca  “Symbolic synthesis of non-linear data converters”, 1999
  * [12] A C Guyton, T G Coleman and H J Granger  “Circulation: Overall Regulation” PMID: 4334846  In Annual Review of Physiology 34.1, 1972, pp. 13–44  DOI: https://doi.org/10.1146/annurev.ph.34.030172.000305
  * [13] Eugene M Izhikevich  “Polychronization: computation with spikes”  In Neural computation 18.2 MIT Press, 2006, pp. 245–282  DOI: https://doi.org/10.1162/089976606775093882
  * [14] James D. Martin Markl  “Operads in algebra, topology and physics”  Amer. Math. Soc., 2002, pp. 349
  * [15] Samuel J. Mason  “Feedback Theory-Some Properties of Signal Flow Graphs”  In Proceedings of the IRE 41.9, 1953, pp. 1144–1156  DOI: https://doi.org/10.1109/JRPROC.1953.274449
  * [16] Jade Master  “Petri nets based on Lawvere theories”  In Mathematical Structures in Computer Science 30.7 Cambridge University Press, 2020, pp. 833–864  DOI: 10.1017/S0960129520000262
  * [17] N… Sloane and Aaron D. Wyner  “The Theory and Design of Linear Differential Equation Machines Report to National Defense Research Council, January, 1942.”  In Claude E. Shannon: Collected Papers, 1993, pp. 514–559  DOI: https://doi.org/10.1109/9780470544242
  * [18] Herbert S. Wilf  “Generatingfunctionology”  Wellesley, MA: A K Peters Ltd., 2006, pp. x+245  DOI: https://doi.org/10.1016/C2009-0-02369-1
  * [19] Stephen Wolfram  “A New Kind of Science”  Wolfram Media, 2002  URL: https://www.wolframscience.com
  * [20] Inc. Wolfram Research  “Mathematica, Version 12.1” Champaign, IL, 2020  URL: https://www.wolfram.com/mathematica