Preface
Graph theory is a wide topic, and there are many possible ways of getting into it. Basically any question which is of discrete nature, with a finite number of objects [math]N[/math] interacting between them, has an associated graph [math]X[/math], and the question can be reformulated, and hopefully solved, in terms of that graph [math]X[/math]. A possible exception seems to come from discrete questions which are naturally encoded by a matrix, but isn't a [math]N\times N[/math] matrix [math]A[/math] some kind of graph too, having [math]1,\ldots,N[/math] as vertices, and with any pair of vertices [math]i,j[/math] producing the oriented edge [math]i\to j[/math], colored by corresponding the matrix entry [math]A_{ij}[/math].
Graphs appear as well in connection with continuous questions, via discretization methods. Discretizing is something commonplace in physics, and sometimes in pure mathematics too, with the continuous question, system or manifold [math]M[/math] appearing as the [math]N\to\infty[/math] limit of its discrete versions, which typically correspond to graphs [math]X_N[/math], which are often easier to solve, and with this philosophy having produced good results all around the spectrum, from common sense science and engineering questions up to fairly advanced topics, such as quantum gravity, dark matter and teleportation.
The purpose of this book is to talk about graphs, viewed from this perspective, as being discrete geometry objects. To be more precise, we will be rather mathematical, and the cornerstone of our philosophy will be the commonly accepted fact that the basic objects of mainstream, continuous mathematics are the Riemannian manifolds [math]M[/math], together with their Laplacians [math]\Delta[/math]. In the discrete setting the analogues of these objects are the finite graphs [math]X[/math], together with their adjacency matrices [math]d[/math], and this will be our way to view the graphs, in this book, as being some kind of “discrete Riemannian manifolds”.
This was for the philosophy. In practice, this will not prevent us from doing many elementary things, and our purpose will be to talk about graphs in a large sense, ranging from very basic, definition and elementary properties, to more advanced.
More in detail now, we will start in Part I with standard introductory material on graph theory, namely definition, main examples, and some computations and basic theorems. Our presentation here will be for the most of spectral flavor, by translating everything in terms of the adjacency matrix [math]d[/math], and proving the results via linear algebra.
As a continuation of this, in Part II we will discuss various geometric aspects, first with a study of the Laplacian of graphs, and a discussion of related discretization methods, then with a look into trees and other planar graphs, and higher genus graphs as well, and finally with a look into knot invariants, constructed via plane projections.
Switching gears, in Part III we will decide that graph theory is most likely related to abstract algebra, and that what we are mostly interested in is the systematic study of the symmetry groups [math]G(X)[/math] of the finite graphs [math]X[/math]. The material here will be mostly upper undergraduate level, sometimes erring on the graduate side.
Escalating difficulties, in Part IV we will include as well in our discussion the quantum symmetry groups [math]G^+(X)[/math] of the same finite graphs [math]X[/math], which are in general bigger than their classical counterparts [math]G(X)[/math], and with our motivation here coming from theoretical physics, and more specifically from quantum and statistical mechanics.
Part of this book is based on research work that I did some time ago on graphs and their symmetries, and I would like to thank my coworkers. Many thanks go as well to the young researchers in the area, who have recently pushed things to unexpected levels of deepness, that we will try to explain a bit here. Finally, many thanks go to my cats. When it comes to quick search over a graph, they are the kings of this universe.
\
Cergy, October 2024
Teo Banica \baselineskip=15.95pt \tableofcontents \baselineskip=14pt
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].