Journal of Combinatorics

Volume 14 (2023)

Number 4

Seven open problems in applied combinatorics

Pages: 559 – 601



Sinan G. Aksoy (Pacific Northwest National Laboratory, Richland, Washington, U.S.A.)

Ryan Bennink (Oak Ridge National Laboratory, Oak Ridge, Tennessee, U.S.A.)

Yuzhou Chen (Temple University, Philadelphia, Pennsylvania, U.S.A.)

José Frías (University of Texas, Dallas, Tx., U.S.A.)

Yulia R. Gel (University of Texas, Dallas, Tx., U.S.A.)

Bill Kay (Pacific Northwest National Laboratory, Richland, Washington, U.S.A.)

Uwe Naumann (RWTH Aachen University, Aachen, Germany)

Carlos Ortiz Marrero (Pacific Northwest National Laboratory, Richland, Washington, U.S.A.)

Anthony V. Petyuk

Sandip Roy (Washington State University, U.S.A.)

Ignacio Segovia-Dominguez (University of Texas at Dallas, Jet Propulsion Laboratory, Caltech, U.S.A.)

Nate Veldt (Texas A&M University, College Station, Tx., U.S.A.)

Stephen J. Young (Pacific Northwest National Laboratory, Richland, Washington, U.S.A.)


We present and discuss seven different open problems in applied combinatorics. The application areas relevant to this compilation include quantum computing, algorithmic differentiation, topological data analysis, iterative methods, hypergraph cut algorithms, and power systems.


open problems, applied combinatorics, quantum computing, quantum circuit, hypergraphs, algorithmic differentiation, directed acyclic graphs, zero-forcing, topological data analysis, Dowker complex, asynchronous updates, iterative methods

2010 Mathematics Subject Classification

Primary 05C90. Secondary 05C65, 65D25, 65F10, 65Y04, 81P68.

Sinan G. Aksoy, Anthony V. Petyuk, and Stephen J. Young were supported by the Resilience through Data-driven Intelligently- Designed Control (RD2C) Initiative, under the Laboratory Directed Research and Development (LDRD) Program at Pacific Northwest National Laboratory (PNNL). PNNL is a multi-program national laboratory operated for the U.S. Department of Energy (DOE) by Battelle Memorial Institute under Contract No. DE-AC05-76RL01830. Sandip Roy conducted this research during an appointment at the U.S. National Science Foundation, supported by an Intergovermental Personnel Act agreement with Washington State University.

Received 9 March 2023

Published 14 April 2023