Abstract The main obstacle in the quest for non-uniform cellular automata that meet the often desired property of number conservation is the vast size of the search space, going far beyond the capabilities of today’s computers. In this paper, we expound the construction of a directed graph $$\Pi $$ Π related to the set of all number-conserving non-uniform one-dimensional binary cellular automata with radius one and half (i.e., the neighborhood of a cell consists of four cells). We show that there is a one-to-one correspondence between the set of all such cellular automata on a finite grid with n cells and the set of all length-n closed directed walks in $$\Pi $$ Π . This provides us with a powerful tool to investigate non-uniform cellular automata of this type.

Cartan matrices, quasi-Cartan matrices and associated upper triangular Gram matrices control important combinatorial aspects of Lie theory and representation theory of associative algebras. We provide a graph theoretic proof of the fact that the absolute values of the coefficients of a non-negative quasi-Cartan matrix A as well as of its (minimal) symmetrizer D are bounded by 4, and that the analogous bound in case of the associated Gram matrix GˇA is 8. Moreover, we show that D (and GˇA) has at least one diagonal coefficient equal to 1. We describe some other restrictions and interrelations between the coefficients of A, D and GˇA, and the corank and other properties of A relevant in Lie theory. We apply our results to construct an algorithm by which we classify all non-negative quasi-Cartan matrices of small sizes.

We continue the study of finite connected edge-bipartite graphs Δ, with m ≥ 2 vertices (a class of signed graphs), started in [SIAM J. Discrete Math. 27(2013), 827-854] and developed in [Fund. Inform. 139(2015), 249-275, 145(2016), 19-48] by means of the non-symmetric Gram matrix G ∨ Δ ∈ 𝕄 n ( ℤ ) defining Δ, its symmetric Gram matrix G Δ : = 1 2 [ G Δ ∨ + G Δ t r ∨ ] ∈ 𝕄 n ( 1 2 ℤ ) , and the Gram quadratic form q Δ : ℤ n → ℤ. In the present paper we study connected positive Cox-regular edge-bipartite graphs Δ, with n ≥ 2 vertices, in the sense that the symmetric Gram matrix G Δ ∈ 𝕄 n (ℤ) of Δ is positive definite. Our aim is to classify such Cox-regular edge-bipartite graphs with at least one loop by means of an inflation algorithm, up to the weak Gram ℤ-congruence Δ ~ ℤ Δ′, where Δ ~ ℤ Δ′ means that G Δ ′ = B tr · G Δ · B, for some B ∈ 𝕄 n (ℤ) such that det B = ±1. Our main result of the paper asserts that, given a positive connected Cox-regular edge-bipartite graph Δ with n ≥ 2 vertices and with at least one loop there exists a Cox-regular edge-bipartite Dynkin graph 𝒟 n ∨ {ℬ n , 𝒞 n , ℱ 4 , 𝒢 2 } with loops and a suitably chosen sequence t • − of the inflation operators of one of the types Δ ′ ↦ t a − Δ ′ and Δ ′ ↦ t a b − Δ ′ such that the composite operator Δ ↦ t • − Δ reduces Δ to the bigraph 𝒟 n such that Δ ~ ℤ 𝒟 n and the bigraphs Δ, 𝒟 n have the same number of loops. The algorithm does not change loops and the number of vertices, and computes a matrix B ∈ 𝕄 n (ℤ), with det B = ±1, defining the weak Gram ℤ-congruence Δ ~ ℤ 𝒟 n , that is, satisfying the equation G 𝒟 n = B