1a. Finite graphs
We will be interested in this book in graph theory, which is the same as discrete geometry. Or perhaps vice versa. Personally I prefer the “vice versa” viewpoint, geometry is something basic, coming first, and graphs, which are more specialized, come after. And this, I hope, will agree with you too. I can only imagine that you have some knowledge of geometry, for instance that round thing that you played with as a kid is a sphere, and that's quality geometry, called Riemannian, you're already a bit expert in that. While in what regards graphs, you've probably heard of them, but have no idea what they are good for, and you are here, starting this book, for getting introduced to them.
So, discrete geometry. And the first question here is of course, why? Is there something wrong with the usual, continuous geometry?
Good question, and as a first answer, I would argue that a good quality digital music record is as good as an old vinyl one. Of course some people might claim the opposite, but these people can be proved, scientifically, to be wrong, for the simple reason that the human ear has a certain resolution, and once your digital technology passes that resolution, records are [math]100\%[/math] perfect to the human ear. And there is even more, because the same goes for vision, smell, taste and touch. In short, all our senses function like a computer, in a digital way, and we might be well living in a continuous world, but we will never be able to really sense this, and so fully benefit from that continuity.
Some further thinking on this leads to the scary perspective that our world might be actually discrete, at a resolution much finer than that of our human senses. You might argue that why not using some sharp scientific machinery instead, but that machinery has a certain resolution too. And so our scare is justified, and time to ask:
\begin{question} Is the world continuous, or quantized? \end{question} Here we have used the word “quantized”, which is a fancy scientific way of saying “discrete”, as a matter of getting into serious physics. And here, hang on, opinions are split, but most physicists tend to favor the possibility that our world is indeed quantized. And at a resolution that is so fine, that is guaranteed to stay beyond the level of what can be directly observed with past, present and future scientific machinery.
But probably enough talking, time to get to work, remember that we are here for doing math and computations. Let us summarize this discussion by formulating:
\begin{conclusion}
Discrete geometry is worth a study, as a useful discretization of our usual continuous geometry. And why not as a replacement for it, in case it's wrong.
\end{conclusion}
In order now to get started, we first need to talk about continuous geometry. Generally speaking, that is about curves, surfaces and other shapes, called “manifolds” in [math]\mathbb R^N[/math]. However, instead of getting into what a manifold exactly is, which can be a bit technical, let us just take this intuitively, [math]M[/math] is by definition a “continuous shape” in [math]\mathbb R^N[/math].
Now for discretizing such a manifold [math]M\subset\mathbb R^N[/math], the idea is very simple, namely placing a sort of net on [math]M[/math]. To be more precise, assume that we found a finite set of points [math]X\subset M[/math], with some edges between them, denoted [math]i-j[/math], and corresponding to paths on [math]M[/math], all having the same lenght [math]\varepsilon \gt 0[/math]. Then, we have our discretization [math]X\subset M[/math].
As an example here, let us try to discretize a sphere [math]S\subset\mathbb R^3[/math]. There are many ways of doing so, and a quite straightforward one is by using an inscribed cube, as follows:
With this done, let us try now to forget about [math]M[/math] itself, and think at [math]X[/math], taken alone. This beast [math]X[/math] is a finite set of points, with edges between them. In addition, all edges have the same lenght [math]\varepsilon \gt 0[/math], but now that [math]M[/math] is gone, we can assume if we want that we have [math]\varepsilon=1[/math], or simply forget about [math]\varepsilon[/math]. Thus, we are led into the following definition:
A graph [math]X[/math] is a finite set of points, with certain edges [math]i-j[/math] drawn between certain pairs of points [math](i,j)[/math].
All this might seem overly simplified, and I can hear some of you saying hey, but deep mathematics needs very complicated definitions, that no one really understands, and so on. Wrong. The above definition is in fact the good one, and the graphs themselves are very interesting objects. That will keep us busy, for the rest of this book.
Before getting into mathematics, let us explore a bit Definition 1.3, and see how the graphs look like. We would need here some sort of “random graph”, in order to see what types of phenomena can appear, and here is an example, which is quite illustrating:
We can see that there are several things going on here, and here is a list of observations that can be formulated, just by looking at this graph:
(1) First of all, in relation with our discretization philosophy, [math]X\subset M[/math], there is a bit of a mess with dimensions here, because the whole middle of the graph seems to discretize a surface, or 2D manifold, but the left part is rather 1D, and the right part, with that crossing edges, suggests either a 2D manifold in [math]\mathbb R^3[/math] or higher, or a 3D manifold.
(2) So, this is one problem that we will have to face, when working with Definition 1.3, at that level of generality there is no indication about the “dimension” of what our graph is supposed to describe. But this is not an issue, because when this will be really needed, with some further axioms we can divide the graphs into classes and so on.
(3) As another observation now, our graph above is not that “random”, because it is connected. If this annoys you, please consider that the graph contains as well three extra points, that I can even draw for you, here they are, [math]\bullet\bullet\bullet[/math]\,, not connected to the others. But will this bring something interesting to our formalism, certainly not.
(4) In short, we will usually not bother with disconnected graphs [math]X[/math], a bit like geometers won't bother with disconnected manifolds [math]M[/math]. This being said, at some point of this book, towards the end, when looking at graphs from a quantum perspective, we will reconsider this, because “quantum” allows all sorts of bizarre “jumps”. More later.
(5) Finally, if you're an electric engineer you might be a bit deceived by all this, because what we're doing so far is obviously binary, and won't allow the installation of bulbs, resistors, capacitors and so on, having continuous parameters. Criticism accepted, and we will expand our formalism, once our theory using Definition 1.3 will be ripe.
As a last comment, we are of course allowed to draw graphs as we find the most appropriate, and no rules here, free speech as we like it. However, as an important point, if you are a bit familiar with advanced mathematics, and know the difference between geometry and topology, you might have the impression that what we are doing is topology. But this is wrong, what we will be doing is definitely geometry. More on this later.
Let us record the main conclusions from this discussion, as follows:
\begin{conclusion} Our definition for the graphs looks good, and appears as a good compromise between:
- More particular definitions, such as looking at connected graphs only, which is the main case of interest, geometrically speaking.
- More general definitions, such as allowing machinery and symbols to be installed, either at the vertices, or on the edges, or both.
\end{conclusion} We will come back to this, when needed, and fine-tune our definition for the graphs, along the above lines, depending on the exact problems that we are interested in.
Moving ahead, now that we have our objects of study, the graphs, time to do some mathematics. For this purpose, we will mostly use linear algebra, and a bit of calculus too. At some point later, we will need as well some basic knowledge of group theory, along with some basic functional analysis, and basic probability theory. All these can be learned from many places, and if looking for a compact package, talking a bit about everything that will be needed here, you can check my linear algebra book [1].
But let us start with some algebra and generalities. We surely know from Definition 1.3 what a graph is, and normally no need for more, we are good for starting some work. However, it is sometimes useful to have some alternative points of view on this. So, let us replace Definition 1.3 with the following definition, which can be quite useful:
A graph [math]X[/math] can be viewed as follows:
- As a finite set of points [math]X[/math], with certain edges [math]i-j[/math] drawn between certain pairs of distinct points [math](i,j)[/math].
- As a finite vertex set [math]X[/math], given with an edge set [math]E\subset X\times X[/math], which must be symmetric, and avoiding the diagonal.
- As a finite set [math]X[/math], given with a relation [math]i-j[/math] on it, which must be non-reflexive, meaning [math]i\not\!\!-\,i[/math], and symmetric.
To be more precise, here the formulation in (1) is the one in our old Definition 1.3, with the remark that we forgot to say there that [math]i\neq j[/math], and with this coming from the fact that, geometrically speaking, self-edges [math]i-i[/math] look like a pathology, to be avoided.
Regarding now (2), this is something clearly equivalent to (1). It is sometimes convenient to use the notation [math]X=(V,E)[/math], with the vertex set denoted [math]V[/math], but in what concerns us, we will keep using our policy of calling [math]X[/math] both the graph, and the vertex set.
Finally, regarding (3), this is something equivalent to (1) and (2), and with “relation on [math]X[/math]” there not meaning anything in particular, and more specifically, just meaning “subset of [math]X\times X[/math]”. Observe that nothing is said about the transitivity of [math]-[/math].
All this is nice, and as a first mathematical question for us, let us clarify what happens in relation with the transitivity of [math]-[/math]. To start with, as our previous examples of graphs indicate, the relation [math]-[/math] is not transitive, in general. In fact, [math]-[/math] can never be transitive, unless for graphs of type [math]\bullet\bullet\bullet[/math]\,, without edges at all, because once we have an edge [math]i-j[/math], by symmetry and then transitivity we are led to the following wrong conclusion:
However, as a matter of recycling our question, we can ask if [math]-[/math], once completed with [math]i-i[/math] as to be symmetric, can be transitive. And the answer here is as follows:
The graphs [math]X[/math] having the property that [math]-[/math], once completed with [math]i-i[/math] as to be symmetric, is transitive, are exactly the graphs of type
This is clear, because after thinking a bit, our question simply asks to draw the graph of an equivalence relation, and what you get is of course a picture as above, with various complete graphs corresponding to the various equivalence classes.
In practice now, all three formulations of the notion of graph from Definition 1.5 can be useful, for certain pruposes, but we will keep using by default the formulation (1) there. Indeed, here is what happens for the cube, and judge yourself:
The cube graph is as follows:
- Viewed as a set, with edges drawn between points:
[[math]] \xymatrix@R=18pt@C=18pt{ &\bullet\ar@{-}[rr]&&\bullet\\ \bullet\ar@{-}[rr]\ar@{-}[ur]&&\bullet\ar@{-}[ur]\\ &\bullet\ar@{-}[rr]\ar@{-}[uu]&&\bullet\ar@{-}[uu]\\ \bullet\ar@{-}[uu]\ar@{-}[ur]\ar@{-}[rr]&&\bullet\ar@{-}[uu]\ar@{-}[ur] } [[/math]]
- Viewed as a vertex set, plus edge set:
[[math]] X=\{1,2,3,4,5,6,7,8\} [[/math]][[math]] E=\left\{\begin{matrix} 12,14,15,21,23,26,32,34,37,41,43,48\\ 51,56,58,62,65,67,73,76,78,84,85,87 \end{matrix}\right\} [[/math]]
- Viewed as a set, with a relation on it: same as in [math](2)[/math].
To start with, (1) is clear. For (2) however, we are a bit in trouble, because in order to figure out what the edge set is, we must first draw the cube, as in (1), so failure with respect to (1), and then label the vertices with numbers, say [math]1,\ldots,8[/math]:
But with this done, we can then list the 12 edges, say in lexicographic order. Finally, (3) is obviously the same thing as (2), so failure too with respect to (1).
Summarizing, and hope you agree with me, Definition 1.5 (1), which is more or less our original Definition 1.3, is the best, for general graphs. This being said, the cube example in Proposition 1.7 might look quite harsh, to the point that you might now be wondering if Definition 1.5 (2) and Definition 1.5 (3) have any uses at all.
Good point, and in order to answer, let us go back to the cube. With mea culpa to that cube, we can in fact do better when labeling the vertices, and we have:
The cube can be best viewed, via edge and vertex set, as follows:
- The vertices are the usual [math]3{\rm D}[/math] coordinates of the vertices of the unit cube, that is, [math]000[/math], [math]001[/math], [math]010[/math], [math]011[/math], [math]100[/math], [math]101[/math], [math]110[/math], [math]111[/math].
- The edge set consists of the pairs [math](abc,xyz)[/math] of such coordinates having the property that [math]abc\leftrightarrow xyz[/math] comes by modifying exactly one coordinate.
This is clear from definitions, and no need to draw a cube or anything for this, in fact the geometric cube is there, in what we said in (1) and (2). Here is however an accompanying picture, in case you have troubles in seeing this right away:
Thus, one way or another, we are led to the conclusion in the statement.
As a comment here, we can further build along the above lines, with the ultimate conclusion being something which looks very good and conceptual, as follows:
\begin{advertisement} The cube is the Cayley graph of [math]\mathbb Z_2^3[/math]. \end{advertisement} Obviously, this looks like a quite deep statement, probably beating everything else that can be said, about the cube graph. We will talk about this later, when discussing in detail the Cayley graphs, but coming a bit in advance, some explanations on this:
(1) You surely know about the cyclic group [math]\mathbb Z_N[/math], having as elements the remainders [math]0,1,\ldots,N-1[/math] modulo [math]N[/math]. But at [math]N=2[/math] this group is simply [math]\mathbb Z_2=\{0,1\}[/math], so in view of what we found in Proposition 1.8, and leaving now 3D geometry aside, for a trip into arithmetic, we can say that the vertices of the cube are the elements [math]g\in\mathbb Z_2^3[/math].
(2) Regarding now the edges [math]g-h[/math], we know from Proposition 1.8 that these appear precisely at the places where the passage [math]g\leftrightarrow h[/math] comes by modifying exactly one coordinate. But, and skipping some details here, with all this left to be discussed later in this book, this means precisely that the cube is the Cayley graph of [math]\mathbb Z_2^3[/math].
As an overall conclusion now, we have several equivalent definitions for the graphs, those in Definition 1.5, which can sometimes lead to interesting mathematics, and we have as well Conclusion 1.4, telling us how to fine-tune our graph formalism, when needed, depending on the precise questions that we are interested in. Very nice all this, foundations laid, and we are now good to go, for some tough mathematics on graphs.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].