-
Notifications
You must be signed in to change notification settings - Fork 1
/
2d_adinkras_scraps.tex
508 lines (381 loc) · 29.7 KB
/
2d_adinkras_scraps.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
\com{Do we really need to define this?}
\begin{definition}[Graph homomorphisms]
\label{defn:homomorphism}
A \emph{graph homomorphism} from a graph $(V_1,E_1)$ to a graph $(V_2,E_2)$ is a map $\phi:V_1\to V_2$ so that if $(v,w)\in E_1$ is an edge, then $(\phi(v),\phi(w))\in E_2$ is an edge. If there is a coloring $c_1:E_1\to [n]$ and a coloring $c_2:E_2\to [n]$, we say that $\phi$ \emph{preserves colors} if $c_1(v,w)=c_2(\phi(v),\phi(w))$. We likewise define what it means for $\phi$ to \emph{preserve dashings} or \emph{preserve gradings}. If $\phi$ is bijective, we say that it is a \emph{graph isomorphism}.
\end{definition}
\begin{proof}
The statement that $q_i$ is a graph homomorphism means that if $(v,w)$ is an edge in $A$, then so is $(q_i(v),q_i(w))$. This follows from items 2 and 3 in the definition of an Adinkra above, using $j=c(v,w)$.
The fact that $q_i(q_i(v))=v$ for all $v\in V$ follows from item 2 in the definition. This means that $q_i$ is an involution and in particular is an isomorphism.
The equation (\ref{eq:commute}) follows from item 3 of the definition when $i\not=j$ and is trivial when $i=j$.
\end{proof}
\begin{proof}
This follows directly from interpreting the group action as following edges with various colors. A path in the graph corresponds to a sequence of edges, which, depending on the color, gives an action of $q_i$. The composite of these $q_i$'s, reordered using the commutativity of the $q_i$'s, is an action of an element of $\ZZ_2^n$.
\end{proof}
(\ref{eq:commute})
\begin{prop}
\label{prop:actioniso}
The above defines an action by graph isomorphisms that preserve colors.
\end{prop}
\begin{proof}
Acting on $v$ by $\vec{y}$ and then $\vec{x}$ gives
\begin{eqnarray*}
\vec{x}\vec{y}(v)
&=&q_1^{x_1}\circ\cdots\circ q_n^{x_n}\circ
q_1^{y_1}\circ\cdots\circ q_n^{y_n}(v)\\
&=&q_1^{x_1+y_1}\circ\cdots\circ q_n^{x_n+y_n}(v)
\end{eqnarray*}
by the commutativity shown in (\ref{eq:commute}), and where the exponents are taken modulo $2$, because each $q_i$ is an involution. Therefore this is equal to
\[(\vec{x}+\vec{y})(v).\]
Proposition~\ref{prop:qmap} says that each $q_i$ is an isomorphism which preserves colors, and this action is a composition of such maps.
\end{proof}
\begin{definition}
A path is a finite sequence of edges of the form $((v_1,v_2),(v_2,v_3),\ldots,(v_{k-1},v_k))$. The {\em color sequence} of the path is the sequence $(c(v_1,v_2),c(v_2,v_3),\ldots,c(v_{k-1},v_k))$.
\end{definition}
So if there is a path from $v$ to $w$ with color sequence $(i_1, \ldots, i_k)$, we have $w=q_{i_k}\circ \cdots\circ q_{i_1}(v)$.
\begin{prop}
\label{prop:colorpath}
Let $A$ be an Adinkra and let $v$ be a vertex of $A$. Let $\sigma$ be a color sequence. There exists a unique path in $A$ that starts at $v$ and has color sequence $\sigma$.
\end{prop}
\begin{proof}
This can be proved by induction on the length of $\sigma$, and using the fact that given a vertex $v_i$ of $A$, and a color $c_i$, there exists a unique vertex $v_{i+1}$ so that $(v_i,v_{i+1})$ is an edge of $A$ with color $c_i$.
\end{proof}
Now, define a map $s$ that takes a color sequence and returns an element of $\ZZ_2^n=\{0,1\}^n$ where the $i$-th coordinate is the number of times (modulo $2$) that color $i$ appears in the sequence. For example, $s(3,1,2,1) = 0110$. Note that $s(\sigma)$ does not depend on the ordering of the color sequence $\sigma$. This relates to paths in Adinkras because of the following:
\begin{prop}
\label{prop:colorendpath}
Let $A$ be an Adinkra. Let $v$ be a vertex of $A$ and let $p$ be a path that begins at $v$. Let $\sigma$ be the color sequence obtained from $p$. Then the path $p$ ends at the vertex $s(\sigma)v$.
\end{prop}
\begin{proof}
If the color sequence is $\sigma=(i_1,\ldots,i_k)$, then the path $p$ ends at
$q_{i_k}\circ \cdots \circ q_{i_1}(v)$. By the commutativity of the $q_i$, we can order them in non-decreasing order of $i_j$. If any of the $q_i$ appear more than once, we use the fact that $q_i^2$ is the identity to reduce the number of $q_i$ modulo $2$. The result is $s(\sigma)v$.
\end{proof}
\begin{cor}
\label{prop:pathands}
Let $A$ be an Adinkra. Let $v$ be a vertex of $A$ and let $p$ and $p'$ be paths that begin at $v$. Let $\sigma$ and $\sigma'$ be the color sequences obtained from $p$ and $p'$, respectively. If $s(\sigma)=s(\sigma')$, then $p$ and $p'$ both end at the same point.
\end{cor}
Let $v$, $w$ be vertices of $A$. If $A$ is connected, then there is a path in $A$ connecting $v$ to $w$. Let $\sigma$ be the color sequence obtained from this path. Then by Proposition~\ref{prop:colorendpath}, $s(\sigma)v=w$.
Conversely, suppose the action is transitive. Let $v$ and $w$ be vertices of $A$. Then there exists a $\vec{x}\in\ZZ_2^n$ so that $w=\vec{x}v$. Write $\vec{x}=(x_1,\ldots,x_n)$ and construct a color sequence $\sigma$ by taking the $i$ for which $x_i=1$. By Proposition~\ref{prop:colorpath}, there is a path starting at $v$ that has $\sigma$ as its color sequence. By Proposition~\ref{prop:colorendpath}, this path ends at $s(\sigma)v=\vec{x}v=w$.
\begin{definition}
Given a connected Adinkra $A$, the \emph{code} for $A$, called $C(A)$, is defined to be $C(A,v)$, where $v$ is a vertex of $A$.
\end{definition}
\begin{prop}
\label{prop:paths}
Let $A$ be an Adinkra. Let $v$ be a vertex of $A$ and let $p$ and $p'$ be paths that begin at $v$. Let $\sigma$ and $\sigma'$ be the color sequences obtained from $p$ and $p'$, respectively. The paths $p$ and $p'$ end at the same vertex if and only if
\[s(\sigma)-s(\sigma')\in C(A).\]
\end{prop}
\begin{proof}
Suppose $p$ and $p'$ end at the same vertex. Then by Proposition~\ref{prop:colorendpath},
\[s(\sigma)v=s(\sigma')v.\]
Then\footnote{Note that in this sequence of equations, $\ZZ_2^n$ is written additively but the group action is written multiplicatively.}
\[v=s(\sigma')^{-1}(s(\sigma)v)=(s(\sigma)-s(\sigma'))v.\]
Thus, $s(\sigma)-s(\sigma')\in C(A)$.
Conversely, suppose $s(\sigma)-s(\sigma')\in C(A)$. Then by reversing the above argument,
\[s(\sigma)v=s(\sigma')v\]
and thus, by Proposition~\ref{prop:colorendpath}, $p$ and $p'$ end at the same vertex.
\end{proof}
\begin{prop}
\label{prop:reorderpath}
If $v_1$ and $v_2$ are vertices of a $2$-d Adinkra, and $p$ is a path from $v_1$ to $v_2$, then there exists a path $p_L$ consisting only of left-moving edges from $v_1$ to a vertex $u$, and a path $p_R$ consisting only of right-moving edges from $u$ to $v_2$.
Likewise there exists a path $q_R$ consisting only of right-moving edges from $v_1$ to a vertex $w$, and a path $q_L$ consisting only of left-moving edges from $w$ to $v_2$.
\end{prop}
\begin{proof}
Take the color sequence $\sigma$ of the path $p$. Then $s(\sigma)v_1=v_2$. Let $\sigma_L$ be the subsequence consisting only of the left-moving colors, and let $\sigma_R$ be the subsequence consisting only of the right-moving colors. Using Proposition~\ref{prop:colorpath}, we obtain the path $p_L$. Let $x$ be the endpoint of this path. We again use Proposition~\ref{prop:colorpath} with $\sigma_R$ starting from $x$, and obtain the path $p_R$. By Proposition~\ref{prop:colorendpath}, the end of this path is $s(\sigma_R)s(\sigma_L)v_1=s(\sigma_R\sigma_L)v_1=s(\sigma)v_1=v_2$.
The remaining result follows by symmetry.
\end{proof}
\begin{prop}
\label{prop:rectangle-completion}
Let $A$ be a connected Adinkra. Suppose $(x_1,y_1)$ and $(x_2,y_2)$ are in the support of $A$. Then $(x_1,y_2)$ and $(x_2,y_1)$ are also in the support of $A$.
\end{prop}
\begin{proof}
The statement that $(x_1,y_1)$ and $(x_2,y_2)$ is in the support of $A$ means that there exist vertices $v_1$ and $v_2$ of $A$ with $(h_L(v_1),h_R(v_1))=(x_1,y_1)$ and $(h_L(v_2),h_R(v_2))=(x_2,y_2)$, respectively. Since $A$ is connected, there exists a path from $v_1$ to $v_2$.
By Proposition~\ref{prop:reorderpath}, there is a left-moving path from $v_1$ to a vertex $u$ and a right-moving path from $u$ to $v_2$. Then $h_R(u)=h_R(v_1)=y_1$ and $h_L(u)=h_L(v_2)=x_2$. Therefore $(x_2,y_1)$ is in the support of $A$.
In the same way, Proposition~\ref{prop:reorderpath} provides a vertex $w$ with bigrading $(x_1,y_2)$.
\end{proof}
\begin{proof}
Let $X$ and $Y$ be two connected components of $A_L$. Pick vertices $x \in X$ and $y \in Y$. Since $A$ is connected, there is a path from $x$ to $y$ in $A$. Using Proposition~\ref{prop:reorderpath}, reorder the path so that the right-moving edges occur before the left-moving edges. Since the left-moving edges stay in $Y$, the right-moving edges alone take $x$ to a vertex $y' \in Y$. The sequence of right-moving edges provides a color sequence $i_1,\ldots,i_k$, and thus, a sequence of compositions $q_{i_k}\circ\cdots\circ q_{i_1}$. Now $q_{i_k}\circ\cdots\circ q_{i_1}(x)=y'$. By repeated application of Lemma~\ref{lem:qiconnected}, we have that $q_{i_k}\circ\cdots\circ q_{i_1}(X)$ is a connected component of $A_L$ that contains $y'$, which is $Y$. By repeated application of Lemma~\ref{lem:qiso}, we have an isomorphism of graphs that preserves colors and the grading $h_L$.
\end{proof}
\begin{construction}
\label{const:product}
Let $p$ and $q$ be non-negative integers. Let $A_1=(V_1, E_1, c_1, \mu_1,h_1)$ be a $1$-d Adinkra with $p$ colors and let $A_2=(V_2, E_2, c_2, \mu_2,h_2)$ be a $1$-d Adinkra $q$ colors. We define the \emph{product} of these Adinkras $A_1\times A_2$ as the following 2-Adinkra with $(p,q)$ colors:
\[A_1\times A_2=(V,E,c,\mu,h_L,h_R)\]
where
\begin{eqnarray*}
V&=&V_1\times V_2\\
E&=&E_1\cup E_2\mbox{ where}\\
E_1&=&\{((v_1,w),(v_2,w))\,|\,(v_1, v_2)\in E_1,\mbox{ and } w\in V_2\}\\
E_2&=&\{((v,w_1),(v,w_2))\,|\,v\in V, \mbox{ and }(w_1,w_2)\in E_2\}\\
c((v_1,w),(v_2,w))&=&c_1(v_1,v_2)\mbox{ for all $((v_1,w),(v_2,w))\in E_1$}\\
c((v,w_1),(v,w_2))&=&p+c_2(w_1,w_2)\mbox{ for all $(v,w_1),(v,w_2)\in E_2$}\\
h_L(v,w)&=&h_1(v)\\
h_R(v,w)&=&h_2(w)\\
\mu((v_1,w),(v_2,w))&=&\mu_1(v_1,v_2)\\
\mu((v,w_1),(v,w_2))&=&\mu_2(w_1,w_2)+h_1(v)\pmod{2}
\end{eqnarray*}
See Figure~\ref{fig:product} for an example.
\end{construction}
pick a path from $\overline{0}$ to $v$. Use Proposition~\ref{prop:reorderpath} to obtain a left-moving path from $\overline{0}$ to a vertex $w$, and a right-moving path from $w$ to $v$. Then $w\in A_L^0$ and define $h_L(v)=h_L(w)$.
Likewise define $h_R$ on $A$.
---------------------------
Section \ref{sec:structural} hints that the information contained in a $2$-d Adinkra may be captured by just looking at two ``slices'' of the Adinkra. It is natural to guess that there is some product structure lying underneath, especially given the rectangular shape of the support proven in Corollary~\ref{cor:rectangle}.
---------------------------
\section{Structural Theorems}
\label{sec:structural}
\com{To be honest we can probably kill this whole section and get it as corollaries of the quotienting result... no piece of this seems to be used anywhere except 3.4, which is used once and can thus be used as a lemma.}
In this section, we show that the coherence conditions of $2$-d adinkras force a lot of structure onto them. The main idea is that we can think of the vertices of $2$-d adinkras as arranged in a rectangle, with the stucture of the entire adinkra basically determined by a horizontal and a vertical ``slice'' of the picture.
Let the \emph{support} of a $2$-d adinkra (and/or its bigrading function $(h_L,h_R)$) be defined as the range of $(h_L,h_R)$, its bigrading function. Now, we show that the support of a connected $2$-d adinkra must form a rectangle in $\ZZ^2$.
\begin{definition}
Let $p$ and $q$ be non-negative integers and let $n=p+q$. Define $\pi_L:\ZZ_2^n\to\ZZ_2^p$ to be projection onto the first $p$ bits and $\pi_R:\ZZ_2^n\to\ZZ_2^q$ to be projection onto the last $q$ bits.
\end{definition}
\begin{prop}
\label{prop:rectangle-completion}
Let $A$ be a connected Adinkra. Suppose $(x_1,y_1)$ and $(x_2,y_2)$ are in the support of $A$. Then $(x_1,y_2)$ and $(x_2,y_1)$ are also in the support of $A$.
\end{prop}
\begin{proof}
Suppose $v_1$ is a vertex with bigrading $(x_1,y_1)$ and $v_2$ is a vertex with bigrading $(x_2,y_2)$. Since $A$ is connected, there is an $\vec{x}\in\ZZ_2^n$ so that $\vec{x}v_1=v_2$. Write $\vec{x}=\vec{x}_L+\vec{x}_R$, where $\vec{x}_L$ is zero in the last $q$ bits and $\vec{x}_R$ is zero in the first $p$ bits. Then $\vec{x}_R(\vec{x}_Lv_1)=v_2$, and acting on both sides with $\vec{x}_R$, we get $\vec{x}_Lv_1=\vec{x}_Rv_2$. This is a vertex that shares the $h_R$ of $v_1$ and $h_L$ of $v_2$, so that it has bigrading $(x_2,y_1)$. Likewise, $\vec{x}_L v_2=\vec{x}_R v_1$ has bigrading $(x_1,y_2)$.
\end{proof}
\begin{cor}
\label{cor:rectangle}
The support of a connected $2$-d Adinkra is a rectangle. That is, there exist integers $x_0$, $x_1$, $y_0$, and $y_1$ so that the support is
\[\{(x,y)\in\ZZ^2\,|\,x_0\le x\le x_1\mbox{ and }y_0\le y\le y_1\}\]
\end{cor}
\begin{proof}
Let $x_0$ and $y_0$ be the minima of the $x$ and $y$ coordinates, respectively, of the support of the Adinkra. By Proposition~\ref{prop:rectangle-completion}, $(x_0,y_0)$ is in the support as well.
Likewise, if $x_1$ and $y_1$ are the maxima of the $x$ and $y$ coordinates, respectively, of the support of the Adinkra, then $(x_1,y_1)$ is in the support. By Proposition~\ref{prop:rectangle-completion}, $(x_1,y_0)$ and $(x_0,y_1)$ are also in the support.
Since the Adinkra is connected, there must be paths from vertices with bigrading $(x_0,y_0)$ to vertices with bigrading $(x_1,y_1)$. Since $h_L$ and $h_R$ can change by at most 1 along these paths, we see that for all $x_0\le x\le x_1$, there must exist $y_x$ so that $(x,y_x)$ is in the support. Likewise for all $y_0\le y\le y_1$, there must exist $x_y$ so that $(x_y,y)$ is in the support. By application of Proposition~\ref{prop:rectangle-completion} again, we get that $(x,y)$ is in the support for all $x_0\le x\le x_1$ and $y_0\le y\le y_1$.
\end{proof}
\begin{prop}
\label{prop:heightcode}
Let $v$ be a vertex in the $2$-d Adinkra $A$, and let $\vec{x}\in C(A)$. Write $\vec{x}=\vec{x}_L+\vec{x}_R$ where $\vec{x}_L$ is zero in the last $q$ bits and $\vec{x}_R$ is zero in the first $p$ bits. Then $\vec{x}_L v=\vec{x}_R v$ and this has the same bigrading as $v$.
\end{prop}
This has a very similar proof to that of Proposition~\ref{prop:rectangle-completion}.
\begin{proof}
Since $\vec{x}\in C(A)$, we know that $\vec{x}v=v$. Write this as $\vec{x}_R(\vec{x}_L v)=v$ and act on both sides with $\vec{x}_R$ to get $\vec{x}_L v = \vec{x}_R v$. Since $\vec{x}_L v$ has the same $h_R$ as $v$ and since $\vec{x}_R v$ has the same $h_L$ as $v$, we have that $\vec{x}_L v$ has the same bigrading as $v$.
\end{proof}
\subsection{Left and Right parts of a $2$-d Adinkra}
\begin{definition}
Let $A$ be a $2$-d Adinkra with $(p,q)$ colors. Let $A_L$ be the subgraph of $A$ consisting of the left-moving edges of $A$. Together with the coloring, the dashing, and the grading $h_L$, this is a $1$-d Adinkra with $p$ colors.
Let $A_R$ be the subgraph of $A$ consisting of right-moving edges of $A$. Define the coloring $c'(e)=c(e)-p$ (so that the colors range from $1$ to $q$ instead of $p+1$ to $p+q$). Using this coloring, the dashing, and the grading $h_R$, this is a $1$-d Adinkra with $q$ colors.
\end{definition}
The fact that these are $1$-d Adinkras is straightforward. We now consider their connected components.
\begin{lem}
\label{lem:qiso}
Let $A$ be a $2$-d Adinkra. If $X$ is a connected component of $A_L$ and $i$ is a right-moving color, then there is a graph isomorphism between $X$ and $q_i(X)$ that preserves colors and $h_L$. The analogous statement for $A_R$ also holds.
\end{lem}
\begin{proof}
Propostion~\ref{prop:qmap} states that $q_i$ is a graph isomorphism from the underlying graph of $A$ to itself that preserves colors. If we restrict $q_i$ to a connected component $X$ of $A_L$, the restricted map is an isomorphism from $X$ to $q_i(X)$ that preserves colors.
Since $i$ is a right-moving color, then for all vertices $v\in X$, $h_L(v)=h_L(q_i(v))$.
\end{proof}
\begin{lem}
\label{lem:qiconnected}
Let $A$ be a $2$-d Adinkra. If $X$ is a connected component of $A_L$ and $i$ is a right-moving color, then $q_i(X)$ is the vertex set of a connected component of $A_L$. The analogous statement for $A_R$ also holds.
\end{lem}
\begin{proof}
Because the property of connectedness is preserved under graph isomorphism, we know that $q_i(X)$ is connected. If we let $X'$ be the connected component of $A_L$ that contains $q_i(X)$, then the same argument proves that $q_i(X')$ is connected as well. Since $X$ was assumed to be a connected component of $A_L$, we have that $q_i(X')\subseteq X$. But since $q_i^2$ is the identity, $X=q_i^2(X)\subseteq q_i(X')\subseteq X$. This means $q_i(X')=X$. By the fact that $q_i^2$ is the identity, we also have $q_i(X)=X'$.
\end{proof}
\begin{prop}
\label{prop:kevin}
Let $A$ be a connected $2$-d Adinkra. All connected components of $A_L$ (and respectively $A_R$) are isomorphic as graded posets.
\end{prop}
\begin{proof}
Let $X$ and $Y$ be two connected components of $A_L$. Since $A$ is connected, there is a $\vec{x}\in \ZZ_2^n$ that send a vertex in $X$ to a vertex in $Y$. Write $\vec{x}=\vec{x}_L+\vec{x}_R$ where $\vec{x}_L$ has only $1$s for left-moving colors, and $\vec{x}_R$ has only $1$s for right-moving colors. Since $X$ is a connected component of $A_L$, $\vec{x}_L$ sends $X$ to itself, and so $\vec{x}_R$ sends $X$ to $Y$.
Then $\vec{x}_R$ acts on $A$ via graph isomorphisms that preserve color, and preserves $h_L$. Since $X$ is connected, $\vec{x}_R(X)$ is connected. It is therefore a subset of $Y$. Likewise, $\vec{x}_R(Y)$ is a connected subset of $X$. Since $\vec{x}_R$ is an involution, $\vec{x}_R(X)=Y$ and acting by $\vec{x}_R$ produces an isomorphism.
\end{proof}
With all this redundancy, what is the minimal amount of information required for us to understand a $2$-d Adinkra? Proposition~\ref{prop:kevin} suggests we just need a single connected component for each direction to give us all the data; this turns out to basically be true, as we see in the upcoming sections.
--------------------
\subsection{Dashings}
The main thing we need about dashings is:
\begin{thm}
\label{thm:1d-dashings}
Let $A$ be a $1$-d Adinkra with a $k$-dimensional code $C(A)$ of length $n$. Then there are exactly $2^{2^{n-k}+k-1}$ admissable dashings.
\end{thm}
\begin{proof}
See \cite{zhang:adinkras} for a proof of the above enumeration. See \cite{d2l:topology} for a constructive proof of the existence of at least one dashing.
\end{proof}
---------------------
\subsection{Original language}
\com{This is copied and pasted from Tristan's article. Probably don't include this.}
The statement of Theorem~\ref{thm:quotient} is a bit different from the statement of the conjecture in \cite{hubsch:weaving}:
\begin{conjecture}[Conjecture 2.1 (completeness)] The application of Constructions 2.1, 2.2 and 2.3 together with the projections of the kind (28)--detailed in Section 3--generates all $(p,q)$-Adinkras and so also all adinkraic off-shell worldsheet $(p, q)$-supermultiplets--for all $p, q \ge 0$.
\end{conjecture}
\begin{construction}[Construction 2.1 (off-shell)] Let $R_+$ and $R_-$ denote off-shell representations of two copies of the
(centrally unextended) worldline supersymmetry algebras, $Sp_+^{1|p}$ and $Sp_-^{1|q}$ respectively, and let $Z$ be a symmetry of $R_+ \otimes R_-$, covariant with supersymmetry (1) and including the trivial case, $Z = 1$. The $Z$-quotient of the tensor product $(R_+ \otimes R_-)/Z$ is then an off-shell representation of $Sp^{1,1|p,q} = Sp^{1|p}\oplus Sp^{1|q}$, but when $Z\not= l$ need not itself be a tensor product.
\end{construction}
\subsection{Detailed Formal Nonsense section}
\com{This is what I had originally but it was maybe too detailed and too mathematically formal. I'm keeping it here just in case.}
\label{app:repn}
The $1$-d $n$-extended supersymmetry algebra is a superalgebra consisting of an even operator $H$ and $n$ odd operators $Q_1, \ldots, Q_n$ with the following relations:
\begin{eqnarray}
\label{eqn:susy1d1}
[H,Q_i]&=&0\\
\label{eqn:susy1d2}
\{Q_i,Q_j\}&=&2\delta_{ij}H
\end{eqnarray}
\begin{construction}
\label{cons:susy1d}
Given a $1$-d Adinkra $A=(V,E,c,\mu,h)$ with $n$ colors, we can find a representation $R(A)$ of the $1$-d $n$-extended supersymmetry algebra as follows:
\begin{itemize}
\item Let $R_0$ be the real vector space generated by $V$. That is, $R_0$ is the set $\{f:V\to \RR\}$ viewed as a vector space with function addition and scalar multiplication. There is a basis given by $\{b_v\,|\,v\in V\}$ with $b_v(v)=1$ and $b_v(w)=0$ if $v\not=w$.
\item Let $R(A)=R_0\otimes_\RR \RR[H]$. This is a representation of $\RR[H]$ with $H(b\otimes H^k)=b\otimes H^{k+1}$, and $H$ extends to all of $R$ linearly.
\item If $v\in V$ and $w=q_i(v)$, then
\[Q_i(b_v\otimes H^k)=(-1)^{\mu(v,w)} b_w\otimes H^{k+\frac12(1-h(w)+h(v))}\]
Extend $Q_i$ to all of $R(A)$ linearly.
\item There is a $\ZZ_2$ grading of $R(A)$: let the $\ZZ_2$ grading of $b_v\otimes H^k$ be $h(v)\pmod{2}$.
\end{itemize}
\end{construction}
Note that the exponent of $H$, $i+\frac12(1-h(w)+h(v))$, is an integer because $|h(w)-h(v)|=1$.
\begin{prop}
\label{prop:rep1}
$R$ is a representation of the $1$-d supersymmetry algebra.
\end{prop}
\begin{proof}
First note that each $Q_i$ acts by changing the $\ZZ_2$ grading and $H$ does not. Therefore the $Q_i$ are odd operators and $H$ is an even operator.
Since $b_v$ is a basis for $R_0$, $b_v\otimes 1$ is a generator of $R$ as an $\RR[H]$-module. It suffices, then, to prove (\ref{eqn:susy1d1})--(\ref{eqn:susy1d2}) for $b_v\otimes 1$.
If $q_i(v)=w$, then
\begin{eqnarray*}
Q_i(H(b_v\otimes H^k))&=&Q_i(b_v\otimes H^{k+1})\\
&=&(-1)^{\mu(v,w)}b_w\otimes H^{k+1+\frac12(1-h(w)+h(v))}\\
&=&H((-1)^{\mu(v,w)}b_w\otimes H^{k+\frac12(1-h(w)+h(v))})\\
&=&H(Q_i(b_v\otimes H^k))
\end{eqnarray*}
We also have
\begin{eqnarray*}
Q_i(Q_i(b_v\otimes H^k))
&=&Q_i((-1)^{\mu(v,w)} b_w\otimes H^{k+\frac12(1-h(w)+h(v))})\\
&=&(-1)^{\mu(v,w)} (-1)^{\mu(w,v)} b_v\otimes H^{k+\frac12(1-h(w)+h(v))+\frac12(1-h(v)+h(w))}\\
&=&b_v\otimes H^{k+1}\\
&=&H(b_v\otimes H^{k})
\end{eqnarray*}
Now consider $\{Q_i,Q_j\}$ where $i\not=j$. Let $w=q_i(v)$ and $x=q_j(w)$ and $y=q_i(x)$. Then from Property 3 of Adinkras, $v=q_j(y)$.
\begin{eqnarray*}
Q_i(Q_j(b_v\otimes H^k))
&=&Q_i((-1)^{\mu(v,y)}b_y\otimes H^{k+\frac12(1-h(y)+h(v))})\\
&=&(-1)^{\mu(v,y)+\mu(y,x)}b_x\otimes H^{k+\frac12(1-h(y)+h(v))+\frac12(1-h(x)+h(y))})\\
&=&(-1)^{\mu(v,y)+\mu(y,x)}b_x\otimes H^{k+\frac12(2-h(x)+h(v))})
\end{eqnarray*}
while
\begin{eqnarray*}
Q_j(Q_i(b_v\otimes H^k))
&=&Q_j((-1)^{\mu(v,w)}b_w\otimes H^{k+\frac12(1-h(w)+h(v))})\\
&=&(-1)^{\mu(v,w)+\mu(w,x)}b_x\otimes H^{k+\frac12(1-h(w)+h(v))+\frac12(1-h(x)+h(w))})\\
&=&(-1)^{\mu(v,w)+\mu(w,x)}b_x\otimes H^{k+\frac12(2-h(x)+h(v))})
\end{eqnarray*}
Since
\[\mu(v,w)+\mu(w,x)+\mu(x,y)+\mu(y,v)\equiv 2\pmod{2},\]
we have
\[Q_jQ_i(b_v\otimes H^k)=-Q_iQ_j(b_v\otimes H^k).\]
\end{proof}
\begin{definition}[Adinkraic representations]
A representation $M$ of $1$-d $n$-extended supersymmetry algebra is called \emph{adinkraic} if there exists a $1$-d Adinkra $A$ with $n$ colors so that $R(A)=M$ in Construction~\ref{cons:susy1d}.
\end{definition}
Though not relevant for our theorems, one can notice that the grading $h$ provides a grading to $R$ in the following way: the mass dimension of $b_v\otimes H^k$ is $k+\frac12 h(v)$. Then $H$ has grading $1$ and each $Q_i$ has grading $\frac12$.
\subsection{Representations of $2$-d supersymmetry}
The $2$-d $(p,q)$-extended supersymmetry algebra has two even operators $H$ and $P$, and $n$ odd operators $Q_1,\ldots, Q_n$, with the first $p$ being viewed as ``left-moving'' and the remaining $q=n-p$ being viewed as ``right-moving''. $H$ and $P$ commute with everything, while
\[
\{Q_i, Q_j\}=\begin{cases}
2\delta_{ij}(H+ P),&\mbox{ if $i\le p$}\\
2\delta_{ij}(H- P),&\mbox{ if $i> p$}\\
\end{cases}
\]
We define $P_- = H+ P$ and $P_+=H-P$.
\begin{construction}
Given a $2$-d Adinkra $A=(V,E,c,\mu,h_L,h_R)$ with $(p,q)$ colors, we get a representation of the $2$-d $(p,q)$-extended supersymmetry algebra as follows:
\begin{itemize}
\item Let $R_0=\{f:V\to\RR\}$ as a vector space. Again, for every $v\in V$ define $b_v(v)=1$ and $b_v(w)=0$ if $v\not=w$.
\item Let $R(A)=R_0\otimes_\RR \RR[P_-,P_+]$ as a free $\RR[P_-,P_+]$-module.
\item If $i\le p$, and $w=q_i(v)$, then define
\[Q_i(b_v\otimes P_-^k P_+^l)=
(-1)^{\mu(v,w)}b_w\otimes P_-^{k+\frac12(1-h_L(w)+h_L(v))}P_+^l \]
\item If $i>p$ then
\[Q_i(b_v\otimes P_-^k P_+^l)=
(-1)^{\mu(v,w)}b_w\otimes P_-^k P_+^{l+\frac12(1-h_L(w)+h_L(v))} \]
\item There is a $\ZZ_2$ grading of $R(A)$: let the $\ZZ_2$ grading of $b_v\otimes P_-^k P_+^l$ be $h_L(v)+h_R(v)\pmod{2}$.
\end{itemize}
\end{construction}
\begin{prop}
\label{prop:rep2}
$R(A)$ is a representation of the $2$-d $(p,q)$-extended supersymmetry algebra.
\end{prop}
\begin{proof}
The proof is largely the same as Proposition~\ref{prop:rep1}.
\end{proof}
\begin{construction}
Let $R_L$ be a representation of $1$-d $p$-extended supersymmetry and $R_R$ be a representation of $1$-d $q$-extended supersymmetry. Then we define
\[R_L\otimes R_R\]
a representation of $2$-d $(p,q)$ supersymmetry as follows.
\begin{itemize}
\item For $i\le p$, $Q_i(a\otimes b)=Q_i(a)\otimes b$.
\item For $i>p$, $Q_i(a\otimes b)=(-1)^{|a|}a\otimes Q_{i-p} b$.
\item $H(a\otimes b)=H a\otimes b + a\otimes Hb$
\item $P(a\otimes b)=Pa \otimes b + a\otimes Pb$
\end{itemize}
Here $|a|$ means the $\ZZ_2$ grading of the element $a$ in $R_L$.
\end{construction}
\begin{prop}
$R_L\otimes R_R$ is a representation of $2$-d $(p,q)$-extended supersymmetry.
\end{prop}
\begin{proof}
This is standard in the SUSY literature.
\end{proof}
\begin{prop}
Let $A_L$ and $A_R$ be $1$-d Adinkras with $p$ and $q$ colors respectively. Let $R(A_L)$ and $R(A_R)$ be the representations of $1$-d supersymmetry obtained from $A_L$ and $A_R$, respectively, by Construction~\ref{cons:susy1d}. Then there is an isomorphism of representations of $2$-d $(p,q)$-extended supersymmetry
\[R(A_L)\otimes R(A_R) \cong R(A_L\times A_R)\]
\end{prop}
\begin{proof}
Let $v\in A_L$ and $w\in A_R$. The isomorphism sends $(b_v\otimes H^k)\otimes (b_w\otimes H^l)$ to $b_{(v,w)}\otimes P_-^{k}P_+^l$.
\end{proof}
\begin{prop}
Let $A$ be an Adinkra and let $v$ be a vertex of $A$. Let $A'$ be the Adinkra obtained by doing a vertex flip on $v$. Then there is an isomorphism from $R(A)$ and $R(A')$.
\end{prop}
\begin{proof}
Let $\Phi$ be the linear map that sends $b_v\otimes H^k$ to $-b_v\otimes H^k$, and for every $w\not=v$, $b_w\otimes H^k$ to $b_w\otimes H^k$.
Let $w=q_i(v)$. Now $Q_i(\Phi(b_v\otimes H^k))=Q_i(-b_v\otimes H^k)=-(-1)^{\mu(v,w)}b_w H^{k+\frac12(1-h(w)+h(v)}=(-1)^{\mu'(v,w)}b_w H^{k+\frac12(1-h(w)+h(v)}=\Phi(Q_i(b_v\otimes H^k))$.
etc. etc. [This is tedious.]
\end{proof}
\begin{prop}
Let $A=(V,E,c,\mu,h_L,h_R)$ and $A'=(V,E,c,\mu,h_L,h_R)$ be $2$-d Adinkras and let $f:V\to V'$ be a graph homomorphism that preserves coloring, dashing, and gradings. Then the linear map
\[f_*:R(A)\to R(A')\]
\[f_*(b_v\otimes P_-^kP_+^l)=b_{f(v)}\otimes P_-^kP_+^l\]
is a homomorphism of representations.
\end{prop}
\begin{proof}
The map $f_*$ commutes with $P_+$ and $P_-$. If $i$ is a left-moving color and $q_i(v)=w$, then $q_i(f(v))=f(w)$ and
\[f_*(Q_i(b_v\otimes P_-^kP_+^l))=f_*((-1)^{\mu(v,w)}b_w\otimes P_-^{k+\frac12(1-h_L(w)+h_L(v))}P_+^l\]
while
\[Q_i(f_*(b_v\otimes P_-^kP_+^l))=Q_i(b_{v'}\otimes P_-^kP_+^l)
=(-1)^{\mu'(f(v),f(w))}b_{f(w)}\otimes P_-^{1-h'_L(f(w))-h'_R(f(v))}P_+^l\]
which is the same thing if $f$ preserves dashing and gradings.
Likewise if $i$ is a right-moving color.
\end{proof}
\begin{thm}
If $A$ is a $2$-d Adinkra with $(p,q)$ colors, then
\[R(A)=(R(A_L^0)\otimes R(A_R^0))/M\]
where $M$ is a submodule.
\end{thm}
\begin{proof}
From the main theorem Theorem~\ref{thm:quotient},
\[A=(A_L^0\times A_R^0)/K\]
and in particular there is a graph homomorphism
\[f:A_L^0\times A_R^0\to A\]
that is surjective and preserves coloring, dashing, and gradings. Take the coresponding linear map
\[f_*:R(A_L^0\times A_R^0)\to R(A)\]
and let $M$ be the kernel of this map. Composed with the isomorphism
\[R(A_L^0)\otimes R(A_R^0)\cong R(A_L^0\times A_R^0)\]
we have the isomorphism.
\end{proof}
%%%%
\section{Equivalence with other notions of $2$-d Adinkras}
In \cite{gates:dimensional_extension,hubsch:weaving}, the notion of a $2$-d Adinkra is equivalent to that given here.
If I read Tristan's stuff right, we can completely translate the combinatorial rules to: a \emph{2-d Adinkra} (of dimension $n$) is a finite simple connected graph $A$ such that:
\begin{itemize}
\item It is an $1$-d Adinkra (with the associated ranking, dashing, etc.).
\item It has $p + q = n$ colors, where the first $p$-colors are called ``left-moving'' and the second $q$-colors are called ``right-moving.''
\item A coherence condition: for any cycle, we imagine the following sum: going up (here ``up'' comes from the grading we have from the engineering dimension in our ranking for the $1$-d Adinkra) a left-handed edge adds $-1$, and going up a right-handed edge adds $1$; going down the edges give contributions with opposite signs. The sum of this around any cycle must be $0$. (in particular, this rules out things like ambidextrous bow-ties)
\end{itemize}
Assuming I interpreted these rules correctly, now I can do combinatorics without needing any physics.
%%
The first structural fact we can impose is a bi-grading that is compatible with the grading we already have from the $1$-d Adinkra structure, in the sense that the $1$-d grading is simply one of the coordinates of our bi-grading.
\begin{prop}
A $1$-d Adinkra can be extended to a $2$-d Adinkra if and only if the $1$-d Adinkra has a \emph{bigrading} to $\ZZ^2$. This is a map $g: V \rightarrow \ZZ^2$, such that all left-moving edges correspond to displacements of $(0, 1)$ and right-moving edges correspond to displacements of $(1, 0)$.
\end{prop}
\begin{proof}
Proof delayed until talking more with Kevin and Tristan about the easiest way to write things up to avoid reinventing wheels.
\end{proof}