author: niplav, created: 2025-07-10, modified: 2025-07-23, language: english, status: in progress, importance: 3, confidence: likely
.
I am afflicted by a strange curse, which condemns me to be creative enough to find new mathematical structures, but too dumb to prove anything interesting about them.
Inspired by (A -> B) -> A (Scott Garrabrant, 2018):
On a meditation retreat in 2022 I was remembering that post and just doodled the above image in my notebook, together with some other graphs where edges could go between edges. I'll call those "pergraphs"; they haven't (to my knowledge) been explored yet.
Intuitively, a pergraph is a mathematical structure made from nodes and edges, where each edge needs to have a source and a sink. The source and the sink can be any node or edge, including itself.
Given a finite set of vertices $V$ and a finite set of peredges $P$
(where a peredge is simply a label), a pergraph is the tuple $(V,
E \subseteq P \times (V \cup P) \times (V \cup P))$ with the closure
constraint that $\forall (p, s, t) ∈ E: s ∈ P \Rightarrow ∃(s,
s', t') ∈ E \land t ∈ P \Rightarrow ∃(t, s'', t'') ∈ E$.
Up to isomorphism for renamings of vertices and peredges.
Sequence of pergraphs with $n=|V|+|P|$ constituents, starting at n=0:
1, 2, 15, 180, 3638, …
This sequence is not yet in the OEIS.
$(\emptyset, \emptyset)$.$(\{v_1, \emptyset\})$ and the self-directed edge $(\emptyset, \{(e_1, e_1, e_1)\})$.
Code for computing the first terms of the sequence here, generated by Claude Sonnet 4, which I can also thank for talking through all the cases for n=2.
As a variant one could ditch the nodes entirely, and replace them self-directed edges. I think that one has different combinatorial behavior.
{directed, undirected} edges×{allows, disallows} multi-edges×{allows, disallows} loops×{allows, disallows} hyperedges×{allows, disallows} edges between edges×{allows, disallows} edges from/to themselves×{allows, disallows} edges between arbitrary sets of vertices.
Pergraphs are distinct from hypergraphs, as they don't allow for an edge between more than two nodes; they are not multigraphs, because they allow for edges from/to edges (similar to multigraphs, they allow for multiple edges between the same two nodes); they are distinct from higraphs, as they don't allow for edges to originate from collections of multiple nodes; they are different from Petri nets, because they don't have movable tokens; they are not the same as metagraphs, because they again allow for edges between (nested) collections of nodes. They are probably different from categories, because they're more specific than categories and don't require composition, but I don't know enough category theory to confirm that.
The closest I've found to this concept is in this unsourced section on the Wikipedia article on hypergraphs:
Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges
$e_{1}$and$e_{2}$, and zero vertices, so that$e_{1}=\{e_{2}\}$and$e_{2}=\{e_{1}\}$. As this loop is infinitely recursive, sets that are the edges violate the axiom of foundation. In foundation](https://en.wikipedia.org/wiki/Axiom_of_Foundation). In particular, there is no transitive closure of set membership for such hypergraphs. Although such structures may seem strange at first, they can be readily understood by noting that the equivalent generalization of their Levi graph is no longer bipartite, but is rather just some general directed graph.The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the incidence matrix is simply
$$\begin{pmatrix} 0 & 1 \cr 1 & 0 \cr \end{pmatrix}$$
The concept appears under-developed, and slightly different from what I'm pointing at.
(Many thanks to Claude 4 Sonnet for several long conversations which fleshed out the concept.)