Continue graphs from last time.
A matching in a graph is a collection of edges so that different edges do not share vertices. A maximum matching is a matching with the largest number of edges. Many problems can be recast as a graph matching problem, for example:
Resource Assignment: you have n jobs and n people and only certian people can do certian jobs. You want to assign jobs to people so that each person gets one job, each job gets completed, and each person is assigned a job they can do. Set up a graph. There will be 2n vertices: one vertex for each job and one vertex for each person. Add an edge between a job and a person if the person can do the job. A maximum matching is then an assignment of jobs to people with the required properties.
Image Feature Matching: here we are given two images that are of the same or similar things and want to match pieces of the image. I found these slides to have a good view in pictures what we are trying to do (only need to look at the first 8 slides or so). Here is another page with some nice pictures. The goal here is to make points in the images into vertices and put edges between vertices if the regions of the image are similar. A matching in this graph is then a coorespondence between points in the image.
Graphs.sagews is a sage worksheet with some graphs. The graph reference manual lists off the different methods available to graphs. I also used graph plotting to draw the graphs.
This is where my own research is. Consider this classical problem from the late 1800s that really launched extremal graph theory.
Among other applications, questions of this type have applications to algorithm analysis. For example, you could have an algorithm where if there are triangles the algorithm runs really slow and if there are no triangles the algorithm is fast. So you want to understand what kinds of graphs your algorithm will run fast on.
Another place extremal graph theory comes into play is property testing. The first two or three pages of this survey give a good intro to what property testing is: we want to solve problems with a huge amount of data where we don't have time to process all the data and just want to look at pieces of it.
k colors. What is the probability that if I select t vertices the graph just on those t vertices is not k colorable? If that probability were large, I could just select t vertices at random, compute the chromatic number, and use it as an approximation for the whole graph. As long as the probability is large I should get a good approximation and as long as t is small it should run much faster. In fact this is true and t only needs to be around 36 k ln k where ln is the natural log.No homework