Document Actions

Research Interests

On this page I have attempted to describe my papers and what they are about, sometimes including a few stories about how I got interested in the problems. If you are thinking of doing a PhD and something sounds interesting then please get in touch.

Graph Polynomials

Much of my research has been centred on graph polynomials. Perhaps the most well-known graph polynomial is the chromatic polynomial, which counts the number of ways of properly colouring the vertices of a graph from a fixed palette of colours. I have been mostly interested in the Tutte polyomial which is a two-variable polynomial, incorporating the chromatic polynomial as a one-variable specialization. For me the Tutte polynomial has two attractions. First, it specializes to a vast range of interesting, yet otherwise apparently unconnected invariants with links to knot theory via the Jones polynomial, statistical physics via the partition functions of the Ising and Potts models, operational research via the reliability polynomial and many parts of graph theory. Second, a vast range of beautiful mathematics has already been discovered concerning the polynomial, but there is still a vast amount that is unknown and the range of unsolved problems is likely to lead to much more beautiful mathematics.

The diagram depicts the Tutte plane, and more precisely, the complexity of evaluating the Tutte polynomial at different points. Evaluations at green points are easy, those at blue points can be computed for planar graphs, those at red points might be approximated efficiently (it is an open problem) and those at black points cannot be approximated. The diagram was popularized by Dominic Welsh. I have yet to incorporate the more recent results due to Leslie Goldberg and Mark Jerrum - unfortunately their excellent results rather spoil the picture.

What does the Tutte polynomial tell us?

An interesting question is to learn more about exactly what information can be determined from the Tutte polynomial of a graph. For instance it is easy to determine whether a graph is a series-parallel network, but it is not possible to determine if it is planar.
  • In the following paper we prove that one can determine whether a graph is a simple outerplanar graph from its Tutte polynomial. (Simple graphs are those with no loops or parallel edges. Outerplanar graphs are planar graphs which can be drawn so that all the vertices appear on the same face.)

    Goodall, A.J., de Mier, A., Noble, S.D., Noy, M. The Tutte polynomial characterizes simple outerplanar graphs. Combinatorics, Probability and Computing 20 (2011) 609-616.

  • It is easy to see that the Tutte polynomial is increasing along the portion of any line with positive gradient which lies in the first quadrant. This observation allows one to deduce relationships between different evaluations of the Tutte polynomial. But what happens along lines with negative gradients. A long-standing unresolved conjecture is the Merino-Welsh which makes a first step towards suggesting that the Tutte polynomial should be convex along these lines. We were able to show that this result is true for the class of paving matroids. Another conjecture states that asymptotically almost all matroids are paving matroids. If this is the case then our result implies that the Merino-Welsh conjecture must hold for almost all graphs.

    Chavez-Lomelí, L.E., Merino, C., Noble, S.D., Ramírez-Ibañez, M. Some inequalities for the Tutte polynomial. European Journal of Combinatorics 32 (2011) 422-433. ArXiv.

The U-polynomial

The U-polynomial is one of my favourite topics around the Tutte polynomial, although I have not thought about it for a little while now. It generalises the Tutte polynomial by using weighted graphs. Roughly speaking it is defined using a delete-contraction relation, where when an edge is contracted the single vertex formed takes the sum of the two weights of the end-vertices of the contracted edge. It includes the Tutte polynomial as a special case, but also includes many other invariants such as the matching polynomial and is equivalent to Stanley's symmetric function generalization of the Tutte polynomial.

  • This paper from my DPhil thesis introduces the U polynomial and establishes many of its basic properties and specializations.

    Noble, S.D., Welsh, D.J.A. A weighted graph polynomial from chromatic invariants of knots. Annales de l'Institute Fouier 49 (1999) 1057-1087.

  • Roughly speaking, the U polynomial replaces the x variable of the Tutte polynomial by a countably infinite family of variables. It is possible to do the same thing for the y variable and also to get a analogous generalization of Stanley's symmetric function generalization. Answering a question posed by Dominic Welsh we proved that these two generalizations are indeed equivalent, in the sense that the coefficients of one can be obtained from the other.

    Merino, C., Noble, S.D. The equivalence of two graph polynomials and a symmetric function. Combinatorics, Probability and Computing 18 (2009) 601-615.

  • The techniques in my paper on evaluating the Tutte polynomial for graphs of bounded tree-width, which is described below, can be applied, with several extra complications, to the U-polynomial.

    Noble, S.D. Evaluating a weighted graph polynomial for graphs of bounded tree-width. The Electronic Journal of Combinatorics 16(1) (2009) R64. EJC Volume 16

Tutte polynomial inspired techniques

The next section of papers is not so easy to categorize. They are usually indirectly connected with the Tutte polynomial by discussing an invariant of the Tutte polynomial, rather than the polynomial itself. This means that techniques used on the polynomial itself are often useful.

  • I was the referee on the first version of this paper, where my eventual coauthors proved a nice result about planar graphs. I was able to generalize it to all graphs. There are several binary vector spaces which can be associated with a graph including the cycle spaces, generated by incidence vectors of cycles, and the cocycle space, generated by incidence vectors of cocycles. A particularly curious binary vector space is the bicycle space which is the intersection of the cycle and cocycle spaces. The authors were interested in which graphs with minimum degree three had the dimension of the bicycle space one less than that of the cycle space. (In a previous paper they had considered when equality held.) They proved that the only such planar graph with minimum degree three was the complete graph on 4 vertices.

    Lin, Y., Noble, S.D., Jin, X., Cheng, W. On plane graphs with link component number equal to the nullity. Discrete Applied Mathematics 160 (2012) 1369-1375. ScienceDirect

  • A long-standing conjecture of Stanley states that the h-vector of every matroid is a pure O-sequence. There's not room to define what these things mean here. We were able to prove the result for the class of paving matroids. As mentioned earlier, there is a conjecture stating that asymptotically almost all matroids are paving matroids. If this conjecture is true then our result implies that Stanley's conjecture holds for almost all matroids.

    Merino, C., Noble, S.D., Ramírez-Ibañez, M., Villarroel, R. On the structure of the h-vector of a paving matroid. European Journal of Combinatorics 33 (2012) 1787-1799. ArXiv.

  • There are interesting connections between graph theory and knot theory. Any knot can be represented by a signed graph. Roughly speaking each vertex of the signed represents a crossing in the knot and the signs determine whether the crossing is an over / under crossing. Any knot can be transformed to any equivalent knot using a sequence of 3 very simple moves, the Reidemeister moves. These moves can be translated to graphs. Understanding which knots can be constructed from a simple loop using Reidemeister moves is a key question because it would help us to determine whether or not a knot is genuinely knotted. What happens if we apply the equivalent of the Reidmeister moves to graphs? Which graphs may be obtained? We attempt to answer some of these questions in the following paper.

    Noble, S.D., Welsh, D.J.A. Knot graphs. Journal of Graph Theory 34 (2000) 100-111. BURA

  • A key problem in statistical mechanics is to determine how various graph invariants grow on lattice-like graphs as the size of the lattice grows. In the following paper we establish bounds on the number of forests and acyclic orientations

    Calkin, N., Merino, C., Noble, S.D., Noy, M. Improved bounds for the number of forests and acyclic orientations in the square lattice. The Electronic Journal of Combinatorics 10 (2003) R4. EJC Volume 10

Complexity

A lot of my interest in the Tutte polynomial used to be around complexity: given a class of graphs, how difficult is it to compute the polynomial? However I have not thought about this quite so much for a little while.

  • One of the first problems I considered while studying for my DPhil was how to evaluate the Tutte polynomial for graphs of bounded tree-width. These graphs can be viewed in many ways. Perhaps the simplest way to motivate them is to think that most graph problems are easy to solve on trees. In many ways, graphs with bounded tree-width incorporate this simplicity, as they contain many small vertex cuts. This allows one to design algorithms using dynamic programming. It is not difficult to generalize the techniques which I used in this paper to many other polynomials.

    Noble, S.D. Evaluating the Tutte polynomial for graphs of bounded tree-width. Combinatorics Probability and Computing 7 (1998) 307-323. BURA

  • In 1990, Francois Jaeger, Dirk Vertigan and Dominic Welsh published a seminal paper which completely described the complexity of evaluating the Tutte polynomial at any rational point in the plane. One of my results in my DPhil thesis, adapted this technique to another polynomial. It is possible to think of the Tutte polynomial as a generating function counting all subsets of the edges by their size and the number of components in the corresponding spanning subgraph. If instead one counts the subsets of the edges by their size and the number of vertices that they are incident with, then one obtains another rich polynomial which was introduced by James Oxley and Geoff Whittle and includes the matching polynomial as a specialization.

    Noble, S.D. Evaluating the rank generating function of a graphic 2-polymatroid. Combinatorics Probability and Computing 15 (2006) 449-461. BURA

  • Dominic Welsh retired in 2005. I wrote a survey article summarising his 1990 paper, which I mentioned above, and my article on evaluating the Tutte polynomial. I included details of how my result can be extended to other polynomials.

    Noble, S.D. The complexity of graph polynomials. Chapter in Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh. Ed Geoffrey Grimmett and Colin McDiarmid OUP 2007.

Algorithms and complexity

When not thinking about graph polynomials, I generally like to think about problems with an algorithmic flavour. How easy or hard is it to solve a particular problem? Are there subcases which are easier?

Frequency Assignment

I first heard about the frequency assignment problem in 1995 from a talk given by Robert Leese in Oxford. I have returned to it a few times since. The idea is to give integer labels to the vertices of a graph, subject to certain constraints, in such a way that the difference between the largest and the smallest labels is minimized. The vertices of the graph represent transmitters, the labels represent frequencies of radio channels and the constraints are there to ensure that users in the vicinity of more than one transmitter do not suffer from interference.
  • Nicole Eggemann was my second PhD student and spent part of her time on placement with Frederic Havet in Sophis-Antipolis - a beautiful place to work. Perhaps the most commonly studied version of the frequency assignment problem is when the constraints dictate that adjacent vertices must receive labels which differ by 2 and vertices at distance two must also receive different labels. For planar graphs, some partial results existed describing the complexity of the problem; we were able to completely resolve it.

    Eggemann, N., Havet, F., Noble, S.D. k-L(2,1)-Labelling for Planar Graphs is NP-complete for k >= 4. Discrete Applied Mathematics 158 (2010) 1777-1778. ArXiv

    This paper involved constructing some rather pretty graphs to act as gadgets in the reduction. Here are two of them.

  • In the following paper with Robert Leese, we considered a variation of the problem where the set of labels is the integers modulo n. We completely solved this problem on cycles. Even cycles were easy, as we were able to show that the optimal labelling had to belong to one of three distinct types. Odd cycles were harder. If the cycle was very small, we could solve exhaustively. If the cycle was large enough, there was some flexibility to allow the adaptation of the methods used for even cycles. But we struggled to solve the problem for the 7-cycle for a very long time.

    Leese, R.A., Noble, S.D. Cyclic labelling with constraints at two distances. The Electronic Journal of Combinatorics 11 (2004) R10. EJC Volume 11

  • Angela Koller was my first PhD student. We worked on a problem suggested to me by a former colleague, Gregory Gutin, who is now at Royal Holloway. He was interested in the domination number of problems and associated algorithms. Historically one generally measures the qualiy of an optimization heuristic by observing how close to the optimum its solutions are guaranteed to be. The domination number is an alternative approach which counts how many feasible solutions the heuristic is guaranteed to beat. We investigated two simple greedy algorithms for a commonly studied version of the problem. Despite there being very little difference between the algorithms one had a very poor domination number, whereas the other was good.

    Koller, A.E., Noble, S.D. The domination number of greedy heuristics for the frequency assignment problem. Discrete Mathematics 275 (2004) 331-338. BURA

Complexity of other problems

  • The next two papers are two different versions of the same thing. The problem considered came about from a placement Nicole undertook working with Advanced Transport Systems in Bristol on the design of urban light rail systems. The problem is rather like being given the plan of a town centre and being told that all the streets must be turned into one-way streets in such a way that the maximum journey time is minimized. We solve this problem in slightly different ways in the two papers. Part of our algorithm relies on solving the problem when the input graph has bounded tree-width. In the first paper we use some highly sophisticated, but well-known general results from mathematical logic; in the second paper we sketch a direct approach.

    Eggemann, N., Noble, S.D. The complexity of two graph orientation problems. Discrete Applied Mathematics 160 (2012) 513-517. ArXiv.

    Eggemann, N., Noble, S.D. Minimizing the oriented diameter of a planar graph. Electronic Notes in Discrete Mathematics 34 (2009) 267-271. BURA.

  • My very first paper solved a problem I heard of from my DPhil supervisor, Prof Dominic Welsh. To a combinatorialist, a simplicial complex is just a collection of sets which are closed under taking subsets. It is partionable if for each maximal set F, one can associate a subset B, so that the collection of Boolean intervals of the form [B, F] partitions the simplicial complex. We proved that recognising such complexes is in NP - possibly the last result of this type to be published.

    Noble, S.D. Recognising a partitionable simplicial complex is in NP. Discrete Mathematics 152 (1996) 303-305. BURA

  • Ilia Krasikov is a former colleague, who was once asked a question in an undergraduate lecture he was giving about shortest paths. Ilia misheard the question and thought that he had been asked how one could find a path in a graph which the shortest path amongst those which are longer than the shortest path. Using max flow techniques, we show how that this can be done in polynomial time for undirected graphs providing all the edges lengths are strictly positive. The problem is known to be NP-complete in directed graphs when negative length edges are allowed.

    Krasikov, I., Noble, S.D. Finding next-to-shortest paths in a graph. Information Processing Letters 92 (2004) 117-119. BURA

  • With Malwina Luczak, I worked on a problem described by BT, where we considered the complexity of arranging data in a directory structure which takes the form of a tree with the data on the leaves. The objective was to minimize the sum of the path lengths between related pieces of data. We showed that this problem was NP-complete. This paper appears as an erratum because, by mistake, Elsevier published the version of the paper submitted before refereeing.

    Luczak, M.J., Noble, S.D. Optimal arrangement of data in a tree directory. Discrete Applied Mathematics 121 (2002) 307-315. BURA

  • Nenad Mladenovic is another former colleague who suggested the following problem. Nenad is interested in heuristic methods to solve hard problems, but before one can justify using a heuristic, one ought to prove that the problem is hard. An interesting problem in real world networks is finding communities, i.e. groups of vertices which have relatively many connections with other members of the group but relatively few outside. We showed that it is NP-hard to find such a community in one precise formulation of the problem.

    Noble, S.D., Hansen, P., Mladenović, N. Maximizing edge-ratio is NP-complete. Discrete Applied Mathematics 159 (2011) 2276-2280. Preprint.

Scale-free Networks

  • Nicole Eggemann was my second PhD student and was sponsored by the EU under a Marie-Curie grant. We started off working together on problems in preferential attachment graphs. These are random graphs which grow over time, with a new vertex joining at each time step. The other end-vertices of edges linking the new vertex to the rest of the graph are determined by the existing degrees of these vertices, with higher degrees being favoured. Real-world networks tend to be highly clustered, which is the opposite of what happens in a purely random network with a similar number of edges. Bollobas and Riordan gave a precise result desribing the expectation of the clustering coefficient in one particular form of preferential attachment network. We generalized their result to a wider class of networks, and needed to use some Martingale bounds which are a little more involved than the most commonly used ones. After completing this paper, we got distracted by completely different problems.

    Eggemann, N., Noble, S.D. The clustering coefficient of a scale-free random graph. Discrete Applied Mathematics 159 (2011) 953-965. ArXiv

Contact Details

Phone: +44 (0) 20 7631 6417

Email: s.noble@bbk.ac.uk

Room: 728

Current news

  • ESRC Postdoctoral Fellowships

    The UCL, Bloomsbury and East London DTP invites applications for three postdoctoral fellowships (PDFs) to be based within departments at the partner institutions within the Doctoral Training Partnership (DTP): University College London, Birkbeck, the London School of Hygiene & Tropical Medicine, the School of Oriental and African Studies, and the University of East London.

  • Competition for ESRC Studentships for October 2018 entry is now open

    ESRC PhD Scholarships for 2018 entry are available via UCL, Bloomsbury and East London Doctoral Training Partnership (DTP) for suitable candidates.

  • Sundstrom Scholarships for 2017/18 Entry

    Two Home/EU scholarships for MSc programmes are available in the Department of Economics, Mathematics and Statistics.