Column: Bipartite Graphs

I do not like Christmas very much. I hate Christmas songs on the radio and at the age of 54 I still do not see the point behind the yearly Christmas card terror.  And although I like food, I feel a bit anxious as soon as people start to talk about Christmas dinners. Fascinating to see how people can turn a daily habit into an unsolvable scheduling problem. At first I thought this would be a perfect topic for this column, that I write before Christmas and you read after. However, since this is a magazine for econometricians and you expect me to write columns with a mathematical or agricultural twist I decided to concentrate on bipartite graphs.

I was introduced to bipartite graphs in the first trimester of my study (Technical) Mathematics in Eindhoven during the course Discrete Mathematics 1 when we discussed the theorem of König and Hall. I have remembered this theorem ever since because the popular version of it is called the marriage theorem. In this theorem the vertices of the bipartite graph consist of men and women and there is an edge between a man and a woman if they would be willing to marry. The aim is to find the largest possible number of disjoint couples. The theorem states that this maximum number is equal to the minimum number of persons that cover all possible marriages and the proof consists of an algorithm that finds both. For the single young man that I was back then, this was a fascinating result. Since I realized that all persons in this minimal set will marry in case of a maximal matching I determined my strategy to focus on rival-free girls. Of course these girls typically have a lot of imperfections but that means that you do not have to bother about your own either. Furthermore it is a much nicer experience to find out later that behind all these imperfections there is still some unexpected beauty hidden, instead of being confronted with major shortcomings hidden behind beauty. 

For the second example of bipartite graphs I first want to look at the (trivial) mathematical part. When for a bipartite graph you want to determine the average degree of the vertices in each of the two co-cliques, you just have to divide the total number of edges by the number of vertices in that co-clique. So if the two co-cliques have (more or less) the same size, also the average degrees should be (more or less) the same. This was what I had in mind when I read about a research by psychologists that determined the average number of sexual partners for men and women. In their research women scored considerably lower than men and although they talked about a double standard and men and women lying in opposite directions, they totally seemed to have missed the fact that these averages should be more or less the same. My point is: I understand that all the kids that scored bad grades for math at school should finally get some position such that they also can contribute to society, but something went wrong here. 

I want to end with the Christmas issue I started with. When you finally found your partner with or without my advice you automatically also get his/her family with it, meaning that you are supposed to show up together at two Christmas dinners. At first sight it seems to be enough to have the two Christmas days to plan these dinners but then you forget all other couples that put on similar constraints. What you try to do here is coloring a graph with two colors, however this is only possible if the graph is bipartite and of course not all graphs are. Now try to explain this to your parents in law if these are for instance psychologists. Good luck!