Archive for Graph Theory

Cosmology with the Minimal Spanning Tree

Posted in The Universe and Stuff with tags , , , , , , on July 8, 2019 by telescoper

There’s a nice paper on the arXiv (by Naidoo et al) with the abstract:

The code mentioned at the end can be found here.

The appearance of this paper gives me an excuse to mention that I actually wrote a paper (with Russell Pearson) on the use of the Minimal (or Minimum) Spanning Tree (MST) to analyze galaxy clustering way back in 1995.

Here’s how we described the Minimal Spanning Tree in that old paper:

Strictly speaking , we used the Euclidean Minimum Spanning Tree in which the total length of the lines connecting a set of points in a tree is minimized. In general cases a weight can be assigned to each link that is not necessarily defined simply by the length. Here is visual illustration (which I think we drew by hand!)

You can think of the MST as a sort of pre-processing technique which accentuates linear features in a point process that might otherwise get lost in shot noise. Once one has a tree (pruned and/or separated as necessary) one can then extract various statistical properties in order to quantify the pattern present.

Way back in 1995 there were far fewer datasets available to which to apply this method and it didn’t catch on at the time. Now, with  ever-increasing availability of spectroscopic redshift surveys maybe its time has come at last! I look forward to playing with the Python code in due course!

 

Trees, Graphs and the Leaving Certificate

Posted in Biographical, mathematics, Maynooth, The Universe and Stuff with tags , , , , , , on December 15, 2017 by telescoper

I’m starting to get the hang of some of the differences between things here in Ireland and the United Kingdom, both domestically and in the world of work.

One of the most important points of variation that concerns academic life is the school system students go through before going to University. In the system operating in England and Wales the standard qualification for entry is the GCE A-level. Most students take A-levels in three subjects, which gives them a relatively narrow focus although the range of subjects to choose from is rather large. In Ireland the standard qualification is the Leaving Certificate, which comprises a minimum of six subjects, giving students a broader range of knowledge at the sacrifice (perhaps) of a certain amount of depth; it has been decreed for entry into this system that an Irish Leaving Certificate counts as about 2/3 of an A-level for admissions purposes, so Irish students do the equivalent of at least four A-levels, and many do more than this.

There’s a lot to be said for the increased breadth of subjects undertaken for the leaving certificate, but I have no direct experience of teaching first-year university students here yet so I can’t comment on their level of preparedness.

Coincidentally, though, one of the first emails I received this week referred to a consultation about proposed changes to the Leaving Certificate in Applied Mathematics. Not knowing much about the old syllabus, I didn’t feel there was much I could add but I had a look at the new one and was surprised to see a whole `Strand’, on Mathematical Modelling with netwworks and graphs.

The introductory blurb reads:

In this strand students learn about networks or graphs as mathematical models which can be used to investigate a wide range of real-world problems. They learn about graphs and adjacency matrices and how useful these are in solving problems. They are given further opportunity to consolidate their understanding that mathematical ideas can be represented in multiple ways. They are introduced to dynamic programming as a quantitative analysis technique used to solve large, complex problems that involve the need to make a sequence of decisions. As they progress in their understanding they will explore and appreciate the use of algorithms in problem solving as well as considering some of the wider issues involved with the use of such techniques.

 

Among the specific topics listed you will find:

  • Minimal Spanning trees applied to problems involving optimising networks and algorithms associated with finding these (Kruskal, Prim);  
  • Bellman’s Optimality Principal to find the shortest paths in a weighted directed network, and to be able to formulate the process algebraically;
  •  Dijkstra’s algorithm to find shortest paths in a weighted directed network; etc.

 

For the record I should say that I’ve actually used Minimal Spanning Trees in a research context (see, e.g., this paper) and have read (and still have) a number of books on graph theory, which I find a truly fascinating subject. It seems to me that the topics all listed above  are all interesting and they’re all useful in a range of contexts, but they do seem rather advanced topics to me for a pre-university student and will be unfamiliar to a great many potential teachers of Applied Mathematics too. It may turn out, therefore, that the students will end up getting a very superficial knowledge of this very trendy subject, when they would actually be better off getting a more solid basis in more traditional mathematical methods  so I wonder what the reaction will be to this proposal!