Georgia Institute of Technology College of Sciences

The study of Legendrian and transversal knots has been an essential part of contact topology for quite some time now, but until recently their study in overtwisted contact structures has been virtually ignored. In the past few years that has changed. I will review what is know about such knots and discuss recent work on the "geography" and "botany" problem.

Lopsided bipartite graphs naturally appear in advertising setting. One side is all the eyeballs and the other side is all the advertisers. An edge is when an advertiser wants to reach an eyeball, aka, ad targeting. Such a bipartite graph is lopsided because there are only a small number of advertisers but a large number of eyeballs. We give algorithms which have running time proportional to the size of the smaller side, i.e., the number of advertisers. One of the main ideas behind our algorithm and as well as the analysis is a property, which we call, monotonic quality bounds. Our algorithm is flexible as it could easily be adapted for different kinds of objective functions. Towards the end of the talk we will describe a new matching polytope. We show that our matching polytope is not only a new linear program describing the classical matching polytope, but is a new polytope together with a new linear program. This part of the talk is still theoretical as we only know how to solve the new linear program via an ellipsoid algorithm. One feature of the polytope, besides being intriguing, is that it has some notion of fairness built in. This is important for advertising since if an advertiser wants to reach 10 million users of type A or type B, advertiser won't necessarily be happy if we show the ad to 10 million users of type A only (though it fulfills the advertising contract in a technical sense).

A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring \phi of C can be extended inside the cycle, or there exists a subgraph H with at most 5^{q^3} vertices such that \phi cannot be extended to a 5-coloring of H. In Chapter 2, we provide an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. Finally, in Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface \Sigma, with Euler genus g and has no cycles of length four through ten, then |V(G)| \leq 2442g + 37.

Estimating the Tree of Life, an evolutionary tree describing how all life evolved from a common ancestor, is one of the major scientific objectives facing modern biologists. This estimation problem is extremely computationally intensive, given that the most accurate methods (e.g., maximum likelihood heuristics) are based upon attempts to solve NP-hard optimization problems. Most computational biologists assume that the only feasible strategy will involve a divide-and-conquer approach where the large taxon set is divided into subsets, trees are estimated on these subsets, and a supertree method is applied to assemble a tree on the entire set of taxa from the smaller "source" trees. I will present supertree methods in a mathematical context, focusing on some theoretical properties of MRP (Matrix Representation with Parsimony), the most popular supertree method, and SuperFine, a new supertree method that outperforms MRP.