New on arXiv
Sort: by field | by arXiv number | trending
Mathematics
Every $r$-regular Hamiltonian graph with $r\geq 17$ contains a second Hamilton cycle
A conjecture of Sheehan states that every Hamiltonian $4$-regular graph contains a second Hamilton cycle. A natural problem is to find the smallest positive integer $k$ such that every Hamiltonian $r$-regular graph contains a second Hamilton cycle when $r\geq k$. Thomassen proved that $k\leq 300$. Improving Thomassen's result, Haxell, Seamone, and Verstra{\"e}te proved that $k\leq 23$. We improve...
The Spectral Theory of Cographs: A Survey, Organized by Graph Matrix
Cographs, the $P_4$-free graphs, are exactly the graphs obtained from a single vertex by repeated disjoint union and complementation. They contain the threshold graphs, $\mathcal{C}$-graphs and form one of the primary areas for spectral graph theory. This survey is organized by matrix: after a preliminary section, there is one section for each of the adjacency, Laplacian, signless Laplacian,...
Hypergraphs with zero uniform Tur\'an density at intermediate levels
An $r$-uniform hypergraph $H$ is uniformly dense with respect to $j$-graphs if, up to a small error, at least a prescribed proportion of the $r$-cliques of every $j$-uniform hypergraph on the same vertex set are edges of $H$. For a forbidden hypergraph $F$, its uniform Tur\'an density at level $j$ is the supremum of these density bounds over arbitrarily large $F$-free hypergraphs with the error...
Limits of Generalized Magnitudes of Dissimilarity Spaces
For a finite symmetric nonnegative dissimilarity matrix $D=(d_{ij})$ with zero diagonal, we study the high-resolution limit ($t\to \infty$) of $\mathbf{1}^T(e^{-td_{ij}})^+\mathbf{1}$. We prove that this limit always exists in the extended real line and is rational whenever finite, without weightability or invertibility assumptions. At fixed cardinality, a finite rational polyhedral fan governs...
A uniform double-factorial construction for consecutive-pattern packings
For every overlap $m\geq 3$ and every pattern length $K\geq 2m+1$, we construct an explicit permutation $p\in\mathfrak{S}_K$ such that the number of permutations containing $j$ prescribed occurrences of $p$, with successive starts separated by $K-m$, is $(2j-1)!!$ for every $j\geq 1$. Additional occurrences are permitted. We prove that the corresponding occurrence poset is the ordinal sum of a...
Almost sure bounds and tail phases for critical non-Gaussian holomorphic chaos
Gu and Zhang asked for almost sure upper and lower bounds on the Taylor coefficients $a_n$ of $\exp(\sum_{k\ge1}X_kz^k/\sqrt{k})$ in the unit disc, and for the dependence of these bounds on the input tail. For independent, identically distributed, rotationally invariant complex inputs with $\mathbb E|X_1|^2=1$, we prove the universal almost sure bound $|a_n|=O((\log n)^{1/4})$. Almost surely,...
A Central Limit Theorem For Random Variables Under A Constraint
We consider vectors chosen randomly from high-dimensional hypersurfaces of the form $\{x\in\mathbb{R}^n: \sum_{j=1}^n V_j(x_j)=an\}$. These in general asymmetric surfaces generalize classical spheres and include unbounded and disconnected surfaces. We show that under mild assumptions as $n\to\infty$, any weighted sum of the random coordinates is asymptotically Gaussian, provided that no weight...
Low-Temperature Sampling via Equilibrium Disagreements
We develop a new framework for sampling at low temperatures using Glauber dynamics. In this regime, the coexistence of competing modes (commonly referred to as phases) creates bottlenecks that can make worst-case mixing exponentially slow. The main new ingredient in our framework is to relate convergence within a phase to the geometry of disagreements between two independent configurations drawn...
A Simple Approach to the Complexity of Mean Field Ising Spin Glasses
The geometry of spherical spin glasses is relatively well understood, thanks in large part to the Kac-Rice formula. However, this formula does not directly apply to discrete spin systems, and much less is known mathematically about the geometry of Ising spin glasses. In this paper, we present a simple method for counting local optima and gapped states in a broad class of discrete spin glasses. To...
The singular Gaussian scaling limit for a tagged particle in the infinite-dimensional Dyson model at $\beta=2$
We prove a logarithmic central limit theorem for a tagged particle in infinite-dimensional Dyson Brownian motion at inverse temperature $\beta=2$, starting from the sine$_2$ point process. The fluctuation is of order $\sqrt{\log t}$, which is subdiffusive and substantially slower than the polynomial fluctuations of classical short-range interacting particle systems, reflecting the rigidity...
Global solutions for continuous-time Burgers equations and infinite-volume polymer measures
We study the stochastic Burgers equation on the whole space, driven by space-homogeneous Gaussian noises that are white in time and colored in space, for both positive and zero viscosity. We show that in dimension one, for any fixed average velocity, there is a unique ergodic global solution to the Burgers equation for all nonnegative viscosities, and that the One Force---One Solution principle...
Fluctuations, Moderate and Large Deviations about Hydrodynamic Limits of Space-Time Hawkes Processes
We study Gaussian fluctuations, moderate and large deviations around the high-density hydrodynamic limit of critical and nearly critical space-time Hawkes processes initialized by a prescribed Poisson field of past events, with no subsequent immigration. Under a finite mean reproduction delay and centered displacements with finite spatial covariance, a positive cluster-transform estimate yields a...
Random Fibonacci Tilings
The Fibonacci spiral is formed by a square-joining rule: begin with a unit square and attach squares whose side lengths follow the Fibonacci sequence; in the standard construction, choices of direction produce a spiral and a tiling of the plane. We study a randomization of this construction, in which the attachment axis alternates deterministically, while fair coin flips determine direction. For...
Ignoring Blow-Ups for Approximations
It is well known that for SDEs with non-Lipschitz coefficients, the Euler scheme can fail to converge in an Lp sense. It is also widely observed that convergence fails only due to rare explosive trajectories, that distort the expectation. In this work we demonstrate that almost any method of removing these rare explosive trajectories leads to convergence in a suitable strong and weak sense. We...
Existence, Uniqueness, Feller Property and Diricihlet form of the Keller-Segel particle system up to blow up
The Keller-Segel particle system as defined in \cite{ft} through the Dirichlet form theory (see \cite{f}) consists of $N$ planar Brownian motions interacting through the kernel $x\in \rr^2 \mapsto \theta K(x) = -\theta x/\|x\|^2$, where $\theta >0$. One particularity of this model is that collisions (i.e. overlapping of particles) occur depending on the value of $\theta$, making the...
Necessary and sufficient conditions for the self-normalized central limit theorem for independent triangular arrays
For a rowwise independent triangular array $\{X_{n,i}:1\le i\le n\}$, put $S_n=\sum_{i=1}^nX_{n,i}$ and $V_n^2=\sum_{i=1}^nX_{n,i}^2$. We prove that $S_n/V_n\xrightarrow{\mathrm d}{\mathrm N}(0,1)$ implies $\max_{i\le n}|X_{n,i}|/V_n\xrightarrow{\mathbb P}0$. The same assumption gives $V_n^2/b_n^2\xrightarrow{\mathbb P}1$ for any choice of medians $b_n^2$ of $V_n^2$. Combined with the results of...
Sharp moderate deviations and uniform Berry--Esseen bounds for Hotelling's $T^2$-statistic via Stein's method
Let $\mathbf X_1,\ldots,\mathbf X_n$ be independent random vectors in $\mathbb R^d$ with common mean $\boldsymbol\mu_n$, where $d\ge2$ is a fixed integer. Let $\bar{\mathbf X}_n=n^{-1}\sum_{i=1}^n\mathbf X_i$ denote the sample mean and let \[ \widehat\Sigma_n=\frac1n\sum_{i=1}^n (\mathbf X_i-\bar{\mathbf X}_n) (\mathbf X_i-\bar{\mathbf X}_n)^\top \] denote the sample covariance matrix. Assume...
On some stochastic evolutions on Laguerre-Polya functions
We prove uniqueness in law for three stochastic evolutions on normalised Laguerre-P\'{o}lya functions arising as scaling limits of matrix characteristic polynomial dynamics. In particular, this implies that Ahn's universal Brownian Gibbs line ensemble arising from random matrix products has the law of the logarithms of the reciprocal zeros of the solution, unique in law, to a simple stochastic...
The stochastic Ginzburg-Landau equation with harmonic potential in the full subcritical regime
In this paper, we construct the complex Ginzburg-Landau dynamic associated with the harmonic oscillator, with a random force which is white in time and covers the full subcritical range in space. We are able to renormalise the non-linearity using the same constant as the one used to renormalise the problem associated to the Laplacian. By an extension of the problem to complex times, we are able...
Exact regions for the symmetrized Blest coefficient
Spearman's rho treats all ranks alike, yet in many comparisons of two rankings an agreement at the top matters more than one at the bottom. Blest's rank correlation builds this preference into Spearman's rho, and its symmetrized version $\eta$, introduced by Genest and Plante, does so without favoring either of the two rankings. How far can such a top-weighted coefficient stray from other rank...
Darboux transformations of linear birth-death processes
In a previous paper we characterized the lower-upper (LU) and upper-lower (UL) factorizations of the infinitesimal generator of a possibly nonconservative birth-death process whose Darboux transformations are again generators of birth-death processes. Here we apply these results to several classical models with linear rates and explicitly known spectral measures: the $M/M/\infty$ queue (Charlier...
Constructive Probability, Foundations and Numerical Analysis for mathematical finance and machine learning
This monograph sets out a constructive theory of stochastic processes in the continuum, in the sense of constructive field theory: the continuum is not postulated but reached as the limit of a sequence of lattice approximations, with the renormalisation the limit requires exhibited rather than assumed, and the limit controlled by estimates that can be checked. The primitive object is not a...
The second reconstruction transition for random graphs from 2-neighborhoods
We prove that, with high probability, the Erd\H{o}s--R\'enyi random graph $G(n,p)$ is reconstructible up to isomorphism from the multiset of its rooted induced 2-neighborhoods whenever $p\geq n^{-3/4}(\log n)^3$. Together with the non-reconstructibility result of Johnston, Kronenberg, Roberts and Scott, our result locates the second reconstruction transition at the scale $p=n^{-3/4}$ up to...
A Feynman-Kac Representation and Large Deviation Bounds for the Fisher-KPP Equation Driven by Finite-Activity Pure Jump Noise
We study the asymptotic propagation speed of travelling wave solutions to the stochastic Fisher-KPP equation with multiplicative finite-activity pure jump L\'evy noise. The noise is represented by a compensated Poisson random measure with finite intensity, so that the solution evolves deterministically between successive jump times and undergoes multiplicative jumps at the event times. Our main...
Recurrence and Uniqueness Criteria for Markov Processes from Moments of Integral-Type Functionals
We investigate recurrence and uniqueness of continuous-time Markov chains using moments of integral-type functionals. Unlike the classical criteria from Chen (2004) and the Feller-Reuter criterion, we develop general unified conditions for recurrence and uniqueness of Markov processes based on moments of integral-type functionals. The associated criteria follow directly from these conditions...
Geometric Functional Inequalities for Markov Processes: An Invitation via the Langevin Diffusion
Functional inequalities provide a language for reasoning about the long-time properties of ergodic Markov processes in terms of their macroscopic geometry. This article offers an informal introduction to functional inequalities for readers who are more familiar with probabilistic tools based around couplings, Lyapunov techniques, and similar. The main ideas are developed through the overdamped...
Nonlinear optimal stopping and domineering claims
We study nonlinear optimal stopping and domineering claims in a Brownian--Poisson filtration, under a nonlinear evaluation induced by a Lipschitz BSDE driver satisfying a comparison condition. A nonlinear domineering claim is a strong $\mathcal{E}^f$-martingale dominating the reward process at every stopping time. We first establish the existence of such claims for every optional reward in...
Random complex cross ratios
We study the cross ratio of four independent points chosen uniformly on the Riemann sphere. A positive integral over a two-dimensional simplex gives its normalized planar density. We then evaluate this integral in terms of the Bloch--Wigner dilogarithm, providing a closed formula. We describe its symmetries, real-axis values, moment bounds and geometric interpretations. We use these to evaluate...
Approximate independence of typical marginals of high-dimensional probability measures
For many probability measures on $\mathbb{R}^n$, and for $k$ sufficiently smaller than $n$, most $k$-dimensional coordinate marginals are close to product measures. We prove this in two regimes, which notably involve no exchangeability assumptions as in prior theorems of de Finetti type. First, for log-concave measures, the quantitative bound depends on the measure only through the operator norm...
Weak uniqueness for the stochastic heat equation with nondegenerate diffusion: the full H\"older regime
We prove weak well-posedness for the scalar stochastic heat equation on the one-dimensional torus with uniformly nondegenerate diffusion that is Holder continuous of any positive order. This resolves the weak uniqueness problem in the full positive Holder range, extending our earlier result for exponents above two thirds (arXiv:2608.01279). The proof couples a weak solution to a smooth companion...
On the critical value of void percolation in high dimensions
In the random Lorentz gas, a point tracer moves through spherical obstacles of (reduced) density $\Phi$ centered on a Poisson point process in $d$-dimensional space, $\mathbb{R}^d$, and becomes localized once the vacant space stops percolating, at $\Phi_{\rm p}(d)$. The dimensional scaling of this void percolation threshold has remained elusive. Prior bounds, conjectural ones included, ranged...
A second eigenvalue lower bound for the directed configuration model
We prove a high-probability lower bound for the second eigenvalue in modulus of the transition matrix of the simple random walk on a directed configuration model with minimal out-degree at least two and maximal degree not too large. The lower bound matches the upper bound found by Coste (2021) on the same model. Our proof bypasses the need to establish convergence of the empirical eigenvalue...
Necessary and sufficient conditions for the martingale property of stochastic exponentials driven by multi-dimensional diffusions
We give necessary and sufficient coefficient conditions for stochastic exponentials driven by multidimensional diffusions to be true martingales. The classical reduction to non-exit of the diffusion with Girsanov-shifted drift separates the analysis into smooth boundary points, infinity, and nonsmooth boundary pieces. On smooth domains, under regularity and non-explosion hypotheses, martingality...
Validity of the Behrens--Fisher solution
The Behrens--Fisher fiducial interval for the difference of two normal means is known from the numerical work of Robinson (1976) to be conservative, but a proof has been lacking. The results here prove that the fiducial interval for any linear combination of $k$ normal means has coverage probability at least its nominal level for all values of the unknown variances. Taraldsen (2026) explains this...
An Accelerated Proximal Gradient Method for Bures-Wasserstein Space
We study composite optimization over the Bures--Wasserstein (BW) space of Gaussian measures. Our main observation is that a useful class of BW problems can be lifted into the Euclidean space of affine transport maps, such that the lifted problems can be solved efficiently using accelerated proximal gradient methods. For objectives whose smooth and nonsmooth components admit convex smooth and...
Augmented Lagrangian methods with telescopic subproblems for MPCCs and cardinality constraints with general constraints: constraint-preserving swaps and B-stationarity
We consider optimization problems with general equality and inequality constraints and partitioned cardinality constraints, which include complementarity constraints. In the augmented Lagrangian method that we consider, the bounds and the cardinality constraints are kept in the subproblems, which are solved by the Telescopic Method. The limit points of this method are B-stationary, without...
A Theoretical Analysis of a Bilevel Optimization Formulation for Combined Local-Global Optical Flow Models
This paper analyzes a bilevel formulation for learning the regularization parameter of combined local-global (CLG) optical flow models. The lower-level problem computes the flow from a Lucas--Kanade data term and a quadratic or total variation (TV) regularizer, and the upper-level problem selects the parameter that minimizes the squared distance to a ground-truth flow. The setting is...
Hardness of integer linear feasibility with cyclic support
We prove that integer linear feasibility is strongly $NP$-complete even when the constraint matrix has exactly two nonzero entries in every row and column, with its support forming a single cycle. This holds already for monotone systems (one positive and one negative coefficient in each inequality) with nonzero coefficients of absolute value $2$ or $3$ and right-hand sides in $\{-1,0,1,2\}$. No...
A Proximal Newton Framework with Local Superlinear Convergence for Simple Bilevel Optimization
In this paper, we study a penalty method for simple bilevel optimization in which the lower-level objective has a convex composite structure. Our approach is based on a vanishing-penalty reformulation, which gives rise to a sequence of penalized problems as the penalty parameter decreases. A key difficulty is that metric subregularity of the lower-level optimality mapping does not, in general,...
Adaptive pairwise preference elicitation for decision support: identifying the best alternative with fewer judgments
Interactive decision support systems often require repeated preference judgments, although identifying the best alternative may not justify eliciting all \(n(n-1)/2\) pairwise comparisons. We propose ALEC (Adaptive Lexicographic Elicitation of Comparisons), which re-ranks the alternatives after each judgment and asks the first unobserved pair in the lexicographic order of the current ranking,...
Overcoming Fundamental Control Limitations in Powered Descent Flight through Robust Incremental Nonlinear Dynamic Inversion
This work identifies a fundamental, controller-independent limitation in reusable launch vehicle powered descent: a sudden $180^\circ$ phase transition in the open-loop transfer functions from the control inputs to the lateral drift and drift rate. The transition occurs inside the flight envelope, reverses the effective control direction, and can destabilize the closed loop system under...
On the Minimal Controllability of Boolean Networks With $k$-Regular Dependency Graphs
Boolean networks (BNs) are widely used to model gene regulatory networks and other biological systems. In this paper, we investigate the minimal controllability problem for BNs subject to degree constraints. We first establish three new best-case upper bounds for XOR-BNs whose dependency graphs are $k$-regular. We then introduce classes of BNs that are invariant under cyclically partite...
A Solution Method for Single-Source Capacitated Facility Location Problems Under Decision-Dependent Demand Uncertainty
We present a model and an exact solution method for single-source capacitated facility location problems with decision-dependent demand uncertainty. The model allows the joint probability distribution of customer demands to depend on the facility to which demand points are allocated. The number of possible decision-dependent distributions is therefore equal to the number of feasible allocations...
A globally convergent stochastic semismooth Newton method for strongly convex problems in Hilbert spaces
We propose and analyze a globalized stochastic semismooth Newton method for stochastic optimization problems in Hilbert spaces where the objective is strongly convex with Lipschitz continuous, Newton differentiable gradient. Gradient and generalized Hessian information are only available through mini-batching. In each iteration, a full semismooth Newton trial step is accepted or rejected based on...
Funnel MPC for port-Hamiltonian systems
Port-Hamiltonian systems are an energy-based modelling formalism, that has strong ties to the physical models and allows interconnection of systems. Funnel MPC, a Model Predictive Control (MPC) scheme, allows for output tracking with prescribed error bounds. Earlier works focused on systems with stable internal dynamics, which typically excludes port-Hamiltonian systems. We introduce a modified...
Quantifying the remaining search space in analogue optimisation
Benchmarking analogue optimisers requires certifying not only how close a returned energy is to the optimum, but also how many better configurations may remain. Semidefinite relaxations provide rigorous bounds on the ground-state energy and selected observables, yet reveal little about the size of this residual search space. We introduce a deterministic, instance-specific upper bound on the...
On the Spectral Dependence of Decentralized Stochastic Gradient Tracking
We study how the spectral geometry of the mixing matrix enters the convergence of decentralized stochastic gradient tracking (GT) for smooth strongly convex problems. General bounds contain the factor $\Delta_\lambda^{-3}$ in the higher-order stochastic term, where $\Delta_\lambda$ is the absolute spectral gap. We show that, even for two agents with identical quadratic objectives, the exact...
Newton Steps are Faster for Linear Complementarity Problems
Linear Complementarity Problems (LCPs) with sufficient matrices form a well-studied class of problems, dating back from the foundational works of Cottle and Dantzig (1968). LCPs capture convex quadratic programs, and admit reductions from problems such as discounted stochastic games or mean-payoff games. While the original approach for solving these problems was based on pivoting methods, in...
Online Optimization for Controlling HVAC Systems
Heating, ventilation, and air-conditioning (HVAC) systems account for a significant portion of buildings' energy consumption, motivating the design of energy- and cost-efficient control strategies. However, conventional strategies employ simple, reactive control, without incorporating a model. Therefore, in this paper we adopt an economic model predictive control framework and focus on designing...
Randomized and Oracle-Based Feasible Directions Methods for Nonsmooth Nonconvex Constrained Optimization
Minimizing nonsmooth nonconvex objectives over general convex sets using no derivatives of the objective, together with structural access to the constraint set, poses a fundamental geometric difficulty: at boundary points, the feasible direction cone may fail to be closed, preventing the construction of finite sets of search directions that capture all feasible descent directions. We develop a...
Only titles, authors and the start of each abstract are shown here, as arXiv published them. Open a paper to read its whole abstract and, with your own AI key, a plain-language summary. Papers on arXiv are preprints and may not have been peer reviewed.
Data from arXiv, used through the arXiv API. Thank you to arXiv for use of its open access interoperability.