Showing 1–50 of 79 results for author: Gong, S

Minimizing the number of edges in $\mathcal{C}_{[4,6]}$-saturated graphs

Authors: Qi Liu, Dijian Wang, Shicai Gong

Abstract: Let $\mathcal{C}_{[4,r]}$ be the family of cycles $\{C_4, \dots, C_r\}$. A graph $G$ is said to be $\mathcal{C}_{[4,r]}$-saturated if $G$ does not contain a copy of cycle $C_i$ for $4\le i\le r$, but the addition of any edge $e\notin E(G)$ creates at least one copy of $C_i$ for $4\le i\le r.$ The saturation number $sat(n, \mathcal{C}_{[4,r]})$ is the minimum number of edges in an $n$-vertex… ▽ More Let $\mathcal{C}_{[4,r]}$ be the family of cycles $\{C_4, \dots, C_r\}$. A graph $G$ is said to be $\mathcal{C}_{[4,r]}$-saturated if $G$ does not contain a copy of cycle $C_i$ for $4\le i\le r$, but the addition of any edge $e\notin E(G)$ creates at least one copy of $C_i$ for $4\le i\le r.$ The saturation number $sat(n, \mathcal{C}_{[4,r]})$ is the minimum number of edges in an $n$-vertex $\mathcal{C}_{[4,r]}$-saturated graph. In 2025, Ma determined that $sat(n, \mathcal{C}_{[4,5]})=\lceil \frac{5n}{4} - \frac{3}{2} \rceil$, and conjectured that for any $r \ge 5$, $sat(n, \mathcal{C}_{[4,r]}) = \lceil\frac{5n}{4} - \frac{3}{2} \rceil$ holds for large $n$. In this paper we prove that $sat(n, \mathcal{C}_{[4,r]}) \le \lceil\frac{5n}{4} - \frac{r+1}{4}\rceil$ for $n \ge r+1$, which disproves Ma's conjecture for $r\ge 6.$ For $r=6,$ we determine that $sat(n, \mathcal{C}_{[4,6]})=\lceil\frac{5n}{4}-\frac{7}{4}\rceil.$ {\bf Keywords}: Saturation graphs; Saturation number; Cycles; Edge minimization △ Less

Submitted 19 August, 2026; originally announced August 2026.

Comments: 25 pages, 11 figures

MSC Class: 05C35

Dual-Thrust Switching Analytical Guidance Algorithm for Powered Landing with Attitude Smoothness Optimization

Authors: Wenbo Li, Dai Shen, Shengping Gong

Abstract: Traditional numerical guidance methods for powered landing of reusable rockets are typically constrained by high computational complexity and inadequate real-time performance. Moreover, insufficient consideration of attitude smoothness often induces severe fluctuations in control commands; meanwhile, most existing approaches are tailored for single-thrust scenarios, failing to accommodate the guid… ▽ More Traditional numerical guidance methods for powered landing of reusable rockets are typically constrained by high computational complexity and inadequate real-time performance. Moreover, insufficient consideration of attitude smoothness often induces severe fluctuations in control commands; meanwhile, most existing approaches are tailored for single-thrust scenarios, failing to accommodate the guidance requirements of multi-engine thrust switching. To mitigate these limitations, this paper proposes an analytical guidance method optimized for attitude smoothness, which supports dual-thrust-mode switching. First, a corresponding optimal control problem is formulated, and it is theoretically proven that the optimal attitude command takes a concise piecewise cubic function form. This transforms complex trajectory optimization into a parametric analytical optimization problem, yielding a substantial improvement in computational efficiency. Further, a three-phase guidance framework is designed to enable adaptive determination of the guidance activation point and thrust switching point; when integrated with an aerodynamic correction strategy, this framework enhances the method's adaptability in complex flight environments particularly under high lift-to-drag ratio conditions. Simulation results demonstrate that the attitude command profile generated by the proposed method aligns closely with the theoretical optimal solution, with an ultra-short computation time, confirming its strong potential for online real-time implementation. Even under stringent conditions (e.g., limited thrust adjustment range, high lift-to-drag ratios, and parameter deviations), the method consistently achieves high-precision landing, showcasing promising prospects for engineering applications. △ Less

Submitted 16 August, 2026; originally announced August 2026.

Condensed PIPG Sequential Convex Optimization for Reusable-Rocket Powered Landing with Strong Aerodynamics

Authors: Wenbo Li, Linwei Li, Ziqi Xu, Shengping Gong

Abstract: Reusable-rocket powered landing under strong aerodynamics couples variable mass, free final time, and bounded aerodynamic controls through nonlinear velocity-frame dynamics. This paper develops a condensed proportional--integral projected-gradient (PIPG) sequential-convex method whose principal contribution is an exact reduced-space inner architecture. Because the problem contains only six termina… ▽ More Reusable-rocket powered landing under strong aerodynamics couples variable mass, free final time, and bounded aerodynamic controls through nonlinear velocity-frame dynamics. This paper develops a condensed proportional--integral projected-gradient (PIPG) sequential-convex method whose principal contribution is an exact reduced-space inner architecture. Because the problem contains only six terminal hard equalities and no state path constraints, 217 nodal-state variables and 210 trapezoidal dynamics equalities are eliminated from the 31-node convex subproblem, leaving 101 primal variables and six terminal equalities. Row-orthogonal preconditioning, fixed-size matrix--vector products, and nodewise circular-epigraph projections then yield a customized PIPG kernel. Physical consistency of the angle-dependent axial force is maintained by gradually releasing drag sensitivity between the reference squared angle and an epigraph variable $A$, together with a convex tightness term. A pointwise Hamiltonian argument shows that the fully released limiting subproblem admits a tight optimum satisfying $A=α^2+β^2$. Deterministic annealing, two-stage inner accuracy, and a rejected-on-failure threefold extrapolation are secondary outer-loop accelerators. △ Less

Submitted 16 August, 2026; originally announced August 2026.

Submillisecond Sequential Convex Optimization for Powered Landing via Dynamics Condensation and xPIPG

Authors: Wenbo Li, Ziqi Xu, Dai Shen, Shengping Gong

Abstract: Powered landing with variable mass, free final time, and quadratic aerodynamic drag requires the repeated solution of local convex subproblems, whose main online cost lies in the long dynamics-equality chain and the inner iterations. This paper develops a condensed sequential convex approximation designed for low latency. Exact block elimination removes 217 intermediate-state components and 210 in… ▽ More Powered landing with variable mass, free final time, and quadratic aerodynamic drag requires the repeated solution of local convex subproblems, whose main online cost lies in the long dynamics-equality chain and the inner iterations. This paper develops a condensed sequential convex approximation designed for low latency. Exact block elimination removes 217 intermediate-state components and 210 interval equations from a 31-node model, leaving 100 primal variables coupled by six terminal equalities. A low-weight energy term and fixed quadratic proximal regularization make the ideal surrogate strongly convex with predictable curvature. The inner solver is an extrapolated proportional--integral projected gradient (xPIPG) implemented with fixed-size arrays, $3\times3$ interval solves, and a fused one-pass node map. The one-pass map is a deliberate low-cost approximation, not the exact joint proximal operator. We therefore evaluate the timed code by nonlinear trajectory residuals and independent physical checks rather than by a claim of exact KKT convergence. The single-precision C implementation completes one plan in four outer updates and 336 xPIPG updates. On an Intel Core i7-10875H, the median end-to-end solve time is \SI{374}{\micro\second} and the P99 value is \SI{512}{\micro\second}. All 100 common initial-state perturbations pass validation, and the median remains below \SI{0.7}{\milli\second} for 15--51 nodes. An independent high-accuracy first-order-hold integration gives a terminal position error of \SI{0.183}{\meter}. Within the stated model, hardware, stopping rule, and timing boundary, this is, to the authors' knowledge, the first submillisecond end-to-end sequential-convex solve for a single powered-landing trajectory. △ Less

Submitted 10 August, 2026; originally announced August 2026.

Explicit Matrices over $\mathbb Z_2$ with CNOT and Row Complexity $4n-\mathrm{o}(n)$ and Local Logic Gates

Authors: Sherry Gong, Andrew Yu

Abstract: In this article, we present an explicit family of invertible $n\times n$ matrices over $\mathbb Z_2$ whose CNOT and row complexity is at least $4n-\text{o}(n)$; equivalently, reducing these matrices to the identity requires at least $4n-\text{o}(n)$ elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by ar… ▽ More In this article, we present an explicit family of invertible $n\times n$ matrices over $\mathbb Z_2$ whose CNOT and row complexity is at least $4n-\text{o}(n)$; equivalently, reducing these matrices to the identity requires at least $4n-\text{o}(n)$ elementary row operations. Moreover, the same complexity lower bound holds in the stronger computational model where the CNOT gates are replaced by arbitrary local linear logic gates, namely arbitrary invertible linear transformations acting on pairs of coordinates. Let $G_n$ denote the permutation group generated by local logic gates acting on the set of binary strings of length $n$. We prove that $G_n$ is naturally isomorphic to the group of all invertible affine transformations of the vector space $\mathbb Z_2^n$, thus reducing the problem of estimating the quantum complexity of permutations in $G_n$ to the row reduction complexity of invertible matrices over $\mathbb Z_2$. As an application, we show that the permutations associated with our explicit matrices have quantum complexity at least $4n-\text{o}(n)$. △ Less

Submitted 30 July, 2026; originally announced July 2026.

Microsecond-Class Powered-Descent Optimization via Exact Condensation and Strong Convex Regularization

Authors: Wenbo Li, Ziqi Xu, Dai Shen, Shengping Gong

Abstract: Fuel-dominant powered descent can be written as a convex program, but the usual full-state epigraph formulation still carries many state variables, fuel epigraph variables, and dynamics equalities. In addition, the pure-fuel objective provides no strong-convexity curvature. This paper combines three structural reductions. First, a dimensionally consistent low-weight energy term makes the control s… ▽ More Fuel-dominant powered descent can be written as a convex program, but the usual full-state epigraph formulation still carries many state variables, fuel epigraph variables, and dynamics equalities. In addition, the pure-fuel objective provides no strong-convexity curvature. This paper combines three structural reductions. First, a dimensionally consistent low-weight energy term makes the control solution unique. Second, a terminal-state sensitivity recursion eliminates every intermediate state exactly; invertible row normalization turns the 30-node baseline with 300 primal variables and 174 equality multipliers into a problem with 90 control variables and six terminal multipliers. Third, the shared radial structure of the fuel norm and thrust ball gives an exact closed-form proximal operator consisting of group shrinkage followed by magnitude clipping. The condensed problem is solved with a fixed-budget extrapolated proportional--integral projected-gradient iteration implemented in fixed-size C17 arrays. In a Mars powered-descent case with energy weight 0.02 and relative reference-solution tolerance $10^{-3}$, the iteration count decreases from 2744 for the pure-fuel full-state epigraph baseline to 93, while the fuel metric increases by only 0.033\%. The mean end-to-end solve time is \SI{68.2}{\micro\second}, and P99 is \SI{128.1}{\micro\second}, on an Intel i7-10875H. Because the thrust set in this test case is already a convex ball, the contribution is fast solution of the convex core rather than a new lossless-convexification theorem. △ Less

Submitted 28 July, 2026; originally announced July 2026.

The Conclave Process

Authors: Itai Benjamini, Zhenhao Cai, Guanyi Chen, Shuyang Gong, Zhangsong Li

Abstract: We introduce a stochastic model for the papal conclave in which $n$ cardinals vote repeatedly among themselves until one cardinal receives all the votes. In each round, the probability that a cardinal votes for a given candidate is proportional to the $α$-th power of that candidate's vote count in the preceding round. For $α=1$, the model reduces to the Wright-Fisher model and is dual to Kingman's… ▽ More We introduce a stochastic model for the papal conclave in which $n$ cardinals vote repeatedly among themselves until one cardinal receives all the votes. In each round, the probability that a cardinal votes for a given candidate is proportional to the $α$-th power of that candidate's vote count in the preceding round. For $α=1$, the model reduces to the Wright-Fisher model and is dual to Kingman's n-coalescent. We reveal a sharp transition in the absorption time $\mathcal{T}$ at $α=1$. It was known that when $α=1$, $\mathcal{T}$ is typically of order $n$. We prove that for $α>1$, it drops to order $\textit{loglog n.}$ In contrast, for $α<1$, $\mathcal{T}$ is typically at least $\exp(Ω(n))$. We also prove a sharp phase transition in the identity of the winner when $α>1$. For every positive integer $k$, if $2^{1/k}<α<2^{1/(k-1)}$ (where we write $2^{1/0} = +\infty$), with probability tending to 1 as $n\to\infty$, the eventual winner is the unique leader after round $k$. These results show that reinforced voting processes reach consensus remarkably quickly even for large electorates. △ Less

Submitted 10 August, 2026; v1 submitted 24 July, 2026; originally announced July 2026.

Three-Body Earth-Moon Transfers with Different Departure/Arrival Orbital Altitudes: New Phenomenon and Diffusion Model-Augmented Construction

Authors: Shuyue Fu, Wenxuan Zhang, Di Wu, Shengping Gong, Peng Shi

Abstract: Construction of Earth-Moon transfers is the basis of missions to explore the Moon and cislunar space. The traditional grid search method suffers from a relatively low convergence rate and computational efficiency, mainly focusing on the distribution of transfer characteristic parameters. Moreover, when constructing transfers with different departure/arrival orbital altitudes, the process of grid s… ▽ More Construction of Earth-Moon transfers is the basis of missions to explore the Moon and cislunar space. The traditional grid search method suffers from a relatively low convergence rate and computational efficiency, mainly focusing on the distribution of transfer characteristic parameters. Moreover, when constructing transfers with different departure/arrival orbital altitudes, the process of grid search and trajectory correction should be repeated with a low convergence rate and computational efficiency. To address these limitations of the traditional grid search method, this paper is devoted to exploring an effective way to augment the grid search method. Bi-impulsive Earth-Moon transfers from a circular Earth parking orbit to a circular Moon target orbit in the Earth-Moon planar circular restricted three-body problem are considered in this paper. Firstly, the transfers are constructed, and the corresponding solution space is explored in terms of construction parameters, including departure phase angle at the Earth parking orbit, initial-to-circular velocity ratio, and time of flight. An interesting phenomenon about the discontinuous behavior of the time-of-flight distribution with respect to departure phase angle is identified. This phenomenon is further used to train a diffusion model, which aims to augment the traditional grid search method and generate high-quality initial guesses for transfers with different departure/arrival orbital altitudes. The construction results of the proposed method are presented and analyzed. The proposed diffusion model-augmented grid search method improves the convergence rate by 47.34-56.25% and saves the wall-clock time by 39.39-40.52% over the traditional grid search method relatively, while ensuring comparable transfer characteristics. △ Less

Submitted 4 August, 2026; v1 submitted 26 June, 2026; originally announced June 2026.

A conservative adaptive rank method for the Wigner-Poisson system

Authors: Andrew Christlieb, Sining Gong, F. Alejandro Padilla-Gomez, Jing-Mei Qiu

Abstract: We propose a conservative adaptive rank method for the 1D1V Wigner-Poisson system. The method targets a central challenge in deterministic quantum kinetic simulations: reducing the cost of phase-space evolution while preserving the macroscopic invariants needed for physical fidelity. The scheme combines a sampling-based adaptive rank Wigner-Poisson update [7] with a conservative macroscopic correc… ▽ More We propose a conservative adaptive rank method for the 1D1V Wigner-Poisson system. The method targets a central challenge in deterministic quantum kinetic simulations: reducing the cost of phase-space evolution while preserving the macroscopic invariants needed for physical fidelity. The scheme combines a sampling-based adaptive rank Wigner-Poisson update [7] with a conservative macroscopic correction. A conservative density-momentum solve provides local macroscopic updates, a Fermi-Dirac-type reconstruction transfers them to the kinetic solution, and a global quadratic moment correction enforces the discrete total energy constraint at the kinetic level. Unlike Maxwell-Boltzmann-type corrections commonly used in classical kinetic settings, the reconstruction uses a Fermi-Dirac-type form motivated by the model's quantum-statistical structure. The corrected state is incorporated into an ACA SVD representation, allowing the numerical rank to adapt to the phase-space complexity generated by the nonlocal Wigner operator and self-consistent Poisson field. Numerical experiments for the two-stream instability, strong Landau damping, and bump-on tail instability show that the method captures benchmark Wigner-Poisson dynamics for several values of the quantum parameter H, maintains bounded adaptive ranks, and preserves the specified global discrete invariants with conservation errors near machine precision. We also compare this formulation, which uses local density-momentum correction plus global total energy correction, with a related globally conservative formulation for mass, momentum, and energy [8]. The two approaches produce nearly identical phase-space and diagnostic results for the periodic benchmark test considered here, indicating that both correction strategies are compatible with adaptive rank compression for Wigner-Poisson dynamics in the tested 1D1V periodic setting. △ Less

Submitted 18 June, 2026; originally announced June 2026.

A Structure-preserving Adaptive-Rank Approach to the High-Dimensional Wigner-Poisson System

Authors: Andrew J. Christlieb, Sining Gong, Jing-Mei Qiu, Nanyi Zheng

Abstract: The Wigner-Poisson system is a deterministic phase-space model for quantum kinetic electron dynamics, but high-dimensional simulations are limited by the full 3D3V phase space and the nonlocal Wigner potential. We develop a structure-preserving, sampling-based adaptive-rank solver in hierarchical Tucker format for finite-$H$ regimes in which Wigner-Poisson solutions exhibit exploitable low-rank st… ▽ More The Wigner-Poisson system is a deterministic phase-space model for quantum kinetic electron dynamics, but high-dimensional simulations are limited by the full 3D3V phase space and the nonlocal Wigner potential. We develop a structure-preserving, sampling-based adaptive-rank solver in hierarchical Tucker format for finite-$H$ regimes in which Wigner-Poisson solutions exhibit exploitable low-rank structure. The central difficulty is that adaptive compression can destroy the Fourier-Hermitian tensor symmetry required for a real inverse velocity transform and can break discrete global conservation laws. We address these issues with a Fourier-Hermitian-symmetry-aware sampling and mapping procedure and a global moment correction enforcing mass, momentum, and self-consistent total energy. Numerical tests for two-stream instability and strong Landau damping in 2D2V and 3D3V show roundoff-level conservation, preservation of the real-valued inverse transform, and approximately linear scaling with respect to the number of grid points per coordinate over the tested rank range. The results demonstrate that long-time 3D3V Wigner-Poisson simulations can be performed without assembling the full phase-space tensor. △ Less

Submitted 12 June, 2026; originally announced June 2026.

An Energy-Conserving Unstaggered Electromagnetic-Potential Particle-in-Cell Method, Part I: Non-relativistic Generalized-Momentum Formulation

Authors: Andrew J. Christlieb, Luis Chacon, Sining Gong

Abstract: We develop an unstaggered, potential-based particle-in-cell method for the nonrelativistic Vlasov-Maxwell system in the Lorenz gauge. The field update is written as a Crank-Nicolson discretization of first-order wave systems for the scalar potential, the vector potential, and their time derivatives. The charge density is not deposited directly; instead, it is advanced from the discrete continuity… ▽ More We develop an unstaggered, potential-based particle-in-cell method for the nonrelativistic Vlasov-Maxwell system in the Lorenz gauge. The field update is written as a Crank-Nicolson discretization of first-order wave systems for the scalar potential, the vector potential, and their time derivatives. The charge density is not deposited directly; instead, it is advanced from the discrete continuity equation using the current deposited from the particles. This opens up algorithmic flexibility with a range of innovation, including unstaggered mesh layouts that preserve the Lorenz gauge and Gauss's law at the discrete level. In the potential formulation, this source ordering also permits preservation of the Lorenz gauge and Gauss's law at the discrete level. To extend the paradigm to an energy-conserving formulation, we introduce a consistent orbit-averaged scatter, gather, and particle push. For energy consistency, the update of the canonical momentum is modified by replacing the pointwise midpoint derivative of the vector potential with an orbit-averaged discrete gradient of the mesh-interpolated vector potential consistent with the orbit-average maps. This construction satisfies an exact finite-difference chain rule along each particle orbit. As a result, the particle work equals the mesh work appearing in the Crank-Nicolson field-energy balance, yielding exact total-energy conservation up to nonlinear solver tolerance and roundoff. We demonstrate exact energy conservation of the method in 3D on the cold two-stream instability. △ Less

Submitted 12 June, 2026; originally announced June 2026.

Convergence of parallel overlapping domain decomposition methods with impedance boundary conditions for time-harmonic Maxwell equations in heterogeneous media

Authors: Luyu Cen, Shihua Gong, Euan A. Spence, Yue Yu

Abstract: This paper analyzes the convergence of parallel overlapping domain-decomposition methods with impedance boundary conditions for the time-harmonic Maxwell equations in heterogeneous media. We prove that the parallel iterative method is well-posed in an appropriate function space, and characterize the error propagation operator through impedance-to-impedance maps that describe interactions between n… ▽ More This paper analyzes the convergence of parallel overlapping domain-decomposition methods with impedance boundary conditions for the time-harmonic Maxwell equations in heterogeneous media. We prove that the parallel iterative method is well-posed in an appropriate function space, and characterize the error propagation operator through impedance-to-impedance maps that describe interactions between neighboring subdomains. For strip domain decompositions, we derive explicit convergence estimates in terms of the norms of the impedance-to-impedance maps. At the discrete level, we develop the finite-element counterpart of these results based on Nédélec-element discretisations. Under the assumption that the discrete impedance-to-impedance maps approximate their continuous counterparts as the mesh is refined, we show that the discrete method inherits the convergence behavior of the continuous method. We illustrate this theory with numerical experiments for strip domain decompositions, and also present numerical experiments for checkerboard domain decompositions that go beyond our theory. △ Less

Submitted 3 June, 2026; originally announced June 2026.

Comments: 38 pages

MSC Class: 65N30

The 2-Twist Spun Trefoil Has Crossing Number Six

Authors: Sherry Gong, Samuel Lewis-Monkman, Jesse Osnes

Abstract: We study the tri-plane crossing number, that is, the minimal number of crossings in a tri-plane diagram for a bridge trisection of a knotted sphere in $S^4$. We show that every 2-knot in $S^4$ that admits a bridge trisection with at most five crossings is ribbon. As a consequence, we show that the 2-twist spin of the trefoil has crossing number 6. This is the first such computation for a non-trivi… ▽ More We study the tri-plane crossing number, that is, the minimal number of crossings in a tri-plane diagram for a bridge trisection of a knotted sphere in $S^4$. We show that every 2-knot in $S^4$ that admits a bridge trisection with at most five crossings is ribbon. As a consequence, we show that the 2-twist spin of the trefoil has crossing number 6. This is the first such computation for a non-trivial knotted surface. △ Less

Submitted 15 June, 2026; v1 submitted 2 June, 2026; originally announced June 2026.

Comments: 10 pages, 14 figures. Comments welcome

MSC Class: 57K45

Sharp inf-sup estimate for the Stokes equation in tight domains with periodic pillars and some numerical implications

Authors: Qi Xin, Shihua Gong, Jinchao Xu

Abstract: The predictive simulation of fluid dynamics in densely packed microfluidic devices, such as Deterministic Lateral Displacement (DLD) arrays, stagnates with standard iterative solvers. We show that this failure is not algorithmic but rooted in the pre-asymptotic degradation of the pressure-velocity coupling stability. For periodic pillar geometries in a generalized lattice framework, we prove that… ▽ More The predictive simulation of fluid dynamics in densely packed microfluidic devices, such as Deterministic Lateral Displacement (DLD) arrays, stagnates with standard iterative solvers. We show that this failure is not algorithmic but rooted in the pre-asymptotic degradation of the pressure-velocity coupling stability. For periodic pillar geometries in a generalized lattice framework, we prove that the continuous Ladyzhenskaya-Babuška-Brezzi (LBB) condition, also called the inf-sup constant, deteriorates exactly as $m^{-1}$ up to a positive multiplicative constant, where $m$ is the pillar density (the number of pillars per unit length). This induces a priori error amplification proportional to $m$ and a pressure Schur complement condition number scaling as $\mathcal{O}(m^2)$. To overcome this theoretical limit, we propose a parameter-free, adaptively scaled Augmented Lagrangian (AL) stabilization strategy with penalty $γ\propto m^2$. Numerical experiments on both standard square and asymmetric DLD arrays validate the theoretical bounds: the AL method reduces outer FGMRES iterations from 437 to 22 on a 1.85M-DoF square array and from 687 to 24 on a 1.77M-DoF DLD array. △ Less

Submitted 23 May, 2026; v1 submitted 14 April, 2026; originally announced April 2026.

Comments: 20 pages

MSC Class: 65N30; 65N55; 65N20

Stable algorithms cannot reliably find isolated perceptron solutions

Authors: Shuyang Gong, Brice Huang, Shuangping Li, Mark Sellke

Abstract: We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A striking feature of this model is that at every positive constraint density, it is expected that a $1-o_N(1)$ fraction of solutions are \emph{strongly isolated}, i.e. separated from all others by Hamming distance $Ω(N)$. At the… ▽ More We study the binary perceptron, a random constraint satisfaction problem that asks to find a Boolean vector in the intersection of independently chosen random halfspaces. A striking feature of this model is that at every positive constraint density, it is expected that a $1-o_N(1)$ fraction of solutions are \emph{strongly isolated}, i.e. separated from all others by Hamming distance $Ω(N)$. At the same time, efficient algorithms are known to find solutions at certain positive constraint densities. This raises a natural question: can any isolated solution be algorithmically visible? We answer this in the negative: no algorithm whose output is stable under a tiny Gaussian resampling of the disorder can \emph{reliably} locate isolated solutions. We show that any stable algorithm has success probability at most $\frac{3\sqrt{17}-9}{4}+o_N(1)\leq 0.84233$. Furthermore, every stable algorithm that finds a solution with probability $1-o_N(1)$ finds an isolated solution with probability $o_N(1)$. The class of stable algorithms we consider includes degree-$D$ polynomials up to $D\leq o(N/\log N)$; under the low-degree heuristic \cite{hopkins2018statistical}, this suggests that locating strongly isolated solutions requires running time $\exp(\widetildeΘ(N))$. Our proof does not use the overlap gap property. Instead, we show via Pitt's correlation inequality that after a random perturbation of the disorder, the number of solutions located close to a pre-existing isolated solution cannot concentrate at $1$. △ Less

Submitted 31 March, 2026; originally announced April 2026.

Comments: 27 pages, 1 figure

Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models

Authors: Shuyang Gong, Dong Huang, Zhangsong Li

Abstract: We consider the problem of community detection from the joint observation of a high-dimensional covariate matrix and $L$ sparse networks, all encoding noisy, partial information about the latent community labels of $n$ subjects. In the asymptotic regime where the networks have constant average degree and the number of features $p$ grows proportionally with $n$, we derive a sharp threshold under wh… ▽ More We consider the problem of community detection from the joint observation of a high-dimensional covariate matrix and $L$ sparse networks, all encoding noisy, partial information about the latent community labels of $n$ subjects. In the asymptotic regime where the networks have constant average degree and the number of features $p$ grows proportionally with $n$, we derive a sharp threshold under which detecting and estimating the subject labels is possible. Our results extend the work of \cite{MN23} to the constant-degree regime with noisy measurements, and also resolve a conjecture in \cite{YLS24+} when the number of networks is a constant. Our information-theoretic lower bound is obtained via a novel comparison inequality between Bernoulli and Gaussian moments, as well as a statistical variant of the ``recovery to chi-square divergence reduction'' argument inspired by \cite{DHSS25}. On the algorithmic side, we design efficient algorithms based on counting decorated cycles and decorated paths and prove that they achieve the sharp threshold for both detection and weak recovery. In particular, our results show that there is no statistical-computational gap in this setting. △ Less

Submitted 8 February, 2026; originally announced February 2026.

Comments: 49 pages, 5 figures

MSC Class: Primary 62F15; 68Q87; Secondary 05C85; 90C35

A quasi-monolithic localized high-order ALE finite element method for multi-scale fluid-structure interaction problems

Authors: Lingyue Shen, Qi Xin, Yan Chen, Jiarui Han, Yumiao Zhang, Jinchao Xu, Shihua Gong

Abstract: This paper presents a quasi-monolithic localized high-order arbitrary Lagrangian-Eulerian (qMLH-ALE) finite element method for multi-scale fluid-structure interaction (FSI) in microfluidic systems. The fluid momentum, the incompressible Neo-Hookean constitutive law, and the left Cauchy-Green tensor $\mathcal{B}$ are assembled into a single implicit system, while the harmonic mesh extension is upda… ▽ More This paper presents a quasi-monolithic localized high-order arbitrary Lagrangian-Eulerian (qMLH-ALE) finite element method for multi-scale fluid-structure interaction (FSI) in microfluidic systems. The fluid momentum, the incompressible Neo-Hookean constitutive law, and the left Cauchy-Green tensor $\mathcal{B}$ are assembled into a single implicit system, while the harmonic mesh extension is updated explicitly in a staggered manner. Isoparametric $\mathcal{P}_2$ elements provide third-order geometric approximation of curved fluid-solid interfaces, and a second-order implicit-explicit partitioned Runge-Kutta scheme delivers second-order temporal accuracy without the dissipation of backward Euler. A localized updating strategy confines the moving mesh and the deformation history to a body-fitted sub-domain coupled with a precomputed steady background flow, bridging the scale disparity between local FSI dynamics and the macroscopic microchannel geometry. The Turek-Hron FSI3 benchmark, performed at unit fluid-solid density ratio, reproduces the reference beam-tip amplitude and frequency within $3\%$, confirming stability under the strong added-mass coupling that destabilizes conventional partitioned schemes. Three-dimensional particle-focusing simulations in spiral microchannels further illustrate the framework on long-range multi-scale problems. △ Less

Submitted 22 May, 2026; v1 submitted 2 February, 2026; originally announced February 2026.

Comments: 31 pages

MSC Class: 65L60

High-order DLM-ALE discretizations with robust operator preconditioning for fluid-rigid-body interaction

Authors: Qi Xin, Shihua Gong, Lingyue Shen, Pinjing Wen, Yumiao Zhang, Yan Chen, Jiarui Han, Jinchao Xu

Abstract: Motivated by the design of deterministic lateral displacement (DLD) microfluidic devices, we develop a high-order numerical framework for fluid-rigid-body interaction on fitted moving meshes. Rigid-body motion is enforced by a distributed Lagrange multiplier (DLM) formulation, while the moving fluid domain is treated by an arbitrary Lagrangian-Eulerian (ALE) mapping. In space, we use isoparametric… ▽ More Motivated by the design of deterministic lateral displacement (DLD) microfluidic devices, we develop a high-order numerical framework for fluid-rigid-body interaction on fitted moving meshes. Rigid-body motion is enforced by a distributed Lagrange multiplier (DLM) formulation, while the moving fluid domain is treated by an arbitrary Lagrangian-Eulerian (ALE) mapping. In space, we use isoparametric Taylor-Hood elements to achieve high-order accuracy and to represent curved boundaries and the fluid-particle interface. In time, we employ a high-order partitioned Runge-Kutta strategy in which the mesh motion is advanced explicitly and the coupled physical fields are advanced implicitly, yielding high-order accuracy for the particle trajectory. The fully coupled system is linearized into a generalized Stokes problem subject to distributed constraints of incompressibility and rigid-body motion. We establish well-posedness of this generalized Stokes formulation at both the continuous and discrete levels, providing the stability foundation for operator preconditioning that is robust with respect to key physical and discretization parameters. Numerical experiments on representative benchmarks, including a DLD case, demonstrate high-order convergence for the fluid solution and rigid-body dynamics, as well as robust iterative convergence of the proposed preconditioners. △ Less

Submitted 8 February, 2026; v1 submitted 1 February, 2026; originally announced February 2026.

MSC Class: 65L60; 65F08

Massively parallel Schwarz methods for the high frequency Helmholtz equation

Authors: Yan Xie, Shihua Gong, Ivan G. Graham, Euan A. Spence, Chen-Song Zhang

Abstract: We investigate the parallel one-level overlapping Schwarz method for solving finite element discretization of high-frequency Helmholtz equations. The resulting linear systems are large, indefinite, ill-conditioned, and complex-valued. We present a practical variant of the restricted additive Schwarz method with Perfectly Matched Layer transmission conditions (RAS-PML), which was originally analyze… ▽ More We investigate the parallel one-level overlapping Schwarz method for solving finite element discretization of high-frequency Helmholtz equations. The resulting linear systems are large, indefinite, ill-conditioned, and complex-valued. We present a practical variant of the restricted additive Schwarz method with Perfectly Matched Layer transmission conditions (RAS-PML), which was originally analyzed in a theoretical setting in {\tt arXiv:2404.02156}, with some numerical experiments given in {\tt arXiv:2408.16580}. In our algorithm, the width of the overlap and the additional PML layer on each subdomain is allowed to decrease with $\mathcal{O}(k^{-1} \log(k))$, as the frequency $k \rightarrow \infty$, and this is observed to ensure good convergence while avoiding excessive communication. In experiments, the proposed method achieves $\mathcal{O}(k^d)$ parallel scalability under Cartesian domain decomposition and exhibits $\mathcal{O}(k)$ iteration counts and convergence time for $d$-dimensional Helmholtz problems ($d = 2,3$) as $k$ increases. In this preliminary note we restrict to experiments on 2D problems with constant wave speed. Details, analysis and extensions to variable wavespeed and 3D will be given in future work. △ Less

Submitted 31 January, 2026; originally announced February 2026.

Efficient Enumeration of Cliques in Graphs with Bounded Maximum Degree

Authors: Shi-Cai Gong, Jia-Jin Wang, Xin-Hao Zhu, Bo-Jun Yuan

Abstract: In recent years, there has been a surge of interest in extremal problems concerning the enumeration of independent sets or cliques in graphs with specific constraints. For instance, the Kahn-Zhao theorem establishes an upper bound on the number of independent sets in a $d$-regular graph. Building on this, Cutler and Radcliffe extended the result by identifying the graph that maximizes the number o… ▽ More In recent years, there has been a surge of interest in extremal problems concerning the enumeration of independent sets or cliques in graphs with specific constraints. For instance, the Kahn-Zhao theorem establishes an upper bound on the number of independent sets in a $d$-regular graph. Building on this, Cutler and Radcliffe extended the result by identifying the graph that maximizes the number of cliques among graphs with bounded order and maximum degree. In this paper, we introduce an innovative approach for counting cliques in graphs with a bounded maximum degree. To demonstrate the effectiveness of the method, we provide a new proof for the above Cutler-Radcliffe theorem and the Kahn-Zhao theorem. △ Less

Submitted 4 January, 2026; originally announced January 2026.

The trinacria graphs $T_{(b+2)b2}$ are $e$-positive

Authors: Simon Y. M. Gong, David G. L. Wang, K. Zhang

Abstract: In this paper, we identify a new family of $e$-positive graphs, called the trinacria graphs $T_{(b+2)b2}$, thereby providing a partial answer to Stanley's question on which graphs are $e$-positive. The trinacria graph $T_{abc}$ is the graph on $a+b+c+3$ vertices obtained by attaching paths $P_a$, $P_b$ and~$P_c$ to the vertices of a triangle, respectively. Our proof relies on several ad hoc combin… ▽ More In this paper, we identify a new family of $e$-positive graphs, called the trinacria graphs $T_{(b+2)b2}$, thereby providing a partial answer to Stanley's question on which graphs are $e$-positive. The trinacria graph $T_{abc}$ is the graph on $a+b+c+3$ vertices obtained by attaching paths $P_a$, $P_b$ and~$P_c$ to the vertices of a triangle, respectively. Our proof relies on several ad hoc combinatorial ideas, and employs divide-and-conquer techniques, charging arguments, and progressive repair methods. △ Less

Submitted 25 December, 2025; originally announced December 2025.

Ribbon concordances and slice obstructions: experiments and examples

Authors: Nathan M. Dunfield, Sherry Gong

Abstract: There are 352.2 million prime knots in the 3-sphere with at most 19 crossings. We study which of these knots are slice, in both the smooth and topological categories. While no algorithm is known for deciding whether a given knot is slice in either setting, we are able to determine it smoothly for all but about 11,400 knots (0.003% or 1 in 30,000) and topologically for all but about 1,400 knots (0.… ▽ More There are 352.2 million prime knots in the 3-sphere with at most 19 crossings. We study which of these knots are slice, in both the smooth and topological categories. While no algorithm is known for deciding whether a given knot is slice in either setting, we are able to determine it smoothly for all but about 11,400 knots (0.003% or 1 in 30,000) and topologically for all but about 1,400 knots (0.0004% or about 1 in 250,000). In particular, we show that some 1.6 million of these knots (0.46%) are smoothly slice (in fact ribbon) and that 350.5 million are not even topologically slice (99.54%). We use a wide range of tools and techniques, and introduce several new or refined methods for probing these properties. Along the way, we produce 500,000 pairs of 0-friends, that is, pairs of distinct knots with the same 0-surgery. We discuss how our data is consistent with several important conjectures and suggests new ones, and highlight the simplest knots where sliceness remains unknown. △ Less

Submitted 25 December, 2025; originally announced December 2025.

Comments: 62 pages, 24 figures, 12 tables

MSC Class: 57K10 (Primary) 57K18; 57K32; 57K40; 57M99 (Secondary)

Parameter Optimization in Trajectory Planning via Differentiable Convex Programming

Authors: Ziqi Xu, Lin Cheng, Di Wu, Shengping Gong

Abstract: Sequential convex programming has been established as an effective framework for solving nonconvex trajectory planning problems. However, its performance is highly sensitive to problem parameters, including trajectory variables, algorithmic hyperparameters, and physical vehicle parameters. This paper introduces a differentiable sequential convex programming framework that integrates differentiable… ▽ More Sequential convex programming has been established as an effective framework for solving nonconvex trajectory planning problems. However, its performance is highly sensitive to problem parameters, including trajectory variables, algorithmic hyperparameters, and physical vehicle parameters. This paper introduces a differentiable sequential convex programming framework that integrates differentiable convex optimization with sequential convex programming to enable end-to-end parameter optimization. By deriving first-order sensitivity relations of second-order cone programming solutions with respect to problem data, exact gradients of trajectory performance metrics with respect to arbitrary parameters are obtained and propagated through iterations. The effectiveness of the proposed framework is validated through three representative applications: optimal terminal-time prediction for powered landing, trust-region penalty optimization in subproblems, and surface-to-mass ratio optimization for hypersonic gliding vehicles. Simulation results show that the proposed framework enables reliable gradient-based parameter learning and significantly improves numerical performance, convergence behavior, and design efficiency. These results indicate that the differentiable sequential convex programming framework provides a powerful and general tool for vehicle design, mission optimization, and hyperparameter selection in aerospace trajectory planning. △ Less

Submitted 8 December, 2025; v1 submitted 3 December, 2025; originally announced December 2025.

Discontinuous Behavior of Time-of-Flight Distribution for Bi-impulsive Earth-Moon Transfers in the Three-Body Model

Authors: Shuyue Fu, Di Wu, Shengping Gong

Abstract: As interest in the Earth-Moon transfers renewed around the world, understanding the solution space of transfer trajectories facilitates the construction of transfers. This paper is devoted to reporting a novel or less-reported phenomenon about the solution space of bi-impulsive Earth-Moon transfers in the Earth-Moon planar circular restricted three-body problem. Differing from the previous works f… ▽ More As interest in the Earth-Moon transfers renewed around the world, understanding the solution space of transfer trajectories facilitates the construction of transfers. This paper is devoted to reporting a novel or less-reported phenomenon about the solution space of bi-impulsive Earth-Moon transfers in the Earth-Moon planar circular restricted three-body problem. Differing from the previous works focusing on the transfer characteristics of the solution space, we focus on the distribution of the construction parameters, i.e., departure phase angle at the Earth parking orbit, initial-to-circular velocity ratio, and time of flight. Firstly, the construction method of bi-impulsive transfers is described, and the solutions satisfying the given constraints are obtained from the grid search method and trajectory correction. Then, the distribution of the obtained solutions is analyzed, and an interesting phenomenon about the discontinuous behavior of the time-of-flight distribution for each departure phase angle is observed and briefly reported. This phenomenon can further provide useful insight into the construction of bi-impulsive transfers, deepening the understanding of the corresponding solution space. △ Less

Submitted 30 October, 2025; originally announced October 2025.

Families of Transfers from circular low Earth orbit to Distant Prograde Orbit around the Moon

Authors: Shuyue Fu, Di Wu, Yihan Peng, Peng Shi, Shengping Gong

Abstract: Distant prograde orbits around the Moon exhibit remarkable potential for practical applications such as cislunar surveillance activities and low-energy transfers due to their instability. Previous works on transfers from circular low Earth orbit to distant prograde orbits mainly focused on construction methods based on dynamical structures, lacking a comprehensive analysis of the solution space of… ▽ More Distant prograde orbits around the Moon exhibit remarkable potential for practical applications such as cislunar surveillance activities and low-energy transfers due to their instability. Previous works on transfers from circular low Earth orbit to distant prograde orbits mainly focused on construction methods based on dynamical structures, lacking a comprehensive analysis of the solution space of this transfer scenario. This paper investigates the solution space and identifies families of transfers from a 167 km circular low Earth orbit to a 1:1 distant prograde orbit. In particular, grid search and trajectory continuation are performed to construct these transfer trajectories. Initial guesses of the transfers are selected in the 1:1 distant prograde orbit through a backward propagation strategy and are then corrected to satisfy specified constraints. Based on the obtained solutions, a linear predictor is derived to predict more feasible solutions and a predictor-corrector continuation method is used to extend the solution space. Twelve transfer families are identified, most of which are new or previously underexplored. The distributions of construction parameters and transfer characteristics of these twelve families are analyzed and discussed, showing which families are applicable to which types of specific practical missions. Comparison between the obtained solution and solution developed by previous works is further performed to imply the effects of the selection of dynamical model on transfer construction. △ Less

Submitted 3 August, 2025; originally announced August 2025.

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms

Authors: Shankar Bhamidi, David Gamarnik, Shuyang Gong

Abstract: We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applications in biology and social sciences \cites{madeira-survey,shabalin2009finding} and is known to exhibit a computation-to-optimization gap between the optimal value and best values achievable by existing polynomial time a… ▽ More We consider the problem of finding a dense submatrix of a matrix with i.i.d. Gaussian entries, where density is measured by average value. This problem arose from practical applications in biology and social sciences \cites{madeira-survey,shabalin2009finding} and is known to exhibit a computation-to-optimization gap between the optimal value and best values achievable by existing polynomial time algorithms. In this paper we consider the class of online algorithms, which includes the best known algorithm for this problem, and derive a tight approximation factor ${4\over 3\sqrt{2}}$ for this class. The result is established using a simple implementation of recently developed Branching-Overlap-Gap-Property \cite{huang2025tight}. We further extend our results to $(\mathbb R^n)^{\otimes p}$ tensors with i.i.d. Gaussian entries, for which the approximation factor is proven to be ${2\sqrt{p}/(1+p)}$. △ Less

Submitted 25 July, 2025; originally announced July 2025.

Comments: 11 pages

MSC Class: 62G32 60G70; 68Q17

A Sampling-Based Adaptive Rank Approach to the Wigner-Poisson System

Authors: Andrew Christlieb, Sining Gong, Jing-Mei Qiu, Nanyi Zheng

Abstract: We develop a mass-conserving, adaptive-rank solver for the 1D1V Wigner-Poisson system. Our work is motivated by applications to the study of the stopping power of $α$ particles at the National Ignition Facility (NIF). In this regime, electrons are in a warm dense state, requiring more than a standard kinetic model. They are hot enough to neglect Pauli exclusion, yet quantum enough to require accou… ▽ More We develop a mass-conserving, adaptive-rank solver for the 1D1V Wigner-Poisson system. Our work is motivated by applications to the study of the stopping power of $α$ particles at the National Ignition Facility (NIF). In this regime, electrons are in a warm dense state, requiring more than a standard kinetic model. They are hot enough to neglect Pauli exclusion, yet quantum enough to require accounting for uncertainty. The Wigner-Poisson system captures these effects but presents challenges due to its nonlocal nature. Based on a second-order Strang splitting method, we first design a full-rank solver with a structure-preserving Fourier update that ensures the intermediate solutions remain real-valued (up to machine precision), improving upon previous methods. Simulations demonstrate that the solutions exhibit a low rank structure for moderate to high dimensionless Planck constants ($H \ge 0.1$). This observed low rank structure motivates the development of an adaptive-rank solver, built on a Semi-Lagrangian adaptive-rank (SLAR) scheme for advection and an adaptive-rank, structure-preserving Fourier update for the Wigner integral terms, with a rigorous proof of structure-preserving property provided. Our solver achieves $O(N)$ complexity in both storage and computation time, while preserving mass and maintaining momentum accuracy up to the truncation error. The adaptive rank simulations are visually indistinguishable from the full-rank simulations in capturing solution structures. These results highlight the potential of adaptive rank methods for high-dimensional Wigner-Poisson simulations, paving the way toward fully kinetic studies of stopping power in warm dense plasmas. △ Less

Submitted 26 June, 2025; originally announced June 2025.

Detection and Reconstruction of a Random Hypergraph from Noisy Graph Projection

Authors: Shuyang Gong, Zhangsong Li, Qiheng Xu

Abstract: For a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included i.i.d.\ so that the average degree in the hypergraph is $n^{δ+o(1)}$, the projection of such a hypergraph is a graph on the same $n$ vertices where an edge connects two vertices if and only if they belong to a same hyperedge. In this work, we study the inference problem where the observation is a \emph{noisy} vers… ▽ More For a $d$-uniform random hypergraph on $n$ vertices in which hyperedges are included i.i.d.\ so that the average degree in the hypergraph is $n^{δ+o(1)}$, the projection of such a hypergraph is a graph on the same $n$ vertices where an edge connects two vertices if and only if they belong to a same hyperedge. In this work, we study the inference problem where the observation is a \emph{noisy} version of the graph projection where each edge in the projection is kept with probability $p=n^{-1+α+o(1)}$ and each edge not in the projection is added with probability $q=n^{-1+β+o(1)}$. For all constant $d$, we establish sharp thresholds for both detection (distinguishing the noisy projection from an Erdős-Rényi random graph with edge density $q$) and reconstruction (estimating the original hypergraph). Notably, our results reveal a \emph{detection-reconstruction gap} phenomenon in this problem. Our work also answers a problem raised in \cite{BGPY25+}. △ Less

Submitted 2 April, 2026; v1 submitted 20 June, 2025; originally announced June 2025.

Comments: 19 pages, 1 figure; Section 6 rewritten to fix a previous error

Asymptotic diameter of preferential attachment model

Authors: Hang Du, Shuyang Gong, Zhangsong Li, Haodong Zhu

Abstract: We study the asymptotic diameter of the preferential attachment model $\operatorname{PA}\!_n^{(m,δ)}$ with parameters $m \ge 2$ and $δ> 0$. Building on the recent work \cite{VZ25}, we prove that the diameter of $G_n \sim \operatorname{PA}\!_n^{(m,δ)}$ is $(1+o(1))\log_νn$ with high probability, where $ν$ is the exponential growth rate of the local weak limit of $G_n$. Our result confirms the conje… ▽ More We study the asymptotic diameter of the preferential attachment model $\operatorname{PA}\!_n^{(m,δ)}$ with parameters $m \ge 2$ and $δ> 0$. Building on the recent work \cite{VZ25}, we prove that the diameter of $G_n \sim \operatorname{PA}\!_n^{(m,δ)}$ is $(1+o(1))\log_νn$ with high probability, where $ν$ is the exponential growth rate of the local weak limit of $G_n$. Our result confirms the conjecture in \cite{VZ25} and closes the remaining gap in understanding the asymptotic diameter of preferential attachment graphs with general parameters $m \ge 1$ and $δ>-m$. Our proof follows a general recipe that relates the diameter of a random graph to its typical distance, which we expect to have applicability in a broader range of models. △ Less

Submitted 30 April, 2025; originally announced April 2025.

Comments: 11 pages

MSC Class: 05C80; 05C82

Journal ref: Electronic Communications in Probability, 31:1-12 (2026)

Design and Continuation of Nonlinear Teardrop Hovering Formation along the Near Rectilinear Halo Orbit

Authors: Shuyue Fu, Yihan Peng, Shengping Gong, Peng Shi

Abstract: This short communication is devoted to the design and continuation of a teardrop hovering formation along the Near Rectilinear Halo orbit and provides further insights into future on-orbit services in the cislunar space. First, we extend the concept of the teardrop hovering formation to scenarios along the Near Rectilinear Halo orbit in the Earth-Moon circular restricted three-body problem. Then,… ▽ More This short communication is devoted to the design and continuation of a teardrop hovering formation along the Near Rectilinear Halo orbit and provides further insights into future on-orbit services in the cislunar space. First, we extend the concept of the teardrop hovering formation to scenarios along the Near Rectilinear Halo orbit in the Earth-Moon circular restricted three-body problem. Then, we develop two methods for designing these formations based on the nonlinear model for relative motion. The first method addresses the design of the teardrop hovering formations with relatively short revisit distances, while the second method continues hovering trajectories from short to longer revisit distances. In particular, new continuation method is developed to meet the design requirements of this new scenario. Simulation results verify the effectiveness of the proposed methods, and a near-natural teardrop hovering formation is achieved by considering the dynamical properties near the NRHO. Comparisons between design results obtained using linear and nonlinear models further strengthen the necessity of using the nonlinear model. △ Less

Submitted 16 April, 2025; originally announced April 2025.

Journal ref: Aerospace Science and Technology, 2025

Analytical Strategies and Winning Conditions for Elliptic-Orbit Target-Attacker-Defender Game

Authors: Shuyue Fu, Shengping Gong, Di Wu, Peng Shi

Abstract: This paper proposes an analytical framework for the orbital Target-Attacker-Defender game with a non-maneuvering target along elliptic orbits. Focusing on the linear quadratic game, we derive an analytical solution to the matrix Riccati equation, which yields analytical Nash-equilibrium strategies for the game. Based on the analytical strategies, we derive the analytical form of the necessary and… ▽ More This paper proposes an analytical framework for the orbital Target-Attacker-Defender game with a non-maneuvering target along elliptic orbits. Focusing on the linear quadratic game, we derive an analytical solution to the matrix Riccati equation, which yields analytical Nash-equilibrium strategies for the game. Based on the analytical strategies, we derive the analytical form of the necessary and sufficient winning conditions for the attacker. The simulation results show good consistency between the analytical and numerical methods, exhibiting 0.004$\%$ relative error in the cost function. The analytical method achieves over 99.9$\%$ reduction in CPU time compared to the conventional numerical method, strengthening the advantage of developing the analytical strategies. Furthermore, we verify the proposed winning conditions and investigate the effects of eccentricity on the game outcomes. Our analysis reveals that for games with hovering initial states, the initial position of the defender should be constrained inside a mathematically definable set to ensure that the attacker wins the game. This constrained set further permits geometric interpretation through our proposed method. This work establishes the analytical framework for orbital Target-Attacker-Defender games, providing fundamental insights into the solution analysis of the game. △ Less

Submitted 28 March, 2025; v1 submitted 18 March, 2025; originally announced March 2025.

Comments: Correction on Eq. (78) for this paper and Eq. (55) for the article published in Aerospace Science and Technology (doi:10.1016/j.ast.2025.109946)

Journal ref: Journal of Guidance, Control, and Dynamics, 2025

Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime

Authors: Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li

Abstract: Consider a pair of sparse correlated stochastic block models $\mathcal S(n,\tfracλ{n},ε;s)$ subsampled from a common parent stochastic block model with two symmetric communities, average degree $λ=O(1)$, divergence parameter $ε\in (0,1)$ and subsampling probability $s$. For all $ε\in(0,1)$ and $Δ>0$, we construct a statistic based on the combination of two low-degree polynomials and show that ther… ▽ More Consider a pair of sparse correlated stochastic block models $\mathcal S(n,\tfracλ{n},ε;s)$ subsampled from a common parent stochastic block model with two symmetric communities, average degree $λ=O(1)$, divergence parameter $ε\in (0,1)$ and subsampling probability $s$. For all $ε\in(0,1)$ and $Δ>0$, we construct a statistic based on the combination of two low-degree polynomials and show that there exists a sufficiently small constant $δ=δ(ε,λ,Δ)>0$ such that if $ε^2 λs>1+Δ$ and $s>\sqrtα-δ$ where $α\approx 0.338$ is Otter's constant, this statistic can distinguish this model and a pair of independent stochastic block models $\mathcal S(n,\tfrac{λs}{n},ε)$ with probability $1-o(1)$. We also provide an efficient algorithm that approximates this statistic in polynomial time. The crux of our statistic's construction lies in a carefully curated family of multigraphs called \emph{decorated trees}, which enables effective aggregation of the community signal and graph correlation by leveraging the counts of the same decorated tree while suppressing the undesirable correlations among counts of different decorated trees. We believe such construction may be of independent interest. △ Less

Submitted 23 September, 2025; v1 submitted 9 March, 2025; originally announced March 2025.

Comments: This substantially improves the result in an earlier version. 98 pages, 13 figures

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models

Authors: Hang Du, Shuyang Gong, Jiaming Xu

Abstract: We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al.~\cite{bet2023detecting} show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change o… ▽ More We investigate the problem of detecting and estimating a changepoint in the attachment function of a network evolving according to a preferential attachment model on $n$ vertices, using only a single final snapshot of the network. Bet et al.~\cite{bet2023detecting} show that a simple test based on thresholding the number of vertices with minimum degrees can detect the changepoint when the change occurs at time $n-Ω(\sqrt{n})$. They further make the striking conjecture that detection becomes impossible for any test if the change occurs at time $n-o(\sqrt{n}).$ Kaddouri et al.~\cite{kaddouri2024impossibility} make a step forward by proving the detection is impossible if the change occurs at time $n-o(n^{1/3}).$ In this paper, we resolve the conjecture affirmatively, proving that detection is indeed impossible if the change occurs at time $n-o(\sqrt{n}).$ Furthermore, we establish that estimating the changepoint with an error smaller than $o(\sqrt{n})$ is also impossible, thereby confirming that the estimator proposed in Bhamidi et al.~\cite{bhamidi2018change} is order-optimal. △ Less

Submitted 5 June, 2025; v1 submitted 1 February, 2025; originally announced February 2025.

Comments: Added more discussion on background and proof ideas; Extended abstract of this paper will be presented at the Conference on Learning Theory (COLT) 2025

MSC Class: Primary 05C80; Secondary 68Q87

The number of dissociation sets in connected graphs

Authors: Bo-Jun Yuan, Ni Yang, Hong-Yan Ge, Shi-Cai Gong

Abstract: Extremal problems related to the enumeration of graph substructures, such as independent sets, matchings, and induced matchings, have become a prominent area of research with the advancement of graph theory. A subset of vertices is called a dissociation set if it induces a subgraph with vertex degree at most $1$, making it a natural generalization of these previously studied substructures. In th… ▽ More Extremal problems related to the enumeration of graph substructures, such as independent sets, matchings, and induced matchings, have become a prominent area of research with the advancement of graph theory. A subset of vertices is called a dissociation set if it induces a subgraph with vertex degree at most $1$, making it a natural generalization of these previously studied substructures. In this paper, we present efficient tools to strictly increase the number of dissociation sets in a connected graph. Furthermore, we establish that the maximum number of dissociation sets among all connected graphs of order $n$ is given by \begin{align*} \begin{cases} 2^{n-1}+(n+3)\cdot 2^{\frac{n-5}{2}}, &~ {\rm if}~ n~{\rm is}~{\rm odd};\\ 2^{n-1}+(n+6)\cdot 2^{\frac{n-6}{2}}, &~ {\rm if}~ n~{\rm is}~{\rm even}. \end{cases} \end{align*} Additionally, we determine the achievable upper bound on the number of dissociation sets in a tree of order $n$ and characterize the corresponding extremal graphs as an intermediate result. Finally, we identify the unicyclic graph that is the candidate for having the second largest number of dissociation sets among all connected graphs. △ Less

Submitted 22 December, 2024; originally announced December 2024.

Analytical Pursuit-Evasion Game Strategy in Arbitrary Keplerian Reference Orbits

Authors: Shuyue Fu, Shengping Gong, Peng Shi

Abstract: This paper develops an analytical strategy for solving the linear quadratic pursuit-evasion game in arbitrary Keplerian reference orbits. The motion of the pursuer and evader is described using the controlled Tschauner-Hempel equations, and the optimal game strategies of the pursuer and evader are presented by the solution of the differential Riccati equation.The analytical solution of the differe… ▽ More This paper develops an analytical strategy for solving the linear quadratic pursuit-evasion game in arbitrary Keplerian reference orbits. The motion of the pursuer and evader is described using the controlled Tschauner-Hempel equations, and the optimal game strategies of the pursuer and evader are presented by the solution of the differential Riccati equation.The analytical solution of the differential Riccati equation is presented for elliptic, parabolic, and hyperbolic reference orbits, thereby enabling an analytical pursuit-evasion game strategy. Then, the procedure to solve the pursuit-evasion game using this analytical strategy is proposed. Simulations of pursuit-evasion game in elliptic, parabolic, and hyperbolic reference orbits validate the effectiveness of the developed analytical strategy. Results indicates that the analytical strategy saves the CPU time by more than 99.8$\%$ compared to the numerical one, highlighting the efficiency of the developed strategy. The developed analytical strategy is also applicable to pursuit-evasion game scenarios considering orbital disturbances. Compared to the conventional strategy, which succeed in only two out of six test scenarios, the developed strategy achieves success in all six cases, particularly demonstrating its effectiveness in high-eccentricity cases. △ Less

Submitted 18 December, 2024; v1 submitted 24 November, 2024; originally announced November 2024.

Journal ref: Aerospace Science and Technology, 2025

Deep Generative Demand Learning for Newsvendor and Pricing

Authors: Shijin Gong, Huihang Liu, Xinyu Zhang

Abstract: We consider data-driven inventory and pricing decisions in the feature-based newsvendor problem, where demand is influenced by both price and contextual features and is modeled without any structural assumptions. The unknown demand distribution results in a challenging conditional stochastic optimization problem, further complicated by decision-dependent uncertainty and the integration of features… ▽ More We consider data-driven inventory and pricing decisions in the feature-based newsvendor problem, where demand is influenced by both price and contextual features and is modeled without any structural assumptions. The unknown demand distribution results in a challenging conditional stochastic optimization problem, further complicated by decision-dependent uncertainty and the integration of features. Inspired by recent advances in deep generative learning, we propose a novel approach leveraging conditional deep generative models (cDGMs) to address these challenges. cDGMs learn the demand distribution and generate probabilistic demand forecasts conditioned on price and features. This generative approach enables accurate profit estimation and supports the design of algorithms for two key objectives: (1) optimizing inventory for arbitrary prices, and (2) jointly determining optimal pricing and inventory levels. We provide theoretical guarantees for our approach, including the consistency of profit estimation and convergence of our decisions to the optimal solution. Extensive simulations-ranging from simple to complex scenarios, including one involving textual features-and a real-world case study demonstrate the effectiveness of our approach. Our method opens a new paradigm in management science and operations research, is adaptable to extensions of the newsvendor and pricing problems, and holds potential for solving other conditional stochastic optimization problems. △ Less

Submitted 13 November, 2024; originally announced November 2024.

Comments: 30 pages, 6 figures

Maximal and maximum induced matchings in connected graphs

Authors: Bo-Jun Yuan, Zhao-Yu Yang, Lu Zheng, Shi-Cai Gong

Abstract: An induced matching in a graph is a set of edges whose endpoints induce a $1$-regular subgraph. Gupta et al. (2012,\cite{Gupta}) showed that every $n$-vertex graph has at most $10^{\frac{n}{5}}\approx 1.5849^n$ maximal induced matchings, which is attained by the disjoint union of copies of the complete graph $K_5$. In this paper, we show that the maximum number of maximal and maximum induced mat… ▽ More An induced matching in a graph is a set of edges whose endpoints induce a $1$-regular subgraph. Gupta et al. (2012,\cite{Gupta}) showed that every $n$-vertex graph has at most $10^{\frac{n}{5}}\approx 1.5849^n$ maximal induced matchings, which is attained by the disjoint union of copies of the complete graph $K_5$. In this paper, we show that the maximum number of maximal and maximum induced matchings in a connected graph of order $n$ is \begin{align*} \begin{cases} {n\choose 2} &~ {\rm if}~ 1\leq n\le 8; \\ {{\lfloor \frac{n}{2} \rfloor}\choose 2}\cdot {{\lceil \frac{n}{2} \rceil}\choose 2} -(\lfloor \frac{n}{2} \rfloor-1)\cdot (\lceil \frac{n}{2} \rceil-1)+1 &~ {\rm if}~ 9\leq n\le 13; \\ 10^{\frac{n-1}{5}}+\frac{n+144}{30}\cdot 6^{\frac{n-6}{5}} &~ {\rm if}~ 14\leq n\le 30;\\ 10^{\frac{n-1}{5}}+\frac{n-1}{5}\cdot 6^{\frac{n-6}{5}} & ~ {\rm if}~ n\geq 31, \\ \end{cases} \end{align*} and also show that this bound is tight. This result implies that we can enumerate all maximal induced matchings of an $n$-vertex connected graph in time $O(1.5849^n)$. Moreover, our result provides an estimate on the number of maximal dissociation sets of an $n$-vertex connected graph. △ Less

Submitted 15 October, 2024; originally announced October 2024.

Boundary corrections for kernel approximation to differential operators

Authors: Andrew Christlieb, Sining Gong, Hyoseon Yang

Abstract: Kernel-based approach to operator approximation for partial differential equations has been shown to be unconditionally stable for linear PDEs and numerically exhibit unconditional stability for non-linear PDEs. These methods have the same computational cost as an explicit finite difference scheme but can exhibit order reduction at boundaries. In previous work on periodic domains, [8,9], order red… ▽ More Kernel-based approach to operator approximation for partial differential equations has been shown to be unconditionally stable for linear PDEs and numerically exhibit unconditional stability for non-linear PDEs. These methods have the same computational cost as an explicit finite difference scheme but can exhibit order reduction at boundaries. In previous work on periodic domains, [8,9], order reduction was addressed, yielding high-order accuracy. The issue addressed in this work is the elimination of order reduction of the kernel-based approach for a more general set of boundary conditions. Further, we consider the case of both first and second order operators. To demonstrate the theory, we provide not only the mathematical proofs but also experimental results by applying various boundary conditions to different types of equations. The results agree with the theory, demonstrating a systematic path to high order for kernel-based methods on bounded domains. △ Less

Submitted 23 November, 2025; v1 submitted 11 October, 2024; originally announced October 2024.

A computational transition for detecting correlated stochastic block models by low-degree polynomials

Authors: Guanyi Chen, Jian Ding, Shuyang Gong, Zhangsong Li

Abstract: Detection of correlation in a pair of random graphs is a fundamental statistical and computational problem that has been extensively studied in recent years. In this work, we consider a pair of correlated (sparse) stochastic block models $\mathcal{S}(n,\tfracλ{n};k,ε;s)$ that are subsampled from a common parent stochastic block model $\mathcal S(n,\tfracλ{n};k,ε)$ with $k=O(1)$ symmetric communiti… ▽ More Detection of correlation in a pair of random graphs is a fundamental statistical and computational problem that has been extensively studied in recent years. In this work, we consider a pair of correlated (sparse) stochastic block models $\mathcal{S}(n,\tfracλ{n};k,ε;s)$ that are subsampled from a common parent stochastic block model $\mathcal S(n,\tfracλ{n};k,ε)$ with $k=O(1)$ symmetric communities, average degree $λ=O(1)$, divergence parameter $ε$, and subsampling probability $s$. For the detection problem of distinguishing this model from a pair of independent Erdős-Rényi graphs with the same edge density $\mathcal{G}(n,\tfrac{λs}{n})$, we focus on tests based on \emph{low-degree polynomials} of the entries of the adjacency matrices, and we determine the threshold that separates the easy and hard regimes. More precisely, we show that this class of tests can distinguish these two models if and only if $s> \min \{ \sqrtα, \frac{1}{λε^2} \}$, where $α\approx 0.338$ is the Otter's constant and $\frac{1}{λε^2}$ is the Kesten-Stigum threshold. Combining a reduction argument in \cite{Li25+}, our hardness result also implies low-degree hardness for partial recovery and detection (to independent block models) when $s< \min \{ \sqrtα, \frac{1}{λε^2} \}$. Finally, our proof of low-degree hardness is based on a conditional variant of the low-degree likelihood calculation. △ Less

Submitted 22 July, 2025; v1 submitted 2 September, 2024; originally announced September 2024.

Comments: 80 pages, 2 figures, added further explanations and remarks; to appear in Annals of Statistics

MSC Class: Primary 62M20; Secondary 68Q87; 68Q17

Journal ref: Annals of Statistics, 54(1):226-251 (February 2026)

Schwarz methods with PMLs for Helmholtz problems: fast convergence at high frequency

Authors: Jeffrey Galkowski, Shihua Gong, Ivan G. Graham, David Lafontaine, Euan A. Spence

Abstract: We discuss parallel (additive) and sequential (multiplicative) variants of overlapping Schwarz methods for the Helmholtz equation in $\mathbb{R}^d$, with large real wavenumber and smooth variable wave speed. The radiation condition is approximated by a Cartesian perfectly-matched layer (PML). The domain-decomposition subdomains are overlapping hyperrectangles with Cartesian PMLs at their boundarie… ▽ More We discuss parallel (additive) and sequential (multiplicative) variants of overlapping Schwarz methods for the Helmholtz equation in $\mathbb{R}^d$, with large real wavenumber and smooth variable wave speed. The radiation condition is approximated by a Cartesian perfectly-matched layer (PML). The domain-decomposition subdomains are overlapping hyperrectangles with Cartesian PMLs at their boundaries. In a recent paper ({\tt arXiv:2404.02156}), the current authors proved (for both variants) that, after a specified number of iterations -- depending on the behaviour of the geometric-optic rays -- the error is smooth and smaller than any negative power of the wavenumber $k$. For the parallel method, the specified number of iterations is less than the maximum number of subdomains, counted with their multiplicity, that a geometric-optic ray can intersect. The theory, which is given at the continuous level and makes essential use of semi-classical analysis, assumes that the overlaps of the subdomains and the widths of the PMLs are all independent of the wavenumber. In this paper we extend the results of {\tt arXiv:2404.02156} by experimentally studying the behaviour of the methods in the practically important case when both the overlap and the PML width decrease as the wavenumber increases. We find that (at least for constant wavespeed), the methods remain robust to increasing $k$, even for miminal overlap, when the PML is one wavelength wide. △ Less

Submitted 20 October, 2025; v1 submitted 29 August, 2024; originally announced August 2024.

Comments: 8 pages, 2 figures

On Edge Multiscale Space based Hybrid Schwarz Preconditioner for Helmholtz Problems with Large Wavenumbers

Authors: Shubin Fu, Shihua Gong, Guanglian Li, Yueqi Wang

Abstract: In this work, we develop a novel hybrid Schwarz method, termed as edge multiscale space based hybrid Schwarz (EMs-HS), for solving the Helmholtz problem with large wavenumbers. The problem is discretized using $H^1$-conforming nodal finite element methods on meshes of size $h$ decreasing faster than $k^{-1}$ such that the discretization error remains bounded as the wavenumber $k$ increases. EMs-HS… ▽ More In this work, we develop a novel hybrid Schwarz method, termed as edge multiscale space based hybrid Schwarz (EMs-HS), for solving the Helmholtz problem with large wavenumbers. The problem is discretized using $H^1$-conforming nodal finite element methods on meshes of size $h$ decreasing faster than $k^{-1}$ such that the discretization error remains bounded as the wavenumber $k$ increases. EMs-HS consists of a one-level Schwarz preconditioner (RAS-imp) and a coarse solver in a multiplicative way. The RAS-imp preconditioner solves local problems on overlapping subdomains with impedance boundary conditions in parallel, and combines the local solutions using partition of unity. The coarse space is an edge multiscale space proposed in [13]. The key idea is to first establish a local splitting of the solution over each subdomain by a local bubble part and local Helmholtz harmonic extension part, and then to derive a global splitting by means of the partition of unity. This facilitates representing the solution as the sum of a global bubble part and a global Helmholtz harmonic extension part. We prove that the EMs-HS preconditioner leads to a convergent fixed-point iteration uniformly for large wavenumbers, by rigorously analyzing the approximation properties of the coarse space to the global Helmholtz harmonic extension part and to the solution of the adjoint problem. Distinctly, the theoretical convergence analysis are valid in two extreme cases: using minimal overlapping size among subdomains (of order $h$), or using coarse spaces of optimal dimension (of magnitude $k^d$, where $d$ is the spatial dimension). We provide extensive numerical results on the sharpness of the theoretical findings and also demonstrate the method on challenging heterogeneous models. △ Less

Submitted 15 August, 2024; originally announced August 2024.

Comments: 24 pages

MSC Class: 65F08; 65F10; 65N55

Positivity and Maximum Principle Preserving Discontinuous Galerkin Finite Element Schemes for a Coupled Flow and Transport

Authors: Shihua Gong, Young-Ju Lee, Yukun Li, Yue Yu

Abstract: We introduce a new concept of the locally conservative flux and investigate its relationship with the compatible discretization pioneered by Dawson, Sun and Wheeler [11]. We then demonstrate how the new concept of the locally conservative flux can play a crucial role in obtaining the L2 norm stability of the discontinuous Galerkin finite element scheme for the transport in the coupled system with… ▽ More We introduce a new concept of the locally conservative flux and investigate its relationship with the compatible discretization pioneered by Dawson, Sun and Wheeler [11]. We then demonstrate how the new concept of the locally conservative flux can play a crucial role in obtaining the L2 norm stability of the discontinuous Galerkin finite element scheme for the transport in the coupled system with flow. In particular, the lowest order discontinuous Galerkin finite element for the transport is shown to inherit the positivity and maximum principle when the locally conservative flux is used, which has been elusive for many years in literature. The theoretical results established in this paper are based on the equivalence between Lesaint-Raviart discontinuous Galerkin scheme and Brezzi-Marini-Suli discontinuous Galerkin scheme for the linear hyperbolic system as well as the relationship between the Lesaint-Raviart discontinuous Galerkin scheme and the characteristic method along the streamline. Sample numerical experiments have also been performed to justify our theoretical findings △ Less

Submitted 25 May, 2024; originally announced May 2024.

Convergence of overlapping domain decomposition methods with PML transmission conditions applied to nontrapping Helmholtz problems

Authors: Jeffrey Galkowski, Shihua Gong, Ivan G. Graham, David Lafontaine, Euan A. Spence

Abstract: We study overlapping Schwarz methods for the Helmholtz equation posed in any dimension with large, real wavenumber and smooth variable wave speed. The radiation condition is approximated by a Cartesian perfectly-matched layer (PML). The domain-decomposition subdomains are overlapping hyperrectangles with Cartesian PMLs at their boundaries. The overlaps of the subdomains and the widths of the PMLs… ▽ More We study overlapping Schwarz methods for the Helmholtz equation posed in any dimension with large, real wavenumber and smooth variable wave speed. The radiation condition is approximated by a Cartesian perfectly-matched layer (PML). The domain-decomposition subdomains are overlapping hyperrectangles with Cartesian PMLs at their boundaries. The overlaps of the subdomains and the widths of the PMLs are all taken to be independent of the wavenumber. For both parallel (i.e., additive) and sequential (i.e., multiplicative) methods, we show that after a specified number of iterations -- depending on the behaviour of the geometric-optic rays -- the error is smooth and smaller than any negative power of the wavenumber. For the parallel method, the specified number of iterations is less than the maximum number of subdomains, counted with their multiplicity, that a geometric-optic ray can intersect. These results, which are illustrated by numerical experiments, are the first wavenumber-explicit results about convergence of overlapping Schwarz methods for the Helmholtz equation, and the first wavenumber-explicit results about convergence of any domain-decomposition method for the Helmholtz equation with a non-trivial scatterer (here a variable wave speed). △ Less

Submitted 2 April, 2024; originally announced April 2024.

The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime

Authors: Shuyang Gong, Zhangsong Li

Abstract: Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permutation. Specifically, given an unknown permutation $π^*$ on $\{1,\ldots,n\}$ and given $n$ i.i.d. pairs of correlated Gaussian vectors $\{X_{π^*(i)},Y_i\}$ in $\mathbb{R}^d$ with noise parameter $σ$, we consider two types… ▽ More Motivated by the problem of matching two correlated random geometric graphs, we study the problem of matching two Gaussian geometric models correlated through a latent node permutation. Specifically, given an unknown permutation $π^*$ on $\{1,\ldots,n\}$ and given $n$ i.i.d. pairs of correlated Gaussian vectors $\{X_{π^*(i)},Y_i\}$ in $\mathbb{R}^d$ with noise parameter $σ$, we consider two types of (correlated) weighted complete graphs with edge weights given by $A_{i,j}=\langle X_i,X_j \rangle$, $B_{i,j}=\langle Y_i,Y_j \rangle$. The goal is to recover the hidden vertex correspondence $π^*$ based on the observed matrices $A$ and $B$. For the low-dimensional regime where $d=O(\log n)$, Wang, Wu, Xu, and Yolou [WWXY22+] established the information thresholds for exact and almost exact recovery in matching correlated Gaussian geometric models. They also conducted numerical experiments for the classical Umeyama algorithm. In our work, we prove that this algorithm achieves exact recovery of $π^*$ when the noise parameter $σ=o(d^{-3}n^{-2/d})$, and almost exact recovery when $σ=o(d^{-3}n^{-1/d})$. Our results approach the information thresholds up to a $\operatorname{poly}(d)$ factor in the low-dimensional regime. △ Less

Submitted 6 April, 2026; v1 submitted 22 February, 2024; originally announced February 2024.

Comments: 31 pages; updated funding information

MSC Class: 68Q87 (Primary); 62M15 (Secondary)

Families of metrics with positive scalar curvature on spectral sequence cobordisms

Authors: Sherry Gong

Abstract: We study families of metrics on the cobordisms that underlie the differential maps in Bloom's monopole Floer spectral sequence, a spectral sequence for links in $S^3$ whose $E^2$ is the Khovanov homology of the link, and which abuts to the monopole Floer homology of the double branched cover of the link. The higher differentials in the spectral sequence count parametrized moduli spaces of soluti… ▽ More We study families of metrics on the cobordisms that underlie the differential maps in Bloom's monopole Floer spectral sequence, a spectral sequence for links in $S^3$ whose $E^2$ is the Khovanov homology of the link, and which abuts to the monopole Floer homology of the double branched cover of the link. The higher differentials in the spectral sequence count parametrized moduli spaces of solutions to Seiberg-Witten equations, parametrized over a family of metrics with asymptotic behaviour corresponding to a configuration of unlinks with 1-handle attachments. For a class of configurations, we construct families of metrics with the prescribed behaviour, such that each metric therein has positive scalar curvature. The positive scalar curvature implies that there are no irreducible solutions to the Seiberg-Witten equations and thus, when the spectral sequences are computed with these families of metrics, only reducible solutions must be counted. The class of configurations for which we construct these families of metrics includes all configurations that go into the spectral sequence for $T(2,n)$ torus knots, and all configurations that involve exactly two 1-handle attachments. △ Less

Submitted 3 October, 2023; originally announced October 2023.

MSC Class: 57K18; 57K41; 57R35;

The Novikov conjecture, the group of diffeomorphisms and continuous fields of Hilbert-Hadamard spaces

Authors: Sherry Gong, Jianchao Wu, Zhizhang Xie, Guoliang Yu

Abstract: In this paper, we prove the Novikov conjecture for a class of highly non-linear groups, namely discrete subgroups of the diffeomorphism group of a compact smooth manifold. This removes the volume-preserving condition in a previous work. This result is proved by studying operator $K$-theory and group actions on continuous fields of infinite dimensional non-positively curved spaces. In this paper, we prove the Novikov conjecture for a class of highly non-linear groups, namely discrete subgroups of the diffeomorphism group of a compact smooth manifold. This removes the volume-preserving condition in a previous work. This result is proved by studying operator $K$-theory and group actions on continuous fields of infinite dimensional non-positively curved spaces. △ Less

Submitted 21 February, 2025; v1 submitted 2 October, 2023; originally announced October 2023.

Comments: 103 pages, comments are welcome

The Algorithmic Phase Transition of Random Graph Alignment Problem

Authors: Hang Du, Shuyang Gong, Rundong Huang

Abstract: We study the graph alignment problem over two independent Erdős-Rényi graphs on $n$ vertices, with edge density $p$ falling into two regimes separated by the critical window around $p_c=\sqrt{\log n/n}$. Our result reveals an algorithmic phase transition for this random optimization problem: polynomial-time approximation schemes exist in the sparse regime, while statistical-computational gap emerg… ▽ More We study the graph alignment problem over two independent Erdős-Rényi graphs on $n$ vertices, with edge density $p$ falling into two regimes separated by the critical window around $p_c=\sqrt{\log n/n}$. Our result reveals an algorithmic phase transition for this random optimization problem: polynomial-time approximation schemes exist in the sparse regime, while statistical-computational gap emerges in the dense regime. Additionally, we establish a sharp transition on the performance of online algorithms for this problem when $p$ lies in the dense regime, resulting in a $\sqrt{8/9}$ multiplicative constant factor gap between achievable and optimal solutions. △ Less

Submitted 26 March, 2025; v1 submitted 13 July, 2023; originally announced July 2023.

Comments: 56 pages, add further explanations and remarks, to appear in Probability Theory and Related Fields

MSC Class: 60C05; 68R10; 05C80

On the rank of knot homology theories and concordance

Authors: Nathan M. Dunfield, Sherry Gong, Thomas Hockenhull, Marco Marengon, Michael Willis

Abstract: For a ribbon knot, it is a folk conjecture that the rank of its knot Floer homology must be 1 modulo 8, and another folk conjecture says the same about reduced Khovanov homology. We give the first counter-examples to both of these folk conjectures, but at the same time present compelling evidence for new conjectures that either of these homologies must have rank congruent to 1 modulo 4 for any rib… ▽ More For a ribbon knot, it is a folk conjecture that the rank of its knot Floer homology must be 1 modulo 8, and another folk conjecture says the same about reduced Khovanov homology. We give the first counter-examples to both of these folk conjectures, but at the same time present compelling evidence for new conjectures that either of these homologies must have rank congruent to 1 modulo 4 for any ribbon knot. We prove that each revised conjecture is equivalent to showing that taking the rank of the homology modulo 4 gives a homomorphism of the knot concordance group. We check the revised conjectures for 2.4 million ribbon knots, and also prove they hold for ribbon knots with fusion number 1. △ Less

Submitted 7 March, 2023; originally announced March 2023.

Comments: 27 pages, 10 figures

Report number: MPIM-Bonn-2023 MSC Class: 57K18; 57-11 (Primary) 57K14 (Secondary)

Discrete Elasticity Exact Sequences on Worsey-Farin Splits

Authors: Sining Gong, Jay Gopalakrishnan, Johnny Guzmán, Michael Neilan

Abstract: We construct conforming finite element elasticity complexes on Worsey-Farin splits in three dimensions. Spaces for displacement, strain, stress, and the load are connected in the elasticity complex through the differential operators representing deformation, incompatibility, and divergence. For each of these component spaces, a corresponding finite element space on Worsey-Farin meshes is exhibited… ▽ More We construct conforming finite element elasticity complexes on Worsey-Farin splits in three dimensions. Spaces for displacement, strain, stress, and the load are connected in the elasticity complex through the differential operators representing deformation, incompatibility, and divergence. For each of these component spaces, a corresponding finite element space on Worsey-Farin meshes is exhibited. Unisolvent degrees of freedom are developed for these finite elements, which also yields commuting (cochain) projections on smooth functions. A distinctive feature of the spaces in these complexes is the lack of extrinsic supersmoothness at subsimplices of the mesh. Notably, the complex yields the first (strongly) symmetric stress finite element with no vertex or edge degrees of freedom in three dimensions. Moreover, the lowest order stress space uses only piecewise linear functions which is the lowest feasible polynomial degree for the stress space. △ Less

Submitted 19 August, 2023; v1 submitted 16 February, 2023; originally announced February 2023.

A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs

Authors: Jian Ding, Hang Du, Shuyang Gong

Abstract: For two independent Erdős-Rényi graphs $\mathbf G(n,p)$, we study the maximal overlap (i.e., the number of common edges) of these two graphs over all possible vertex correspondence. We present a polynomial-time algorithm which finds a vertex correspondence whose overlap approximates the maximal overlap up to a multiplicative factor that is arbitrarily close to 1. As a by-product, we prove that the… ▽ More For two independent Erdős-Rényi graphs $\mathbf G(n,p)$, we study the maximal overlap (i.e., the number of common edges) of these two graphs over all possible vertex correspondence. We present a polynomial-time algorithm which finds a vertex correspondence whose overlap approximates the maximal overlap up to a multiplicative factor that is arbitrarily close to 1. As a by-product, we prove that the maximal overlap is asymptotically $\frac{n}{2α-1}$ for $p=n^{-α}$ with some constant $α\in (1/2,1)$. △ Less

Submitted 14 October, 2022; originally announced October 2022.

Comments: 38 pages, 3 figures

MSC Class: 60C05; 68W25; 68R10