Seven open problems in applied combinatorics

Sinan G. Aksoy, Ryan Bennink, Yuzhou Chen, José Frías, Yulia R. Gel, Bill Kay, Uwe Naumann, Carlos Ortiz Marrero, Anthony V. Petyuk, Sandip Roy, Ignacio Segovia-Dominguez, Nate Veldt, Stephen J. Young

This isn't your typical research paper. Instead of presenting a single breakthrough, "Seven open problems in applied combinatorics" acts as a curated "hit list" for discrete mathematicians and engineers. It bridges the gap between abstract graph theory and the messy constraints of real-world systems, ranging from the stability of the U.S. power grid to the "expressiveness" of quantum circuits.

TL;DR

This paper identifies seven high-impact unsolved challenges in applied combinatorics, spanning quantum computing, topological data analysis, and high-performance computing. It provides a roadmap for researchers to translate theoretical graph properties into practical tools for optimizing complex, large-scale systems.

What Problem Does This Paper Address?

While combinatorial mathematics (the study of finite structures like graphs and networks) is a mature field, its application to modern engineering often hits a wall. Standard algorithms frequently fail to account for the specific "physics" of a problem—such as the way a quantum circuit applies phases to qubits or how communication delays between supercomputer nodes slow down linear solvers.

The authors argue that we lack the theoretical "connective tissue" to solve these problems efficiently. For example, in Topological Data Analysis (TDA), we know how to find the "shape" of data, but doing so for massive datasets is computationally prohibitive. In power systems, we can model a static grid, but we struggle to mathematically guarantee that a grid remains "observable" (controllable) when lines go down or renewable sources fluctuate.

Methods

Because this is a compilation of open problems, the "methods" described are the novel mathematical formulations used to frame these challenges:

  • Dowker Complexes (TDA): To solve the scalability issue in TDA, the authors propose using Dowker complexes as a "relaxed" version of the standard Vietoris-Rips complex. This involves selecting a subset of "landmarks" to represent the data's topology.
  • Probabilistic Combinatorics (Quantum): The paper maps the "expressiveness" of a quantum circuit (how well it can explore the state space) to a counting problem on binary matrices, specifically involving "abelian squares."
  • Cardinality-based Hypergraph Cuts (Optimization): In hypergraphs (where edges can connect more than two nodes), the authors introduce different "penalties" for how an edge is split (e.g., a 1-vs-3 split vs. a 2-vs-2 split), which changes the problem's computational complexity.
  • Zero-Forcing (Power Grids): They introduce $(n-k)$-contingent zero-forcing, a new variant of a graph-coloring process used to ensure that a set of sensors can "see" the entire state of a power grid even if $k$ edges are removed.

Datasets

As a theoretical framework paper, it does not rely on a single massive dataset. However, it utilizes:

  • Synthetic Graph Models: Cycle graphs (see Figure 1), trees, and random regular graphs.
  • Matrix Ensembles: For the "Price of Asynchrony" problem, the authors used Gaussian Orthonormal Ensembles and Wishart ensembles to simulate the iteration matrices of large-scale linear solvers.

Key Insights and Ideas

  • The Landmark Bottleneck: In TDA, the choice of landmarks is everything. Figure 1 illustrates how landmarks ($l_i$) and "witnesses" are used to build a simplicial complex on a cycle graph. The "aha moment" here is that Dowker complexes might preserve the "genus" (number of holes) of a graph while being much cheaper to compute than traditional methods.
Figure 1: Landmarks in a cycle graph.
  • Complexity Jumps: In hypergraph cuts, the problem is solvable in polynomial time if a 2-vs-2 split is twice as "expensive" as a 1-vs-3 split. However, if the 2-vs-2 split becomes even slightly more expensive ($w_2 > 2$), the complexity becomes an open question, potentially jumping to NP-hard.
  • The Convergence Bound: For asynchronous computing, the authors conjecture a specific upper bound on the convergence rate: $\rho(M^{(\delta)}) \leq \rho(M)^{1/(k+1)}$, where $k$ is the maximum delay. This suggests that asynchrony slows down solvers in a mathematically predictable way.

Key Results

  • Quantum Expressiveness: The authors provide an exact probability formula for the expressiveness of circuits using weight-1 and specific weight-2 qubit subsets.
  • Power Grid Resilience: They proved that for a tree-structured network (common in power distribution), a set of sensors is resilient to $k$ edge failures if and only if it contains all vertices with a degree of $k$ or less.
  • Asynchrony Experiments: Preliminary simulations on random matrices support their conjectured bound on convergence rates, showing that the "Price of Asynchrony" is largely determined by the mean delay between compute nodes.

Limitations and Future Work

The primary limitation is that many of these problems are likely NP-complete in their general forms. The "future work" is the core of the paper:

  1. Finding Approximation Algorithms: Especially for the "Data Flow Reversal" problem, where we need to reverse complex computer programs with limited memory.
  2. Structural Characterization: Can we find specific graph properties (like "few cycles" or "large diameter") that make these NP-hard problems solvable in practice for power grids?
  3. Refining Bounds: Moving from experimental observations to formal proofs for the convergence of asynchronous iterative methods.

Summary updated

Abstract

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.
BibTeX
@article{aksoy2023seven,
  author = {Sinan G. Aksoy and Ryan Bennink and Yuzhou Chen and José Frías and Yulia R. Gel and Bill Kay and Uwe Naumann and Carlos Ortiz Marrero and Anthony V. Petyuk and Sandip Roy and Ignacio Segovia-Dominguez and Nate Veldt and Stephen J. Young},
  title = {{Seven open problems in applied combinatorics}},
  journal = {Journal of Combinatorics},
  year = {2023},
  doi = {10.4310/joc.2023.v14.n4.a8},
}
Figure