C&O PhD student Ahmad Abdi is a recipient of the 2018 Huawei Prize. This award provides $4,000 to a graduate student in the Faculty of Mathematics for demonstration of outstanding achievement in research through a peer-reviewed paper.
Ahmad was nominated for his paper "Packing odd T-joins with at most two terminals" (also available here), published in the Journal of Graph Theory and co-authored with his advisor, Professor Bertrand Guenin. An abbreviated version of the paper had appeared in the proceedings of the IPCO 2014 conference.
Ahmad's paper proves an important special case of Paul Seymour's celebrated Cycling Conjecture. This conjecture, first proposed in 1977, is widely considered as one of the most challenging and fundamental problems in the area of combinatorial optimization. The conjecture posits that binary Eulerian matroids for which the cut condition holds but which do not have an integer flow must contain one of four possible obstructions. This conjecture has far reaching consequences, including generalizations of the four-colour theorem such as Tutte's 4-flow conjecture.
Ahmad's paper proves the Cycling Conjecture for the class of even cycle matroids -- binary matroids that can be obtained as lifts of graphic matroids. The proof uses novel and powerful techniques, as well as tools from matroid theory, graph connectivity, and topological graph theory.