By Steve Kaliszewski of Arizona State University

A directed graph is a set of points, or vertices, together with a set of arrows, or edges, which connect some of the vertices. Graphs have had various and significant applications throughout mathematics, physical science, and computer science. For instance, to solve the famous Konigsberg Bridge Problem in 1736, Leonhard Euler made a graph in which the vertices represented pieces of land, and the edges represented the bridges between them. Using simple observations about graphs, he was able to conclude that there was no round trip which used each bridge exactly once.

More abstractly, graphs have been used to encode the algebraic structure of mathematical objects such as groups (via their Coxeter graphs) and C*-algebras (via Bratteli diagrams). Bratteli diagrams, for instance, provided a complete classification of the C*-algebras known as AF-algebras.

Reversing the trend of the previous examples (in which a graph was associated to a problem or object from another subject), it has been found that a C*-algebra can be associated to a directed graph in such a way that the structure of the graph is reflected in the structure of the algebra.

This development has injected C*-theory with a vast array of interesting yet manageable and concrete examples: a large class of C*-algebras, called the Cuntz-Krieger algebras, for instance, can be realized as graph C*-algebras. A flourishing industry --- much of it originating from ASU --- is now centered around the study of C*-algebras arising from directed graphs, their generalizations, and their applications.

The extent to which a C*-algebra can capture the structure of a graph is sometimes remarkable: for example, the C*algebra of any finite graph with no directed loops is built out of basic (matrix) algebras in a very natural and predictable way. Other graph constructions are also reflected in analogous C*-algebraic constructions: for instance, the C*-algebra of a Cartesian product of graphs is a tensor product of the individual graph C*-algebras.

ASU Professors Steve Kaliszewski and John Quigg, together with Professor Iain Raeburn of the University of Newcastle, Australia, have recently extended the "dictionary" which translates between graph concepts and C*-algebraic concepts to include several more fundamental constructions. Strikingly, these constructions had arisen independently of one another in graph theory and in C*-theory, and therefore appeared superficially to be so different that the analogies between them had not yet been noticed. Besides having significant applications in C*-theory, results like these are expected to provide new and useful tools for graph theorists. Because of the widespread applications of graphs, this in turn could have repercussions throughout much of mathematics, physical science, and computer science.

Back