Combinatorics
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Sunday 26 July
The Grone–Merris inequality, conjectured by Grone and Merris~(1994) and first proved by Bai~(2011), states that for every graph $G$ of order $n$ and every $1\le k\le n$, $\sum_{i=1}^k\lambda_i(G)\le\sum_{i=1}^k d_i^*(G)$, where $\lambda_1\ge\cdots\ge\lambda_n$ are the Laplacian eigenvalues and $d_1^*\ge\cdots\ge d_n^*$ is the conjugate degree sequence. In this paper we determine exactly when equality holds. Using the split-graph trace inequality developed by Kothari and Tudose~(2026) in their proof of Brouwer's Laplacian conjecture—which relies on Bai's theorem and also establishes the equivalence between the two conjectures—together with the recent characterization of the Brouwer equality cases by Cai, Chen, Yang and Zhang~(2027), we prove that equality holds in the Grone–Merris inequality if and only if the graph $G$ belongs to one of two explicitly described families. Both families are obtained from a threshold graph by a surgical operation at one terminal block: in the first family, edges are removed from the initial dominating block; in the second, edges are added inside the initial isolated block. Our analysis yields a complete combinatorial description of all pairs $(G,k)$ for which the Grone–Merris bound is tight.
Geometric Topology
An Algorithmic Search for Knots Bounding Möbius Bands in $B^4$
This study examines the smooth non-orientable $4$-genus of knots using a large-scale computational search. Knot invariant obstructions were computed, and existing computational algorithms were extended to identify prime knots in $S^3$ of crossing number at most $14$ that bound Möbius bands in $B^4$. The findings significantly expand the known examples of knots of non-orientable $4$-genus equal to $1$ and contribute new data relevant to the study of the non-orientable $4$-genus.
Read the full abstract
Analysis of PDEs
Decay estimates for a class of dispersive equations with partial inverse-square potentials
Let $\mathcal{L}_a=-\Delta_x-\Delta_y+\frac{a}{2}|x|^{-2}$ with $a>0$ denote the Schrödinger operator on $L^2(\mathbb{R}^2_x\times \mathbb{R}^n_y)$, which involves a singular partial inverse-square potential. The purpose of this manuscript is twofold. First, relying on the explicit representation for the spectral measure associated with the operator $\mathcal{L}_a$ established by Zhang-Zhang [J. Geom. Anal. 35(3), Paper No. 71, 27pp (2025)], we investigate the decay estimate for a class of dispersive semigroups of the form $e^{it\phi(\sqrt{\mathcal{L}_a})}$, where $\phi: \mathbb{R}^+ \to \mathbb{R}$ is a smooth function. To handle the technical difficulty arising from the inhomogeneity of the phase function $\phi$, we adopt the frequency localization and the stationary phase method. In the second part of the paper, we first derive boundary Strichartz estimates for the fractional Schrödinger operator $e^{it\mathcal{L}_a^\nu}$, $0<\nu\neq\frac{1}{2}$. As applications of the established decay estimates, we further obtain Strichartz estimates for some concrete wave equations associated with the operator $\mathcal{L}_a$, which corresponds to $\phi(r)=r, r^2, r^2+r^4, \sqrt{1+r^2}, \sqrt{1+r^4}$, and $r^\mu,0<\mu\neq 1$. Most notably, our results unify and simplify existing dispersive estimates for the operator $\mathcal{L}_a$, while extending the relevant theory to more general scenarios.
Read the full abstract
Statistics Theory
Estimation of multiple precision matrices under shared support with heterogeneous edge strengths
Estimating multiple precision matrices in high-dimension presents significant challenges, particularly when distinct datasets share a common conditional dependency structure but exhibit population-specific interaction strengths. We address this problem by introducing the Multiplicative Graphical Lasso (Mglasso), a method for jointly estimating precision matrices across multiple Gaussian graphical models under a shared sparsity constraint. Each precision matrix is decomposed as a Schur-Hadamard product of a shared structural matrix $\boldsymbol{\Theta}$, which encodes the common conditional independence graph, and a population-specific matrix $\boldsymbol{\Gamma}_{l}$, which captures variation in edge strengths across populations. We optimize a penalized log-likelihood that utilizes an $\ell_1$-penalty to enforce common sparsity and a Frobenius norm penalty to regulate population-specific variations. The optimization is efficiently performed using the Alternating Direction Method of Multipliers (ADMM) algorithm integrated with gradient descent. Theoretically, we establish the local strict convexity of the objective function and provide rigorous high-dimensional consistency guarantees, including supremum norm error bounds and exact support recovery under sub-Gaussian tail conditions. Extensive simulations show superior model selection consistency at smaller sample sizes compared to the benchmark Group Graphical Lasso (GGL). Finally, the method's practical utility is further validated through real-world applications.
Read the full abstract
Numerical Analysis
Optimal Polynomial Tractability Exponents for the Inverse Star Discrepancy
The inverse of the star discrepancy $n^\ast(d, \varepsilon)$ satisfies \[ d \varepsilon^{-1} \lesssim n^{\ast}(d,\varepsilon)\lesssim d\varepsilon^{-2} \] for all $d \in \mathbb{N}$ and $0 < \varepsilon < \varepsilon_0$. The upper bound was established by Heinrich, Novak, Wasilkowski and Woźniakowski (2001), while the lower bound is due to Hinrichs (2004). Steinerberger (2023) subsequently gave an elementary proof of the latter result. These bounds imply that the inverse of the star discrepancy depends linearly on the dimension, but the exact exponent of $\varepsilon^{-1}$ had remained open. In this paper we prove a lower bound which shows that the exponent $2$ of $\varepsilon^{-1}$ in the upper bound cannot be improved. More precisely, for every $0<\alpha<1$ and fixed $0<A\le B$, there exist constants $c_{\alpha,B}>0$ and $\varepsilon_{\alpha,A}>0$ such that, for every $0<\varepsilon<\varepsilon_{\alpha,A}$ and every integer $d$ satisfying \[ A\varepsilon^{-\alpha}\le d\le B\varepsilon^{-\alpha}, \] one has \[ n^\ast(d,\varepsilon) \ge c_{\alpha,B}\,d\,\varepsilon^{-(2-\alpha)}. \] Along these polynomial strips the right-hand side is of order $\varepsilon^{-2}$. Consequently, every uniform polynomial upper estimate $n^{\ast}(d,\varepsilon)\le C d^q\varepsilon^{-p}$ must satisfy $p\ge2$. Together with the lower bound of Hinrichs (2004), which forces $q\ge1$, this proves that the exponents $p=2$ and $q=1$ in the Heinrich–Novak–Wasilkowski–Woźniakowski upper bound are individually optimal. In particular, the optimal exponent $p^\ast = 2$.
Read the full abstract
Geometric Topology
Topological line arrangements and their topological invariants
A topological line arrangement is an arrangement of embedded spheres in the complex projective plane that topologically generalizes a complex line arrangement. In this paper, we establish foundational results on the topology of the complement of topological line arrangements. First, we prove that the cohomology ring of the complement is isomorphic to the Orlik-Solomon algebra, as for classical complex line arrangements. We then study the homotopy type of the complement. We prove that the complement of a symplectic line arrangement has the homotopy type of a minimal CW complex. In contrast, every combinatorial type realizable by a topological line arrangement admits a realization with a non-minimal complement. Moreover, every such combinatorial type admits infinitely many realizations whose complements are pairwise non-homotopy equivalent.
Read the full abstract
Mathematical Physics · Cross-listed from quant-ph
A Probabilistic Representation for Multi-State Discrete-time Quantum Walks
Building upon the pioneering framework of Vu (2026), we construct a probabilistic representation for three-state discrete-time quantum walks on integer lattices and validate it through empirical examples. Furthermore, we establish that this representation converges to the continuum solution of multi-state Dirac partial differential equations. Broadly, our findings demonstrate that this probabilistic paradigm serves as a robust alternative for simulating higher-dimensional quantum walks, opening new theoretical avenues to analyze quantum dynamics using classical stochastic processes.
Read the full abstract
Numerical Analysis
Adaptive Consistency for Mimetic Finite Differences
The mimetic finite difference (MFD) method provides a robust discretization for flow simulation on general polyhedral meshes, but its computational cost can become significant due to dense local operators and reduced global sparsity. While the two-point flux approximation (TPFA) offers a substantially cheaper alternative, its accuracy is generally restricted to $K$-orthogonal grids. To balance these competing considerations, we present an adaptive MFD framework based on a residual-based consistency indicator derived from the discrete constitutive equations. The indicator measures local inconsistency and enables adaptive TPFA/MFD stencil selection through a user-prescribed tolerance $\tau$. Because the adaptation is performed within a mimetic framework, arbitrary TPFA/MFD partitions remain stable and structure preserving. Theoretical analysis establishes uniform coercivity and proves explicit tolerance-controlled convergence of the relative flux error. Numerical experiments on challenging polyhedral reservoir benchmarks demonstrate accuracy comparable to full MFD discretizations while substantially reducing matrix density and computational cost.
Read the full abstract
Category Theory
Guarded Realization Semantics: Occurrence-Sensitive Certificates and Behavior-Dependent Lower Bounds
Distinct proofs, programs, formulas, or rewrite paths may have the same observable behavior while differing in occurrence structure, sharing, interfaces, or transformation history. We develop a guarded realization semantics that retains these distinctions when an error is extracted. The resulting error magnitude is bounded above by a certificate attached to the chosen realization and below by the greatest lower bound determined solely by the observed behavior. For linear double-pushout rewriting in a typed presheaf setting, we identify the greatest subobject transported intact through a rewrite step and through a finite rewrite path. Guarded local estimates compose to give pathwise upper certificates. At the set level, the complementary lower bound is the infimum of magnitudes in a behavior fiber. For non-discrete categories, it is given by a pointwise right Kan extension when that extension exists, and it reduces to the strict-fiber infimum under a Grothendieck fibration hypothesis. For continuous surjective linear observations onto finite-dimensional normed spaces, the lower reflection is the induced quotient norm. Applied to finitely many distinct characters on a compact metrizable abelian group, this yields an interpolation norm with an exact dual formula. Continuous and discrete Abel transfer theorems then convert observed coefficients into lower bounds for tail amplitudes, with consequences for Mellin transforms, generating functions, and normalized point-count errors of curves over finite fields. Under the stated guards and soundness hypotheses, every realization satisfies $Q(O(\mathrm{Err}(r))) \leq A(\mathrm{Err}(r)) \leq U(r)$.
Read the full abstract
Combinatorics
Tensor Spectral Stability for Uniform Hypergraphs with Bounded Matching Number
We establish a tensor spectral stability theorem for uniform hypergraphs with bounded matching number. More precisely, for fixed integers $k\geq 3$ and $\beta\geq2$, and sufficiently large $n$, we prove that every $n$-vertex $k$-uniform hypergraph $H$ with matching number at most $\beta$ and tensor spectral radius close to the maximum possible value among all such hypergraphs must be structurally close to the extremal hypergraph $S_{n,k,\beta}$, whose edges consist of all $k$-sets intersecting a fixed set of $\beta$ vertices. Furthermore, we show that every edge of $H$ intersects this distinguished vertex set and that $H$ contains all but a small proportion of the edges of $S_{n,k,\beta}$. As an application, we obtain a new proof of the spectral version of the Erdős matching conjecture for sufficiently large $n$.
Read the full abstract
Geometric Topology
A TQFT-based Platform for Efficient Computation of Knot Invariants
We present an interactive web platform that unifies the construction Feynman ribbon diagrams (FRDs), the evaluation of higher-rank Chern–Simons knot invariants, and the identification of FRD-like knots at higher crossing numbers. These tree-structured diagrams naturally represent arborescent knots, which we refer to throughout as FRD-like knots. Within a single visual environment, users can construct an FRD as a tensor network, evaluate its associated Chern–Simons invariants, and use the resulting invariant data to distinguish and identify the corresponding knot. To our knowledge, this is the first platform to combine diagrammatic construction, tensor-network evaluation, invariant computation, and knot identification within a unified workflow.
Read the full abstract
Probability
A CIR-Type Diffusion Driven by Hermite Processes: Well-Posedness, Positivity and Malliavin Analysis
We study a generalized Cox–Ingersoll–Ross (CIR) diffusion \begin{equation*} dX_t = a\bigl(b(t)-X_t\bigr)\,dt + \bigl(\sigma_0+\sigma_1\sqrt{\phi_\eps(X_t)}\bigr)\,dZ_t^{(q,H)}, \quad X_0 = x_0 > 0, \end{equation*} where $Z^{(q,H)}$ is a Hermite process of order $q\geq 1$ and Hurst parameter $H\in(1/2,1)$, and $\phi_\eps$ is a smooth regularisation of the square root. This framework simultaneously captures long-range dependence, non-Gaussian innovations (for $q\geq 2$), and the positivity of the classical CIR model. Since Hermite processes with $q\geq 2$ are not semimartingales, we interpret the dynamics pathwise in the Young–Stieltjes sense, exploiting the Hölder regularity of $Z^{(q,H)}$. We establish four main results. First, well-posedness: a unique strong solution exists in a fractional Sobolev space, under globally Lipschitz coefficients (satisfied by $\phi_\eps$). Second, a quantitative positivity bound: for $\sigma_1=0$, the probability that $X$ stays positive on $[0,T]$ is bounded below by an explicit expression tending to $1$ as the initial level and long-run target grow large relative to $\sigma_0$; an almost-sure statement, available in the classical Brownian case, is not established here, since the usual boundary-non-attainment mechanism relies on tools unavailable for a non-semimartingale driver. Third, Malliavin differentiability: $X_t\in\D^{1,\infty}$, with an explicit formula for the Malliavin derivative as the solution of a linearised Young SDE. Fourth, absolute continuity: the law of $X_t$ is absolutely continuous with respect to the Lebesgue measure for all $t>0$.
Read the full abstract
Representation Theory
The loop-nilpotent cohomological Hall algebra
We give an explicit shuffle algebra model for the loop-nilpotent cohomological Hall algebra (CoHA) of a tripled quiver with canonical cubic potential. As consequences, we (1) relate the loop-nilpotent CoHA to the quantized Coulomb branch algebra of the corresponding quiver gauge theory, (2) show that the loop-nilpotent CoHA is supercommutative after specialization at $\hbar=0$, (3) give generators for both the loop-nilpotent CoHA and the full preprojective CoHA, and (4) obtain an explicit characterization of the BPS Lie algebra of the full preprojective CoHA via certain degree and divisibility conditions. This gives a new formula for the Kac polynomials of the quiver in terms of the dimensions of certain vector spaces of polynomials. We also prove a conjecture on the spherical generation of the localized shuffle algebra and show that for ADE quivers, the loop-nilpotent CoHA is the positive half of Drinfeld-Gavarini dual of the Yangian.
Read the full abstract
Spectral Theory
Graphs with maximal Laplacian eigenvalue multiplicity
In this paper, \( G \) is a simple connected graph, and \( m_G(\lambda) \) denotes the multiplicity of \( \lambda \) as an eigenvalue of the Laplacian matrix \( L(G) \). Let \( p(G) \) denote the number of pendant vertices of \( G \), \( q(G) \) the number of quasi-pendant vertices of \( G \), and \( c(G) \) the dimension of the cycle space of \( G \). Li et al. [Discrete Mathematics, 2026] proved that if \( G \) is a tree with \( G \not\cong K_{1,n-1} \) and \( \lambda \neq 1 \), then \[ m_G(\lambda) \le q(T) - 1. \] Moreover, for a general graph \( G \) with \( \lambda \neq 1 \), Li et al. also proved in the same paper that \[ m_G(\lambda) \le c(G) + q(G), \] with equality if and only if \( G \cong K_{1,n-1} \) or \( G \cong C_n \) with \( \lambda \notin \{0, 4\} \). A natural consequence is that if \( c(G) + q(G) \ge 2 \), then \[ m_G(\lambda) \le 2c(G) + q(G) - 1. \] When \( c(G) = 0 \), this reduces to the result of Li et al. for trees. In this paper, we give a complete characterization of graphs \( G \) attaining the equality \[ m_G(\lambda) = 2c(G) + q(G) - 1. \]
Read the full abstract
Complex Variables
Hilbert matrix norms on weighted Bergman spaces: even exponents and a counterexample to the beta formula
Let $A_\alpha^p$ be the weighted Bergman space on the unit disk, where $\alpha>-1$. For $f(z)=\sum_{k=0}^{\infty}a_k z^k\in A_\alpha^p$, consider the Hilbert matrix operator $\mathcal{H}f(z)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\infty}\frac{a_k}{n+k+1}\right)z^n =\int_0^1\frac{f(t)}{1-tz}\,dt$. For even exponents $p=2m$, we prove that $\|\mathcal{H}\|_{A_\alpha^{2m}\to A_\alpha^{2m}}=B(a,1-a)$, where $a=(\alpha+2)/(2m)$, whenever $0<a\leq m/(2m-1)$. For $p=2,4,6,8,10$, the same formula holds throughout the admissible range. We also show that the beta-function norm formula does not hold for all admissible parameters. Set $a_0=800001/1000000$ and $\alpha_p=a_0p-2$. Then, for every real $p\geq 1100000$, $\|\mathcal{H}\|_{A_{\alpha_p}^p\to A_{\alpha_p}^p}>B(a_0,1-a_0)$. The counterexample is based on the fixed function $f_0(z)=(1-z^2)^{-4/5}=\sum_{k=0}^{\infty}\frac{(4/5)_k}{k!}z^{2k}$. A rigorous interval estimate at $p=1100000$, together with monotonicity in $p$, yields the result on the entire half-line. In particular, the formula fails for every even exponent $p=2m$ with $m\geq 550000$.
Read the full abstract
Differential Geometry
A degenerate free boundary minimal annulus and non-uniqueness in spherical caps beyond the hemisphere
Let $\{\Sigma_a\}$, $a\in(0,1/2)$, be de Oliveira's family of embedded free boundary minimal annuli of revolution in geodesic balls $B(R(a))\subset\mathbb{S}^3$, $R(a)>\pi/2$. We prove that $R$ is real-analytic, tends to $\pi/2$ at both ends, and therefore folds: it has an interior maximum $R_*>\pi/2$ and is not injective. Hence each $B(\rho)$ with $\pi/2<\rho<R_*$ contains at least two, and only finitely many, mutually non-congruent annuli of the family. At every critical point of $R$ the annulus is degenerate modulo ball-preserving isometries: its Jacobi–Robin kernel contains a rotationally invariant, reflection-even field not induced by any Killing field of $\mathbb{S}^3$ preserving the ball; its nullity is at least three. These degenerate annuli form a nonempty discrete set; off it, the rotationally invariant even nullity vanishes. Those sitting at a maximizer of $R$, in the largest cap $B(R_*)$, are called degenerate annuli of maximal cap radius; each such annulus is also a strict local area maximizer in the family, since area and $R$ have the same critical points. Thus the hypothesis that all Jacobi fields of an embedded free boundary minimal annulus in a spherical cap are Killing-induced, used in the Naff–Zhu continuity approach to uniqueness, fails for some radius $R>\pi/2$. The exact identity $\dim K_0^{ev}(\Sigma_a)=\mathbf{1}_{\{R'=0\}}(a)$ detects the degeneration; it follows from the symmetry-free relation $\partial_\eta\varphi_a-\operatorname{ct}_\kappa(r(a))\varphi_a=r'(a)A_a(\eta,\eta)$, a Robin defect identity, which requires of the ambient only that the barrier family be umbilic and which extends to capillary boundary conditions at constant contact angle.
Read the full abstract
Probability
Equivalence of Canonical and Microcanonical Ensembles for Euclidean Lattices
We study the equivalence of canonical and microcanonical ensembles for quadratic Hamiltonians on Euclidean lattices. The answer depends on the arithmetic structure of the energy spectrum: exact-energy microcanonical ensembles converge locally to the canonical Gibbs law in the lattice case, but may retain additional arithmetic information in the nonlattice case. We show that this obstruction disappears after replacing an exact energy shell by any fixed-width energy window. Using uniform local central limit theorems, we also obtain sharp asymptotics for the corresponding state counts and recover Bost's thermodynamic entropy.
Read the full abstract
Combinatorics · Cross-listed from cs.FL
Additive Bases from Primitive Dyck Words: Regular Underapproximations, Motzkin Coding, and Digit Lifting
We study additive representations by integers whose canonical binary expansions are primitive Dyck words. Pairing consecutive bits yields a positional form of the classical relation between Dyck paths and two-colored Motzkin paths: except for 10, primitive Dyck words are exactly the binary block images of base-4 words 3w0, where w is a two-colored Motzkin word. This exposes a regular underapproximation, digit closure, and sharp generation bounds. We prove an interval digit-lifting theorem for digitally closed sets and a constructive base-4 propagation algorithm that lifts finite sumset certificates to infinite tails in logarithmically many recursive stages. Combining these tools with exact finite certificates and generation-gap lower bounds, we classify all positive even integers requiring more than six primitive Dyck summands. The integer 46 requires eight, and 34, 44, 98, 154, 198, 202, 206, 838, 842, and 846 require seven; every other positive even integer requires at most six. Thus 848 is the sharp eventual threshold. The bound is asymptotically optimal because 10*4^(k+1)-6 requires six summands for every k >= 2. The associated halved family has exact asymptotic additive order five. Supplementary programs reproduce all finite certificates using exact integer arithmetic.
Read the full abstract
Category Theory
A Grothendieck category with a noetherian generator and exact products that is not a module category
We construct a Grothendieck category that has a noetherian generator, satisfies AB4*, and is not equivalent to a module category. This gives a negative answer to Djament's problem. The category is obtained as a Gabriel quotient of a module category over the endomorphism ring appearing in the work of Herbera, Příhoda, and Wiegand. The proof relies on the trace criterion established by Martini, Parra, Saorín, and Virili.
Read the full abstract
Information Theory
Lossless Address Coding for Quantum Networks
As quantum systems advance toward interconnected architectures, the ability to identify nodes, manage resources, and support network-level functions becomes increasingly critical. In this work, we propose a lossless source coding scheme for addressing in quantum networks that enables compact, hierarchical, and coherently processable quantum address states. Specifically, we introduce a prefix-suffix address space and develop an isometric hierarchical encoder-decoder that guarantees unique decodability. We further provide a practical Huffman-based procedure that embeds prefix-free, length-eigenstate codewords into the address space, thereby preserving isometry. The scheme is particularly designed for networks with hierarchical structure, heterogeneous cluster sizes, and configurable address assignment to accommodate dynamic network conditions. A numerical example on a 13-node network demonstrates that the proposed hierarchical encoding scheme is feasible and achieves perfect fidelity. This work establishes a rigorous connection between source coding theory and quantum network design, offering a practical framework towards scalable and coherent quantum addressing.
Read the full abstract
Algebraic Topology · Cross-listed from cs.LG
Topological Data Analysis and Graph-Theoretic Approaches for Tennis Match Prediction
We present two approaches for predicting tennis match outcomes using topological data analysis and graph theory on ATP singles matches from 2000-2025. The first method applies lower-star filtration to player competitive networks, extracting topological features through persistent homology using four summary methods (VAB, HNAV, HWNAV, OW-HNPV) combined with Modified Band Depth analysis. Algorithmic optimizations including ego graph approximations and triangle elimination enable analysis of about 66k matches. Our Random Forest model achieves 66.2% accuracy (AUC = 0.719) using topological, graph-theoretic, and ranking features. Feature importance analysis reveals that rankings contribute 36.3%, centralities 25.5%, and TDA features 24.0%, with topological features providing complementary signal. When rankings are unavailable, the topology-only model maintains 63.56% accuracy, demonstrating that network-derived features alone capture meaningful competitive structure. The second method uses a modified Katz similarity index with temporal edge weighting, achieving 62.48% accuracy on held-out test data. This work represents the first application of lower-star filtration to tennis prediction, provides systematic comparison of four topological summary methods in sports analytics, and demonstrates that TDA can achieve above-chance prediction using network topology alone while providing additional value when combined with traditional features.
Read the full abstract
Combinatorics
The Smith normal form of Laplacian matrices of simplicial annuli and high dimensional trees
Inspired by the generalization of the formula of determinant of the distance matrix of trees to $k$-trees, we study the Smith normal form of Laplacian matrices associated with some simplicial complexes. We find relations between sandpile groups of adjacency graphs and the Smith normal form of Laplacian matrices of simplicial complexes. We use such relations to calculate the Smith normal form of the highest Laplacian matrix of simplicial annuli and $k$-trees. %The low dimensional cases seems to be more difficult to calculate. We also provide numerical experiments to visualize how good are these algebraic invariants to distinguish $k$-trees. Finally, we point out that the Graham-Lovász-Pollak matrix, used to compute the determinant of the distance matrix of trees, can be used in the context of Laplacian matrices of trees and block graphs.
Read the full abstract
Statistics Theory · Cross-listed from stat.ML
Learning switched non-linear dynamical systems from a single trajectory
We study empirical risk minimization for learning non-linear dynamical systems whose transition dynamics may switch over time. Under stability assumptions, and i.i.d switching over a set of $K$ modes, we derive non-asymptotic bounds on the prediction risk expressed in terms of the metric entropy of the underlying function class. We instantiate our general result for Hölder and linear function classes, obtaining explicit convergence rates that depend on the effective sample size $Tp_i$, where $T$ is the trajectory length and $p_i$ is the probability of observing mode $i$. Numerical simulations support our theoretical findings. To the best of our knowledge, these results are the first non-asymptotic guarantees for learning switched nonlinear dynamical systems from a single trajectory.
Read the full abstract
Combinatorics · Cross-listed from cs.LO
Formalizing Flag Algebras in Lean
Razborov's flag algebra method is one of the most successful tools for proving asymptotic density inequalities in extremal graph theory. It reduces an inequality about all large graphs avoiding a forbidden pattern to finitely many algebraic conditions, and a certificate satisfying them can be found by semidefinite programming. We formalize the method for finite simple graphs in Lean 4, building on Mathlib. The formalization covers flags and their densities, the flag algebra as a quotient vector space, positive homomorphisms as limits of graph sequences, Razborov's random extensions, and the downward operator that averages out labels. On top of this theory, we build verified computation of flag densities and a tactic that turns certificates found by semidefinite programming into Lean proofs. The certificate serves only as candidate data; Lean checks every fact the proof uses. With this development we verify seven Turán-type upper bounds. Adding lower-bound constructions proved in Lean yields the asymptotic form of Mantel's theorem and the asymptotic Erdős pentagon theorem $\pi(C_5;K_3)=24/625$; to our knowledge, the latter has not previously been formalized in a proof assistant. We also prove two inequalities of Goodman. All density theorems reported here depend only on the standard axioms of Lean's logic. Formalization also led us to treat forbidden subgraphs with a different semantics. Instead of building a separate flag algebra for each forbidden family, we keep a single algebra of all graphs and impose the constraint only when interpreting an inequality, through randomly labeled limits of graphs satisfying it. We prove that this ensemble semantics yields the intended density bounds, and that a condition we call root-plantability characterizes when it agrees with the standard semantics.
Read the full abstract
Representation Theory
On the natural transformations of extension functors
Assume that $n$ is a non-negative integer and $\C$ an $n$-Frobenius category. This paper is concerned with the natural transformations between extension functors on $\C$. The main result of the paper indicates that for any pair of objects $M, N\in \C$, the group of all natural transformations from $\Ext^{n+1}_{\C}(N, -)$ to $\Ext^{n+1}_{\C}(M, -)$ is isomorphic to the quotient group $\Ext^n_{\C}(M, \syz^nN)/{\p}$, where $\p$ is the subgroup consisting of those Yoneda extensions of length $n$ arising as a push-out along a morphism $P\rt\syz^nN$, with $P$ $n$-projective. This result is fruitful from the point of view that, $n$-Frobenius categories may not have projective objects.
Read the full abstract
Optimization and Control · Cross-listed from cs.LG
A Multi-stage Constrained Optimization Framework for Data-driven Problems
Variational autoencoders (VAEs) transform high-dimensional, often noisy data into a compact latent representation, making downstream optimization more tractable. Three challenges persist in VAE-based constrained optimization: (i) sampling effectively within the latent space, (ii) identifying the active decision variables that actually influence the objective and constraints, and (iii) enforcing constraints without destabilizing training. We propose a Multi-stage Constrained Optimization Framework (MCOF). First, an entropy-constrained VAE (EC-VAE) coupled with a feature selector embeds objective and constraint information into a designated subset of latent variables, so that optimization proceeds over a low-dimensional subspace while the remaining coordinates supply solution diversity. Second, a Uniform Transformation (UT) module applies a per-dimension probability integral transform, replacing the irregular aggregate posterior with a uniform distribution over a bounded box and mitigating posterior collapse and Gaussian mixture bias. Third, a constraint-priority filter method (CPFM) solves the resulting surrogate problem by alternating violation-reduction and objective-reduction steps under a filter acceptance test, returning solutions that are feasible for the learned surrogate to a specified tolerance without requiring multiplier estimation. Finally, unselected latent coordinates are resampled to generate diverse decodings of a single optimized solution. We validate MCOF on a synthetic problem, where we ablate each stage and recover the analytic optimum, and on a ZINC250k drug design task, where the generated molecules satisfy the imposed constraints and are entirely novel relative to the training set.
Read the full abstract
Representation Theory
A second reduction-type formula for the refined Littlewood–Richardson coefficients in type A
For a permutation $w$ in the symmetric group $S_n$ and partitions $\lambda, \mu, \nu $ with at most $n$ parts, the refined Littlewood–Richardson (LR) coefficients $c^{\nu}_{\lambda,\mu}(w)$ in type $A_n$ count the multiplicity of the irreducible polynomial representation $V(\nu)$ of the general linear algebra $\mathfrak{gl}_n(\mathbb{C})$ appearing in the decomposition of the Kostant–Kumar submodule $K(\lambda,w,\mu)$ of the tensor product $V(\lambda) \otimes V(\mu)$ of two irreducible polynomial $\mathfrak{gl}_n(\mathbb{C})$-modules. In this paper, we establish a second reduction-type formula for $c^{\nu}_{\lambda,\mu}(w)$, extending the second reduction formula for the classical Littlewood–Richardson coefficients $c^{\nu}_{\lambda,\mu}$. The proof relies on the hive model.
Read the full abstract
Optimization and Control
Convexity and SOS-Convexity of Sum of Separable and Biquadratic Quartic Polynomials and Optimization
Determining whether multivariate polynomials of degree four or higher are nonnegative and convex is a strongly NP-hard problem. To mitigate these computational difficulties, sum-of- squares (SOS) convexity has been proposed as a tractable algebraic relaxation that yields a checkable sufficient condition for convexity and can be expressed as a semidefinite program (SDP). In this work, we introduce a structured subclass of quartic polynomials, called the Sum of Separable and Biquadratic (SPBQ) forms, and conduct a systematic analysis of the connection between convexity and SOS-convexity within this class. Specifically, we show that every convex SPBQ polynomial is necessarily SOS-convex when the associated biquadratic form has size n x 2. We then construct an explicit SPBQ example with a 3 x 3 biquadratic form that is convex but fails to be SOS-convex. Finally, we examine both unconstrained and constrained optimization problems involving SPBQ polynomials, demonstrate notable computational benefits compared to general SOS-based methods, and illustrate their use in convex polynomial regression and fluid dynamics.
Read the full abstract
Optimization and Control
On the Bellman equation in recursive stochastic dynamic programming with the CES aggregator
In this paper we investigate discrete-time infinite horizon Markov decision processes (dynamic programming models) with recursive utilities defined by the classical CES aggregator and the certainty equivalent operator being the negative of the entropic risk measure. Under mild conditions on the primitive data we prove existence and uniqueness of a solution to the Bellman equation. Moreover, we show that for any given stationary policy, the Koopmans equation has a unique solution. These two facts imply that a measurable selector of maxima in the Bellman equation is an optimal stationary policy. The methods of our proofs are applied to study solutions to the Bellman equation for other certainty equivalents, including risk-neutral case.
Read the full abstract
Algebraic Geometry
Sylow Criteria for Liftability of Automorphism Groups of Smooth Hypersurfaces
In this paper, we first establish Sylow criteria for liftability of finite subgroups of the projective linear groups over arbitrary field. We also obtain Sylow criteria for $F$-liftability: if $F$ is a nonsingular polynomial of degree $d$ in $N$ variables over a field of characteristic zero, then a finite subgroup $G$ of $\mathrm{Lin}(F)$ is $F$-liftable if and only if for every prime $p$ dividing $\gcd(|G|,N,d)$, there exists a Sylow $p$-subgroup of $G$ that is $F$-liftable. Our proof combines restriction and corestriction in group cohomology with the reduction-to-Klein method.