Combinatorics and Graph Theory

2105 Submissions

[2] viXra:2105.0120 [pdf] submitted on 2021-05-20 08:17:09

Quantum Partial Automorphisms of Finite Graphs

Authors: Teo Banica
Comments: 28 Pages.

The partial automorphisms of a graph $X$ having $N$ vertices are the bijections $\sigma:I\to J$ with $I,J\subset\{1,\ldots,N\}$ which leave invariant the edges. These bijections form a semigroup $\widetilde{G}(X)$, which contains the automorphism group $G(X)$. We discuss here the quantum analogue of this construction, with a definition and basic theory for the quantum semigroup of quantum partial automorphisms $\widetilde{G}^+(X)$, which contains both $G(X)$, and the quantum automorphism group $G^+(X)$. We comment as well on the case $N=\infty$, which is of particular interest, due to the fact that $\widetilde{G}^+(X)$ is well-defined, while its subgroup $G^+(X)$, not necessarily, at least with the currently known methods.
Category: Combinatorics and Graph Theory

[1] viXra:2105.0107 [pdf] submitted on 2021-05-19 17:03:13

Embedding Cycles Within Adjacency Matrices to Represent Rational Generating Functions

Authors: Yonah Berwaldt
Comments: 24 Pages.

This paper explores populating adjacency matrices with connected cycles whose final outputs represent the coefficients of rational generating functions (RGFs). An RGF takes the form of: $p(x)/q(x) + r(x)$. The denominator, $q(x)$, takes the form of: Constant $\cdot (1-c_1x^{x_1})(1-c_2x^{x_2})... (1-c_nx^{x_n})$ where the $c_i$ are complex numbers and where factors can possibly have multiplicities greater than one. It is well known that a closed form solution exists for computing coefficients of RGFs. Also, one can write the linear recurrence relation associated with every RGF into a matrix format. Using matrices, one can compute coefficients for an RGF, such as Molien series for finite groups, in logarithmic time. What has not yet been shown (or is not yet commonly discussed) is that one can conceptualize an RGF as a system of connected cycles within an overarching adjacency matrix. For example, a single cycle of length two would have vertex A connect to vertex B which itself connects back to vertex A with a directed arrow of weight $c_i$. In this conceptualization, each coefficient of an RGF can be reproduced by taking a suitable adjacency matrix to an integer power. Nothing essential is lost by taking this perspective. Due to the self-similar nature of the matrix, we devise an algorithm that can calculate coefficients of RGFs in constant time. Using memoization, a technique for caching intermediate results, calculating coefficients of RGFs can also be done in logarithmic time. One observation is that, depending on the situation (i.e. what $q(x)$ is), there may be a computational benefit to taking the cyclical perspective. For example, for certain $q(x)$, the traditional matrix has cells containing positive and negative values whereas the cyclical approach has cells containing only positive values. The computational benefit is probably irrelevant for computers; however, it may be important for restrictive systems, such as biological systems / neural networks that may have a tight operating envelope. We make a final observation that each cyclical matrix representation can be thought of as a graph which is an epsilon away from being strongly connected. Studying the behavior of these matrices may yield insight into the behavior of a broader class of function. In essence, the study of sequences modeled by RGFs can be converted to the study of connected cyclical graphs that model the RGFs or vice versa.
Category: Combinatorics and Graph Theory