PNNL researchers outline open combinatorics problems in different scientific areas
Combinatorics have applications across nearly all fields of science.
(Composite image by NicoElNino | Shutterstock.com)
Combinatorics is more than just counting. From quantum computing to stabilizing the power grid, combinatorics methods can be used to solve a myriad of problems across nearly all areas of science. In in a special issue of the Journal of Combinatorics, researchers from Pacific Northwest National Laboratory (PNNL) presented seven different open problems in applied combinatorics.
“The applicability of combinatorics to different problems has increased dramatically in recent years,” said Stephen Young, team leader of the Algorithms, Combinatorics, and Optimization team in the Advanced Computing, Mathematics, and Data Division at PNNL. Young, along with team leader and data scientist Sinan Aksoy of the AI & Data Analytics Division at PNNL, co-authored the paper and guest edited the special issue of the Journal of Combinatorics to highlight the diversity of combinatorics applications.
“Combinatorial methods have evolved to incorporate aspects of other areas of research, such as linear algebra, topology, computer science, and more,” said Aksoy. “The scope of combinatorics research is much broader now than ever before.”
When faced with thousands of different options, making the right choice can be a daunting task. This is where combinatorics excel. One of the most well-known and extensively studied examples of this is the traveling salesman problem.
Pretend you are a salesman traveling the country. If you only need to visit a small number of cities on your round-trip route, you would likely be able to figure out the shortest way to visit them fairly easily. However, as the number of cities increases, the problem becomes more complex. Combinatorics can help by treating this challenge like a graph problem: plotting cities as cities as vertices, and paths as the graph's edges. From there, the path can be optimized.
Though the traveling salesman problem is generally considered to be unsolvable, mathematicians and computer scientists often use this problem as a benchmark to see the power of new algorithms.
In their guest edited special issue, Young and Aksoy curated an eclectic collection of research papers that use combinatorics to solve or optimize scientific problems: from the investigating the thermodynamics of RNA folding to optimizing the computation of Hessian problems. In their paper, the authors pose several open questions in combinatorics to encourage more research in these areas.
“We intentionally selected problems outside of pure mathematics,” said Young. “With applications in areas like scientific computing, quantum computing, and the power grid, the impact of combinatorics research is extensive.”
Aksoy and Young, along with PNNL mathematician Bill Kay, are organizing a collection of talks around “Combinatorics for Science” for an American Mathematical Society special session at the upcoming Joint Mathematics Meeting in 2024.
Other PNNL authors of the paper are Bill Kay, Carlos Ortiz Marrero, Anthony Petyuk, and Washington State University Professor Sandip Roy, who holds a joint appointment with PNNL. The paper also includes authors from Oak Ridge National Laboratory, the University of Texas, Dallas, Temple University, RWTH Aachen University, and Texas A&M University. This work was partially supported by the Resilience through Data-driven Intelligently-Designed Control (RD2C) Initiative, under the laboratory directed research and development program at PNNL.