My interest in geometric graphs started because of my work on graph models for complex networks. Graph theory can be used to study large real-life networks: the "friend" network of Facebook, for example, or the Web itself, but also networks of interactions between the proteins in a cell, or even the network of neural connections in the brain. Geometric graphs are useful models for such networks. The metric space models the underlying, and often hidden, information that guided the formation of the links. A good model should be useful in extracting that information.
I am also interested in the spread of information through such networks. Some questions I would like to consider are: given some estimate of the likelihood of transmission through an edge, how fast does a piece of information spread through a network, and does the information reach all nodes? Which vertices should be "inoculated" to halt the spread of a virus or malicious rumour? Which vertices should be targeted to maximize the spread of good news or useful information?
More on the theoretical side, I am attracted to a new theory of graph limits. This is a new theory, which applies to sequences of graphs of increasing size. There is a connection with models for complex networks here, since in many of these models the graphs grow over time, which can be interpreted as a sequence, or time series, of graphs of increasing size. The new theory develops a natural notion of convergence for such sequences, which leads to a limit which is not a graph, but a function. This function in turn can be used to generate random graph which are very similar in structure to the graphs in the sequence.
Finally, I have a long-standing interest in graph colouring. In particular, I am interested in list colourings. Here, each vertex is given a list of potential colours. The question is whether the vertices can be coloured with colours from their list, and so that adjacent vertices have different colours. An interesting new line of research concerns on-line list colouring. This can be seen as a game between Mr. Pain and Mrs. Correct. In each round, Mr. Paint paints a set of vertices. Mrs. Correct erases the colour on some of the vertices, to make sure adjacent vertices have different colours. However, there is a limit to the number of times she can erase a given vertex. The question is to determine how small this limit can be so that Mrs. Correct wins, i.e the vertices are all coloured at the end of the game.
|