1d. Coloring questions
There are actually two ways of coloring a graph, either by coloring the vertices, or by coloring the edges. Usually mathematicians are quite excited about coloring the vertices, and more on this in a moment. However, electric engineers for instance are more excited about coloring the edges, with machinery like bulbs, resistors and capacitors, or simply with arrows, describing the direction of the current through each edge. Although for machinery having several legs, such as transistors, we are back to vertex coloring.
In this book we will use the edge coloring convention, and this actually for rather mathematical reasons. To be more precise, recall from the very beginning of this book that we are philosophically interested in discretizing manifolds, [math]X\subset M[/math], and in fact this is how we run into graphs, by placing a net over such a manifold [math]M[/math].
But now imagine that our net is allowed to stretch. In this case no more graph, what we have is simply a subset [math]X\subset M[/math], which technically is a finite metric space. Thus, beyond usual graphs, what we would mostly like to cover with our formalism are the finite metric spaces [math]X[/math]. But this can be done by calling “colored graph” a graph with the vertices still uncolored, and with the edges colored. Indeed, any finite metric space [math]X[/math], consisting of [math]N[/math] points, can be viewed as the [math]N[/math]-simplex, with each edge [math]i-j[/math] colored by its length [math]d_{ij} \gt 0[/math]. So, this will be our colored graph formalism in this book:
A colored graph is a usual graph [math]X[/math], which each edge [math]i-j[/math] colored by a symbol [math]d_{ij}\in C[/math], with [math]C[/math] being a set, called color set. We call the matrix
In practice, as already mentioned in the above, we are mostly interested in the case [math]C=\{-1,0,1\}[/math], as to cover the oriented graphs, and also in the case [math]C=\mathbb R_+[/math], as to cover the finite metric spaces. However, the best is to use Definition 1.21 as stated, with an abstract color set [math]C[/math], that will quite often be a set of reals, [math]C\subset \mathbb R[/math].
As a first statement, regarding our enlarged graph formalism, we have:
The following are covered by our colored graph formalism:
- The usual graphs. In fact, the usual graphs are precisely the colored versions of the simplex, with color set [math]C=\{0,1\}[/math].
- The oriented graphs. In fact, the oriented graphs are precisely the colored versions of the simplex, with color set [math]C=\{-1,0,1\}[/math].
- The finite metric spaces. These are the colored versions of the simplex, with color set [math]C=\mathbb R_+[/math], and with the coloring subject to the triangle inequality.
All this is trivial, and self-explanatory, and the reason why we called this Theorem instead of Proposition only comes from its theoretical importance.
As an interesting remark now, with colored graphs we are in fact not that far from the usual graphs, and this due to the following simple fact:
Any formal matrix [math]d\in M_N(C)[/math] has a color decomposition,
As before with Theorem 1.22, this is something trivial, and self-explanatory, and called Theorem instead of Proposition just because its theoretical importance.
Many things can be said about colored graphs, and especially about the oriented graphs and finite metric spaces from Theorem 1.22. We will be back to them, later.
All this being said, coloring the vertices of a graph [math]X[/math], and we will call such a beast a “vertex-colored graph”, is something quite interesting too. Let us formulate:
A vertex-colored graph is a usual graph [math]X[/math], with each vertex [math]i\in X[/math] colored by a symbol [math]c_i\in C[/math], with [math]C[/math] being a set, called color set.
As a first question regarding such vertex-colored graphs, pick whatever black and white geographical map, with countries and boundaries between them, then pick 4 colored pencils, and try coloring that map. Can you do that? What is your algorithm?
Well, the point here is that we have a deep theorem, as follows:
Any map can be colored with [math]4[/math] colors.
This is something non-trivial, which took mankind a lot of time to prove, and whose final proof is something very long, and with computers involved, at several key places. So, theorem coming without proof, and sorry for this. But, we will be back to this in chapter 7 below, when discussing planar graphs, with at least some explanations on what the word “map” in the statement exactly means, mathematically speaking.
As a conclusion now, it looks like with our graph formalism, and our adjacency matrix technology, sometimes modified a bit, as above, we can deal with everything in discrete mathematics. However, before moving ahead with more mathematics, a warning: \begin{warning} Not everything in discrete mathematics having a picture, and an adjacency matrix, is a graph. \end{warning} This is something quite important, worth discussing in detail, with a good example. So, have you heard about projective geometry? In case you didn't yet, the general principle is that “this is the wonderland where parallel lines cross”. Which might sound a bit crazy, and not very realistic, but take a picture of some railroad tracks, and look at that picture. Do that parallel railroad tracks cross, on the picture? Sure they do. So, we are certainly not into abstractions here, but rather into serious science.
Mathematically now, here are some axioms, to start with:
A projective space is a space consisting of points and lines, subject to the following conditions:
- Each [math]2[/math] points determine a line.
- Each [math]2[/math] lines cross, on a point.
As a basic example we have the usual projective space [math]P^2_\mathbb R[/math], which is best seen as being the space of lines in [math]\mathbb R^3[/math] passing through the origin. To be more precise, let us call each of these lines in [math]\mathbb R^3[/math] passing through the origin a “point” of [math]P^2_\mathbb R[/math], and let us also call each plane in [math]\mathbb R^3[/math] passing through the origin a “line” of [math]P^2_\mathbb R[/math]. Now observe the following:
(1) Each [math]2[/math] points determine a line. Indeed, 2 points in our sense means 2 lines in [math]\mathbb R^3[/math] passing through the origin, and these 2 lines obviously determine a plane in [math]\mathbb R^3[/math] passing through the origin, namely the plane they belong to, which is a line in our sense.
(2) Each [math]2[/math] lines cross, on a point. Indeed, 2 lines in our sense means 2 planes in [math]\mathbb R^3[/math] passing through the origin, and these 2 planes obviously determine a line in [math]\mathbb R^3[/math] passing through the origin, namely their intersection, which is a point in our sense.
Thus, what we have is a projective space in the sense of Definition 1.27. More generally now, we can perform in fact this construction over an arbitrary field, as follows:
Given a field [math]F[/math], we can talk about the projective space [math]P^2_F[/math], as being the space of lines in [math]F^3[/math] passing through the origin, having cardinality
This is indeed clear from definitions, with the cardinality coming from:
Thus, we are led to the conclusions in the statement.
As an example, let us see what happens for the simplest finite field that we know, namely [math]F=\mathbb F_2[/math]. Here our projective space, having [math]4+2+1=7[/math] points, and 7 lines, is a famous combinatorial object, called Fano plane, which looks as follows:
Here the circle in the middle is by definition a line, and with this convention, the projective geometry axioms from Definition 1.27 are satisfied, in the sense that any two points determine a line, and any two lines determine a point. And isn't this magic.
The question is now, in connection with Warning 1.26, as follows:
\begin{question}
What type of beast is the above Fano plane, with respect to graph theory, and its generalizations?
\end{question}
To be more precise, the Fano plane looks like a graph, but is not a graph, because, save for the circle in the middle and its precise conventions, it matters whether edges are aligned or not, and with this being the whole point with the Fano plane.
However, not giving up, let us try to investigate this plane, inspired from what we know about graphs. A first interesting question is that of suitably labeling its vertices, and here we know from Theorem 1.28 and its proof that these are naturally indexed by the elements of the group [math]\mathbb Z_2^3[/math], with the neutral element [math]0=000[/math] excluded:
However, there is some sort of too much symmetry between these symbols, which will not help us much, so instead let us just label the vertices [math]1,2,\ldots,7[/math], as follows:
Next comes the question of suitably labeling the lines, and with here, we insist, these lines being not “edges”, because the Fano plane is not a graph, as explained above. This is again an interesting question, of group theory flavor, and among the conclusions that we can come upon, by thinking at all this, we have the quite interesting fact that, when interchanging the 7 points and the 7 lines, the Fano plane stays the same.
Which looks like something quite deep, but which also teaches us that the labeling question for the lines is the same as the labeling question for the points, and so, in view of the above, that we have to give up. So, let us simply label the lines by letters [math]a,b,\ldots,g[/math], in a somewhat random fashion, a bit as we did for the vertices, as follows:
Now with our Fano plane fully labeled, we can answer Question 1.29, as follows:
\begin{answer} The Fano plane can be described by the [math]7\times7[/math] incidence matrix recording the matches between points and lines, which is
with points on the vertical, and lines on the horizontal, labeled as above. However, unlike for graphs, this matrix is no longer symmetric, or having [math]0[/math] on the diagonal. \end{answer} So, question answered, rather defavorably for graph theory, and with this being said, shall we give up? Well, never underestimate the graphs. Indeed, these can strike back, and we have the following alternative answer to Question 1.29:
\begin{answer} The Fano plane can be described by the bipartite graph having as vertices the points and lines, and edges at matches, whose [math]14\times14[/math] adjacency matrix is
with [math]m[/math] being the usual [math]7\times7[/math] incidence matrix between points and lines, constructed before, and with [math]m^t[/math] being the transpose of [math]m[/math]. \end{answer} Not bad all this. By the way, many other interesting things can be said, about the bipartite graphs, that is, about the graphs whose vertices can be divided into 2 classes, with no edges within the same class. For instance, it is clear that these are precisely the graphs having the property that, with a suitable labeling of the vertices, the adjacency matrix looks as follows, with [math]m[/math] being a certain rectangular 0-1 matrix:
Along the same lines, we can talk as well about tripartite graphs, with the adjacency matrices here being as follows, with [math]m,n,p[/math] being certain rectangular 0-1 matrices:
More generally, we can talk about [math]N[/math]-partite graphs for any [math]N\in\mathbb N[/math], among others with the trivial remark that with [math]|X|=N[/math], our graph [math]X[/math] is obviously [math]N[/math]-partite.
We will be back to such graphs, and more specifically to the bipartite ones, which are the most useful and important, among multi-partite graphs, later in this book.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].