The call for entries by Mauricio Islas Gómez, a graduate of the Bachelor's Degree in Applied Mathematics and currently a student of the Master's Degree in Mathematics, both at the Autonomous University of the State of Hidalgo (UAEH), is named "Sotero Prieto Award" in memory of one of the first academics who dedicated himself professionally to the teaching of mathematics at the university level in Mexico.
The prize is awarded every year by the Mexican Mathematical Society (SMM) and consists of recognizing the best undergraduate mathematics theses that were defended in the previous period. In the 2022 edition, three medals were awarded, of which Mauricio Islas received one of them, and the recognition ceremony was held during the inauguration of the 55th SMM Congress, which took place at the University of Guadalajara in a hybrid form.
The thesis is entitled "Homotopy properties of the clan operator in graphs". For a better understanding, we will now describe what kind of things are addressed in the work and some other things about certain applications that some of the concepts we use have.
The main object of study are what we know as graphs, which can be thought of as "networks", i.e. as a series of vertices and edges joining some of these vertices, as shown in Figure 1 below (the vertices are the black points and the edges are the lines joining some of these points).
Figure 1. Vertices and edges
This type of graphs are used by some specialists to model different situations, for example, the vertices could represent neurons and there will be an edge between two of them if they can communicate with each other. Or, a graph like this could model friendships in a social network, i.e., the vertices could represent people and there will be an edge between two of them if they are friends in this social network.
Now, in Mauricio Islas' thesis, of which I was his director, Rafael Villarroel Flores, there is a construction that we are very interested in, which consists in the fact that we can build another graph from each graph, which we know as the clan graph. Let's explain this construction in terms of people and the friendship relationship, let's consider figure 2 below:
Figure 2. Clan chart
Suppose that the vertices in the left graph that we label with G represent people and the edges between two vertices mean that those people are friends. As we can see people 1, 3 and 4 are all friends with each other, but in addition there is no other person who is friends with 1, 3 and 4 at the same time, when we have this situation we say that 1, 3 and 4 form a clan, we will call this clan formed by people 1, 3 and 4 q1. Similarly we can see that people 2, 4 and 5 are all friends with each other, but there is no other person who is friends with all of them at the same time; then 2, 4 and 5 form a clan that we will call q2. Thus one can realize that persons 3 and 6 form another clan that we will call q3, and 5 and 6 form another clan that we will call q4. In short, a clan is a group of people where they are all friends with each other, but there is no longer another person who is friends with all the other people in that group.
From this we form the graph on the right that we label K(G). Where now the vertices of this new graph are the clans and we will put an edge between them if these clans have a person in common. For example, we are left that 1, 3 and 4 form the clan q1; on the other hand 2, 4 and 5 form the clan q2, these two clans have a person in common which is the person 4. Then, as shown in the figure on the right, there must be an edge between q1 and q2. This is how we construct the clan graph.
It is possible to assign a "geometric figure" to each graph as shown in the following image (Figure 3):
Figure 3. "Geometric figure".
In the figure on the left we have a graph like the ones we have already defined and in the figure on the right we have its associated geometric figure. The construction is done as follows: for each vertex of the graph we draw a point, then for each edge we draw a straight line between these points and for each clan of three vertices (i.e., for each triangle) we shade the entire figure. If a graph had a clan of four vertices then we would have to shade and fill a tetrahedron (or pyramid), and so on in larger dimensions.
Now, the main problem studied in the thesis is: what must a graph G satisfy so that the figures associated with G and its clan graph K(G) "look alike"? In mathematics we have a precise term for what it means for two figures to "look alike", that term is what we call homotopy. This is interesting because there are both graphs that resemble their clan graph and those that do not. For example, the next graph shown (Figure 4) is known as the octahedron and its associated figure resembles a sphere that we can draw in three-dimensional space. But the figure associated with the clan graph of the octahedron resembles a sphere that can no longer be drawn in three dimensions, in fact, it is a four-dimensional sphere, so those two spheres mentioned do not resemble each other.
Figure 4. Clan graph of the octahedron.
These concepts that we have presented have been applied to different branches of science. As an example of application of the clan graphs we have that the physicist Manfred Requardt has used them to make some studies in physics, as you can review in his scientific article which you can access through the following link:
https://journals.aps.org/prd/abstract/10.1103/PhysRevD.94.124019. Also the clans have had applications in branches of biology, as an example in the characterization and classification of electrophysiological signals, which can be seen in the following article:(https://www.frontiersin.org/articles/10.3389/fbioe.2020.00324/full).
As a final example of the application of these concepts, the fact of assigning geometric figures to graphs has been used for data analysis. In this case, the vertices of a graph function as the data and there is an edge between two pieces of data if there is a certain relationship between them. The idea of assigning a geometric figure to this data is to find certain "gaps" of different dimensions. Such "gaps" can give certain information to those doing this type of analysis, an example of this can be seen at: https://link.springer.com/chapter/10.1007/978-3-319-69775-8_6.
As already mentioned the main study problem of the thesis was to find conditions in a graph G so that the figures associated to G and its clan graph K(G) "look alike" (we will call the graphs G that fulfill this invariant). Thus, the problem boils down to finding graphs that are invariant. It is known that a certain class of graphs that have a certain property called the clan-Helly property turn out to be invariant. And despite being a "large" class of graphs that comply with it, they are not all known, i.e., there are graphs that do not have the property of being clan-Helly that are also invariant.
In the thesis we focus on a conjecture which is the following: "If a graph G satisfies that its clan graph K(G) has the property of being clan-Helly then G is invariant". Despite not being able to give a proof or a counterexample in the thesis for that conjecture, it did manage to show that it is true for graphs of 8 vertices or less. Furthermore, we found a condition that a minimal counterexample should fulfill in case the conjecture is false. Such a condition helped us to considerably reduce the number of cases to verify that graphs of 8 vertices or less are invariant.
According to what was mentioned in the Sotero Prieto Award, the jury qualified the complexity of the problem studied in the thesis, as well as the writing of the work. Indeed, it does not seem easy to give a proof of the conjecture studied in the project because when it was shown to be valid up to graphs of 8 vertices or less, we could not observe a pattern to give a proof in general. In addition, obtaining the clan graph of a graph is computationally difficult, i.e., in general, it would take a computer a long time to compute the clan graph of a graph in general. This gives us a small idea of the complexity of the problem studied.
That is why the thesis of Mauricio Islas' Bachelor's Degree in Applied Mathematics deserved the recognition granted by the Mexican Mathematical Society; undoubtedly a stimulus for the student, for the academic group of the area and for the rest of the community of the Institute of Basic Sciences and Engineering (ICBI) of the UAEH.
Mauricio Islas has a Bachelor's degree in Applied Mathematics from the Universidad Autónoma del Estado de Hidalgo (UAEH) and is currently pursuing a Master's degree in Mathematics at the same university.
Rafael Villarroel Flores is a full time professor in the Academic Area of Mathematics and Physics at the UAEH. D. in Mathematics from the Faculty of Sciences of the National Autonomous University of Mexico (UNAM) and PhD in Mathematics from the University of Minnesota in the United States.