Abstract
We study the planar matching problem, defined by a symmetric random matrix with independent identically distributed entries, taking values zero and one. We show that the existence of a perfect planar matching structure is possible only above a certain critical density, $p_c$, of allowed contacts. Using a formulation of the problem in terms of Dyck paths and a matrix model of planar contact structures, we provide an analytical estimation for the value of the transition point, $p_c$, in the thermodynamic limit. This estimation is close to the critical value, $p_c \approx 0.379$, obtained in numerical simulations based on an exact dynamical programming algorithm. We characterize the corresponding critical behavior of the model and discuss the relation of the perfect-imperfect matching transition to the known molten-glass transition in the context of random RNA secondary structure formation. In particular, we provide strong evidence supporting the conjecture that the molten-glass transition at $T=0$ occurs at $p_c$.
Introduction
The planar matching problem involves connecting $L$ points on a line in pairs using $L/2$ links under two primary constraints: planarity and admissibility. Planarity requires that no two links cross, a topological constraint common in RNA secondary structure folding where pseudoknots are generally avoided. Admissibility is governed by a random matrix $A$, where a link between points $i$ and $j$ is allowed only if $A_{ij}=1$. This problem serves as a classic Constraint Satisfaction Problem (CSP), analogous to the SAT-UNSAT transition. The central question is identifying the critical density $p$ of allowed contacts at which a perfect matching becomes impossible.
Methodology
The researchers employed four distinct analytical and numerical techniques to estimate the critical threshold:
- Naive Mean-Field Theory: Assumes independence of planar diagrams, predicting $p_c = 0.25$.
- Combinatorial "Corner Counting": Focuses on local "corners" (adjacent links) in Dyck paths, refining the estimate to $p_c \approx 0.35$.
- Matrix Field Theory: Utilizes a $1/N$ expansion from quantum field theory to derive a self-consistent propagator equation, yielding $p_c \approx 0.455$.
- Numerical Simulations: An exact dynamic programming algorithm (similar to the Nussinov algorithm) was used to find ground states for chain lengths $L$ ranging from 500 to 2000, averaged over 10,000 instances per data point.
Results and Scaling Behavior
Numerical simulations pinpoint the phase transition at $p_c \approx 0.379$. Near this threshold, the fraction of perfect matchings $\eta_L(p)$ exhibits a sharp transition that becomes increasingly vertical as the chain length $L$ increases.
Scaling analysis reveals that the data collapses onto a single curve when plotted against $(p - p_c)L^\nu$, with a critical exponent $\nu \approx 0.5$. In the perfect phase ($p > p_c$), the number of missing links (gaps) vanishes exponentially with $L$, whereas in the imperfect phase ($p < p_c$), a finite fraction of vertices remains unpaired, following power-law decay.
Discussion: The RNA Connection
The transition at $p_c$ is physically linked to the molten-glass transition in RNA. In the "molten" phase, the structure is flexible and universal, while in the "glassy" phase, the specific sequence disorder dictates a frozen, unique structure.
The study provides strong evidence that the molten-glass transition curve in the temperature-density $(p, T)$ plane terminates exactly at $p_c$ when the temperature $T = 0$. This identifies $p_c$ as the zero-temperature boundary of the glassy phase, where the lack of allowed contacts prevents the formation of a perfect, stable structure.
Conclusion
This work bridges abstract combinatorics and polymer physics, identifying a critical threshold for perfect planar matching. While analytical approximations vary, numerical results consistently point to $p_c \approx 0.379$. Future work could incorporate more realistic constraints like minimum loop lengths or limited pseudoknots to further refine the model's biological relevance.
Summary updated