# Mengxue Yang

## Contact

Email: myang59@uic.edu
Office: SEO 731
Department website: Mengxue Yang

I'm a fifth year Ph.D. student at the University of Illinois at Chicago [CV]. My advisor is Laura Schaposnik. I'm interested in differential and complex geometry, in particular geometric structures on a Riemann surface such as opers and Higgs bundles. I come from Beijing, China, and I spent 9 years studying in Canada. I received my undergraduate degree from the University of Waterloo, with a double major in Pure Math and Computer Science. You may wonder how to pronounce my first name -- it roughly sounds like "MUNG-SHOO-EY" -- and it translates to "dream snow" in English.

## Something interesting

I learned the following fun piece of math from teaching the Young Scholar Program at UIC recently. The minimum vertex cover problem asks: for a given graph, find a minimal set of vertices that touch all the edges. This is one of Karp's 21 NP-complete problems. We can find a simple algorithm that outputs a good-enough approximate solution, but it's not what you think it is. The naive greedy algorithm is to always add a vertex of the highest degree to the vertex cover, then remove it from the graph and recurse. However there are graphs on which this algorithm produces vertex covers that are arbitrarily far from the minimal one. That is, $n$ times the size of a minimal cover, for any $n$.