3
$\begingroup$

The Mathematics Genealogy Project keeps an online database of information on as many mathematicians as they can get records for, focusing especially on advisor-student relationships. In this way, they have created a graph where the vertices are the mathematicians and the edges are the advisor-student pairings. The site tells us that the graph is non-planar, which means it's impossible to draw the graph in a plane without intersecting edges. From a graph theory perspective, the necessary and sufficient condition for a graph to be non-planar is that it contain at least one $K_5$ or $K_{3,3}$ minor, and this is what is used in the explanation on the site. But I prefer to think about this more in terms of human relationships.

A necessary (but not sufficient) condition for the graph to be non-planar is that sometimes a single student has many advisors, for if each student had exactly 0 or 1 advisors, then the graph would be finitely many disjoint trees. Here is an example where having multiple advisors causes non-planarity: two professors jointly take on three different students, then those three students become professors and jointly take on a common new student. But this example sounds unlikely.

The explanation for non-planarity given on the site is via a single example of a $K_{3,3}$ minor which contains many famous names, e.g. Gauß, Weierstraß, Klein, Hilbert, Frobenius, Kummer. If you look up the advisor-student pairings in this minor, you will find that the non-planarity is essentially caused by Frobenius having two advisors: Weierstraß and Kummer. (I wonder how different things would have been if he'd had to pick one or the other.)

My first reaction to seeing this was: are non-planar subgraphs common, or did they just pick this one so they'd have something with text-book names? And if there are other examples, do they tend to span many generations of influential mathematicians as this one does, or can we find more minimal examples like the one I constructed above?

As a more easily quantifiable measure of non-planarity, which also takes into account the condition discussed above, one could ask: how many edges need to be removed to make a planar graph, where we add the additional rule that we are not allowed to remove all of any one student's advisors? If would also be fun to have the list of name-pairs occurring as candidates for removal in this result.

To answer these questions one would need access to the database, but I wonder if this (or something similar) has already been done in attaining the information on the site.

$\endgroup$

closed as off-topic by David White, Alex Degtyarev, Wolfgang, Stefan Kohl, Chris Godsil Nov 27 '16 at 21:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about research level mathematics within the scope defined in the help center." – David White, Alex Degtyarev, Wolfgang, Stefan Kohl, Chris Godsil
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ A measure of non-planarity is crossing number, which is rather well controlled in terms of the number of edges. $\endgroup$ – Pat Devlin Nov 27 '16 at 0:47
  • $\begingroup$ @PatDevlin I wonder if that data is available, though the data I suggest attaining is more specific to the nature of this graph. $\endgroup$ – j0equ1nn Nov 27 '16 at 1:10
  • $\begingroup$ The thing is probably very close to a forest, as very few people have more than one advisor. $\endgroup$ – Pat Devlin Nov 27 '16 at 1:13
  • $\begingroup$ @PatDevlin Yeah, that's how I felt at first too. Like, saying that the graph is non-planar is basically just saying there has been an instance of multiple advisors in a way that caused it, but this isn't how the analysis is presented. I'd like to see it put that way. $\endgroup$ – j0equ1nn Nov 27 '16 at 1:17
  • 1
    $\begingroup$ This seems like a frivolous question to me. $\endgroup$ – David White Nov 27 '16 at 15:34
2
$\begingroup$

Ok. It seems that they gave the number of students that each node has (i.e., the down degree). Summing this, the graph has 218849 edges (likely made some addition error, but this is at least close). And it has 200037 vertices.

Without knowing much more, it's hard to say how "planar" the thing is. There are about 20000 people with more than one advisor I'd say [some vertices have no advisor and some might have more than 2].

So if you remove those edges it'll be a forest. (The thing is already very close to a forest.)

A person could perhaps do more analysis based on the degree sequence they gave. As per the math genealogy site, you could contact "Cosmin Ionita and Pat Quillen of MathWorks" who analyzed the thing in July 2016. They likely have the data somewhere.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.