My project is about the extremal properties of mixed graphs, which are networks whose nodes can be connected by directed or undirected edges. One of my favorite games is Wikiracing, where one tries to reach one Wikipedia article from another through as few internal links as possible. The game is a version of “six degrees of separation” that showed me a fresh view of the world: everything, and everyone, is connected in one intricate graph. Mixed graphs are a versatile and powerful tool capable of representing all sorts of data and the complex relations within them, and I studied the structure and density of mixed graphs satisfying certain special constraints.
In order to understand the landscape of extremal graph theory, mixed graphs, and partially directed hypergraphs, I read dozens of lecture notes and research papers. While fascinated by high dimensional networks and investigating multifaceted structural relationships, I also encountered numerous brick walls. Sometimes I thought I’d thrown every mathematical method I could think of at a problem, but still failed to reach a desired bound. On another occasion, I attempted to solve part of a problem with computational methods, but was overwhelmed by a million-hour expected run time… This year-long research experience has taught me that staying both optimistic and skeptical, though it sounds paradoxical, is crucial to the research process. I’m infinitely grateful to my mentor, Nitya Mani, for her continuous support, warm encouragement, and generous guidance. I’m also very thankful for the MIT PRIMES-USA program, for giving me the opportunity to conduct mathematical research, and to Professor Yufei Zhao of MIT for inspiring me to study extremal graph theory. Last but not least, I’d like to thank my parents for their unconditional encouragement and love throughout my mathematical endeavors.
Mixed graphs are convenient modeling tools in scientific research to represent relational data. For example, problems in job scheduling, neural networks, and propositional logic in computer science can all be modeled using mixed graphs. My research establishes a theoretical framework for extremal properties of mixed graphs. These results can help other scientists deepen their understanding of large scale data networks with complicated structures, and apply mixed graph models with a new understanding of their asymptotic complexity. The program I developed to compute extremal properties of partially-directed hypergraphs is generalizable to many hypergraph computational problems; I hope that graph theorists, as well as researchers in other fields, can benefit from this implementation when performing hypergraph computations to test their hypotheses and develop intuition in their research.