The notion of sequentiality has always been central in mathematics and at the heart of computation, encoded in objects like the successor function in natural numbers or, as we will study, in paths on graphs. A path on a graph is usually defined as a concatenation of edges, but also can be studied as chains of compositions of edges, thinking of the edges as binary relations.
​
We will construct a generalization of compositions of binary relations to compositions of higher arity relations. Then we will study how chains of compositions of n,m-arity relations applied to a set of hyperedges within a given hypergraph can be thought as a new kind of paths on hypergraphs called compositional paths.
​
The goal of this project is to develop a formalism for studying the compositionality of hyperedges and, therefore, paths on hypergraphs. We will compute examples, multiway systems of compositional paths, and propose new types of path algebras on hypergraphs.
​

Initialization


Concatenation of edges vs compositions of relations

We show how concatenation and composition are two different ways of thinking about reachability and paths on graphs.

Concatenation vs composition paths

Concatenation paths:
Let
G(V,E)
be a directed graph, a path on G is defined as any sequence of edges
α
1
,…,
α
n
connecting two vertices x,y, denoted:
(x|
α
1
,…,
α
n
|y)
.
Example:
Out[]=
◼
  • (1|αβγ|4)
    is a path from 1 to 4 traversing the edges α,β,γ.
    • ◼
  • Two paths
    (1|
    α
    1
    ,…,
    α
    n
    |2)
    ,
    (2|
    β
    1
    ,…,
    β
    n
    |3)
    are concatenated as
    (1|
    α
    1
    ,…,
    α
    n
    ,
    β
    1
    ,…,
    β
    n
    |3)
    .
    • Compositional paths:
    Let
    G(V,E)
    be a directed graph, a compositional path on G is defined as any chain of binary compositions of edges.
    Example:
    Out[]=
    ◼
  • There exists a path from 1 to 3 because
    (1,2)◦(2,3)(1,3)
    , this is a compositional path.
    • ◼
  • Two compositional paths ((1,2)◦(2,3)) and ((3,4)◦(4,5)) are composed by ((1,2)◦(2,3))
    ◦
    ((3,4)◦(4,5)) =
    (1,3)◦(3,5)
    =
    (1,5)
    .
    • NOTE: Although in Graphs the compositions of edges are trivial because they only keep the information of the starting vertex and the target vertex;
    in higher arity relations compositional paths encode information about the hyperedges that were composed to achieve them.
    The transitive closure is a classical concept on a directed graph that encodes the notion of reachability.
    It produces a new graph with directed edges between two points whenever there exists a path between them.
    Out[]=
    For hypergraphs we will construct an analogous concept of the transitive closure o graphs, that will end up being the set of all compositional paths of a hypergraph.

    Compositions of binary relations

    Binary relations

    Goal: extract the minimal compositional properties from paths on ordinary graphs and define a class of rewriting rules on hypergraphs that generalize their behaviour for higher arities.
    The usual composition of binary relations
    S,T
    on a set
    V
    is
    Out[]=
    Which is defined as the binary operation
    Out[]=
    ◼
  • Notation: let
    T{(x,y)}
    and
    S{(y,z)}
    , the composition
    S◦T
    will be denoted as
    • Out[]=
    This corresponds to the following hypergraph rewriting rule on Wolfram Language:
    Out[]=

    Binary rewriting Rules

    A binary rewriting rule R on hypergraphs takes two n,m-hyperedges
    E
    1
    ,
    E
    2
    as inputs and returns one l-hyperedge
    E
    3
    , this behaviour is called a signature (n,m;l).
    Out[]=

    Generalizing Compositional Properties

    We will impose additional structure on binary rewriting rules in order to obtain a class of compositional rewriting rules that capture properties of binary compositions.
    Their formal mathematical definition will be given in the next chapter.

    Compositional properties of binary relations

    Basic Intuitions

    We will describe some properties that hold trivially for binary relations but may indicate a path for generalizing them to compositions of higher relations.
    ◼
  • Endpoints preserving rule: the initial vertex of the resulting hyperedge is the initial vertex on
    E
    1
    and the endpoint on the resulting hyperedge is the endpoint of
    E
    2
    .
    • ◼
  • Direction compatible: a rewriting rule is said to be direction compatible whenever the initial vertex on
    E
    2
    is not the initial vertex on
    E
    1
    , i.e.
    • Out[]=
    ◼
  • Middle vertex deleting: when composing
    E
    1
    ◦
    E
    2
    the initial vertex on
    E
    2
    (last vertex on
    E
    1
    ) vanishes.
    This property is stated because the shared vertex “
    y
    ” vanishes when composing binary relations
    (x,y)◦(y,z)(x,z)
    , although it can be stated in a different way, equivalent in the binary case but with different implications for higher arities:
    • ◼
  • External vertex selecting: Whenever the set of vertices on the resulting hypergraph is a subset of the set of external vertices on the composing hyperedges.
    We will use the Middle vertex deleting property to study rewriting rules in higher arities although we may in the future study how the external vertex selecting rewriting rules behave.
    • ◼
  • Connected rewriting rule: A rewriting rule is said to be connected if the resulting hypergraph is one single connected component.
    • Out[]=
    
    Example for connected composition:
    ,
    Example for non-connected composition:
    
    Compositional rewriting rule: a binary rewriting rule that is “endpoints preserving”, “direction compatible”,”middle vertex deleting” and “connected”.​
    Compositional path: the result of applying any chain of compositional rewriting rules on a given hypergraph. Compositional paths are hypergraphs by themselves.

    Compositions of n,m-arity relations

    The class of n,m Compositions of relations

    In this chapter we propose a rigorous generalization of the compositions of binary relations, motivated by the notion of compositional rewriting rules described earlier, we will use set theoretic language for the construction.
    Let
    X
    be a set,
    S⊆
    n
    X
    be an n-arity relation,
    T⊆
    m
    X
    an m-arity relation, and
    k
    (
    i
    α
    )
    α1
    ,
    ′
    k
    (
    j
    α
    )
    α1
    two fixed subsequences of the sets of indices
    {2,…,n-1}
    and
    {2,…,m-1}
    respectively, abbreviated as
    (
    i
    k
    )
    ,
    (
    j
    ′
    k
    )
    . An
    (n,m)
    composition associated to the subsequences
    k
    (
    i
    α
    )
    α1
    ,
    ′
    k
    (
    j
    α
    )
    α1
    is defined as
    Out[]=
    Then the composition
    S
    (
    i
    k
    ),(
    j
    ′
    k
    )
    ◦
    n,m
    T
    is the direct image of
    ST
    under the function
    (
    i
    k
    ),(
    j
    ′
    k
    )
    ◦
    n,m
    i.e.
    Out[]=
    Therefore, for a given pair of ordered tuples with arities n,m there are different compositions that may be performed, specifically there is one composition for every election of the sequences
    k
    (
    i
    α
    )
    α1
    ⊆{2,…,n-1}
    ,
    ′
    k
    (
    j
    α
    )
    α1
    ⊆{2,…,m-1}
    , then there are
    n-2
    2
    
    m-2
    2
    
    n+m-4
    2
    different compositions between them.

    Compositional operators

    Based on the previous compositions we construct a class of compositional operators on relations.
    Fix a composition
    (
    i
    k
    ),(
    j
    ′
    k
    )
    ◦
    n,m
    and Define the set of all tuples of finite lengths as
    Out[]=
    Let the concatenation operator for tuples
    x
    (
    x
    1
    ,…,
    x
    n
    )
    and
    y
    (
    y
    1
    ,…,
    y
    m
    )
    to be
    x
    
    y
    (
    x
    1
    ,…,
    x
    n
    ,
    y
    1
    ,…,
    y
    m
    )
    and the multiple projection function
    π
    ij
    that projects the i to j entries of an ordered tuple defined by:
    Out[]=
    Then the corresponding compositional operator
    (
    i
    k
    ),(
    j
    ′
    k
    )
    △
    n,m
    is defined as
    Out[]=
    This operators perform a fixed composition between the middle n,m elements of two tuples of any length and allow us to generate different types of algebraic structures from hypergraphs. In the next chapter we will suggest how path algebras can be generated with compositional operators on hypergraphs and describe further steps for related work.

    Motivation example

    We apply a chain of compositions on an Initial hypergraph for generating an example of compositional path.
    Plot initial Hypergraph:
    Then, fix a set of compositional rewriting rules for the possible arity configurations on hyperedges:
    Apply a chain of compositions on the hyperedges of the initial hypergraph:

    Toy Multiway system

    The following is the multiway system for the last motivation example.
    Result: each step on the multiway system corresponds to computing a compositional path from the underlying hypergraph.

    Computation and visualization of compositional rewriting rules

    Computing compositional rewriting rules on hypergraphs

    In this chapter we will compute and visualize some examples of compositional rewriting rules on hypergraphs acting on pairs of hyperedges of mixed arities.
    Create a filter for the Wolfram institute’s rewriting rules enumeration function:

    3,3-hyperedges composed

    In this chapter we will compute the possible ways in which two 3-hyperedges can be composed.
    Enumerating the rules that yield a ternary or a binary hyperedge:
    Filter the rules and enumerate the compositional ones:
    Visualize examples:

    Incrementing arity via compositions

    In this chapter we will compute some examples of how incremental arity compositions behave.

    3,3-hyperedges to 4-hyperedges

    Enumerating the rules that yield a quaternary hyperedge and the number of filtered ones:
    Important example for incrementing arity:
    More examples:

    Multiway Systems of compositional paths

    We compute the set of all compositional paths that do not increment arity on some example hypergraphs and their associated multiway-systems.
    Incremental compositions are not computed in this examples because they generate an infinite number of paths, however, the set of compositional paths on a hypergraph includes them all.
    The set of non incrementing-arity compositional Rules and example hypergraphs :
    Computing up to 5 steps on the multiway system for the first example graph :
    Computing up to 5 steps on the multiway system for the second example graph :
    Computing up to 5 steps on the multiway system for the third example graph :
    Remark:
    The set of all possible chains of compositional rewriting rules on the hyperedges generates the set of compositional paths on the initial hypergraph.
    Mathematically this paths correspond to any non-empty chain of compositions applied on hyperedges and on compositions of hyperedges.

    Compositional path algebras

    In order to study the path algebras, we introduce the classical concept of a Quiver, as an algebraic approach to studying multi-directed graphs.

    Classical path algebras

    This section gives an overview of the classical construction of path algebras. For more details see R.Schiffler(2013).

    Path algebra construction

    Classical results regarding Representation theory and path algebras.
    ◼
  • Gabriel’s Theorem: Gabriel’s theorem states that any finite-dimensional algebra is equivalent (Morita equivalent) to a path algebra modulo some relations.
    • ◼
  • Leavitt Path Algebra: The Leavitt path algebra has been studied extensively in representation theory and C*algebras.

    • Example Path algebra of polynomials

    Compositional path algebras

    This section introduces the concept of compositional path algebras that arise from compositional operators on hypergraphs.
    Open questions regarding Representation theory and compositional path algebras.

    Example: compositional path algebra of polynomials

    We construct a compositional paths algebra that also generates the algebra of polynomials, but using compositional operators rather than concatenation of edges.
    ◼
  • Compositional operators are not commutative in general.
    • ◼
  • (n,m)Compositions are not in general associative.

    • Further research

    ◼
  • Study if there exist any connections between the Multilinear Hyper-quiver Representations and the compositional paths on hypergraphs.
    • ◼
  • Do compositional path algebras encode classical path algebras?
    • ◼
  • State if every finite dimensional algebra can be obtained as a compositional path algebra on a hypergraph.
    • ◼
  • Study which non-commutative algebras may arise from compositional paths on hypergraphs.
    • ◼
  • Study which non-associative algebras may arise from compositional paths on hypergraphs.

    • Concluding Remarks

    ◼
  • Offered a new mathematical framework for studying reachability and paths on hypergraphs.
    • ◼
  • Introduced a class of compositions of n,m-arity relations that generalize the behaviour of compositions of binary relations to higher arities.
    • ◼
  • Created a new class of hypergraph compositional path algebras that may encode classical path algebras.

    • Acknowledgments

    I would like to thank Xerxes Arsiwalla, Nikolay Murzin, Jon Lederman, Hatem Elshatlawy and Stephen Wolfram for their support and guidance during the development of this project, special thanks to Daniel Sanchez for his guidance with the Wolfram Language.
    I extend my gratitude to Ivón Dorado for introducing me to Quiver Representation Theory and Path Algebras.
    Finally, I am grateful for the support of my family during all this process, without them this could never have been possible.

    References

    1
    .
    Schiffler R, (2014). Quiver Represenations, CMS Books in Mathematics, Springer Verlag.
    2
    .
    Zapata and Arsiwalla (2022). An Invitation to Higher Arity Science. Complex Syst., 32, 409-468.
    3
    .
    T. Muller., Nanda and A. Seigal. (2023). Multilinear Hyperquiver Representations.
    4
    .
    Bakri, Zedam, et al (2021), Compositions of ternary relations. Kybernetika. 404-425. 10.14736/kyb-2021-3-0404.

    Cite This Notebook

    “Compositional Paths on Hypergraphs”
    by Sergio Quiroga Sandoval​
    ​https://community.wolfram.com/groups/-/m/t/3210556