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.
Second derivatives of mathematical models for real-world phenomena are fundamental ingredients of a wide range of numerical simulation methods including parameter sensitivity analysis, uncertainty quantification, nonlinear optimization and model calibration. The evaluation of such Hessians often dominates the overall computational effort. The combinatorial Hessian Accumulation problem aiming to minimize the number of floating-point operations required for the computation of a Hessian turns out to be NP‑complete. We propose a dynamic programming formulation for the solution of Hessian Accumulation over a sub-search space. This approach yields improvements by factors of ten and higher over the state of the art based on second-order tangent and adjoint algorithmic differentiation.
In a recent article, Cheng, Maji and Pothen [3] consider squares of sparse Erdős–Rényi graphs $G(n, p)$ with $p = \Theta (1/n)$ as interesting benchmark instances to evaluate parallel algorithms that color the input graph in the context of estimating a sparse Jacobian for optimization. (Here $n$ is the number of vertices in the graph and every edge is included independently with probability $p$.) These authors prove that if $G$ is sampled from $G(n, p)$ with $p = \Theta (1/n)$, then with high probability, the chromatic number of the square graph $G^2$ lies between $\Omega \left ( \frac{\log n}{\log \log n} \right)$ and $\mathcal{O}(\log n)$. In this work we obtain a tight $\Theta \left ( \frac{\log n}{\log \log n} \right)$ bound on the chromatic number of $G^2$. Along the way we also obtain asymptotically tight bounds for the maximum degree of the $k$-th power of graphs sampled from $G(n, p)$.
The branching of an RNA molecule is an important structural characteristic yet difficult to predict correctly, especially for longer sequences. Using plane trees as a combinatorial model for RNA folding, we consider the thermodynamic cost, known as the barrier height, of transitioning between branching configurations. Using branching skew as a coarse energy approximation, we characterize various types of paths in the discrete configuration landscape. In particular, we give sufficient conditions for a path to have both minimal length and minimal branching skew. The proofs offer some biological insights, notably the potential importance of both hairpin stability and domain architecture to higher resolution RNA barrier height analyses.
We investigate various pursuit-evasion parameters on Latin square graphs, including the cop number, metric dimension, and localization number. Bounds for the cop number are given for Latin square graphs and for similarly defined graphs corresponding to $k$ mutually orthogonal Latin squares of order $n$. If $n \gt (k+1)^2$, then the cop number is shown to be $k+2$. Lower and upper bounds are provided for the metric dimension and localization number of Latin square graphs. An analysis of the metric dimension of back-circulant Latin squares shows that the lower bound is close to tight.
I describe how the number of abelian squares of given length relates to a certain problem in theoretical quantum computing, and I present a recursive formula for calculating the number of abelian squares of length $t + t$ over an alphabet of size $d$. The presented formula is similar to a previously known formula but has substantially lower complexity for large $d$, a key improvement resulting in a practical solution to the original application.
Subgraph centrality, introduced by Estrada and Rodríguez-Velázquez in [16], has become a widely used centrality measure in the analysis of networks, with applications in biology, neuroscience, economics and many other fields. It is also worthy of study from a strictly mathematical point of view, in view of its connections to topics in spectral graph theory, number theory, analytic matrix functions, and combinatorics. In this paper, we present some new results and a list of open questions about subgraph centrality and other node centrality measures based on graph walks.
Motivated by the inverse eigenvalue problem, vertex leaky forcing was recently introduced as a new variation of zero forcing in order to show how vertex leaks can disrupt the zero forcing process in a graph. An edge leak is an edge that is not allowed to be forced across during the zero forcing process. The $\ell$-edge-leaky forcing number of a graph is the size of a smallest zero forcing set that can force the graph blue despite $\ell$ edge leaks. This paper contains an analysis of the effect of edge leaks on the zero forcing process instead of vertex leaks. Furthermore, specified $\ell$-leaky forcing is introduced. The main result is that $\ell$-leaky forcing, $\ell$-edge-leaky forcing, and specified $\ell$-leaky forcing are equivalent. Furthermore, all of these different kinds of leaks can be mixed so that vertex leaks, edge leaks, and specified leaks are used. This mixed $\ell$-leaky forcing number is also the same as the (vertex) $\ell$-leaky forcing number.
In this paper, we propose an approximation of Frankl’s conjecture in the complement $\mathcal{C}$ of a union-closed family $\mathcal{F}$ in the power set of $U={1,\dotsc, n}$. Frankl’s conjecture is the statement that at least half the members of $\mathcal{F}$ contain some common element $k$ in $U$ and it is equivalent to at most half the members of $\mathcal{C}$ containing some $k$. This paper proves that at most $1/2 + 1/2n$ of the members in $\mathcal{C}$ contain some common element k. In addition, we show that, for arbitrarily small $\epsilon \gt 0$ and any constant $c$ such that $1 \gt c \gt 0$, there is an $N$ such that whenever $\mathcal{F} \subseteq \mathcal{P}(U)$ is a union-closed family of size ${\lvert \mathcal{F} \rvert} \gt c \cdot 2^n$ for some $n \geq N$ then there exists an element that appears in at least $1/2 - \epsilon$ of the member sets.
Given a graph $G$, the graph associahedron is a simple convex polytope whose face poset is based on the connected subgraphs of $G$. With the additional assignment of a color palette, we define the colorful graph associahedron, show it to be a collection of simple abstract polytopes, and explore its properties.