Description
Abstract:
Let $D = d_1, d_2, \ldots, d_n$ and $F = f_1, f_2, \ldots, f_n$ be two sequences of positive integers such that for all $i$, $d_i \le 4$. Is there a vertex labeled, simple, connected graph $G = (V, E)$ such that for all $v_i$,
$$
d(v_i) = d_i, \ \ \ \ \sum_{w \in \mathcal{N}(v_i)} d(w) = f_i?
$$
Here the notation is usual, that is, $d(v)$ is the degree of $v$ and $\mathcal{N}(v)$ is the set of the neighbors of $v$.
We give a polynomial running time algorithm that decides if such $G$ exists and if so, constructs it. We also give a polynomial delay enumeration algorithm that constructs all possible solutions. Furthermore, we give a small set of perturbations for all possible solutions such that there is a short perturbation path between any two solutions using the given perturbations. These perturbations might form the transition kernel of a Markov chain Monte Carlo method sampling almost uniformly solutions and approximating the number of solutions to a given $D$ and $F$.
We also explain how the given problem is related to the prediction of structural formulae of saturated hydrocarbons using NMR spectroscopy data. No preliminary knowledge in organic chemistry is needed to understand the lecture.
Joint work with Uros Cibej, Aaron Li, Sohaib Nasir and Varun Srikanth.
Zoom link: https://zoom.us/j/2961946869