research articles on graph theory

Graph Theory – A Survey on the Occasion of the Abel Prize for László Lovász

• Survey Article
• Open access
• Published: 24 March 2022
• Volume 124 , pages 83–108, ( 2022 )

Cite this article

You have full access to this open access article

• Johannes Carmesin 1  

2969 Accesses

1 Altmetric

Explore all metrics

In this survey, we explain a few key ideas of the theory of graphs, and how these ideas have grown to form the foundation of entire research areas. Graph Theory is a fairly young mathematical discipline; here we explain some of its major challenges for the 21st century.

László Lovász was recently awarded the Abel Prize. He made important contributions to all the areas discussed in this survey, and we close by summarising his main achievements.

Similar content being viewed by others

Introduction to Graph Theory and Algebraic Graph Theory

Introduction

Introduction to Graphs

Avoid common mistakes on your manuscript.

1 What Is a Graph?

A graph consists of a set of vertices together with a set of edges such that each edge is incident with exactly two vertices. These two incident vertices are called the endvertices of that edge. Sometimes, it will be convenient to allow these two endvertices to be the same or to allow edges with the same pair of endvertices. For now, however, we restrict our attention to graphs where this does not happen. Topologically speaking, a graph is simply a 1-dimensional simplicial complex.

Two graphs are considered the same; that is, they are isomorphic , if there are bijections between their vertex sets and edge sets that commute with their incidence relations, see Fig.  1 .

The graph on the left is isomorphic to the graph on the right

While road networks, and various networks associated to the internet give immediate examples of graphs, see Fig.  2 , here is an example how graphs are used in another area of mathematics. Given a presented group, the vertex set of its Cayley graph is the set of elements of the group, and we join two elements \(a\) and \(b\) by an edge if there is a nontrivial element \(s\) in the generating set such that \(a\cdot s=b\) . Many highly symmetric graphs are Cayley graphs of groups. For example the cube is a Cayley graph of the dihedral group \(D_{4}\) , whereas the Petersen graph depicted in Fig.  1 is not the Cayley graph of any group. Of particular interest are properties of Cayley graphs that are invariant under changing the presentation, and thus they are properties of the underlying groups; for example ends of groups in the sense of Freudenthal [ 31 ]. The structure of ends in groups can be studied through graphs using Bass-Serre Theory Footnote 1 [ 84 , 88 ].

Graphs are used to model road networks (left) and networks associated to the internet (right), (Images from Wikipedia, the right picture is an An Opte Project visualization of routing paths through a portion of the Internet)

2 An Introduction to Graph Theory

Many questions in graph theory arise from studying the structure of natural classes of graphs. There are different approaches to deriving solutions to such questions. Over the years these approaches have been refined into a profound tool box of methods; and often graph theory is thought of as being composed of the subfields that emerged out of these approaches. In what follows I will introduce some of the basic questions of graph theory, and explain how its subfields arose by providing answers to these questions.

Extremal Graph Theory

A natural ordering on graphs is the ‘subgraph relation’; here we say that a graph \(H\) is a subgraph of a graph \(G\) if \(H\) can be obtained from \(G\) by deleting edges and deleting isolated vertices – that is, vertices not incident with any edges. Given a natural number \(r\) , the class of graphs with \(r\) vertices has a unique maximal graph with respect to the subgraph relation (up to isomorphism). This graph has edges between all \(\binom{r}{2}\) pairs of vertices; it is referred to as the complete graph on \(r\) vertices, denoted by \(K_{r}\) . It is natural to ask: which graphs contain the complete graph \(K_{r}\) as a subgraph? Or restating it through the complementary class: what is the structure of the class of graphs that do not have \(K_{r}\) as a subgraph? While this class of graphs seems to be pretty wild and a complete characterisation of the class may well be elusive, in 1941 Turán provided the following partial answer (extending an earlier observation of Mantel from 1907).

Consider a graph \(G\) formed by \(r-1\) classes of vertices such that two vertices are adjacent if and only if they are in different classes (here two vertices are adjacent if they are joined by an edge), see Fig.  3 . Clearly the graph \(G\) does not have the complete graph \(K_{r}\) as a subgraph. We say that \(G\) is a Turán-graph if any two of its \(r-1\) classes of vertices differ in size by at most one. Note that up to isomorphism, there is only one Turán-graph on a fixed number \(n>r\) of vertices. In 1941 Turán proved that any graph on \(n>r\) vertices that does not have the complete graph \(K_{r}\) as a subgraph and has as many edges as possible must be isomorphic to the Turán-graph on \(n\) vertices.

The Turán graph for \(r=4\) on 10 vertices

Turán’s theorem is the foundational example for the approach of Extremal Graph Theory . A key tool in extremal graph theory is Szemerédi’s regularity lemma . This says that the vertex set of every large-enough graph \(G\) can be partitioned into few subsets so that the edges of \(G\) between almost all of these subsets are distributed ‘regularly’: as one would expect it if they were picked at random, given the actual density of the edges of \(G\) between those two sets of vertices. Due to this inherent randomness, results in extremal graph theory that rely on the regularity lemma in their proof are often only asymptotic and approximate; that is, they are only valid for graphs on sufficiently many vertices and quantify by how many edges those graphs differ from a list of constructions.

To summarise, in extremal graph theory we aim to draw structural conclusions (such as the existence of a \(K_{r}\) subgraph) from merely quantitative assumptions (such as having more edges on \(n\) vertices than the Turán-graph does). Many of its methods are closely related to probability theory.

Structural Graph Theory

In the early days of graph theory, an influential problem was the 4-Colour Conjecture. Informally speaking, it says that the countries on any map can be coloured with at most four colours so that adjacent countries receive different colours, see Fig.  4 .

A colouring of the countries of the world with just four different colours (source: Wikipedia)

This problem can be modelled by a graph. Just assign a vertex to each country and join two of these vertices by an edge if their corresponding countries share a border. This graph has the property that it is planar ; that is, its geometric realisation (the associated 1-dimensional simplicial complex) can be injectively and continuously embedded in the two-dimensional plane, see Fig.  5 . Hence the formal statement of the 4-Colour Theorem is that the vertex set of any planar graph can be partitioned into four classes so that no edge has both its endvertices in the same class. In 1976, well over a hundred years after it had been proposed, the 4-Colour Theorem was proved by Appel and Haken. Next to Haken’s foundational contributions to computational topology, in particular the theory of normal surfaces, the 4-Colour Theorem is regarded as one of his main achievements. As for Hales’ proof of Kepler’s Conjecture, so far we only know computer-assisted proofs of the 4-Colour Theorem, which may be unexpected given the statement of the 4-Colour Theorem.

A planar graph with an embedding

Possibly motivated by the 4-Colour Conjecture, in the 1930s mathematicians like Kuratowski, Wagner and Whitney initiated the systematic study of the class of planar graphs. As we shall see, these investigations eventually led to the development of Graph Minor Theory, which nowadays is considered as far more important than the 4-Colour Theorem itself, the intriguing puzzle with which all these developments started.

In the above definition of ‘planar graphs’ we might as well have defined them slightly differently, requiring that the embedding of the edges is not only continuous but differentiable, or piece-wise linear, or even that the edges are embedded as straight lines. In 1943 Koebe proved that all these notions of embeddability are equivalent (for finite graphs, for infinite graphs see [ 43 ]) by proving that they are equivalent to an even stronger notion of embeddability. After being forgotten due to the horrible catastrophe of World War Two, this theorem was rediscovered independently by Andreev and Thurston and subsequently it was shown by Rodin and Sullivan in 1987 that this theorem can be applied in differential geometry to obtain a short combinatorial proof of the Riemannian Mapping Theorem [ 78 ], see also [ 44 ]. To summarise, there are many potential definitions of planar graphs, and it has been shown that they are all equivalent (for finite graphs), leading to a single class of planar graphs.

Making use of Euler’s Polyhedra Formula, it is an easy exercise to show that the complete graph \(K_{5}\) is not planar. Similarly, the complete bipartite graph \(K_{3,3}\) , see Fig.  6 , is not planar.

The graphs \(K_{5}\) (on the left) and \(K_{3,3}\) (on the right)

Since subgraphs of planar graphs are planar, it may be tempting to try to characterise the class of planar graphs by making a list of all the minimally non-planar graphs: those non-planar graphs all whose proper subgraphs are planar. Unfortunately, the list of these graphs is far too complicated. From a structural perspective, the reason for this is that the subgraph relation is not closed under planar duality in the following sense: start with a graph \(G\) embedded in the plane, take its planar dual, delete an edge, and take the planar dual again. The resulting graph is always planar but need not be a subgraph of the graph \(G\) we started with, see Fig.  7 .

The graph \(G\) is the black graph on the left. Its plane dual is depicted in grey in the same figure. The grey graph on the right is obtained from the grey graph on the left by deleting the edge \(e\) . The black graph on the right is dual of the grey graph on the right. However, it is not a subgraph of the graph \(G\) we started with

In 1933, Wagner introduced the ‘minor relation’ as a refinement of the subgraph relation that solved the above problem resulting from the deficit of the subgraph relation that it does not ‘behave well with planar duality’, as follows. A minor of a graph is obtained by deleting edges and contracting connected Footnote 2 edge sets to single vertices, see Fig.  8 . Minors of graphs may have multiple edges between a pair of vertices and may have edges whose two endvertices are the same; this slight extension of the class of graphs is referred to as the class of multigraphs . Footnote 3 The difference between graphs and multigraphs is mostly of a technical nature and with slight abuse of notation we shall not distinguish between the two in this survey; we shall always use the term ‘graph’ although sometimes the objects can actually be multigraphs.

The minor of the graph on the left obtained by deleting the dashed red edges and contracting the gray edges is depicted on the right

For planar graphs, the minor relation is obtained from the subgraph relation by closing it under planar duality (Fig.  9 ), but note that the minors are defined combinatorially for arbitrary graphs.

Contracting an edge in a planar graph is the same operation as dualising, deleting that edge in the dual, and then dualising back; in other words the diagram in this figures commutes. See Fig.  7 for an example for contraction of an edge

Planarity of graphs can be characterised through the minor relation: a graph is planar if and only if it does not have \(K_{5}\) or \(K_{3,3}\) as a minor. With a slightly different notation, this was first proved by Kuratowski [ 51 ], and it is referred to as ‘Kuratowski’s Theorem’. This theorem is an example of what Edmonds calls a good characterisation . Footnote 4 Given a graph, if it is planar, then there is a simple certificate for it: just give the drawing. If it is not planar, by Kuratowski’s theorem, there is also a simple certificate for it: it must have one of the two graphs \(K_{5}\) or \(K_{3,3}\) as a minor.

In addition to the class of planar graphs, there are quite a few other natural classes of graphs that are closed under the minor relation, for example the class of graphs embeddable in any fixed surface. Graph Minor Theory , initiated through the works of Kuratowski and Wagner in the 1930s, investigates the minor relation on general graphs.

A far-reaching generalisation of Kuratowski’s Theorem is the Robertson-Seymour Theorem. This theorem is concerned with general classes of graphs closed under taking minors. Each such class is characterised by its excluded minors , the minor-minimal graphs outside it. This theorem says that for any minor-closed class its list of excluded minors must be finite . While the proof easily spans over 500 pages, at the core of the proof of this theorem is the Graph Minor Structure Theorem , which in a sense gives a topological construction rule for any minor-closed class, establishing a deep connection between graph theory and topology.

To summarise, in Structural Graph Theory we aim to relate structural graph properties to one another, such as embeddability in a surface or the existence of certain minors. Often, results in this area are related to other areas of mathematics, such as topology, geometry or algebra, or to the design of efficient algorithms.

What Is the Difference Between Extremal Graph Theory and Structural Graph Theory?

There are many results in the intersection of these areas. In Extremal Graph Theory, theorems typically relate a numerical graph invariant, such as the number of edges, to a structural one, or even take the form of an inequality between two numerical graph invariants. Results are relatively easy to compare through these estimates. Typical methods, such as Szemerédi’s regularity lemma, are sometimes not even referred to as ‘theorems’, and often applying these methods requires a fair amount of computation and estimating.

In Structural Graph Theory, theorems typically establish a connection between two structural graph properties; such results are then used directly to prove further results, forming a diverse landscape of interconnected theorems.

Both approaches have their advantages, and it depends on the type of problem you are trying to solve which is more suitable.

3 Highlights in Extremal Graph Theory

Ramsey theory.

Today, with data science emerging rapidly as a new discipline of science, it is time to refine our mathematical understanding of what types of structure occur necessarily in any large-enough sample.

In 1930, Ramsey proved that for every natural number \(r\) there is a number \(n\) – much larger than \(r\) – such that every graph with at least \(n\) vertices either contains the complete graph \(K_{r}\) or its complement, which consists of \(r\) vertices with no edges in between [ 72 ].

Ramsey’s theorem is the first of its kind, in fact it finds certain pre-determined substructures in all large-enough graphs. In addition to numerous applications within combinatorics, extensions of Ramsey’s theorem to infinite sets provide tools in set theory, and there is a close connection between Ramsey’s theorem and Van der Waerden numbers for arithmetic progressions in number theory. Natural variants of Ramsey’s Theorem suggest themselves and have been studied a lot in the past century, and are usually subsumed to form the field of ‘Ramsey Theory’.

While Ramsey’s theorem as such is not too difficult to prove, the quantitative behaviour of this phenomenon seems to be particularly difficult to handle; more about this in a moment. Given \(r\) , the Ramsey number is the smallest number \(n\) such that every graph on \(n\) vertices contains a \(K_{r}\) or its complement, see Fig.  10 . The Ramsey number is denoted by \(R(r)\) . The observation that Ramsey numbers, even for pretty small values of \(r\) , are difficult to compute was popularised by Paul Erdős [ 87 ].

The 5-cycle is isomorphic to its complement and does not contain a complete graph \(K_{3}\) . Hence the Ramsey number \(R(3)\) is at least 6; and it is indeed an easy exercise to check that the complete graph \(K_{3}\) appears in any graph on six vertices or its complement as a subgraph

While determining particular Ramsey numbers for \(r\geq 6\) exactly is certainly not an easy task, the real challenge here is to understand their asymptotic behaviour. The known proofs give an exponential upper bound of the order \(2^{2r}\) . The best known lower bounds are based on randomly constructed graphs, and are of the order of magnitude \(2^{r/2}\) .

Open Question 3.1

Can you find accurate asymptotic upper and lower bounds for the Ramsey numbers \(R(r)\) ?

More precisely , Footnote 5 determine a constant \(c\) such that \(R(r)=\Theta (2^{c\cdot r})\) .

By the above, we know that \(\frac{1}{2}\leq c\leq 2\) . Combining results of Spencer [ 87 ] and Conlon [ 21 ] gives the best known bounds to date:

It seems that in order to improve the bounds for \(c\) fundamentally new ideas are required. Interestingly, as soon as we assume some structure for the graphs in which we seek to determine \(c\) , it is possible to prove upper bounds that are much lower.

For example, in the simplified Ramsey problem for triangle-free graphs much better quantitative bounds are known; see recent work of Bohman and Keevash [ 9 ] and Ajtai, Komlós and Szemerédi [ 5 ].

A useful strengthening of the notion of a subgraph is that of an induced subgraph : a graph obtained from another graph by deleting some of its vertices, and all their incident edges. Given a graph \(H\) , we denote by \(\mathcal{F}_{H}\) the class of graphs with no induced subgraph isomorphic to \(H\) . While random graphs have fairly large Ramsey numbers, as mentioned above, Erdős and Hajnal conjectured that in any class \(\mathcal{F}_{H}\) – which cannot contain large random graphs, in the sense that those contain every fixed \(H\) with probability tending to 1 as their size grows – Ramsey numbers restricted to that class are reasonably small:

Conjecture 3.2

Erdős-Hajnal Conjecture 1989

For all graphs \(H\) , there exists a constant \({ \delta _{H}>0}\) such that the \(n\) - vertex graphs in \(\mathcal{F}_{H}\) contain either a complete graph , or its complement , of size \(\Omega (n^{\delta _{H}})\) as an induced subgraph .

While there are a few theorems proving this conjecture for particular graphs \(H\) , this conjecture remains widely open; see Chudnowski’s survey [ 16 ] for details.

Probabilistic Method

There are many beautiful conjectures out there that only have one little problem: they are not true. And we all know that sometimes it can be hard to find a construction for a counterexample. The ‘Probabilistic Method’ provides a systematic way to produce counterexamples: rather than constructing a concrete counterexample explicitly, one proves that they occur with some positive probability and hence must exist. Over the years this method has been applied successfully to a large class of problems in combinatorics.

Let us start at the beginning, with a conjecture that is just too beautiful to be true. A colouring of a graph is an assignment of colours to its vertices such that adjacent vertices receive different colours. The chromatic number of a graph is the least number of colours required. For example, the complete graph \(K_{r}\) has chromatic number \(r\) , while trees – that is, connected graphs without cycles – have chromatic number two (to see this, pick a vertex of the tree, call it the root , and assign one colour to all vertices of even distance from the root and the other colour to the vertices of odd distance). Above we discussed the 4-Colour Theorem, which says that planar graphs have chromatic number at most four.

Assume our task is to colour a huge graph with a small number of colours and we are given colourings with just two colours of all connected subgraphs of some bounded size. One might imagine that there would be a ‘local-global principle’ allowing us to stick together the local colourings of the bounded-sized graphs to produce a global colouring with two colours – or perhaps, allowing for a small slack, with boundedly many colours, see Fig.  11 . In 1959 Erdős showed that such a strategy cannot work, by proving probabilistically the existence of a large class of counterexamples. He showed that for any number \(k\) , there are graphs of chromatic number \(k\) such that all connected subgraphs on at most \(k\) vertices are trees. Put another way, local 2-colourings of graphs cannot always be combined to global colourings with just boundedly many colours.

Although every path can be coloured by alternating between two colours, cycles of odd lengths cannot be coloured using only two colours. They are the simplest examples of graphs where local reasons alone do not determine the chromatic number

How do we randomly generate such a graph? In the simplest (Erdős-Renyi) model, we start with a set of \(n\) vertices and put in each possible edge with the same probability \(p\) – which may depend on \(n\) . With some abuse of terminology, we then say that a random graph has a particular property if the measure of the set of \(n\) -vertex graphs with that property in the resulting probability space \({\mathcal {G} }(n,p)\) tends to 1 as \(n\) tends to infinity, see Fig.  12 .

A graph on \(n=50\) vertices generated in such a way that every edge was added with probability \(p=\frac{1}{2}\) (source: [ 82 ]). It is unlikely that two graphs generated independently in this way are isomorphic. In contrast to this, any two random graphs on a countably infinite vertex set are isomorphic with probability one [ 1 , 30 , 71 ]

We can thus estimate probabilities for events like ‘containing no cycle of length at most \(k\) ’, or of ‘having chromatic number at least \(k\) ’. If both these probabilities were greater than one-half, then the existence of a graph with both properties is proved: the existence of a graph that is locally 2-colourable (because it contains no ‘short’ cycles) yet needs many ( \(>k\) ) colours globally. Unfortunately, in reality things are slightly more complicated; see [ 24 ] for the easy but beautiful details.

In our examples the probabilistic method was introduced to construct graphs with two properties simultaneously. In 1973, more than twenty years after the probabilistic method had been introduced to graph theory, Erdős and Lovász initiated a more systematic study of probabilistic constructions in combinatorics, as follows.

The Chernoff bound from Probability Theory is a commonly used tool to control the joint distribution of many random variables – as long as they are independent. However, in many potential applications in graph theory, we would like to control lots of events but they are not all independent. Still most of the pairs of these events are independent. In this situation, Erdős and Lovász decided to encode this information about the dependencies in a graph, and study which structural property of this dependency graph allow for a solution to all the constraints given by the events. More precisely, the Lovász Local Lemma says that given a family of events such that their dependency graph has maximum degree \(d\) and all these events occur with probability at most \(p\) such that \(ep(d+1)\leq 1\) (where \(e=2.7182\) ..), there is a positive probability that none of these events occurs.

For example, initially with the probabilistic method one was able to prove only the non-existence of a colouring with few colours, in contrast to this the Lovász Local Lemma can be used to prove the existence of such a colouring, significantly expanding the potential applications. In a nutshell, the probabilistic method grew from a useful tool to construct counterexamples to persistent conjectures, through Lovász’ contributions, to one of the key construction methods in the area of Probabilistic Algorithms. While new applications of the Lovász Local Lemma are still being discovered today, Moser and Tardos found a constructive version of the Lovász Local Lemma in 2010 [ 62 , 63 ].

Limits of Graphs

Given that many theorems in graph theory are asymptotic in nature, it is a natural step to study these problems through a suitable limit object. Asymptotic problems for dense graph classes – classes consisting of graphs whose number of edges is a constant fraction of all possible edges – are quite often studied through graphons , which are symmetric measurable functions from the unit square to the unit interval. Indeed, finite graphs can be represented by the following graphons \(W\) : partition the unit interval into equally sized segments \(I_{v}\) , one for each vertex \(v\) . Now define the graphon \(W(x,y)\) to be one if there is an edge between the vertices \(v\) and \(w\) satisfying \(x\in I_{v}\) and \(y\in I_{w}\) , and zero otherwise. Another example of a graphon is given in Fig.  13 .

A graphon is a function from the unit square to the unit interval. We draw them as a unit square, whose points are coloured black if they attain the value 1, white if they attain the value zero, and various shades of grey for all values in between. The graphon here represents the class of graphs that can be partitioned into two equally sized vertex sets such that all edges between them are present. In one of these vertex sets no edge is present. The other vertex set can be partitioned into two independent sets such that an edge between these sets is present with probability one half

Given a sequence of finite graphs, represented by graphons taking only the values zero and one, there is a suitable notion of a limit graphon, similar as the example of Fig.  13 , whose values represent densities from the unit interval obtained by averaging out vertex-adjacencies, roughly speaking; see the foundational book of Lovász [ 56 ] for details.

This way a whole class of graphs can be represented by a single graphon. For example, the graphon that takes constantly the value \(\frac{1}{2}\) represents the class of Erdős-Renyi random graphs, where edges are drawn with probability \(\frac{1}{2}\) . Graph parameters such as edge densities or numbers of triangles can be interpreted as integrals over graphons. This allows us to translate many problems from extremal graph theory into inequalities over multidimensional real-valued integrals.

This topological construction of graphons as limits is accompanied by algebraic constructions, see the flag algebra calculus of Razborov [ 73 ]. In some cases the automatisation of extremal problems through limits is at a level that parts of the problem solving can be done through computer search [ 74 ]. The theory of graphons is closely related to Szemerédi’s regularity lemma. For example, in this language the regularity lemma can be restated in the form that every arbitrary large graph can be approximated (in a suitably quantified way) by a graphon given by a partition of the unit square into boundedly many equally sized squares that is constant on all these partition classes.

Within this framework of graph limits, in 2016 Reiher proved his clique-density theorem, a far-reaching extension of Turán’s classical theorem, which for every natural number \(r\) determines the minimal number of complete graphs on \(r\) vertices that are contained in any graph with a given edge density [ 75 ]. This solved a conjecture of Lovász and Simonovits from the 1970s and extended earlier results of Razborov and Nikiforov. An important conjecture in this area that remains is the following. Given a graph \(H\) and a graph \(G\) , denote by \(t(H,G)\) , the ‘homomorphism density of \(H\) in \(G\) ’ – up to some low-order terms this is equal to the probability that if we pick a set of \(|V(H)|\) vertices of \(G\) at random that the subgraph of \(G\) spanned by these vertices has the graph \(H\) as a subgraph.

Conjecture 3.3

Sidorenko 1986 [ 86 ]

For any bipartite graph \(H\) and every graph \(G\) we have that :

Informally, this conjecture says that in every graph \(G\) , the edge-density \(t(K_{2},G)\) can be used lower-bound densities of arbitrary bipartite graphs \(H\) in the most natural way. In additional to his foundational contributions to the development of the theory of graphons, Lovász asked questions about them with the aim to determine the potential and boundaries of this approach, quite a few of them have been answered recently by Král’ et al. [ 23 , 40 ].

The theory of dense graphs can be used to solve problems in all types of areas, for example it can be applied in number theory to study arithmetic progressions in random subsets of the integers; see for example the works of Schacht [ 80 ] and Conlon and Gowers [ 22 ].

While the methods of graphons and flag algebras are tailored to dense classes of graphs, a theory of limits for sparser classes of graphs has not been fully developed yet [ 50 ].

Open Question 3.4

Can you develop a theory of limits of sparse graphs that provides a systematic framework to study a great variety of asymptotic questions on sparse graphs ?

One hope of such a theory of sparse graphs would be that it might provide tools to study Gromov’s question whether all finitely presented groups are sofic [ 38 ] through the Aldous-Lyons Conjecture [ 6 ], see [ 42 ]. For the emerging theory of sparse graphs see the book of Nešetřil and Ossana de Mendez [ 68 ]. The subfield of Structural Graph Theory that traditionally deals with problems of limits of graphs is called Infinite Graph Theory , which we explore in a separate paragraph below.

4 Highlights in Structural Graph Theory

Matchings, packings and coverings in graphs.

Graph theory is a fairly young mathematical discipline, many of whose foundational results were proved in the 1930s and 1940s. Now it has reached a stage with an abundance of applications in science and connections to other areas of mathematics, where its theorems accumulate and greater patterns between the theorems are recognised. Let me try to illustrate this by explaining four theorems answering four seemingly very different problems, and their common unification.

Firstly, given a graph \(G\) together with two vertex sets \(A\) and \(B\) , what is the largest size of a set of vertex-disjoint paths from \(A\) to \(B\) ? In 1927 Menger answered this question by proving that the largest cardinality of a set of vertex-disjoint paths from \(A\) to \(B\) is equal to the minimum size of a vertex set whose removal separates \(A\) from \(B\) [ 59 ]; note that it clearly cannot be larger, see Fig.  14 a.

Examples related to ( a ) Menger’s Theorem, ( b ) the Covering Theorem and ( c ) the Marriage Theorem, all special cases of the Packing Covering Theorem

Secondly, given a graph \(G\) , how many subtrees of \(G\) are necessary to cover all its edges? Note that when covering the edges of a (connected) graph with trees, we may as well assume that each of these trees contains all vertices of the graph; that is, it is a spanning tree . In 1964 Nash-Williams [ 65 ] answered that question by proving that the minimum number of trees necessary is no larger than the maximum local density of the graph – the largest ratio of the edges over vertices in any subgraph and which clearly is a lower bound since in trees this number is less than 1, see Fig.  14 b.

Thirdly, given a connected graph, what is the maximum number of pairwise edge-disjoint spanning trees? Nash-Williams and Tutte [ 64 , 91 ] answered this question by proving that this number is equal to the minimum local density of a contraction minor Footnote 6 (that is, a minor obtained by only contracting edges).

Fourth, in a small village, what is the maximum number of marriages that can be arranged between men and women, given a graph encoding the possible matchings? Formally, we are given a bipartite graph , a graph whose vertex set is partitioned into two classes such that all edges go between these classes; and we are interested in finding a set of vertex-disjoint Footnote 7 edges – such a set of edges is called a matching . In 1931 Kőnig answered this question by proving that the maximum size of a matching is equal to the minimum size of a vertex set covering all edges, see Fig.  14 c. Independently in 1935, Hall proved an equivalent result, which has been popularised as the ‘Marriage Theorem’. Most certainly it was clear at that time that matchings have numerous applications outside mathematics, for example in scheduling problems. An application within mathematics is a short combinatorial proof of the Cantor-Schröder-Bernstein Theorem in set theory. For details on the theory of matchings, we refer to the book of Lovász and Plummer [ 57 ].

Despite their differences, all these four theorems have the following unification [ 10 , 24 ]. Given a graph \(G\) and a natural number \(k\) , its edge set can be partitioned into a set \(P\) and a set \(C\) satisfying the following:

the graph \(G{\upharpoonright }P\) – the subgraph of \(G\) obtained by deleting the edges outside \(P\) – has \(k\) edge-disjoint spanning trees in each of its connected components. The edge set \(P\) is referred to as a packing ;

the graph \(G_{i}.C\) – the minor obtained from \(G\) by contracting the edges outside \(C\) – has a covering of its edge set by \(k\) trees. The edge set \(C\) is referred to as a covering .

Informally speaking, this theorem says that the edge set of any graph can be partitioned into a dense part, which admits a packing, and a sparse part that admits a covering. The Packing-Covering Theorem is the natural generalisation of this statement where one takes \(k\) matroids sharing a common ground set instead of a single graph \(G\) . While the reductions of the above four theorems from the Packing-Covering Theorem are automatic once we specify to which family of graphs (or matroids) we apply this theorem, the choice of a suitable family requires a little bit of thought.

Quite often in graph theory, people only consider finite graphs – it is the convention to always assume that graphs are finite unless stated explicitly that they are infinite. In the Packing-Covering Theorem allowing the set \(E\) to be infinite, one obtains the Packing-Covering Conjecture [ 10 ], which is still open; important special cases of this conjecture include the Aharoni-Berger Theorem from 2009 [ 4 ], which is an infinite analogue of Menger’s Theorem conjectured by Erdős in the 1960s, and it is a far-reaching extension of the Infinite Hall Theorem of Aharoni, Nash-Williams and Shelah from the 1980s. Quite recently Joó [ 7 ] made a big advance on the Packing-Covering Conjecture.

In its most general form, the Packing Covering Theorem is equivalent to the Matroid Intersection Theorem. This theorem expresses these ideas in terms of submodular rank functions; here a function \(f\) from the power set \(2^{E}\) of a set E to the reals is submodular if \(f(A)+f(B)\geq f(A\cup B)+f(A\cap B)\) for all \(A,B\subseteq E\) . The Lovász extension of a function \(f\) from \(2^{E}\) to the reals is the function \(\widehat{f}\) from the unit cube \([0,1]^{E}\) to the reals given by \(\widehat{f}(x)=\mathbb{E}[f(x_{\lambda })]\) , where the expectation is taken over the parameter \(\lambda \in [0,1]\) and \(x_{\lambda }\) is the binary vector that has a one in all coordinates where \(x\) has a value of at least \(\lambda \) [ 54 ]. This construction is designed so that the function f is submodular if and only if its extension \(\widehat{f}\) is convex. This established an important link with optimisation, allowing us to derive integral solutions for a large class of graph-theoretic problems through fractional relaxations thereof [ 39 ]. Another connection with the related field of Combinatorial Optimisation is described in the paragraph on perfect graphs below.

While the Packing-Covering Theorem gives us a good understanding of how to pack spanning trees in graphs, it is natural to try to pack other graphs. In Design Theory , we are given a large host graph \(G\) and a small graph \(F\) . The task is to partition the edge set of \(G\) into graphs all isomorphic to \(F\) . For simplicity we assume here that all the vertices of \(G\) and \(F\) have the same number of neighbours, and denote these numbers by \(d(G)\) and \(d(F)\) , respectively. For such a partition of the edge set \(G\) to exist, it is necessary that \(d(F)\) divides \(d(G)\) , and that the number of edges of \(F\) divides the number of edges of \(G\) . In this case we say that \(G\) is \(F\) -divisible . In 1853 Steiner conjectured that if \(G\) and \(F\) are both complete graphs such that \(G\) is \(F\) -divisible and \(G\) and \(F\) are sufficiently large, then the edge set of \(G\) can be partitioned into copies of \(F\) . In 2014 Keevash [ 47 ] announced a proof of this conjecture (in a more general form including Steiner triples, see Fig.  15 for details), which is widely believed to be correct though still under review. For general graphs this problem is widely open:

The fano plane is a Steiner-system with parameters \((7,3,2)\) ; here a Steiner-system with parameters \((n,q,r)\) is a set \(S\) of \(q\) -subsets of an \(n\) -set \(X\) , such that every \(r\) -subset of \(X\) belongs to exactly one element of \(S\) . Steiner-systems have applications in error-correcting codes

Conjecture 4.1

Nash-Williams 1970 [ 66 ], generalised by Gustavsson [ 41 ] beyond the case r=3

For every \(r\geq 3\) , there exists a constant \(n_{0}=n_{0}(r)\) such that every \(K_{r}\) - divisible graph \(G\) with \(n\geq n_{0}(r)\) vertices such that every vertex has at least \((1-\frac{1}{r+1})\cdot n\) neighbours admits a partition of its edge set into graphs all isomorphic to \(K_{r}\) .

See [ 37 ] by Glock, Kühn, Lo, Montgomery and Osthus for recent progress towards this conjecture.

Graph Minor Theory

Graph Minor Theory sits at the interface of topology and graph theory, with many algorithmic applications. An important aspect is the connection between embeddings of graphs in 2-dimensional surfaces and the minor relation. The discovery of this connection began in the 1930s when the pioneers Wagner, Kuratowski and Whitney characterised embeddability of graphs in the plane by completely combinatorial conditions [ 51 , 94 , 95 ] and this connection provided crucial tools for the proof of the Robertson–Seymour Theorem [ 76 ] in 2004, which is often regarded as the deepest theorem of combinatorics today. On one hand, the class of graphs embeddable in a fixed surface is closed under taking minors. This means that, like for Kuratowski’s Theorem, embeddability in a fixed surface can be characterised through the minor relation in terms of a list of minimal graphs that do not embed; such graphs are called excluded minors . The Robertson-Seymour theorem says that this list of excluded minors is finite for every minor-closed class of graphs. On the other hand, Robertson’s and Seymour’s structure theorem provides a topological construction for every minor-closed class of graphs; drastically oversimplifying, this theorem says that any minor-closed class of graphs can be built from classes of graphs embedded in a fixed surface by sticking them together in a tree-like way, see Fig.  16 .

A graph embedded in the torus. This embedding induces a toridal embedding of every minor of this graph

This theoretical breakthrough demonstrates the potential of the minor-theoretic approach. Still it seems like we are very much at the beginning of constructing Minor Theory , as the current machinery cannot be used to derive quite a few seemingly natural applications. For example, while Mohar proved that there is a linear time algorithm that verifies embeddability in a fixed surface [ 46 , 61 ] and the Robertson-Seymour theorem predicts that the class of graphs embeddable in a fixed surface is characterised by a finite list of excluded minors, computing this list explicitly for a fixed surface is a challenge – even for the simple surface of the torus this list is not known! Another example is Negami’s Conjecture on coverings of planar graphs from 1988 [ 67 ]. For Hadwiger’s Conjecture see the paragraph on ‘Graph Colouring’.

The spectral theorist Colin de Verdière, introduced the parameter \(\mu (G)\) . It originated from the study of the maximum multiplicity of the second eigenvalue of certain Schrödinger operators on Riemann surfaces [ 93 ]. A discretisation led to a graph-theoretic description of this quantity. Very roughly, \(\mu (G)\) is the largest co-rank of a class of generalised adjacency matrices satisfying a certain linear algebra property called the ‘Strong Arnol’d Property’. While this definition is purely given in terms of linear algebra, it can be shown that the class of graphs with \(\mu (G)\leq c\) for some constant \(c\) is closed under taking minors. So by the Robertson-Seymour Theorem the condition that ‘ \(\mu (G)\leq c\) ’ can be characterised by finitely many excluded minors and the structure theorem suggests that this class can be characterised in topological terms. For small values of \(c\) it has been shown that this is indeed the case, for example for \(c=3\) the class of graphs \(G\) with \(\mu (G)\leq c\) is equal to the class of planar graphs, while for \(c=4\) this class is the class of linklessly embeddable graphs. For \(c=5\) so far there is only a conjecture. We say that a graph \(G\) is 4-flat if the 2-complex obtained from \(G\) by gluing a disc onto each of its cycles is embeddable in 4-dimensional space (in a piece-wise linear way).

Conjecture 4.2

Van der Holst 2006 [ 92 ]

A graph is 4- flat if and only if \(\mu (G)\leq 5\) .

There are quite a few areas of Graph Minor Theory, where exciting new structural methods are being developed. For example, the dichotomy between tree-structure and highly connected clusters led to the Tangle-Tree Theorem, the Cops-and-Robbers Theorem, the Branch Width Theorem, and the Grid Theorem. The Grid Theorem [ 28 ] roughly says that for every number \(n\) there is a number \(t\) such that every graph can be constructed from graphs of size at most \(t\) by gluing them together along a tree or it has a 2-dimensional \(n\times n\) grid as a minor. Of particular interest in this dichotomy result between tree-structure and grid minors is the dependence between the parameters \(n\) and \(t\) ; recently it was proved by Chuzhoy et al. [ 15 , 20 ] that this dependence is polynomial.

A central aim in network theory is to identify ‘clusters’; that is, somewhat highly connected regions in networks. While clusters themselves are usually ‘fuzzy’ in the sense that it is hard to decide where they have their boundary exactly, this does not mean that they must have a fuzzy definition. One type of such clusters are tangles , which obey a precise mathematical axiomatisation and are key in Robertson’s and Seymour’s proof of their structure theorem to detect large grid minors. Diestel et al. developed a systematic theory of tangles [ 25 ] that can also be applied in areas outside Structural Graph Theory such as image recognition [ 26 , 27 , 29 ].

Finally, there are ideas – at various stages – to extend the theory beyond graphs. These include extensions to other natural relations on graphs such as vertex minors and pivot minors by Oum et al. [ 34 , 48 , 69 ], extensions to directed graphs by Archontia, Kawarabayashi, Kreutzer and Kwon [ 36 ], extensions to 2-dimensional simplicial complexes (see the paragraph on ‘Topological Graph Theory’ for details) and extensions to matroids, as follows.

Like the abstraction that came with a base point free axiomatisation of vector spaces deepened our understanding of linear algebra, matroids can be thought of as a ‘vertex-free’ abstraction of graphs. Matroids are fairly general objects which provide a unified way to understand cycles in graphs and linear dependences in vector spaces, which also captures more complicated algebraic constructions like those coming from field extensions [ 70 ]. An exciting conjecture in this area is Rota’s basis conjecture (not to be confused with Rota’s Well-quasi-ordering conjecture mentioned below); for an approach through extremal combinatorics, see [ 12 ] authored by Bucić, Kwan, Pokrovskiy and Sudakov.

Geelen, Gerards and Whittle announced their proof of Rota’s Well-quasi-ordering conjecture [ 35 ], a far-reaching extension of the Robertson-Seymour Theorem from graphs to matroids representable over finite fields – which can be thought of as a well-quasi ordering result for matrices over a fixed finite field, roughly speaking. Matroid Minor Theory is emerging as a research area of its own, which can be applied in coding theory as well as extremal matroid theory, see for example the growth rate theorem for matroids by Geelen and Nelson [ 32 , 33 ].

Graph Colouring

In Graph Colouring we study the chromatic number and related graph parameters, for example fractional relaxations thereof and inductive strengthenings like list-colourings as well as flows, which can be understood for plane graphs through the chromatic number of their plane dual, see Fig.  17 . While the proof of the 4-Colour Theorem in the 1970s resolved a long standing conjecture, during these investigations lots of related questions were asked, some of which go far beyond the 4-Colour Theorem and motivate a lot of research in the field of Graph Colouring till today. Examples include Thomassen’s theorem that planar graphs are 5-list colourable [ 89 ] or Tutte’s flow conjectures [ 24 ].

The vertices of the black graph \(K_{4}\) are assigned colours from the set \(\{0,1,2,3\}\) . The dual graph, which is also a \(K_{4}\) , is drawn in gray. The colouring of the black \(K_{4}\) induces a flow on the gray \(K_{4}\) , as follows. Each gray directed edge crosses a unique black edge. It is assigned the value of the left endvertex of that edge minus the value of the right endvertex of that edge, viewed from the crossing point in the direction of the gray edge. This is a flow on the gray graph as the amount flowing into each gray vertex is equal to the amount flowing out of it. Tutte’s duality theorem formalises a duality between colourings of plane graphs and flows in their duals. Through this duality, the 4-Colour Theorem can be restated as a theorem about the existence of certain flows in plane graphs. Tutte made various related conjectures about flows in graphs

Amongst such questions, Hadwiger’s conjecture – which seeks for a structural understanding of the chromatic number – has probably attracted the most attention. This development began in 1937 when Wagner proved that the 4-Colour Conjecture is equivalent to the statement a graph with no \(K_{5}\) -minor is 4-colourable [ 94 ], de-topologising the 4-Colour Conjecture. Inspired by this, Hadwiger made the following bold conjecture:

Conjecture 4.3

Hadwiger 1943

For all \(t\geq 0\) , every graph of chromatic number \(t\) has a complete graph \(K_{t}\) as a minor .

In 1993, Robertson, Seymour and Thomas proved the case \(t=5\) [ 77 ]. While this conjecture certainly belongs in the area of Structural Graph Theory, a hot topic are quantitative relaxations of this conjecture; so proving statements of the form, chromatic number \(f(t)\) implies a \(K_{t}\) -minor with the goal to eventually prove such a result for the function \(f(t)=t\) . See Seymour’s survey [ 85 ] for details.

Perfect Graphs

Quite a few important theorems in combinatorics can be stated in a min-max form; usually such theorems involve two parameters one of which is clearly bounded by the other, and the theorem says that these two parameters are equal. For example, Berge observed that in complements of bipartite graphs – that is, graphs whose vertex set can be partitioned into two complete graphs, the chromatic number is always equal to the clique number , the largest size of a complete subgraph. While the clique number is an obvious lower bound for the chromatic number, in the paragraph on the ‘Probabilistic Method’ we explained that in general the chromatic number can be much larger than the clique number. So Berge’s observation is an example of a min-max theorem.

Many min-max theorems can be proved through the duality theorem of linear programming; in such cases one of the parameters is determined by a linear maximisation problem and the other parameter can be described by the dual minimisation problem. In fact, Berge’s observation is of this form. There are many classes of graphs that allow for a min-max relation between clique number and chromatic number. In the 1960s Berge began to systematically study these classes.

Recall that an induced subgraph of a graph \(G\) is obtained by deleting a set of vertices and those edges with at least one endvertex in that set. We say that a graph \(G\) is perfect if in each of its induced subgraphs, the clique number is equal to the chromatic number, see Fig.  18 . For example, complements of bipartite graphs are perfect but also bipartite graphs themselves are perfect, as are chordal graphs – graphs such that all induced cycles have length three. Put another way, the class of perfect graphs is the class of those graphs such that they and all their induced subgraphs satisfy a min-max relation between clique number and chromatic number.

The complement of the 7-cycle. This graph has no \(K_{4}\) -subgraph, yet it is not 3-colourable. So this graph is not perfect

While min-max theorems tend to have connections with the duality theorem of linear programming, it is a priori not clear that the class of perfect graphs has pleasant algorithmic (or structural) properties. The theory of perfect graphs today answers the following questions. Is there a natural characterisation of the class of perfect graphs in terms of induced subgraphs? In view of the fact that determining the chromatic number of a graph is an NP-hard problem, is there a polynomial algorithm for perfect graphs? Can we recognise a perfect graph in polynomial time?

Recall that the complement of a graph \(G\) is obtained by flipping the adjacency between vertices; that is, the complement of \(G\) is a graph with the same vertex set where two vertices are adjacent if and only if they are not adjacent in \(G\) . Proving a conjecture of Berge in 1972, Lovász proved that a graph is perfect if and only if its complement is perfect. Given that the definition of perfect graphs is not symmetric under complementation, this may come as a surprise.

In [ 39 ], Grötschel, Lovász and Schrijver constructed a polynomial algorithm to determine the chromatic number of perfect graphs, as follows. In view of the fact that determining the chromatic number or the clique number are NP-hard problems for the class of all graphs, this is just another possibly unexpected aspect of perfect graphs. The key to this algorithm is the Lovász number Footnote 8 \(\theta (G)\) [ 53 ]. Lovász carefully designed this geometric graph parameter so that it is essentially ‘sandwiched’ between the clique number \(\omega (G)\) and the chromatic number \(\chi (G)\) ; in formulas \(\omega (G)\leq \theta (\overline{G})\leq \chi (G)\) , where \(\overline{G}\) is the complement of \(G\) . So for perfect graphs, the chromatic number can be computed through the Lovász number of the complement graph. One of the cornerstone results in Combinatorial Optimisation is the fact that the Lovász number can be computed through a semi-definite program, providing a polynomial algorithm to determine the chromatic number of perfect graphs.

Simple examples of graphs that are not perfect are cycles of odd length greater than three – and their complements. In 2006, Chudnovsky, Robertson, Seymour, and Thomas showed that these graphs actually characterise the class of perfect graphs, by showing that a graph is perfect if and only if neither it nor its complement contains an odd cycle of length at least five as an induced subgraph [ 18 ]. This is a far-reaching extension of Lovász’ theorem that complements of perfect graphs are perfect, and settles a conjecture of Berge. As part of this proof, the authors developed a structural decomposition theory for perfect graphs, which in turn was applied by Chudnovsky, Cornuéjols, Liu, Seymour and Vušković to construct a polynomial recognition algorithm for perfect graphs [ 17 ]. It is remarkable that so far it is still open to find a way how to use these decomposition tools to find a combinatorial algorithm to compute the chromatic number of perfect graphs; see [ 19 ] for recent progress in this direction.

Motivated by these successes, in recent years there was a significant interest in understanding graph classes where clique number and chromatic number are not necessarily equal but at least close in a quantified sense. A central conjecture in this area is the following.

Conjecture 4.4

Gyárfás–Sumner 1975

For every tree \(T\) and natural number \(r\) , there is a constant \(c\) such that every graph either contains \(T\) as an induced subgraph , or contains the complete graph \(K_{r}\) as an induced subgraph , or has chromatic number at most \(c\) .

If true, this conjecture would nicely complement the theorem that there are graphs of large chromatic number such that all bounded-size connected subgraphs are trees, discussed in the paragraph on the ‘Probabilistic Method’. In fact this would be a local-global principle for the chromatic number after all. For details, see the survey by Seymour and Scott [ 83 ].

Infinite Graph Theory

Recent breakthroughs in this area include the proof of the Erdős-Menger Conjecture by Aharoni and Berger in 2009 [ 4 ], Diestel’s topological principle which lifts theorems about finite graphs to topological statements about infinite graphs with ends, which climaxed in the solution of Rado’s problem by providing cryptomorphic axiomatisations of infinite matroids in terms of independent sets, cases, circuits, hyperplanes and rank [ 11 ]; and the subsequent development of a theory of infinite matroids by Bowler, Carmesin, Joó and others. An important conjecture in Infinite Graph Theory is that countable graphs are well-quasi ordered.

While there is no doubt that there is an abundance of natural challenges in the field of Infinite Graph Theory, I see the greatest potential for its development in the next decades in questions that apply Infinite Graph Theory in finite graphs.

Let me illustrate this by an example. Developments in science such as parallel computing and large networks motivate the study of local separators – vertex sets that separate graphs locally but not necessarily globally [ 14 ]. More precisely, we are interested in small vertex sets whose removal disconnected a subgraph of bounded radius, while outside that subgraph connections may still exist. The key idea in [ 14 ] is to define these local separators as those vertex sets that lift to separators of a suitable cover; this way they inherit submodularity properties and many structural decomposition theorems can be extended from separators to local separators, see Fig.  19 .

A finite graph covered by an infinite graph. Local separators of finite graphs can be defined through genuine separators of the cover; a local separator and its lift are highlighted in grey

There is a subtle, but important, difference to Diestel’s topological principle. While Diestel’s principle builds exciting problems concerning infinite graphs out of finite graph theory, we go the other way: harness the power of infinite graphs to study local behaviour in finite graphs. There is much to explore in this direction, for example it connects to Open Question  3.4 mentioned above in the paragraph on Graph Limits.

Topological Graph Theory

Above we have seen how the Probabilistic Method can be used to prove the existence of graphs with large chromatic number and large girth, and the 4-Colour Theorem and Hadwiger’s Conjecture are concerned with bounding the chromatic number for specific classes of graphs. Lovász developed a method going the other way round, employing algebraic topology to deduce that certain graph classes have high chromatic number. One such class is that of ‘Kneser-graphs’: given natural numbers \(n\) and \(k\) , the Kneser-graph \(K(n,k)\) has as its vertex set all \(k\) -subsets of an \(n\) -element set, where two vertices are adjacent if their sets are disjoint. M. Kneser conjectured that \(K(n,k)\) has chromatic number exactly \(n-2k + 2\) for \(n \geq 2 k\) .

Example 4.5

The Kneser graph \(K(5,2)\) is isomorphic to the Peterson-graph, see Fig.  1 .

Lovász’ approach is based on the following construction. Given a graph \(G\) , define the neighbourhood complex of \(G\) to be the simplicial complex that has the same vertex set as \(G\) , whose simplicies are those subsets that are contained in the neighbourhood of a single vertex of \(G\) . Lovász [ 52 ] proved if the neighbourhood complex is \(k\) -connected in the sense of homology theory, then the chromatic number of \(G\) is at least \(k-1\) . An application is the proof of the above mentioned conjecture of Kneser.

Since then a whole research area, usually referred to as Combinatorial Algebraic Topology , has grown out of these ideas, for details we refer to book of Kozlov [ 49 ], Babson and Kozlov [ 8 ] or Ziegler [ 98 ]. Aharoni and Berger extended these methods allowing them to study many more graph parameters than just colourings [ 3 ], and this work inspired them to propose a matroidal strengthening of Ryser’s conjecture [ 2 ].

In the 1930s Kuratowski, MacLane, Wagner and Whitney proved various characterisations of the topological property of embeddability of graphs in the plane through algebraic and combinatorial properties; a linear algorithm for testing planarity was discovered by Hopcroft and Tarjan [ 45 ] in 1974, and at the end of the 1970s several algorithms had been published that construct plane embeddings in linear time, see [ 58 ] for details. The higher dimensional analogue of this problem is to embed 2-dimensional simplicial complex into 3-dimensional space, see Fig.  20 .

The cone over \(K_{5}\) . The fact that the graph \(K_{5}\) does not embed in the plane lifts to the non-embeddability of the cone over \(K_{5}\) in 3-space

In his survey article on Graph Minor Theory, Lovász asked whether there is an analogue of graph minors in three dimensions. This was answered by Carmesin in 2017, who characterised embeddability of simply connected 2-dimensional simplicial complexes in 3-space in a way analogous to Kuratowski’s characterisation of graph planarity, by excluded minors. This characterisation also answered related questions of Pardon and Wagner. A tool in the proof is Perelman’s Theorem that any simply connected compact 3-manifold is isomorphic to the 3-sphere.

While Perelman’s Theorem is certainly a great advancement in mathematics, the algorithmic aspects of the Poincaré Conjecture remain open: is there a polynomial time algorithm that tests isomorphy with the 3-sphere for triangulated 3-manifolds? While existence of some algorithm was proved by Rubinstein [ 90 ], Footnote 9 Schleimer [ 81 ] strengthened this by showing that this problem lies in NP, and Zentner [ 97 ] showed that this problem lies in co-NP provided the generalised Riemann Hypothesis. An equivalent combinatorial version is the following:

Open Question 4.6

Is there a polynomial algorithm that tests embeddability in 3- dimensional space for the class of 2- dimensional simplicial complexes whose first homology group over the rationals is trivial ?

Without the assumption on the homology group, de Mesmay, Rieck, Sedgwick and Tancer [ 60 ] have shown that such a polynomial algorithm cannot exist. In contrast to this, if we strengthen the assumption requiring that the 2-complex is simply connected, the proof of Carmesin’s Kuratowski Theorem gives a quadratic time algorithm [ 13 ]. This algorithm relies on Perelman’s theorem. It would be desirable to have a combinatorial proof of Perelman’s Theorem. Towards this goal Rubinstein, a pioneer in computational topology, asked the following.

Open Question 4.7

Rubinstein [ 79 ]

Is there a robust notion of discrete curvature that allows for a discrete analogue of Ricci flow ?

In this survey, we made an attempt to explain what graph theory is by sketching some of its main lines of research. By doing so, we were forced to omit many exciting developments in graph theory. For example, an important problem at the interface of group theory, combinatorics and computer science is the graph isomorphism problem , which asks whether there is a polynomial time algorithm that decides whether two given graphs are isomorphic. Despite Babai’s recent subexponential time algorithm, it is not even known whether this problem is NP-hard. The \(P\neq NP\) -Conjecture is another problem that we did not explain here although there are many problems in graph theory that are known to be NP-complete, for example deciding whether a graph has a cycle that contains all its vertices [ 96 ].

6 László Lovász

In the past century, graph theory emerged as a new area of mathematics. We explained some of its fundamental ideas, its diverse links to other areas of mathematics, as well as today’s questions and challenges. Many of these challenges are foundational in nature and are motivated by recent developments in science, intrinsic questions or link to mysteries in other parts of mathematics. Today’s graph theorists owe the privilege to work in this exciting area of research to the hard work and deep insights of generations of graph theorists before. In particular László Lovász played a key role through his inspiring ideas, guiding the field. His main contributions include:

He played a leading role in the development of the Theory of Graphons, which allow us to solve many problems of extremal graph theory through this limit object. A prominent example is the clique density theorem of Reiher, which had been conjectured by Lovász and Simonovits a few decades before.

The Lovász Local Lemma (LLL) revolutionised Probabilistic Combinatorics, and is a fundamental result in the area of randomised algorithms.

His topological methods to compute the chromatic number of Kneser graphs were foundational to the field of Combinatorial Algebraic Topology.

Lovász developed sophisticated tools such as the Lovász Theta function and the Lovász extension of submodular functions. These connect to the ellipsoid method, a central result in optimization, whose applications to combinatorial optimisation were developed by Grötschel, Lovász and Schrijver.

The Lovász Theta function connects Combinatorial Optimisation with the theory of perfect graphs, to which Lovász also made important contributions.

He shaped mathematics as President of the International Mathematical Union (2007-2010) and President of the Hungarian Academy of Sciences (2014-2020).

Beyond solving hard problems, he also wrote comprehensive text books on cutting edge research areas making them accessible to a much broader audience, for example his book ‘Large networks and graph limits’ or the book on Matching Theory with Plummer.

Lovász is known for his inspiring questions and conjectures. For example his question on a 3-dimensional graph minor theory is foundational to the development of 3-dimensional Combinatorics. Another puzzle of his is the Erdős-Lovász-Faber conjecture, which has recently been proved by Kang, Kelly, Kühn, Methuku and Osthus.

7 Further Reading

Diestel’s textbook ‘ Graph Theory ’ is an excellent introduction to the topic, which also treats some of its advanced methods in later chapters.

Bass-Serre theory is a subfield of combinatorial group theory that deals with analysing groups acting by automorphisms on trees. Tools in this area allow us to detect free products with amalgamation or HHN-extensions.

An edge set is connected if any two of their endvertices can be joined by a path.

In Graph Minor Theory, the term ‘graph’ is used for ‘multigraphs’, while ‘graphs’ as we defined them here are referred to as ‘simple graphs’.

Formally, a problem has a good characterisation if it is in the complexity class \(\text{NP}\cap \text{co-NP}\) [ 24 , 55 , 96 ].

Given functions \(f\) and \(g\) , we write \(g=\theta (f)\) as a shorthand for: there are constants \(a\) and \(b\) such that \(a\cdot f\leq g\leq b\cdot f\) .

There is a variant of this theorem with ‘contraction minor’ replaced by ‘quotient’ [ 24 ]. These two versions are clearly equivalent.

We say that a set of edges is vertex-disjoint if no two edges in that set share a vertex.

Sometimes the Lovász number is also called the Lovász theta-function .

See for example [ 81 ] for details on the history.

Ackermann, W.: Die widerspruchsfreiheit der allgemeinen mengenlehre. Math. Ann. 114 (1), 305–315 (1937)

Article   MathSciNet   MATH   Google Scholar  

Aharoni, R.: Ryser’s conjecture for tripartite 3-graphs. Combinatorica 21 (1), 1–4 (2001)

Aharoni, R., Berger, E.: The intersection of a matroid and a simplicial complex. Trans. Am. Math. Soc. 358 (11), 4895–4917 (2006)

Aharoni, R., Berger, E.: Menger’s theorem for infinite graphs. Invent. Math. 176 , 1–62 (2009)

Ajtai, M., Komlós, J., Szemerédi, E.: A note on Ramsey numbers. J. Comb. Theory, Ser. A 29 (3), 354–360 (1980)

Aldous, D., Lyons, R.: Processes on unimodular random networks. Electron. J. Probab. 12 , 1454–1508 (2007)

Attila, J.: Proof of Nash-Williams’ intersection conjecture for countable matroids. Adv. Math. 380 , 107608 (2021)

Babson, E., Kozlov, D.N.: Proof of the Lovász conjecture. Ann. Math., 965–1007 (2007)

Bohman, T., Keevash, P.: The early evolution of the h-free process. Invent. Math. 181 (2), 291–336 (2010)

Bowler, N., Carmesin, J.: Matroid intersection, base packing and base covering for infinite matroids. Combinatorica 35 (2), 153–180 (2015)

Bruhn, H., Diestel, R., Kriesell, M., Pendavingh, R., Wollan, P.: Axioms for infinite matroids. Adv. Math. 239 , 18–46 (2013)

Bucić, M., Kwan, M., Pokrovskiy, A., Sudakov, B.: Halfway to rota’s basis conjecture. Int. Math. Res. Not. 2020 (21), 8007–8026 (2020)

Carmesin, J.: Embedding simply connected 2-complexes in 3-space – V. A refined Kuratowski-type characterisation. Preprint 2017. Available at https://arxiv.org/pdf/1709.04659.pdf

Carmesin, J.: Local 2-separators. Preprint. Available at http://web.mat.bham.ac.uk/J.Carmesin/

Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. J. ACM 63 (5), 40, 65 pp. (2016)

Chudnovsky, M.: The Erdös–Hajnal conjecture – a survey. J. Graph Theory 75 (2), 178–190 (2014)

Chudnovsky, M., Cornuéjols, G., Liu, X., Seymour, P., Vušković, K.: Recognizing Berge graphs. Combinatorica 25 , 143–186 (2005)

Chudnovsky, M., Robertson, N., Seymour, P., Thomas, R.: The strong perfect graph theorem. Ann. Math., 51–229 (2006)

Chudnovsky, M., Lagoutte, A., Seymour, P., Spirkl, S.: Colouring perfect graphs with bounded clique number. J. Comb. Theory, Ser. B 122 , 757–775 (2017)

Chuzhoy, J., Tan, Z.: Towards tight(er) bounds for the excluded grid theorem. J. Comb. Theory, Ser. B 146 , 219–265 (2021)

Conlon, D.: A new upper bound for diagonal Ramsey numbers. Ann. Math., 941–960 (2009)

Conlon, D., Gowers, W.T.: Combinatorial theorems in sparse random sets. Ann. Math., 367–454 (2016)

Cooper, J.W., Král’, D., Martins, T.L.: Finitely forcible graph limits are universal. Adv. Math. 340 , 819–854 (2018)

Diestel, R.: Graph Theory, 5th edn. Springer, Berlin (2017). Electronic edition available at: http://diestel-graph-theory.com/index.html

Book   MATH   Google Scholar  

Diestel, R.: Abstract separation systems. Order 35 (1), 157–170 (2018)

Diestel, R.: Tangles in the social sciences. arXiv preprint. 1907.07341 (2019)

Diestel, R., Oum, S.-i.: Tangle-tree duality in abstract separation systems. Adv. Math., 107470 (2020)

Diestel, R., Jensen, T.R., Gorbunov, K.Yu., Thomassen, C.: Highly connected sets and the excluded grid theorem. J. Comb. Theory, Ser. B 75 (1), 61–73 (1999)

Elbracht, C., Fioravanti, D., Klepper, S., Kneip, J., Rendsburg, L., Teegen, M., von Luxburg, U.: Tangles: from weak to strong clustering. arXiv preprint. arXiv:2006.14444 (2020)

Erdos, P., Rényi, A.: Asymmetric graphs. Acta Math. Acad. Sci. Hung. 14 (295–315), 15 (1963)

MathSciNet   MATH   Google Scholar  

Freudenthal, H.: Neuaufbau der Endentheorie. Ann. Math. 43 , 261–279 (1942)

Geelen, J., Nelson, P.: On minor-closed classes of matroids with exponential growth rate. Adv. Appl. Math. 50 (1), 142–154 (2013)

Geelen, J., Nelson, P.: The densest matroids in minor-closed classes with exponential growth rate. Trans. Am. Math. Soc. 369 (9), 6751–6776 (2017)

Geelen, J., Oum, S.-i.: Circle graph obstructions under pivoting. J. Graph Theory 61 (1), 1–11 (2009)

Geelen, J., Gerards, B., Whittle, G.: Solving Rota’s conjecture. Not. Am. Math. Soc. 61 (7), 736–743 (2014)

Giannopoulou, A.C., Kawarabayashi, K.-i., Kreutzer, S., Kwon, O.-j.: The directed flat wall theorem. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 239–258. SIAM, Philadelphia (2020)

Chapter   Google Scholar  

Glock, S., Kühn, D., Lo, A., Montgomery, R., Osthus, D.: On the decomposition threshold of a given graph. J. Comb. Theory, Ser. B 139 , 47–127 (2019)

Gromov, M.: Endomorphisms of symbolic algebraic varieties. J. Eur. Math. Soc. 1 (2), 109–197 (1999)

Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization, vol. 2. Springer, Berlin (2012)

MATH   Google Scholar  

Grzesik, A., Král, D., Lovász, L.M.: Elusive extremal graphs. Proc. Lond. Math. Soc. 121 (6), 1685–1736 (2020)

Gustavsson, T.: Decompositions of large graphs and digraphs with high minimum degree. PhD thesis, Univ. (1991)

Hatami, H., Lovász, L., Szegedy, B.: Limits of locally–globally convergent graph sequences. Geom. Funct. Anal. 24 (1), 269–296 (2014)

He, Z.-X., Schramm, O.: Hyperbolic and parabolic packings. Discrete Comput. Geom. 14 (2), 123–149 (1995)

He, Z.-X., Schramm, O.: On the convergence of circle packings to the Riemann map. Invent. Math. 125 (2), 285–305 (1996)

Hopcroft, J., Tarjan, R.: Efficient planarity testing. J. ACM 21 (4), 549–568 (1974)

Kawarabayashi, K.-i., Mohar, B., Reed, B.: A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pp. 771–780. IEEE (2008)

Keevash, P.: The existence of designs. arXiv preprint. 1401.3665 (2014)

Kim, R., Kwon, O.-j., Oum, S.-i., Sivaraman, V.: Classes of graphs with no long cycle as a vertex-minor are polynomially \(\chi \) -bounded. J. Comb. Theory, Ser. B 140 , 372–386 (2020)

Kozlov, D.: Combinatorial Algebraic Topology, vol. 21. Springer, Berlin (2008)

Kunszenti-Kovács, D., Lovász, L., Szegedy, B.: Measures on the square as sparse graph limits. J. Comb. Theory, Ser. B 138 , 1–40 (2019)

Kuratowski, K.: Sur le probleme des courbes gauches en topologie. Fundam. Math. 15 (1), 271–283 (1930)

Lovász, L.: Kneser’s conjecture, chromatic number, and homotopy. J. Comb. Theory, Ser. A 25 (3), 319–324 (1978)

Lovász, L.: On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25 (1), 1–7 (1979)

Lovász, L.: Submodular functions and convexity. In: Mathematical Programming the State of the Art, pp. 235–257. Springer, Berlin (1983)

Lovász, L.: Combinatorial Problems and Exercises, vol. 361. Am. Math. Soc., Providence (2007)

Lovász, L.: Large Networks and Graph Limits, vol. 60. Am. Math. Soc., Providence (2012)

Lovász, L., Plummer, M.D.: Matching Theory, vol. 367. Am. Math. Soc., Providence (2009)

Mehlhorn, K., Mutzel, P.: On the embedding phase of the hopcroft and Tarjan planarity testing algorithm. Algorithmica 16 (2), 233–242 (1996)

Menger, K.: Zur allgemeinen Kurventheorie. Fundam. Math. 10 (1), 96–115 (1927)

Article   MATH   Google Scholar  

de Mesmay, A., Rieck, Y., Sedgwick, E., Tancer, M.: Embeddability in R3 is NP-hard. J. ACM 67 (4), 1–29 (2020)

Mohar, B.: A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math. 12 (1), 6–26 (1999)

Moser, R.A.: A constructive proof of the Lovász local lemma. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 343–350 (2009)

Moser, R.A., Tardos, G.: A constructive proof of the general Lovász local lemma. J. ACM 57 (2), 1–15 (2010)

Nash-Williams, C.St.J.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 1 (1), 445–450 (1961)

Nash-Williams, C.St.J.A.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. 1 (1), 12 (1964)

Nash-Williams, C.St.J.A.: An unsolved problem concerning decomposition of graphs into triangles combinatorial theory and its applications III. P. Erdös, P. Rényi and V.T. Sós (eds.) (1970)

Negami, S.: The spherical genus and virtually planar graphs. Discrete Math. 70 (2), 159–168 (1988)

Nešetřil, J., Ossona de Mendez, P.: Sparsity: Graphs, Structures, and Algorithms. Springer, Berlin (2012)

Oum, S.-i.: Rank-width and vertex-minors. J. Comb. Theory, Ser. B 95 (1), 79–100 (2005)

Oxley, J.: Matroid Theory, 2nd edn. Oxford University Press, London (2011)

Rado, R.: Universal graphs and universal functions. Acta Arith. 9 (4), 331–340 (1964)

Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. 2 (1), 264–286 (1930)

Razborov, A.A.: Flag algebras. J. Symb. Log. 72 (4), 1239–1282 (2007)

Razborov, A.A.: Flag algebras: an interim report. In: The Mathematics of Paul Erdős II, pp. 207–232. Springer, Berlin (2013)

Reiher, C.: The clique density theorem. Ann. Math., 683–707 (2016)

Robertson, N., Seymour, P.D.: Graph minors. XX. Wagner’s conjecture. J. Comb. Theory, Ser. B 92 (2), 325–357 (2004)

Robertson, N., Seymour, P., Thomas, R.: Hadwiger’s conjecture for K6-free graphs. Combinatorica 13 (3), 279–361 (1993)

Rodin, B., Sullivan, D.: The convergence of circle packings to the Riemann mapping. J. Differ. Geom. 26 (2), 349–360 (1987)

Rubinstein, J.H.: Problems around 3-manifolds. In: Workshop on Heegaard Splittings. Geom. Topol. Monogr., vol. 12, pp. 285–298 (2007)

Google Scholar  

Schacht, M.: Extremal results for random discrete structures. Ann. Math., 333–365 (2016)

Schleimer, S.: Sphere recognition lies in np. In: Low-Dimensional and Symplectic Topology, vol. 82, pp. 183–213 (2011)

Schmidt, D.R., Thomas, P.J.: Measuring edge importance: a quantitative analysis of the stochastic shielding approximation for random processes on graphs. J. Math. Neurosci. 4 (1), 1–52 (2014). Available at https://www.researchgate.net/publication/261755434

Scott, A., Seymour, P.: A survey of \(\chi \) -boundedness. J. Graph Theory 95 (3), 473–504 (2020)

Article   MathSciNet   Google Scholar  

Serre, J.-P.: Trees. Springer, Berlin (1980). (Translated from the French by John Stillwell.)

Seymour, P.: Hadwiger’s conjecture. In: Open Problems in Mathematics, pp. 417–437. Springer, Berlin (2016)

Sidorenko, A.: A correlation inequality for bipartite graphs. Graphs Comb. 9 (2), 201–204 (1993)

Spencer, J.: Ramsey’s theorem—a new lower bound. J. Comb. Theory, Ser. A 18 (1), 108–115 (1975)

Stallings, J.R.: On torsion-free groups with infinitely many ends. Ann. Math., 312–334 (1968)

Thomassen, C.: Every planar graph is 5-choosable. J. Comb. Theory, Ser. B 62 (1), 180–181 (1994)

Thompson, A.: Thin position and the recognition problem for \(S^{3}\) . Math. Res. Lett. 1 (5), 613–630 (1994)

Tutte, W.T.: Graph Theory as I Have Known It, vol. 11. Oxford University Press, London (1998)

van der Holst, H.: Graphs and obstructions in four dimensions. J. Comb. Theory, Ser. B 96 (3), 388–404 (2006)

Van Der Holst, H., Lovász, L., Schrijver, A., et al.: The Colin de Verdiere graph parameter. In: Graph Theory and Computational Biology, Balatonlelle, 1996, pp. 29–85 (1999)

Wagner, K.: Über eine Eigenschaft der ebenen Komplexe. Math. Ann. 114 (1), 570–590 (1937)

Whitney, H.: Non-separable and planar graphs. Trans. Am. Math. Soc. 34 , 339–362 (1932)

Wigderson, A.: Mathematics and Computation. Princeton University Press, Princeton (2019)

Zentner, R.: Integer homology 3-spheres admit irreducible representations in sl(2,c). Duke Math. J. 167 (9), 1643–1712 (2018)

Ziegler, G.M.: Generalized Kneser coloring theorems with combinatorial proofs. Invent. Math. 147 (3), 671–691 (2002)

Download references

Author information

Authors and affiliations.

University of Birmingham, Birmingham, UK

Johannes Carmesin

You can also search for this author in PubMed   Google Scholar

Additional information

Publisher’s note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Carmesin, J. Graph Theory – A Survey on the Occasion of the Abel Prize for László Lovász. Jahresber. Dtsch. Math. Ver. 124 , 83–108 (2022). https://doi.org/10.1365/s13291-022-00247-7

Download citation

Accepted : 21 February 2022

Published : 24 March 2022

Issue Date : June 2022

DOI : https://doi.org/10.1365/s13291-022-00247-7

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Find a journal
• Publish with us
• Track your research

Click through the PLOS taxonomy to find articles in your field.

For more information about PLOS Subject Areas, click here .

Loading metrics

Open Access

Peer-reviewed

Research Article

Recent Developments in Quantitative Graph Theory: Information Inequalities for Networks

* E-mail: [email protected]

Affiliation Institute for Bioinformatics and Translational Research, UMIT, Hall in Tyrol, Austria

• Matthias Dehmer, 
• Lavanya Sivakumar

• Published: February 15, 2012
• https://doi.org/10.1371/journal.pone.0031395
• Reader Comments

In this article, we tackle a challenging problem in quantitative graph theory. We establish relations between graph entropy measures representing the structural information content of networks. In particular, we prove formal relations between quantitative network measures based on Shannon's entropy to study the relatedness of those measures. In order to establish such information inequalities for graphs, we focus on graph entropy measures based on information functionals. To prove such relations, we use known graph classes whose instances have been proven useful in various scientific areas. Our results extend the foregoing work on information inequalities for graphs.

Citation: Dehmer M, Sivakumar L (2012) Recent Developments in Quantitative Graph Theory: Information Inequalities for Networks. PLoS ONE 7(2): e31395. https://doi.org/10.1371/journal.pone.0031395

Editor: Frank Emmert-Streib, Queen's University Belfast, United Kingdom

Received: December 2, 2011; Accepted: January 6, 2012; Published: February 15, 2012

Copyright: © 2012 Dehmer, Sivakumar. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Funding: Matthias Dehmer and Lavanya Sivakumar thank the Austrian Science Fund (Project No. PN22029-N13) for supporting this work. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.

Competing interests: The authors have declared that no competing interests exist.

Introduction

Complexity is an intricate and versatile concept that is associated with the design and configuration of any system [1] , [2] . For example, complexity can be measured and characterized by quantitative measures often called indices [3] – [5] . When studying the concept of complexity, information theory has been playing a pioneering and leading role. Prominent examples are the theory of communication and applied physics where the famous Shannon entropy [6] has extensively been used. To study issues of complexity in natural sciences and, in particular, the influence and use of information theory, see [7] .

In this paper, we deal with an important aspect when studying the complexity of network-based systems. In particular, we establish relations between information-theoretic complexity measures [3] , [8] – [11] . Recall that such entropic measures have been used to quantify the information content of the underlying networks [8] , [12] . Generally, this relates to exploring the complexity of a graph by taking its structural features into account. Note that numerous measures have been developed to study the structural complexity of graphs [5] , [8] , [13] – [22] . Further, the use and ability of the measures has been demonstrated by solving interdisciplinary problems. As a result, such studies have led to a vast number of contributions dealing with the analysis of complex systems by means of information-theoretic measures, see, e.g., [8] , [13] – [22] . Figure 1 shows a classification scheme of quantitative network measures exemplarily.

• PPT PowerPoint slide
• PNG larger image
• TIFF original image

https://doi.org/10.1371/journal.pone.0031395.g001

The main contribution of this paper is to study relations between entropy measures. We will tackle this problem by means of inequalities involving network information measures. In particular, we study so-called implicit information inequalities which have been introduced by Dehmer et al. [23] , [24] for studying graph entropies using information functionals. Generally, an implicit information inequality involves information measures which are present on either side of the inequality. It is important to emphasize that relatively little work has been done to investigate relations between network measures. A classical contribution in this area is due to Bonchev et al. [25] . Here, the relatedness between information-theoretic network measures has been investigated to detect branching in chemical networks. Further, implicit information inequalities have been studied for hierarchical graphs which turned out to be useful in network biology [26] .

In this section, we briefly state the concrete definitions of the information-theoretic complexity measures that are used for characterizing complex network structures [3] , [6] , [9] , [27] . Here we state measures based on two major classifications namely partition-based and partition-independent measures and deal mainly with the latter.

In the context of theory of communication, the above equation is called as Shannon equation of information [28] .

In order to define concrete graph entropies, we reproduce the definitions of some information functionals based on metrical properties of graphs [3] , [9] , [27] .

Remark 3 Note that centrality is an important concept that has been introduced for analyzing social networks [29] , [30] . Many centrality measures have been contributed [30] , and in particular, various definitions for closeness centrality [30] – [32] . We remark that the above definition has been firstly defined by Sabidussi [31] for arbitrary graphs. However, we use the measure as a local invariant defined on the subgraphs induced by the local information graph [9] .

Results and Discussion

Closed form expressions and explicit information inequalities.

When calculating the structural information content of graphs, it is evident that the determination of closed form expressions using arbitrary networks is critical. In this section, we consider simple graphs namely trees with smallest and largest diameter and compute the measures defined in the previous section. By using arbitrary connected graphs, we also derive explicit information inequalities using the measures based on information functionals (stated in the previous section).

Now, we present closed form expressions for the graph entropy by using star graphs. For this, we apply the information-theoretic measures based on information functionals defined in the preliminaries section.

General connected graphs.

In the next theorem, we obtain explicit bounds when using the information functional given by Equation (6).

Let us distinguish two cases:

Implicit Information Inequalities

Proof: Follows from Corollary (9).

Union of Graphs.

Join of Graphs.

Further, an alternate set of bounds can be achieved as follows.

Summary and Conclusion

In this article, we have investigated a challenging problem in quantitative graph theory namely to establish relations between graph entropy measures. Among the existing graph entropy measures, we have considered those entropies which are based on information functionals. It turned out that these measures have widely been applicable and useful when measuring the complexity of networks [3] .

In general, to find relations between quantitative network measures is a daunting problem. The results could be used in various branches of science including mathematics, statistics, information theory, biology, chemistry and social sciences. Further, the determination of analytical relations between measures is of great practical importance when dealing with large scale networks. Also, relations involving quantitative network measures could be fruitful when determining the information content of large complex networks.

Note that our proof technique follows the one proposed in [23] . It is based on three main steps: Firstly, we compute the information functionals and in turn, we calculate the probability values for every vertex of the graph in question. Secondly, we start with certain conditions for the computed functionals and arrive at a system of inequalities. Thirdly, by adding up the corresponding inequality system, we obtain the desired implicit information inequality. Using this approach, we have inferred novel bounds by assuming certain information functionals. It is evident that further bounds could be inferred by taking novel information functionals into account. Further, we explored relations between the involved information measures for general connected graphs and for special classes of graphs such as stars, path graphs, union and join of graphs.

As noted earlier, relations between entropy-based measures for graphs have not been extensively explored so far. Apart from the results we have gained in this paper, we therefore state a few open problems as future work:

• To find relations between measures based on information functionals and the other classical graph measures.
• To derive information inequalities for graph entropy measures using random graphs.
• To derive statements to judge the quality of information inequalities.

Author Contributions

Wrote the paper: MD LS. Performed the mathematical analysis: MD LS.

• 1. Basak SC (1999) Information-theoretic indices of neighborhood complexity and their applications. In: Devillers J, Balaban AT, editors. Topological Indices and Related Descriptors in QSAR and QSPAR, Gordon and Breach Science Publishers. pp. 563–595. Amsterdam, The Netherlands.
• 2. Wang J, Provan G (2009) Characterizing the structural complexity of real-world complex networks. In: Zhou J, editor. pp. 1178–1189. Complex Sciences, Springer, Berlin/Heidelberg, Germany, volume 4 of Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering .
• View Article
• Google Scholar
• 4. Li M, Vitányi P (1997) An Introduction to Kolmogorov Complexity and Its Applications. Springer.
• 7. Bonchev D, Rouvray DH (2003) Complexity in chemistry: Introduction and Fundamentals. Mathematical and Computational Chemistry 7. New York: CRC Press.
• 8. Bonchev D (1983) Information Theoretic Indices for Characterization of Chemical Structures. Research Studies Press, Chichester.
• 12. Bonchev D (2003) Complexity in Chemistry. Introduction and Fundamentals. Taylor and Francis. Boca Raton, FL, USA.
• 17. Bertz SH (1983) A mathematical model of complexity. In: King R, editor. pp. 206–221. Chemical applications of topology and graph theory, Elsevier, Amsterdam.
• 19. Bonchev D, Rouvray DH (2005) Complexity in chemistry, biology, and ecology. Mathematical and Computational Chemistry. New York: Springer. pp xx+344. doi: https://doi.org/http://dx.doi.org/10.1007/b136300 .
• 21. Körner J (1973) Coding of an information source having ambiguous alphabet and the entropy of graphs. pp. 411–425. Trans 6th Prague Conference on Information Theory.
• 28. Shannon C, Weaver W (1997) The Mathematical Theory of Communication. University of Illinois Press, Urbana, IL, USA.
• 33. Simonyi G (1995) Graph entropy: A survey. In: Cook W, Lovász L, Seymour P, editors. pp. 399–441. Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 20.
• 34. Emmert-Streib F, Dehmer M, Kilian J, et al HRA, editor (2006) Classification of large graphs by a local tree decomposition. pp. 477–482. Proceedings of DMIN'05, International Conference on Data Mining, Las Vegas, USA.

Help | Advanced Search

Mathematics > Combinatorics

Title: reinforcement learning for graph theory, i. reimplementation of wagner's approach.

Abstract: We reimplement here the recent approach of Adam Zsolt Wagner [ arXiv:2104.14516 ], which applies reinforcement learning to construct (counter)examples in graph theory, in order to make it more readable, more stable and much faster. The presented concepts are illustrated by constructing counterexamples for a number of published conjectured bounds for the Laplacian spectral radius of graphs.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

An official website of the United States government

The .gov means it’s official. Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

The site is secure. The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

• Publications
• Account settings

Preview improvements coming to the PMC website in October 2024. Learn More or Try it out now .

• Advanced Search
• Journal List
• Dialogues Clin Neurosci
• v.20(2); 2018 Jun

Language: English | Spanish | French

Graph theory methods: applications in brain networks

Métodos de la teoría de grafos: aplicaciones en las redes cerebrales, méthode de la théorie des graphes et ses applications dans les réseaux cérébraux, olaf sporns.

Department of Psychological and Brain Sciences, Indiana University, Bloomington, Indiana, USA; IU Network Science Institute, Indiana University, Bloomington, Indiana, USA

Network neuroscience is a thriving and rapidly expanding field. Empirical data on brain networks, from molecular to behavioral scales, are ever increasing in size and complexity. These developments lead to a strong demand for appropriate tools and methods that model and analyze brain network data, such as those provided by graph theory. This brief review surveys some of the most commonly used and neurobiologically insightful graph measures and techniques. Among these, the detection of network communities or modules, and the identification of central network elements that facilitate communication and signal transfer, are particularly salient. A number of emerging trends are the growing use of generative models, dynamic (time-varying) and multilayer networks, as well as the application of algebraic topology. Overall, graph theory methods are centrally important to understanding the architecture, development, and evolution of brain networks.

La neurociencia de la red es un campo próspero y de rápida expansión. Los datos empíricos sobre las redes cerebrales, desde niveles moleculares hasta niveles conductuales, son cada vez más grandes en tamaño y complejidad. Estos desarrollos llevan a una fuerte demanda de herramientas y métodos apropiados que modelen y analicen los datos de la red cerebral, como los proporcionados por la teoría de grafos. Esta breve revisión examina algunas de las medidas y técnicas gráficas más comúnmente empleadas y neurobiológicamente más discriminadoras. Entre estas, son particularmente importantes la detección de módulos o comunidades de redes, y la identificación de elementos de redes centrales que facilitan la comunicación y la transferencia de señales. Algunas tendencias emergentes son el empleo creciente de modelos generativos, de redes dinámicas (de tiempo variable) y de multicapa, así como la aplicación de topología algebraica. En general, los métodos de la teoría de grafos son especialmente importantes para comprender la arquitectura, el desarrollo y la evolución de las redes cerebrales.

La neuroscience des réseaux est un domaine florissant qui s'étend rapidement. Les données empiriques sur les réseaux cérébraux, de l'échelle moléculaire à comportementale, ne cessent d'augmenter en volume et en complexité. Ces développements génèrent une demande forte d'outils et de méthodes appropriés pour modéliser et analyser les données des réseaux cérébraux, comme celles fournies par la théorie des graphes. Dans cette rapide analyse, nous examinons certaines des techniques et mesures de graphes les plus couramment utilisées et les plus signifiantes neurobiologiquement. Parmi elles, la détection des modules ou communautés de réseaux et l'identification des éléments de réseau central qui facilite la communication et le transfert du signal, sont particulièrement marquantes. Dans les tendances émergentes, on note l'utilisation croissante de modèles génératifs, dynamiques (variables avec le temps) et les réseaux multi-couches, ainsi que l'application de la topologie algébrique. Globalement, les méthodes de la théorie des graphes sont essentielles pour comprendre l'architecture, le développement et l'évolution des réseaux cérébraux.

Introduction

Some of the most daunting scientific challenges of the 21 st century involve complex social, technological, and biological systems—from the stability of global financial and economic networks to the spreading of epidemics, the web of biotic interactions in an ecosystem, and metabolic and transcriptional processes inside cells and tissues. An important theoretical foundation for understanding complexity is network science, 1 - 3 which focuses on the structure and function of systems that are composed of numerous elements and their interactions. Over the past couple of decades, the network perspective has gained considerable ground in neuroscience. 4 - 11 Brain networks have become a fertile area of research, now called network neuroscience, ranging across different scales, from interacting biomolecules all the way to social behavior. A major driving force has been the application of mathematical and computational network science tools to neurobiological systems, especially models and measures of graph theory. 1 , 5 , 9

Graph theory is a branch of mathematics that dates back to the 18 th century. Today, applications of graph theory pervade all scientific disciplines as well as many modern information and computing technologies. The brain is a natural fit for graph theory approaches as it is readily represented as a network (a graph) of elements and their pairwise interconnections, also called nodes and edges. Comprehensive maps of brain connectivity have given rise to the emerging field of connectomics, 12 , 13 a central focus of which is the systematic and quantitative study of brain networks and graphs.

Graph theory methods, when applied properly, can offer important new insights into the structure and function of networked brain systems, including their architecture, evolution, development, and clinical disorders. This brief review surveys some of the most relevant graph theory methods and illustrates their application in various neurobiological contexts. Comprehensive coverage of the topic is beyond the scope of this article (see a recent textbook 9 ). Instead, the emphasis here is on highlighting some new methodological trends, discussing their application to brain data, and suggesting future avenues for graphical models and measures.

Basic concepts

Networks or graphs are collections of elements (nodes, vertices) and their pairwise links (edges, connections) which, in their simplest form, can be summarized in the form of a connection (or adjacency) matrix. The complete set of all pairwise connections defines the graph's topology, providing a complete map of all relations among nodes and edges. Brain nodes may be individual neurons or entire brain regions, depending on the measurement technique. Edges can take on binary or weighted values, and they can be directed or undirected, depending on how interactions are estimated from empirical data. The selection of appropriate graph theory methods for modeling and analyzing empirical data requires that the nature of the edge representation is taken into account. 6 , 9 Put differently, not all graph theory methods fit all purposes.

The two most common species of brain graphs describe structural and functional connectivity among neural elements. Structural graphs are generally sparse (most possible structural connections in a given nervous systems do not exist) and temporally relatively stable (but subject to plasticity and development). In contrast, functional graphs record statistical dependencies among neuronal time series, and hence are often dense and highly variable across time. The dichotomy of structural and functional graphs is important to consider, as each domain draws on a specific subset of graph theory methods that are commensurate with the origin of the data.

The definition of nodes generally requires sophisticated data-processing pipelines and is the subject of much methodological discussion. In whole-brain networks acquired with neuroimaging, nodes are often derived from a parcellation of the original voxel-level data, designed to extract coherent brain “areas” that form the building blocks of structural or functional brain networks. Some approaches leverage anatomical templates, others pursue parcellation in a data-driven manner, eg, by boundary detection and clustering patterns of connectivity. 14 A recent multimodal study employed machine learning to extract coherent brain regions on the basis of several different anatomical and functional criteria. 15 Node definition is considerably more straightforward in studies of circuits and neuronal populations, where individual neurons are natural candidates for individual network nodes.

A major simplification inherent in most current applications of graph theory is the assumption that, within a given network representation, all nodes and edges are identical and homogeneous. Annotation of nodes and edges can address this limitation of simple graphs, by allowing additional layers of data to be linked to network elements, which can be useful for identifying biologically meaningful network communities. 16 A further elaboration of simple graphs is the inclusion of multidimensional relationships which can be expressed in multilayer networks, 17 composed of different layers that encode different types of interactions (eg, synaptic links, temporal correlations, transmitter systems, or gene coexpression).

Graphs can be investigated at different levels of scale, and specific measures capture graph attributes at local (nodal) and global (network-wide) scales. 6 Nodal measures include simple statistics such as node degree or strength, while global measures express network-wide attributes such as the path length or the efficiency. Intermediate scales can be accessed via hierarchical neighborhoods around single graph elements, 18 or by considering subgraphs or motifs. 19 , 20 Motifs are defined as subsets of network nodes and their mutual edges whose patterns of connectivity can be classified into distinct motif categories. In empirical networks, these categories often occur in characteristic frequencies that can be compared with distributions from appropriate (random) null models. In the brain, motif analysis has been applied to structural 20 and functional graphs. 21

Most highly resolved structural brain networks are not fully, or even densely, connected. In such sparsely connected graphs, the minimal topological distance between two nodes, ie, the length of the shortest path, often involves multiple steps. Network paths are composed of unique edges that are traversed only once, while the usually much more abundant walks between two nodes can use edges any number of times. Paths and walks are considered important for the flow of signals and communication, 22 and are the basis for popular graph metrics such as the so-called efficiency which defines the global capacity of a graph to pass information via short paths. Importantly, concepts of path lengths and efficiency are most naturally applied to brain graphs that represent structural connectivity. In contrast, they have rather different (and potentially problematic) interpretations when applied to functional connectivity. The distinction derives from the nature of functional connectivity which reports statistical associations among neural time series rather than a web of physical links that propagates neural signals.

Among the most widely encountered and biologically meaningful aspects of brain networks is their organization into distinct network communities or modules 6 , 10 , 23 ( Figure 1 ). Modules are useful to partition larger networks into basic “building blocks,” ie, internally densely connected clusters that are more weakly interconnected amongst each other. Modular partitions have neurobiological significance as their boundaries separate functionally related neural elements, define critical bridges and hubs that join communities, channel and restrict the flow of neural signals and information, and limit the uncontrolled spread of perturbations. 23

There are numerous computational techniques for extracting communities and modules from complex networks. 24 , 25 One of the most widely used approaches in network neuroscience is modularity maximization which aims to divide a given network into a set of non-overlapping communities by maximizing a global objective function, the modularity metric. 26 Originally, this metric was formulated to detect communities whose internal density of connections is maximal, relative to a degree-preserving null model. More recently, variants of the metric that can be applied to directed 27 and signed 28 networks have been proposed. Of special note are variants of the scheme that are designed to deal with correlation matrices, 29 a data type that is often encountered in studies of functional connectivity.

Modularity maximization faces important methodological limitations that need to be addressed. One limitation refers to the existence of several, often quite numerous, distinct partitions that are almost equally optimal (ie, degenerate) under the modularity metric. Given the inherent noisiness of empirical estimates of the network topology, it seems arbitrary to pick a single “optimal” partition as the sole representative of the network's community structure. Instead, multiple degenerate solutions should be aggregated into consensus partitions, for example by forming an agreement matrix that can then be reclustered until a single consensus partition emerges. 30 The application of such a consensus approach can also reveal additional facets of community organization, including the degree to which individual nodes are affiliated with their host community. 28 , 31

Another fundamental limitation is the inability of the original modularity metric to detect modules below a certain size. This resolution limit 32 can be addressed in a number of ways. One common avenue is the inclusion of an additional resolution parameter into the modularity metric that rescales the intrinsic null model and allows the detection of smaller or larger communities. 33 Varying the resolution parameter is important since many brain networks exhibit communities across different scales, 34 which renders the selection of a single scale of analysis potentially problematic. The issue becomes of fundamental neurobiological importance when community detection methods are used to identify, for example, specific partitions of the brain into resting-state functional networks or “functional systems.” While several landmark studies have proposed canonical partitions of such networks; 35 , 36 that are now widely applied in the field, it should be noted that other partitions at both finer and coarser scales may represent additional levels of organization. Up to date, most studies circumvent full multiscale analysis by selecting one or a few settings of the resolution parameter, usually based on some criteria of partition stability.

One way to preserve and represent the full multiscale structure of brain networks is to perform consensus clustering across multiple spatial resolutions, 37 an approach that combines sampling the entire range of possible spatial resolutions with a hierarchical consensus clustering procedure. The approach returns a coassignment matrix that captures the probability that each node pair remains associated within the same community as the scale is varied, together with a hierarchy that illustrates their mutual relations. Multiresolution consensus clustering delivers a more complete picture of community structure than is provided by single partitions, and avoids complicated and often rather arbitrary models for selecting relevant scales in brain networks.

Finally, many extensions of the above framework for detecting communities in brain networks should be noted. While modularity maximization detects non-overlapping communities, it may also be useful to define modules as overlapping communities (eg, see ref 38), ie, sets of nodes where some, or all, nodes maintain multiple affiliations. Other methods, eg, multislice modularity, 39 are designed to track modular partitions, and their nodal memberships, across time. Yet another promising avenue, with deep historical roots in the social sciences, is the use of block models. 40 Block modeling attempts to fit a statistical model for generating networks to empirical data to identify those model parameters that provide the best match. For example, those parameters may correspond to a number of blocks and the corresponding within and between block connection probabilities. Since block models are not limited to strictly modular arrangements (maximizing within-module density while minimizing between-module density) they can detect more complex block structure in networks, 41 including the existence of a dense core and a more weakly connected periphery. In addition to versatility, block models offer the advantage of fitting a generative model to data (see below), which may offer insight into the processes that underlie the observed network topology.

Centrality and communication

Empirical networks have architectures that differ significantly from those of classic random graph models—most importantly, their nodes and edges are not equal in the way they are connected with the rest of the network. Far from being “equipotential,” the ways in which nodes and edges are embedded within the overall topology play a major role in determining their specific contributions to network function. Thus, network theory reconciles functional specialization with distributed processing—a dichotomy that has in the past led to strongly polarized theories of brain function, to the detriment of scientific progress.

Indeed, a major rationale for mapping brain connectivity arises from the idea that connectivity drives the functional specialization of local network elements. This idea is inherent in the notion that different brain regions have unique connectivity fingerprints that are indicative of their network embedding and predictive of their functional roles. 42 Similarities among connectivity fingerprints can be informative of functional groupings of areas and their mutual relations.

Numerous measures quantify the potential of individual nodes and edges to influence the global state of the network. Many of them allow the identification of network hubs, 43 , 44 generally defined as highly central parts of the network. The number of connections maintained by a node (its degree) or the combined weight of these connections (its strength) often provides a strong indicator of influence or centrality. Other measures of centrality take advantage of the layout of the shortest paths within the network, and record the number of such paths that pass through a given node or edge, a measure called the betweenness. Yet another way to approach centrality is by referencing the relation of nodes and edges to a network's community structure. The participation coefficient quantifies the diversity of a given node's connections across multiple modules—high participation indicates that many of these connections are made across modules, thus linking structurally and functionally the distinct communities. This measure is particularly useful in brain networks, as it can be applied to both structural and functional network data. 45

Most measures of node centrality are mutually related (and hence statistically correlated); for example, in most (but not all) networks nodes with many connections (high degree) also serve as intermediaries on many short paths (high betweenness). Since different measures of centrality index different aspects of network organization, it can be beneficial to rank nodes by aggregating multiple centrality measures. 43

Centrality measures can be useful tools for charting the global architecture of a brain network. Of particular neurobiological interest is the mutual association among highly central (eg, high degree) nodes. If these nodes maintain interconnections that are found to be denser than expected by chance (ie, a suitable null model) the network is said to exhibit so-called rich club organization 46 ( Figure 2 ) . Rich clubs have been found in virtually all structural connectivity data, from the connectomes of humans 47 to those of invertebrates. 48 , 49 Rich club organization tends to centralize network traffic, as the dense core formed by interconnected high-degree nodes attracts the bulk of short network paths that link lower degree nodes to each other. 50 This important role in network communication is thought to boost network communication and efficiency, thus trading off against the high wiring cost involved in linking spatially distributed hub regions.

While much of the interest in centrality is based on the putative role of hubs in network communication, it should be noted that the mechanisms by which brain networks communicate remain obscure. Most models and their associated graph theory metrics assume that communication unfolds along the most efficient and shortest paths available. However, this idea ignores the fact that these paths cannot be discovered by neural elements or signals in the absence of global information about the network topology. 22 Hence, alternative models based on spreading and diffusion 51 and path ensembles 52 are important to explore in future work.

Emerging trends

This final section briefly reviews several new directions that have great potential for future applications in brain networks.

Generative models

Most current graph theory methods applied to brain data deliver descriptive statistics that capture various aspects of network architecture. While such measures can be informative about the topological characteristics of a specific empirically measured network, their estimation should always be accompanied by some estimate of statistical significance or evidence. Every graph, even one generated by an entirely random process, will exhibit some graph attributes, including some chance level of clustering and modularity. Null models are important adjuncts of descriptive graph analysis as they allow discriminating which graph attributes are due to chance, and which exceed the expected values given by the null model. The choice of a proper null model is crucial for any descriptive analysis, as it will determine which graph features survive statistical comparison. Classic null models involve the rewiring of an empirical graph by swapping connections such that local degree is preserved while the global graph architecture is randomized. Other null models preserve subgraph frequencies to estimate the significance of larger subgraph distributions, or null models that preserve spatial locations of nodes.

Null models that fix a number of different factors such as local node measures, spatial locations, and wiring cost effectively become generative models of the empirical data. They generate graphs that may become indistinguishable from the empirical network, and in that sense can account for its topological properties. Hence, generative models can provide important insights into the factors that have shaped the emergence of specific architectural or performance characteristics. As such they are important reminders that not all graph attributes are the product of adaptation, and instead may have arisen as “spandrels” along the way, 53 a mere by-product of other more basic generative factors such as degree distributions or spatial embedding. Another important insight that can be gleaned from the design of generative models is that many graph attributes are mutually dependent and arise jointly from a common set of driving factors. For example, high clustering is invariably linked to particular statistics of subgraphs that favor triangles, and strongly favored by spatial embedding and wiring conservation.

Spatial embedding as an important generative principle behind the organization of brain graphs deserves special mention, as it is a fundamental constraint on brain architecture. 54 , 55 Much evidence points to distance-dependence as a major rule that governs the topology of anatomical brain connectivity within local circuits in single brain regions as well as for inter-areal projections. Generative models that combine spatial embedding with other, nonspatial, topological rules have suggested that their mutual trade-off may more fully account for characteristics of brain topology than any single (spatial or topological) factor alone. 56

Generative models are also crucial for understanding the emergence of dynamic states and functional connectivity. 57 Many classic models explored in computational neuroscience are generative models, in that they attempt to generate neuronal activity and dynamics from simple biophysical and structural ingredients. In human neuroimaging, the relationship between structural and functional connectivity has been illuminated by the use of computational models that can capture some of the patterns exhibited in brain dynamics. Some of these generative models are simple, as they can be computed analytically on top of structural graphs, 58 or make minimal assumptions (eg, linearity) about the nature of neuronal dynamics. 59 Other models utilize detailed biophysical mechanisms to generate neuronal time series and population activity. 60 Implementation of large numbers of generative models with varying model parameters combined with model selection are central to estimate variations in network parameters, including causal effects, in the course of varying conditions of stimulus and task.

Dynamic networks

Brain networks are not immutable, static constructs—rather, their structural and functional connectivity patterns change on multiple time scales. Data on time-varying brain graphs generally takes on the form of time series (or stacks) of graphs that form an ordered series of snapshots, for example recorded in the course of learning or across developmental stages. Changes in network topology can be tracked by computing graph measures on each time point followed by the subsequent examination of the resultant time courses of graph metrics. Another analysis approach involves arranging this stack into a series of time slices that are mutually coupled and can be analyzed as a single graph construct. 39 This allows the derivation of nodal measures of flexibility which can pinpoint parts of the network that are more variable across learning or development. 61

Much effort has recently been expended to track fast changes in graph topology and organization of functional networks recorded with fMRI. 62 Most commonly, a long time series of fMRI activations is partitioned into shorter “windows” that are then analyzed separately. Possible confounds are measurement artifacts such as physiological noise and increased uncertainty of estimating the magnitudes of functional connections on short samples. 63 In resting state, fMRI networks appear to undergo fluctuations between states of higher integration and segregation, 64 or modularity. 65 Similar transitions between different network states occur during task switching 66 and in the course of cognitively demanding spontaneous stimulation. 67

Multilayer networks

The arrival of multiomic data has enabled the joint analysis of networks between elements of neurobiological systems at different levels of organization. Prime examples are recent studies that combine maps of anatomical and functional networks, as well as studies that combine large-scale brain connectivity data with spatially registered data on patterns of gene expression. The latter have yielded important insights into relations between the centrality of network elements, for example their membership in a dense core or rich club, and distinct genetic signatures in energy metabolism. 68 In most studies so far, graph theoretic analysis proceeds through simple comparison or correlation of graph metrics across different levels (eg, anatomy and genetics). In the future, more explicit use of a multi-layer graphical framework is likely to occur. A few early examples are studies that place structural and functional connectivity into a multilayer model, eg, with data from human neuroimaging 69 and magnetoencephalography. 70

Algebraic topology

All graph theory approaches discussed so far build on networks that are composed of pairwise (dyadic) interactions. However, higher-order interactions can be highly informative for understanding non-random attributes of brain networks. Such higher-order relations can be represented with tools from applied algebraic topology, such as so-called simplicial complexes or simplices. 71 Simplices reframe the problem of relational data in terms of collections of vertices: a 0-simplex is a node, a 1-simplex is an edge, and a 2-simplex is a filled (connected) triangle. Simplices can be used to locate cliques (all-to-all connected subgraphs) or cavities. Recent applications of simplices to human connectome data have shown the utility of the approach for identifying both densely connected groups of nodes as well as other patterns of connectivity (eg loop-like paths) that would facilitate parallel processing. 72 Finally, the related area of topological data analysis attempts to detect, quantify and compare mesoscale structure present in complex network data. Essentially, the approach attempts to embed the data in a way that provides an optimal summary of its global structure. A recent example used topological data analysis to reveal dynamical organization in multitask fMRI time series, by creating graphical representations of relations among single image frames at the level of individual participants. 73 These representations allow a comparison of how individuals transition among multiple cognitive tasks and states and could provide useful markers for clinical diagnosis and treatment. Overall, the arrival of these topological methods capitalizes on higher-order and high-dimensional features in brain data that have so far been inaccessible with simple graph methods, and are therefore promising avenues for future investigation.

The growth of network neuroscience over the past decade or two has been nothing short of astonishing. A major driving force for this rapid expansion is the availability of relational data recording couplings and interactions among elements of neural systems. For now, most studies remain descriptive and focus entirely on pairwise interactions resulting in graphs composed of dyadic links. But graph theory is much more powerful than current methods applied to brain networks suggest. Generative models, dynamic networks, multilayer models, and algebraic topology are just a few of the promising directions that are currently pursued. With time, these new approaches will likely find applications not only in basic, but also in clinical and translational research. For years to come graph theory methods will remain indispensable tools to further our understanding of the brain as a complex interconnected system.

Acknowledgments

The author's research was supported by the US National Institutes of Health (R01-AT009036). The author has no conflict of interest to declare.

Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.

• View all journals
• Explore content
• About the journal
• Publish with us
• Sign up for alerts
• News & Views
• Published: 18 December 2023

Complex systems

Graph theory captures hard-core exclusion

• Zoltán Toroczkai   ORCID: orcid.org/0000-0002-6602-2849 1  

Nature Physics volume  20 ,  pages 20–21 ( 2024 ) Cite this article

683 Accesses

2 Altmetric

Metrics details

• Applied mathematics
• Complex networks

Physical networks, composed of nodes and links that occupy a spatial volume, are hard to study with conventional techniques. A meta-graph approach that elucidates the impact of physicality on network structure has now been introduced.

This is a preview of subscription content, access via your institution

Access options

Access Nature and 54 other Nature Portfolio journals

Get Nature+, our best-value online-access subscription

24,99 € / 30 days

cancel any time

Subscribe to this journal

Receive 12 print issues and online access

195,33 € per year

only 16,28 € per issue

Rent or buy this article

Prices vary by article type

Prices may be subject to local taxes which are calculated during checkout

Barabási, A.-L. Network Science (Cambridge University Press, 2016).

Wasserman, S. & Faust, K. Social Network Analysis: Methods and Applications (Cambridge University Press, 1994).

Ecological Networks: Linking Structure to Dynamics in Food Webs (eds Pascual, M. & Dunne, J. A.) (Oxford University Press, 2005).

Pastore y Piontti, A. et al. Charting the Next Pandemic: Modeling Infectious Disease Spreading in the Data Science Age (Springer, 2019).

Pósfai, M. et al. Nat. Phys. https://doi.org/10.1038/s41567-023-02267-1 (2023).

Article   Google Scholar  

Download references

Author information

Authors and affiliations.

Department of Physics and Astronomy, University of Notre Dame, Notre Dame, IN, USA

Zoltán Toroczkai

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Zoltán Toroczkai .

Ethics declarations

Competing interests.

The author declares no competing interests.

Rights and permissions

Reprints and permissions

About this article

Cite this article.

Toroczkai, Z. Graph theory captures hard-core exclusion. Nat. Phys. 20 , 20–21 (2024). https://doi.org/10.1038/s41567-023-02342-7

Download citation

Published : 18 December 2023

Issue Date : January 2024

DOI : https://doi.org/10.1038/s41567-023-02342-7

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Quick links

• Explore articles by subject
• Guide to authors
• Editorial policies

Sign up for the Nature Briefing newsletter — what matters in science, free to your inbox daily.

• Election 2024
• Entertainment
• Newsletters
• Photography
• Personal Finance
• AP Buyline Personal Finance
• Press Releases
• Israel-Hamas War
• Russia-Ukraine War
• Global elections
• Asia Pacific
• Latin America
• Middle East
• March Madness
• AP Top 25 Poll
• Movie reviews
• Book reviews
• Personal finance
• Financial Markets
• Business Highlights
• Financial wellness
• Artificial Intelligence
• Social Media

How bracketologists are using artificial intelligence this March Madness

FILE - Lisa Moeller takes a photo of the NCAA bracket for the NCAA college basketball tournament on the side of the JW Marriott in downtown Indianapolis, March 17, 2021. College hoops fans might want to think again before pinning their hopes of a perfect March Madness bracket on artificial intelligence. While the advancement of artificial intelligence into everyday life has made “AI” one of the buzziest phrases of the past year, its application in bracketology circles is not so new. (AP Photo/Darron Cummings, File)

FILE - Staff members for the NCAA place the names of the teams in the Sweet 16 on a bracket in the media workroom before practices at the East Regional of the NCAA college basketball tournament in New York, March 23, 2017. College hoops fans might want to think again before pinning their hopes of a perfect March Madness bracket on artificial intelligence. While the advancement of artificial intelligence into everyday life has made “AI” one of the buzziest phrases of the past year, its application in bracketology circles is not so new. (AP Photo/Julie Jacobson, File)

FILE - Pittsburgh guard Ishmael Leggett, right, places a decal on the bracket after an NCAA college basketball game against Wake Forest in the quarterfinal round of the Atlantic Coast Conference tournament March 14, 2024, in Washington. College hoops fans might want to think again before pinning their hopes of a perfect March Madness bracket on artificial intelligence. While the advancement of artificial intelligence into everyday life has made “AI” one of the buzziest phrases of the past year, its application in bracketology circles is not so new. (AP Photo/Susan Walsh, File)

• Copy Link copied

College hoops fans might want to think again before pinning their hopes of a perfect March Madness bracket on artificial intelligence.

While the advancement of artificial intelligence into everyday life has made “AI” one of the buzziest phrases of the past year, its application in bracketology circles is not so new. Even so, the annual bracket contests still provide plenty of surprises for computer science aficionados who’ve spent years honing their models with past NCAA Tournament results.

They have found that machine learning alone cannot quite solve the limited data and incalculable human elements of “The Big Dance.”

“All these things are art and science. And they’re just as much human psychology as they are statistics,” said Chris Ford, a data analyst who lives in Germany. “You have to actually understand people. And that’s what’s so tricky about it.”

March Madness 2024

BRACKETS: See the brackets for the men’s and women’s tournaments.

QUIZ: How does your knowledge about the tournament stacks up .

GET MORE with AP’s latest March Madness coverage.

Casual fans may spend a few days this week strategically deciding whether to maybe lean on the team with the best mojo — like Sister Jean’s 2018 Loyola-Chicago squad that made the Final Four — or to perhaps ride the hottest-shooting player — like Steph Curry and his breakout 2008 performance that led Davidson to the Sweet Sixteen.

The technologically inclined are chasing goals even more complicated than selecting the winners of all 67 matchups in both the men’s and women’s NCAA tournaments. They are fine-tuning mathematical functions in pursuit of the most objective model for predicting success in the upset-riddled tournament. Some are enlisting AI to perfect their codes or to decide which aspects of team resumes they should weigh most heavily.

The odds of crafting a perfect bracket are stacked against any competitor, however advanced their tools may be. An “informed fan” making certain assumptions based on previous results — such as a 1-seed beating a 16-seed — has a 1 in 2 billion chance at perfection, according to Ezra Miller, a mathematics and statistical science professor at Duke.

“Roughly speaking, it would be like choosing a random person in the Western Hemisphere,” he said.

Artificial intelligence is likely very good at determining the probability that a team wins, Miller said. But even with the models, he added that the “random choice of who’s going to win a game that’s evenly matched” is still a random choice.

For the 10th straight year, the data science community Kaggle is hosting “Machine Learning Madness.” Traditional bracket competitions are all-or-nothing; participants write one team’s name into each open slot. But “Machine Learning Madness” requires users to submit a percentage reflecting their confidence that a team will advance.

Kaggle provides a large data set from past results for people to develop their algorithms. That includes box scores with information on a team’s free-throw percentage, turnovers and assists. Users can then turn that information over to an algorithm to figure out which statistics are most predictive of tournament success.

“It’s a fair fight. There’s people who know a lot about basketball and can use what they know,” said Jeff Sonas, a statistical chess analyst who helped found the competition. “It is also possible for someone who doesn’t know a lot about basketball but is good at learning how to use data to make predictions.”

Ford, the Purdue fan who watched last year as the shortest Division I men’s team stunned his Boilermakers in the first round, takes it a different direction. Since 2020, Ford has tried to predict which schools will make the 68-team field.

In 2021, his most successful year, Ford said the model correctly named 66 of the teams in the men’s bracket. He uses a “fake committee” of eight different machine learning models that makes slightly different considerations based on the same inputs: the strength of schedule for a team and the number of quality wins against tougher opponents, to name a few.

Eugene Tulyagijja, a sports analytics major at Syracuse University, said he spent a year’s worth of free time crafting his own model. He said he used a deep neural network to find patterns of success based on statistics like a team’s 3-point efficiency.

His model wrongly predicted that the 2023 men’s Final Four would include Arizona, Duke and Texas. But it did correctly include UConn. As he adjusts the model with another year’s worth of information, he acknowledged certain human elements that no computer could ever consider.

“Did the players get enough sleep last night? Is that going to affect the player’s performance?” he said. “Personal things going on — we can never adjust to it using data alone.”

No method will integrate every relevant factor at play on the court. The necessary balance between modeling and intuition is “the art of sports analytics,” said Tim Chartier, a Davidson bracketology expert.

Pittsburgh guard Ishmael Leggett, right, places a decal on the bracket after an NCAA college basketball game against Wake Forest in the quarterfinal round of the Atlantic Coast Conference tournament March 14, 2024, in Washington. (AP Photo/Susan Walsh, File)

Chartier has studied brackets since 2009, developing a method that largely relies on home/away records, performance in the second half of the season and the strength of schedule. But he said the NCAA Tournament’s historical results provide an unpredictable and small sample size — a challenge for machine learning models, which rely on large sample sizes.

Chartier’s goal is never for his students to reach perfection in their brackets; his own model still cannot account for Davidson’s 2008 Cinderella story.

In that mystery, Chartier finds a useful reminder from March Madness: “The beauty of sports, and the beauty of life itself, is the randomness that we can’t predict.”

“We can’t even predict 63 games of a basketball tournament where we had 5,000 games that led up to it,” he tells his classes. “So be forgiving to yourself when you don’t make correct predictions on stages of life that are much more complicated than a 40-minute basketball game.”

Pollard is a corps member for the Associated Press/Report for America Statehouse News Initiative. Report for America is a nonprofit national service program that places journalists in local newsrooms to report on undercovered issues.

AP March Madness bracket: https://apnews.com/hub/ncaa-mens-bracket and coverage: https://apnews.com/hub/march-madness

Leaders’ Experiences of Integrated Leadership Development in Higher Education

Kolb’s experiential learning theory and the 70:20:10 model.

• Edinam Bernice Amenumey University of Cape Coast, Ghana
• Yaw Agyeman Badu Ghana Institute of Management and Public Administration, Ghana

This article examines the perceptions of leaders of a public university in Ghana on how leader and leadership development perspectives are reflected in the institution’s leadership development (LD) practices. While there is an extensive body of literature on LD, further research is required on how leader and leadership development perspectives can be integrated. The study examined the applicability of the 70:20:10 model to leaders’ LD experiences and blended this model with Kolb’s experiential learning theory. A qualitative case study research approach was employed to explore the experiences of the institution’s leaders. Data were gathered using semi-structured interviews, document review and observation of a training session. The data were analysed using the thematic perspective of narrative analysis. The study found that the concepts in the 70:20:10 model, namely (1) on-the-job task performance (2) relationships in the workplace, and (3) training formed the basis of formal and informal sources of learning that propelled leaders in their development journeys. However, the university did not leverage these to consciously integrate the perspectives of leader and leadership development. It is thus recommended that LD should be consciously planned to ensure holistic learning from the three sources in the university setting.

How to Cite

• Endnote/Zotero/Mendeley (RIS)

Copyright (c) 2024 International Journal of African Higher Education

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License .

Developed By

Information.

• For Readers
• For Authors
• For Librarians

Make a Submission