Spectra and topology of graphs and of simplicial complexes

The main object of study in our project is a grapha set of nodes joined by edges, which are pairs formed by some of the nodes. It serves as a basic model of pairwise relations and interactions. They are ubiquitous in science as well as in our everyday life. Our ability to exploit models based on graphs often depends on how well we understand the structure of the underlying graphs. For instance, when edges model an undesired relation, we may want to divide the nodes into a small number of groups such that there are no edges within any of the groups. Such a division is called a coloring. In general, it is a difficult problem to find a division with as few groups as possible. As another example, for a model of a network where nodes communicate with other nodes through the edges, we might be interested in knowing how failure of some of the nodes or edge connections affects the ability of the remaining nodes to communicate. A quantitative guarantee asserting that large parts of the network can be disconnected from the rest only by a failure of a large number of nodes is called the expansion of the graph. Many structural properties like the colorability and the expansion are difficult to calculate directly for the given graph. Therefore, it is interesting to study their relation to other properties, which may be easier to work with. One such class of interest in our project consists of algebraic properties. These are usually expressed using G-matrices, which are assignments of numbers to the nodes and the edges of a given graph. A famous result in the area asserts that the so-called spectral gap of the graph, which is a property of a particular G-matrix associated with the graph, is a good measure of the expansion of the given graph. Another useful way of working with a graph is to visualize it. This could mean to draw it in the plane so that points represent the nodes and line segments represent the edges in such a way that no two edges cross. However, this is not always possible. One can then try to draw the graph on a more complicated object, such as the surface of a donut. The existence of such a representation is one example of a topological property that a graph may possess. It turns out that both structural and algebraic properties of graphs are sometimes linked to them. The purpose of the project is to strengthen the existing connections between structural, algebraic and topological properties of graphs as well as to establish new ones. Moreover, we extend our study to simplicial complexes, which are higher dimensional analogs of graphs.

This project studies graphs, a fundamental mathematical structure modeling pairwise relations between objects, e.g., a network of roads connecting a set of cities. We can visualize a graph by drawing it on paper, representing the cities by dots and the roads connecting them by curves. However, we quickly find out that for some networks, no matter how we place the dots and how long or curvy we draw the prescribed connections, some of them always cross. A drawing of a graph in which no two curves cross is called an embedding. If we want to avoid crossings in a physical road network, we can construct bridges. An analogous construction for graphs drawn on a paper leads to two-dimensional objects called surfaces, for example, the shape of a donut or of a pretzel. Trying to draw various networks on a donut, we find out now that more of them embed there than on a flat piece of paper before, whereas many others still do not embed. The same story continues with a pretzel. It turns out that every network, no matter how complex, embeds into some surface, but no surface admits an embedding for every network. Graphs do not have to model only networks. In order to illustrate another object of study in our project, we consider graphs modeling a set of nails with some pairs connected by a rubber band, each with its own strength. If we pin each nail somewhere on a board, the bands become stretched, which results in forces acting on the nails along the bands. Writing down the conditions expressing that the forces acting on a nail are in equilibrium leads to an object known as a weighted Laplacian of the graph, and we have studied its various properties. To describe one of them, we note that we can always choose the positions of the nails so that if we simultaneously unpin the nails and let them move freely, the whole configuration only shrinks by a constant factor per second, and otherwise retains its shape. Typically, such configurations can only correspond to nails being pinned along a single line, and are thus 1-dimensional. Sometimes, however, depending on the graph and the strengths of the individual rubbers, it is possible to find such configurations that are not bound to a single line, but to a plane or even a higher-dimensional space. The maximum dimension we can get this way for a given graph by adjusting the strengths of the rubbers is a quantity of particular interest. There was a conjectured upper bound on it for all graphs that have an embedding onto a fixed surface. We disproved the conjecture.