Operator Algebraic Quotient Structures Induced by Directed Graphs

Our result is about inclusions for (finite or infinite) countable directed graphs. In the proof, we use Free Probability Theory, groupoids, and algebras of operators (von Neumann algebras). We show that inclusions of directed graphs induce quotients for associated groupoid actions. With the use of operator thechniques, we then establish a duality between inclusions of graphs on the one hand and quotients of algebras on the other. Our main result is that each connected graph induces a quotient generated by a free group. This is a generalization of the notion of induced representations in the context of unitary representations of groups, i.e., the induction from the representations of a subgroup of an ambient group. The analogue is to systems of imprimitivity based on the homogeneous space. The parallel of this is the more general context of graphs (extending from groups to groupoids): We first prove that inclusions for connected graphs correspond to free group quotients, and we then build up the general case via connected components of given graphs.     

The graded structure of Leavitt path algebras

A Leavitt path algebra associates to a directed graph a ?-graded algebra and in its simplest form it recovers the Leavitt algebra L(1, k). In this note, we first study this ?-grading and characterize the (?-graded) structure of Leavitt path algebras, associated to finite acyclic graphs, C _n -comet, multi-headed graphs and a mixture of these graphs (i.e., polycephaly graphs). The last two types are examples of graphs whose Leavitt path algebras are strongly graded. We give a criterion when a Leavitt path algebra is strongly graded and in particular characterize unital Leavitt path algebras which are strongly graded completely, along the way obtaining classes of algebras which are group rings or crossed-products. In an attempt to generalize the grading, we introduce weighted Leavitt path algebras associated to directed weighted graphs which have natural ⊕?-grading and in their simplest form recover the Leavitt algebras L(n, k). We then show that the basic properties of Leavitt path algebras can be naturally carried over to weighted Leavitt path algebras.     

On the Hilbert Evolution Algebras of a Graph

Evolution algebras are a special class of nonassociative algebras exhibiting connections with various fields of mathematics. Hilbert evolution algebras generalize the concept in the framework of Hilbert spaces. This allows us to deal with a wide class of infinite-dimensional spaces. We study Hilbert evolution algebras associated to a graph. Inspired by the definitions of evolution algebras we define the Hilbert evolution algebra that is associated to a given graph and the Hilbert evolution algebra that is associated to the symmetric random walk on a graph. For a given graph, we provide the conditions for these structures to be or not to be isomorphic. Our definitions and results extend to the graphs with infinitely many vertices. We also develop a similar theory for the evolution algebras associated to finite graphs.

     

On a class of algebras associated to directed graphs

To any directed graph we associate an algebra with edges of the graph as generators and with relations defined by all pairs of directed paths with the same origin and terminus. Such algebras are related to factorizations of polynomials over noncommutative algebras. We also construct a basis for our algebras associated to layered graphs.     

Algebras Generated by Linearly Dependent Elements with Prescribed Spectra

We consider associative algebras presented by a finite set of generators and relations of special form: each generator is annihilated by some polynomial, and the sum of generators is zero. The growth of this algebra in dependence on the degrees of the polynomials annihilating the generators is studied. The tuples of degrees for which the algebras are finite-dimensional, have polynomial growth, or have exponential growth are indicated. To the tuple of degrees, we assign a graph, and the above-mentioned cases correspond to Dynkin diagrams, extended Dynkin diagrams, and the other graphs, respectively. For extended Dynkin diagrams, we indicate the hyperplane in the space of parameters (roots of the polynomials) on which the corresponding algebras satisfy polynomial identities.     

The structure of Leavitt path algebras and the Invariant Basis Number property

In this paper, we provide the structure of the Leavitt path algebra of a finite graph via some step-by-step process of source eliminations, and restate Kanuni and Özaydin's nice criterion for Leavitt path algebras of finite graphs having Invariant Basis Number via matrix-theoretic language. Consequently, we give a matrix-theoretic criterion for the Leavitt path algebra of a finite graph having Invariant Basis Number in terms of a sequence of source eliminations. Using these results, we show certain classes of finite graphs for which Leavitt path algebras have Invariant Basis Number, as well as investigate the Invariant Basis Number property of Leavitt path algebras of certain Cayley graphs of finite groups.     

Horn classes of predicate systems and varieties of partial algebras

We propound an approach through which techniques of the theory of quasivarieties of predicate systems are brought to bear on partial algebras. For every partial algebra A, two predicate representations are treated. The first is the graph of A whose basic operations are graphs of the basic operations on A. The second representation results from the graph of A by adding domains of the operations on A to its basic relations. Studying partial algebras from various perspectives makes it necessary to deal with different equality semantics. Here we present a general definition of semantics that stretches over such instances as weak semantics, Evans’ semantics. Kleene semantics, and strong semantics. On a set of all semantics, the preorder is induced in increasing “force,” and it is proved that certain of the properties of varieties of partial algebras in a given semantics are individuated by the position it takes in that set. We argue that every variety of partial algebras, in any semantics, is in correspondence with a Horn class of predicate systems which admits a generation operator and is closed under direct limits and retracts. For such classes we prove analogs of the Birkhoff theorem on subdirect decompositions and of the Taylor theorem on residual smallness. Therefore, these are also applicable to varieties of partial algebras in arbitrary semantics. Supported through the RF State Committee of Higher Education (1998 project), jointly by RFFR and DFG grants Nos. 96-01-00097 and 436113/2670, and also through FP “Integration” project No. 274. Translated fromAlgebra i Logika, Vol. 39, No. 1, pp. 23–46, January–February, 2000.     

Vertex-Compressed Subalgebras of a Graph von Neumann Algebra

In Cho (Acta Appl. Math. 95:95–134, 2007 and Complex Anal. Oper. Theory 1:367–398, 2007), we introduced Graph von Neumann Algebras which are the (groupoid) crossed product algebras of von Neumann algebras and graph groupoids via graph-representations, which are groupoid actions. In Cho (Acta Appl. Math. 95:95–134, 2007), we showed that such crossed product algebras have the amalgamated reduced free probabilistic properties, where the reduction is totally depending on given directed graphs. Moreover, in Cho (Complex Anal. Oper. Theory 1:367–398, 2007), we characterize each amalgamated free blocks of graph von Neumann algebras: we showed that they are characterized by the well-known von Neumann algebras: Classical group crossed product algebras and (operator-valued) matricial algebras. This shows that we can provide a nicer way to investigate such groupoid crossed product algebras, since we only need to concentrate on studying graph groupoids and characterized algebras. How about the compressed subalgebras of them? i.e., how about the inner (cornered) structures of a graph von Neumann algebra? In this paper, we will provides the answer of this question. Consequently, we show that vertex-compressed subalgebras of a graph von Neumann algebra are characterized by other graph von Neumann algebras. This gives the full characterization of the vertex-compressed subalgebras of a graph von Neumann algebra, by other graph von Neumann algebras.     

Correlation of Poisson algebras and Lie algebras in the language of identities

In the paper, the varieties of Poisson algebras whose ideals of identities contain the identity {x, y}· {z, t} = 0 are studied, and the correlation of these varieties with varieties of Lie algebras is investigated. A variety of Poisson algebras of almost exponential growth is presented. An example of a variety of Poisson algebras with fractional exponent is also given.     

A characterization of partial directed line graphs

Can a directed graph be completed to a directed line graph? If possible, how many arcs must be added? In this paper we address the above questions characterizing partial directed line (PDL) graphs, i.e., partial subgraph of directed line graphs. We show that for such class of graphs a forbidden configuration criterion and a Krausz's like theorem are equivalent characterizations. Furthermore, the latter leads to a recognition algorithm that requires O(m) worst case time, where m is the number of arcs in the graph. Given a partial line digraph, our characterization allows us to find a minimum completion to a directed line graph within the same time bound.The class of PDL graphs properly contains the class of directed line graphs, characterized in [J. Blazewicz, A. Hertz, D. Kobler, D. de Werra, On some properties of DNA graphs, Discrete Appl. Math. 98(1-2) (1999) 1-19], hence our results generalize those already known for directed line graphs. In the undirected case, we show that finding a minimum line graph edge completion is NP-hard, while the problem of deciding whether or not an undirected graph is a partial graph of a simple line graph is trivial.     

Schrödinger operators on periodic discrete graphs

We consider Schrödinger operators with periodic potentials on periodic discrete graphs. The spectrum of the Schrödinger operator consists of an absolutely continuous part (a union of a finite number of non-degenerated bands) plus a finite number of flat bands, i.e., eigenvalues of infinite multiplicity. We obtain estimates of the Lebesgue measure of the spectrum in terms of geometric parameters of the graph and show that they become identities for some class of graphs. Moreover, we obtain stability estimates and show the existence and positions of large number of flat bands for specific graphs. The proof is based on the Floquet theory and the precise representation of fiber Schrödinger operators, constructed in the paper.     

Vertex Cuts

Given a connected graph, in many cases it is possible to construct a structure tree that provides information about the ends of the graph or its connectivity. For example Stallings' theorem on the structure of groups with more than one end can be proved by analyzing the action of the group on a structure tree and Tutte used a structure tree to investigate finite 2‐connected graphs, that are not 3‐connected. Most of these structure tree theories have been based on edge cuts, which are components of the graph obtained by removing finitely many edges. A new axiomatic theory is described here using vertex cuts, components of the graph obtained by removing finitely many vertices. This generalizes Tutte's decomposition of 2‐connected graphs to k‐connected graphs for any k, in finite and infinite graphs. The theory can be applied to nonlocally finite graphs with more than one vertex end, i.e. ends that can be separated by removing a finite number of vertices. This gives a decomposition for a group acting on such a graph, generalizing Stallings' theorem. Further applications include the classification of distance transitive graphs and k‐CS‐transitive graphs.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

On Rauzy graph sequences of infinite words

Under study are the sequences of Rauzy graphs (i.e., the graphs of subwords overlapping) of infinite words. The k-stretching of a graph is the graph we obtain by replacing each edge with a chain of length k. Considering a sequence of strongly connected directed graphs of maximal in and out vertex degrees equal to s, we prove that it is, up to stretchings, a subsequence of a Rauzy graphs sequence of some uniformly recurrent infinite word on s-letter alphabet. The language of a word of this kind and stretching for a given sequence of graphs are constructed explicitly.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

On the power graph and the reduced power graph of a finite group

In this paper, for a finite group, we investigate to what extent its directed (resp. undirected) reduced power graph determines its directed power graph (resp. reduced power graph). Moreover, we investigate the determination of the orders of the elements of a finite group from its directed (resp. undirected) reduced power graph. Consequently, we show that some classes of finite groups are recognizable from their undirected reduced power graphs. Also, we study the relationship between the isomorphism classes of groups corresponding to the equivalence relations induced by the isomorphism of each of these graphs on the set of all finite groups.     

Duality of Graded Graphs

A graph is said to be graded if its vertices are divided into levels numbered by integers, so that the endpoints of any edge lie on consecutive levels. Discrete modular lattices and rooted trees are among the typical examples. The following three types of problems are of interest to us:(1) path counting in graded graphs, and related combinatorial identities;(2) bijective proofs of these identities;(3) design and analysis of algorithms establishing corresponding bijections.This article is devoted to (1); its sequel [7] is concerned with the problems (2)–(3). A simplified treatment of some of these results can be found in [8].In this article, R.P. Stanley's [26, 27] linear-algebraic approach to (1) is extended to cover a wide range of graded graphs. The main idea is to consider pairs of graded graphs with a common set of vertices and common rank function. Such graphs are said to be dual if the associated linear operators satisfy a certain commutation relation (e.g., the Heisenberg one). The algebraic consequences of these relations are then interpreted as combinatorial identities. (This idea is also implicit in [27].)[7] contains applications to various examples of graded graphs, including the Young, Fibonacci, Young-Fibonacci and Pascal lattices, the graph of shifted shapes, the r-nary trees, the Schensted graph, the lattice of finite binary trees, etc. Many enumerative identities (both known and unknown) are obtained. Abstract of [7]. These identities can also be derived in a purely combinatorial way by generalizing the Robinson-Schensted correspondence to the class of graphs under consideration (cf. [5]). The same tools can be applied to permutation enumeration, including involution counting and rook polynomials for Ferrers boards. The bijective correspondences mentioned above are naturally constructed by Schensted-type algorithms. A general approach to these constructions is given. As particular cases we rederive the classical algorithm of Robinson, Schensted, and Knuth [20, 12, 21], the Sagan-Worley [17, 32] and Haiman [11] algorithms, the algorithm for the Young-Fibonacci graph [5, 15], and others. Several new applications are given.     

Hilbert series of algebras associated to directed graphs and order homology

We give a homological interpretation of the coefficients of the Hilbert series for an algebra associated with a directed graph and its dual algebra. This allows us to obtain necessary conditions for Koszulity of such algebras in terms of homological properties of the graphs. We use our results to construct algebras with a prescribed Hilbert series.     

On Models of Directed Path Graphs Non Rooted Directed Path Graphs

A directed path graph is the intersection graph of a family of directed subpaths of a directed tree. A rooted directed path graph is the intersection graph of a family of directed subpaths of a rooted tree. Clearly, rooted directed path graphs are directed path graphs. Several characterizations are known for directed path graphs: one by forbidden induced subgraphs and one by forbidden asteroids. It is an open problem to find such characterizations for rooted directed path graphs. With the purpose of proving knowledge in this direction, we show in this paper properties of directed path models that can not be rooted for chordal graphs with any leafage and with leafage four. Therefore, we prove that for leafage four directed path graphs minimally non rooted directed path graphs have a unique asteroidal quadruple, and can be characterized by the presence of certain type of asteroidal quadruples.