For Carnegie Mellon University junior Tony Yu, problem solving is logical.
“I’m really curious. If there’s something that’s not known then I want to see if I can fill in some of the gaps,” said Yu, who recently transferred from majoring in discrete mathematics to computer science.
Yu spent the summer working with Peleg Michaeli, a postdoctoral researcher in the Department of Mathematical Sciences, conducting research on the properties of discrepancies in graphs particularly in the case of Hamilton cycles.
“Tony is a curious, bright and hard-working student who took leadership on the project very early,” Michaeli said. “Equipped with proof skills on the one hand and programming skills on the other hand, he successfully navigated the research process, eventually leading to interesting results.”
Essentially, Yu looked at how a set of vertices on a graph are connected by edges.
“We’re looking for ways to group all of the lines and assign colors to the lines by minimizing the difference between the number of lines of different colors,” Yu said. Work like this is foundational for combinatorics, a branch of mathematics dealing with combinations of objects belonging to a set. Methods can be used to count potential outcomes in probability experiments. It also can be used to develop estimates for how many operations an algorithm may need.
“Combinatorial discrepancy is an important field with many connections to the rest of mathematics and applications in computer science,” said Yu, whose work was supported by a Summer Undergraduate Research Fellowship, which awards $3,500 to undergraduates at CMU for eight to 10 weeks of summer research in any field of study.
His summer findings describe more general conditions for a graph to have a linear discrepancy of Hamilton cycles (the difference between the number of edges colored in color 1 and the number of edges colored in color 2 is on the order of the total number of vertices).
“One of the big things about research is that it teaches you to think in a way that’s unconventional and requires pizzazz to obtain to obtain a solution that might be unclear,” Yu said.
Yu’s work often exists at the intersection of mathematics and computer science. Last summer he worked with John Mackey, a teaching professor in the Mathematical Sciences and Computer Science Departments, and Marijn Heule, an associate professor of computer science.
Yu said he came to CMU with an open mind and many interests.
“I was happy to come to CMU, a university where I had really good options,” he said.
“I fell in love with Buggy once I got involved in it,” Yu said. “I really like the energy and the atmosphere and the competitiveness. Students bring their passion to it and test the boundaries of what is possible. It really captures what makes CMU, CMU.”