Peer Revenue Past citations are no guarantee of future returns

Papers

Fresh from arXiv, typeset properly. Highlighted words trade on the market.

Mathematics

math Watch Mathematics (sign in to use)

Thursday 7 May

Statistics Theory · Cross-listed from stat.ML

Risk-Controlled Post-Processing of Decision Policies

Predictive models are often deployed through existing decision policies that stakeholders are reluctant to change unless a risk constraint requires intervention. We study risk-controlled post-processing: given a deterministic baseline policy, choose a new policy that maximizes agreement with the baseline subject to a chance constraint on a user-specified loss. At the population level, we show that the optimal policy has a threshold structure: it follows the baseline except on contexts where switching to the oracle fallback policy yields a large reduction in conditional violation risk. At the finite-sample level, given a fitted fallback policy and score, we develop a post-processing algorithm that uses calibration data to select a threshold. Leveraging tools from algorithmic stability and stochastic processes, we show that under regularity conditions, in the i.i.d. setting, the expected excess risk of the post-processed policy is $O(\log n/n)$. In the special case when an exact-safe fallback policy is available, the algorithm achieves precise expected risk control under exchangeability. In this setting, we also give high-probability near-optimality guarantees on the post-processed policy. Experiments on a COVID-19 radiograph diagnosis task, an LLM routing problem, and a synthetic multiclass decision task show that targeted post-processing can meet or nearly meet risk budgets while preserving substantially more agreement with the baseline than score-blind random mixing.
Read the full abstract

All authors Sunay Joshi, Tao Wang, Hamed Hassani, Edgar Dobriban

Combinatorics

Leap generators for composition schemes

Leap generators have been introduced in [Duchon et al.'04] for exact-size random generation of structures in a class of the form $\mathcal{C}=\mathrm{Seq}(\mathcal{B})$ (sequence construction), in the supercritical case. We extend these generators to supercritical composition schemes $\mathcal{C}=\mathcal{A}\circ\mathcal{B}$. Compared to the sequence construction, the obtained exact-size random generator for $\mathcal{C}$ still has linear time complexity (under conditions on the sampling complexity in $\mathcal{A}$ and $\mathcal{B}$), but perfect uniformity of the distribution is lost in general. However the distribution on $\mathcal{C}_n$, called leap distribution, is asymptotically uniform, the total variation distance from the uniform distribution being $(c+o(1))n^{-1/2}$ for an explicit constant $c$. These generators are simple to implement and can be applied to several classes of walks and trees, in particular Pólya trees. Leap generators can also be given for certain critical composition schemes, those relating planar map families, where this time the total variation distance to the uniform distribution is $\sim c\,n^{-1/3}$ for an explicit constant $c$.
Read the full abstract

Optimization and Control

Dynamic Controlled Variables Based Dynamic Self-Optimizing Control

Self-optimizing control is a strategy for selecting controlled variables, where the economic objective guides the selection and design of controlled variables, with the expectation that maintaining the controlled variables at constant values can achieve optimization effects, translating the process optimization problem into a process control problem. Currently, self-optimizing control is widely applied to steady-state optimization problems. However, the development of process systems exhibits a trend towards refinement, highlighting the importance of optimizing dynamic processes such as batch processes and grade transitions. This paper formally introduces the self-optimizing control problem for dynamic optimization, termed the dynamic self-optimizing control problem, extending the original definition of self-optimizing control. A novel concept, "dynamic controlled variables" (DCVs), is proposed, and an implicit control policy is presented based on this concept. The paper theoretically analyzes the advantages and generality of DCVs compared to explicit control strategies and elucidates the relationship between DCVs and traditional controllers. Moreover, this paper puts forth a data-driven approach to designing self-optimizing DCVs, which considers DCV design as a mapping identification problem and employs deep neural networks to parameterize the variables. Three case studies validate the efficacy and superiority of DCVs in approximating multi-valued and discontinuous functions, as well as their application to dynamic optimization problems with non-fixed horizons, which traditional self-optimizing control methods are unable to address.
Read the full abstract

All authors Chenchen Zhou, Shaoqi Wang, Hongxin Su, Xinhui Tang, Yi Cao, Shuang-Hua Yang

Differential Geometry

Equivalence of intrinsic and extrinsic area bounds for minimal surfaces

We show that intrinsic and extrinsic area density bounds are equivalent, with matching asymptotic values, for complete, connected, smooth minimal immersions $i:\Sigma^d\to\mathbb{R}^N$ of any dimension and codimension. Combining our results with a recent breakthrough by Bellettini, we extend the Schoen–Simon–Yau curvature estimates for smoothly immersed, two-sided, stable minimal hypersurfaces $i:\Sigma^n\to\mathbb{R}^{n+1}$ with bounded intrinsic area density to the missing case $n=6$, which had remained open since.
Read the full abstract

Algebraic Topology · Cross-listed from cs.LG

No Triangulation Without Representation: Generalization in Topological Deep Learning

Despite an ever-increasing interest in topological deep learning models that target higher-order datasets, there is no consensus on how to evaluate such models. This is exacerbated by the fact that topological objects permit operations, such as structural refinements, that are not appropriate for graph data. In this work, we extend MANTRA, a benchmark dataset containing manifold triangulations, to a larger class of manifolds with more diverse homeomorphism types. We show that, contrary to prior claims, graph neural networks can saturate the benchmark, while higher-order message passing methods lag behind. However, we find that this is contingent on the right representation and feature assignment, emphasizing their importance in baseline models. Hence, we present a novel evaluation protocol based on representational diversity and triangulation refinement. Even when including refinement-like changes in the training data, existing models fail to generalize beyond the combinatorial structure of the data. This points towards a research gap in developing models that understand topological structure independent of scale. Our work thus provides the necessary scaffolding to evaluate future models and enable the development of topology-aware inductive biases.
Read the full abstract

All authors Johannes S. Schmidt, Martin Carrasco, Ernst Röell, Guy Wolf, Nello Blaser, Bastian Rieck

Analysis of PDEs

The simplified 2D Ericksen-Leslie liquid crystal model interacting with a 1D flexible shell

We consider the evolution and interaction of a 2-dimensional nematic liquid crystal of Ericksen-Leslie type within a 1-dimensional flexible viscoelastic structure. This is a fully macroscopic model in which the nematic liquid crystal is modelled by the simplified Ericksen-Leslie system with Ginzburg-Landau approximation. The liquid crystal is contained in a thin viscoelastic shell of arbitrary reference configuration that evolves with respect to the forces exerted by the liquid crystal. Barring any degeneracies in the shell, we construct a global weak solution for the coupled system. We then show that any family of such weak solutions that are parametrized by the Ginzburg-Landau coefficient, converges to a weak solution of the original simplified Ericksen-Leslie system without the Ginzburg-Landau term.
Read the full abstract

Combinatorics · Cross-listed from cs.LG

Measuring Structure in Graph Benchmark Datasets Using Graph Invariants

Progress in graph learning is hindered by benchmark practices that conflate the contributions of node features and graph structure, making it hard to tell whether a model actually learns from the graph, or whether it even needs to. We propose measuring this using graph invariants, i.e., permutation-invariant, task-agnostic structural descriptors. Our analysis on datasets substantiates three tacit assumptions in graph learning, namely that (i) a curated subset of invariants is more expressive than standard GNNs, (ii) benchmark datasets exhibit structural heterogeneity even when originating from the same domain, and (iii) simple models are often competitive with, and sometimes exceed, approaches based on transformers or message passing. We thus posit that graph invariants should become a standard tool for measuring graph learning task complexity and the relevance of graph structure.
Read the full abstract

Number Theory

Asymptotic Statistics of Odd Unimodal Sequences: Rank Distributions and Probabilistic Structures

Integer partitions have fascinated people for centuries, from Ramanujan's groundbreaking congruences to the modern theory of modular forms. This paper investigates the statistical properties of odd unimodal sequences–a natural refinement where sequences rise to a peak and then fall, but with the constraint that all parts must be odd, and develops a comprehensive statistical theory for their rank and shape parameters. We establish the asymptotic distribution of the rank statistic and demonstrate that, when properly normalized, it converges to the hyperbolic secant distribution. Beyond the rank distribution, limiting distributions of the peak, the largest parts on either side of the peak, and the joint behavior of small parts are also proved. These results reveal a rich probabilistic structure that parallels the classical theory of integer partitions while exhibiting distinctive new features arising from the odd-part constraint. The analysis employs a synthesis of modular transformation theory, false theta function asymptotics, and conditioned Boltzmann models. This extends the probabilistic machinery previously developed for unimodal sequences into a more general and analytically demanding setting, offering a unified approach that bridges modular forms and probability.
Read the full abstract

Analysis of PDEs

Formal Stability of Tetrahedral Non-Zonal Flows on the Sphere

We investigate the formal stability of finite-amplitude non-zonal flows bifurcating from the trivial state in the unforced 2D Euler equations on the sphere. To bypass the degeneracy of the spherical Laplacian and filter out the low-frequency Fjørtoft instabilities, we restrict the functional space to the invariant subspace of the tetrahedral symmetry group. Using Arnold's Energy-Casimir method, we prove that the linearized elliptic operator derived via Liapunov-Schmidt reduction acts as the Hessian of the conserved functional. By tracking the critical eigenvalue along the bifurcating branches via the Crandall-Rabinowitz theorem, we establish a relation between the bifurcation topology and formal stability. Applying this framework to four distinct geophysical profile functions, we demonstrate that subcritical polynomial and supercritical sine-Gordon flows achieve a negative-definite second variation, that is, their formal stability. In contrast, subcritical sinh-Gordon and supercritical Liouville exponential flows generate saddle points, making them unstable. This classification identifies the specific nonlinear interactions required for the persistence of large-scale coherent waves in planetary atmospheres.
Read the full abstract

Information Theory · Cross-listed from quant-ph

Tight Contraction Rates for Primitive Channels under Quantum $f$-Divergences

Data-processing inequalities capture the phenomenon that two probability distributions can only become less distinguishable under any common post-processing. For more fine-grained inequalities, one turns to strong data-processing inequality (SDPI) constants, which give the strongest inequalities for a given channel and reference state for a fixed measure of distinguishability. These quantities have been used to quantify the rate at which time-homogeneous Markov chains contract towards a fixed point both in the classical and quantum setting. In this work, we establish that quantum $f$-divergences satisfy a local reverse Pinsker inequality, which implies the asymptotic contraction rate of a primitive channel to its stationary state is upper bounded by the SDPI constant of any non-commutative $\chi^2$-divergence. Using quantum-detailed balance, we establish a sufficient condition for these bounds to be tight. Finally, we apply these results to Petz, Matsumoto, and Hirche-Tomamichel $f$-divergences, establishing new and strengthening previously known results.
Read the full abstract

Optimization and Control

Performance guaranteed MPC Policy Approximation via Cost Guided Learning

Model predictive control (MPC) is widely used in industries but implementing it poses challenges due to hardware or time constraints. A promising solution is to approximate the MPC policy using function approximators like neural networks. Existing methods focus on minimizing the error between the approximators outputs and the MPC optimal control actions on training data, which is called error guided learning approach in this paper. However, the goals of control law design is not to minimize the fitting error but to minimize the operation cost. This paper proposes a novel cost-guided learning approach that utilizes the cost sensitivity information from the MPC problem to directly minimize the loss in closed-loop performance. A theoretical analysis shows cost-guided learning provides tighter guarantees on optimality loss compared to traditional error-guided learning. Experiments on a continuous stirred tank reactor (CSTR) benchmark demonstrate that the proposed technique results in approximate MPC policies that achieve substantially better closed-loop performance. This work makes an important contribution by connecting the fitting errors with operational objectives, overcoming key limitations of existing approximation methods. The core idea could be applied more broadly for data-driven control.
Read the full abstract

Optimization and Control

Second-Order Bilevel Optimization with Accelerated Convergence Rates

This paper studies second-order methods for nonconvex-strongly-convex bilevel optimization. We propose a novel fully second-order bilevel approximation method (FSBA) that achieves an iteration complexity of $\tilde{\mathcal{O}}(\epsilon^{-1.5})$ for finding the $(\epsilon, \mathcal{O}(\sqrt{\epsilon}))$ second-order stationary point of the hyper-objective function. Our results demonstrate that second-order methods can achieve an accelerated convergence rate than first-order methods in bilevel optimization. To address the heavy computational cost associated with the second-order oracle, we introduce a lazy variant of FSBA, called LFSBA, which reuses second-order information across several iterations. We prove that LFSBA exhibits better computational complexity than FSBA by a factor of $\sqrt{d}$, where $d$ is the dimension of the problem. We also apply a similar idea to nonconvex strongly-concave minimax optimization and propose the lazy minimax cubic-regularized Newton (LMCN) method with better computational complexity compared to existing second-order methods.
Read the full abstract

All authors Sheng Yang, Chengchang Liu, Lesi Chen, John C.S. Lui

Probability

$\mathsf{GL}_N(\mathbb{C})$ Brownian motion and stochastic PDE on entire functions

We construct the full edge scaling limit of the singular values of Brownian motion on the general linear group $\mathsf{GL}_N(\mathbb{C})$ starting from general conditions. We show that the limiting paths solve an infinite system of SDE with log-interaction and have a Gibbs resampling property with exponential Brownian bridges. Moreover, we show that the evolution of the limiting rescaled reverse characteristic polynomial solves a stochastic partial differential equation with a non-linear multiplicative noise and linear drift. From a special initial condition the resulting line ensemble coincides, in logarithmic coordinates, with a line ensemble constructed by Ahn which arises as a universal scaling limit of singular values of products of random matrices. We prove some analogous results on the evolution of limiting characteristic polynomials for two models whose stationary measures are given by the Hua-Pickrell and Bessel stochastic zeta functions respectively.
Read the full abstract

Mathematical Physics · Cross-listed from cond-mat.stat-mech

Comparative Study of Potts Machine Dynamics and Performance for Max-k-Cut

Combinatorial optimization problems in logistics, finance, energy, and scheduling routinely involve multi-state decision variables. Ising machines (IMs) require binary expansions (e.g., one-hot encoding) to encode such variables, whereas Potts machines (PMs) represent them natively. By doing so, PMs are expected to outperform IMs on multi-state problems. To the best of our knowledge, no systematic study of PM models has yet assessed whether this expectation holds. We therefore benchmark five representative PMs against a reference IM on Max-3-Cut and Max-4-Cut, using 800-vertex GSet graphs and random graphs of up to 50 vertices. Surprisingly, the reference IM still outperforms every PM, and the IM supremacy increases significantly in going from Max-3-Cut to Max-4-Cut. These results provide clear evidence that current PM dynamics underperform relative to binary approaches, even in regimes where they are presumed advantageous. We provide a way forward by quantifying the underperformance of current PMs, as well as by identifying three dynamical properties that correlate strongly with their performance ranking. Our work stresses the need for more systematic assessments of algorithmic performance in order to guide the design of more effective Potts machines.
Read the full abstract

Mathematical Physics · Cross-listed from cond-mat.stat-mech

Finite-Time Optimal Control by Noisy Traps

The optimal control of passive systems in equilibrium typically favours quasistatic (infinite-time) protocols. We show that a breakdown of quasistatic optimality occurs when the controller itself is dissipative. Concretely, we study a Brownian particle confined by a harmonic trap with stochastically fluctuating stiffness, driven by an external protocol. When these fluctuations violate detailed balance, the probe-controller coupling continuously exchanges work with the system, altering the optimisation landscape. In this regime, optimal protocols are characterised by a finite duration which vanishes above a critical fluctuation strength. This transition can be directly observed in a short-time expansion of the mean work functional. When imposing an endpoint constraint, the transition to zero duration disappears and finite duration protocols remain optimal for all values of the controller fluctuations. These results demonstrate that finite-time optimality can emerge in passive systems under nonequilibrium control.
Read the full abstract

Statistics Theory

Minimax estimation of Functional Principal Components from noisy discretized functional data: the case of smooth processes

We study the minimax estimation of covariance eigenfunctions and eigenvalues in functional principal component analysis when $n$ trajectories are observed at $p$ common grid points with additive noise. We consider covariance kernels with arbitrary Hölder smoothness and no prescribed parametric decay of the eigenvalues. In this setting, kernel smoothness and local spectral separation play distinct roles: a minimax inconsistency result over the smoothness-only class shows that kernel regularity alone is not sufficient for minimax-consistent eigenfunction estimation. To capture this interplay, we introduce a class of processes that jointly controls the Hölder smoothness of the covariance kernel and a local relative inverse eigengap quantity at the target index $\ell$. Over this class, we derive non-asymptotic minimax lower bounds for eigenfunction estimation that disentangle sampling variability, discretization and spectral effects, revealing rates of order $\delta_\ell n^{-1}+p^{-2\alpha}$, where $\delta_\ell$ quantifies the spectral difficulty. We also obtain non-asymptotic lower bounds for eigenvalue estimation under a relative squared-error loss. We then construct a computable wavelet projection estimator based on Coiflet scaling functions and a quadrature scheme designed to accommodate arbitrary Hölder smoothness. For eigenfunction estimation, this estimator matches the minimax dependence on the sample size and grid resolution, up to the natural spectral factor, for any Hölder index $\alpha>0$. Finally, we show that the proposed framework covers several classical Gaussian processes and Karhunen–Loève constructions. In particular, a Karhunen–Loève based criterion links spectral decay, eigenfunction regularity and covariance-kernel smoothness, and yields controlled simulation settings illustrating the predicted phase transitions and least-favourable discretization effects.
Read the full abstract

All authors Nassim Bourarach, Franck Picard, Vincent Rivoirard, Angelina Roche

Analysis of PDEs

Entire spacelike radial graphs with prescribed mean curvature in the Lorentz–Minkowski space

In this paper we address the existence and uniqueness of entire spacelike hypersurfaces in the Lorentz–Minkowski space $\mathbb{L}^{m+1}$ with prescribed mean curvature that are star-shaped with respect to a point and asymptotic to a light cone. We also establish a Willmore-type inequality and prove a non-existence result for spacelike radial graphs asymptotic to the light cone whose mean curvature belongs to $L^p$ for $1 \leq p\leq m$, in particular in the case of compactly supported mean curvature.
Read the full abstract

Numerical Analysis

A polar-factor retraction on the symplectic Stiefel manifold with closed-form inverse

In Riemannian computing applications, it is crucial to map manifold data to a Euclidean domain, where vector space arithmetic is available, and back. Classical manifold theory guarantees the existence of such mappings, called charts and parameterizations, or, collectively, local coordinates. When computational efficiency is of the essence, practitioners usually resort to retraction maps to define local coordinates. Retractions yield first-order approximations of the Riemannian normal coordinates. This work introduces a new retraction on the symplectic Stiefel manifold that features a closed-form inverse. We expose essential features and compare the numerical performance to a selection of existing retractions. To the best of our knowledge, prior to this work, the so-called Cayley retraction was the only retraction on the symplectic Stiefel manifold with known closed-form inverse.
Read the full abstract

Mathematical Physics

Dynamical cooling driven by self-similar fronts in the 2D nonlinear Schrödinger model

We analyze the dynamics towards partial thermalization and subsequent cooling in the defocusing two-dimensional nonlinear Schrödinger model, using direct simulations and insights from the wave-kinetic equations (WKE) and a fourth-order differential approximation model (DAM). We show that the evolving WKE spectrum exhibits two distinct similarity ranges–the quasi-thermal core and the ultraviolet tail–whereas in the DAM, an additional range of infrared self-similarity appears. By stretching the quasi-thermal region, the self-similar fronts drive an effective dynamical cooling process towards the formal but ill-defined equilibrium state at vanishing temperature–analogous to an ultraviolet catastrophe in a system of classical waves.
Read the full abstract

Optimization and Control

Unbalanced Optimal Transport and Density Control for Discrete-Time Linear Systems

This article studies unbalanced optimal transport (UOT) and its dynamical extension, unbalanced density control (UDC), for a class of constrained discrete-time linear systems. UOT compares measures with unequal total mass by balancing transport cost and fidelity to reference measures, while UDC incorporates system dynamics and constraints into this framework. Focusing on Gaussian references and discrete-time linear systems, we show that both problems admit globally optimal convex formulations, analogous to covariance steering. A numerical experiment is provided to illustrate our approach.
Read the full abstract

2605.06391 · 7 May · To appear in the Proceedings of MTNS 2026 (extended abstracts). Submitted on February 15, 2026; accepted on April 20, 2026. A significantly expanded version containing additional theoretical results, complete proofs, and numerical experiments, is available at: arXiv:2605.04246v1

Combinatorics

A solution to Frankl and Kupavskii's conjecture concerning Erdős-Kleitman matching problem

For integers $n\ge s\ge2$, let $e(n,s)$ be the maximum size of a family $\mathcal F\subseteq2^{[n]}$ with no $s$ pairwise disjoint members. The study of determining $e(n,s)$ is closely related to its uniform counterpart, the well-known Erdős matching conjecture. Frankl and Kupavskii conjectured an exact formula for $e((m+1)s-\ell,s)$ when $1\le \ell\le \lceil s/2\rceil$. We prove that for every fixed $m\ge3$ and sufficiently large $s$, the extremal families for $e((m+1)s-\ell,s)$ are $P(m,s,\ell;L)\coloneqq\{A\subseteq [n]\colon |A|+|A\cap L|\ge m+1\}$ for some $L$ with $|L|=\ell-1$ when $1\le \ell\le (\frac{m+1}{2m+1}-o(1))s$. In particular, this confirms the Frankl–Kupavskii conjecture for every fixed $m\ge3$ and all sufficiently large $s$. For $m=3$, we determine the whole range of $\ell$ for which $P(3,s,\ell;L)$ is extremal, generalizing a theorem of Kupavskii and Sokolov.
Read the full abstract

Statistics Theory · Cross-listed from econ.EM

Covariate Balancing and Riesz Regression Should Be Guided by the Neyman Orthogonal Score in Debiased Machine Learning

This position paper argues that, in debiased machine learning, balancing functions should be derived from the Neyman orthogonal score, not chosen only as functions of covariates. Covariate balancing is effective when the regression error entering the score can be represented by functions of covariates alone, and it is the natural finite-dimensional approximation for targets such as ATT counterfactual means. For ATE estimation under treatment effect heterogeneity, however, the score error generally contains treatment-specific components because the outcome regression is a function of the full regressor $X=(D,Z)$. In that case, balancing common functions of $Z$ can leave the treatment-specific component unbalanced. We therefore advocate regressor balancing, implemented by Riesz regression with basis functions of $X$, as the general balancing principle for DML. The position is not that covariate balancing is invalid, but that covariate balancing should be understood as the special case that is appropriate when the score-relevant regression error is a function of covariates alone.
Read the full abstract

Dynamical Systems

Orbital Counting in Conjugacy Classes

In this article we consider a restricted orbital counting problem for the action of certain discrete groups on suitable spaces. In particular, we present asymptotics for counting those points in an orbit restricted to a single conjugacy class. A classical example would be cocompact actions of a discrete group acting isometrically on a simply connected manifold with pinched negative curvature. More generally, we obtain results for convex cocompact actions on $CAT(-1)$ spaces.
Read the full abstract

Mathematical Physics · Cross-listed from hep-th

Systematic Extraction of Exact Yang-Mills Solutions via Algebraic Tensor Ring Decomposition

The non-linear nature of Yang-Mills theory presents a challenge for extracting exact classical solutions, which are useful for understanding non-perturbative vacuum structures. In this paper, an algebraic tensor ring decomposition framework is introduced to systematically map the non-linear partial differential equations (PDEs) of Yang-Mills theory into tractable differential-algebraic systems. By promoting static pure-gauge backgrounds to dynamical variables, the reference state acts as a geometric template whose Maurer-Cartan forms generate the algebraic cross-terms necessary to stabilize non-linear self-interactions. To analytically resolve the resulting differential ideals, specific differential-algebraic quotient rings are employed as evaluation tools, and the solution space is organized by an algebraic bifurcation analysis. Applying this framework, three distinct classes of exact solutions are extracted: (i) relativistic $SU(2)$ color waves evaluated over an elliptic quotient ring, where the differential ideal bifurcates into a Decoupled Branch and two Coupled Branches, the latter exhibiting mass gap generation; (ii) dynamical dyonic flux tubes obtained from a time-dependent helical template, where the Gauss law ideal bifurcates the system into Coulomb, Dyonic, and symmetric Meissner branches. In the Meissner branch, an Artinian asymptotic truncation yields Bessel-type exponential screening, stabilized by a temporal dominance condition; and (iii) dynamical $SU(3)$ configurations where the Gauss law ideal bifurcates the solution space into four distinct phases. The non-trivial branches enforce a kinetic cancellation mechanism that maps the amplitude dynamics onto a generalized $x^2y^2$ chaotic oscillator. Across these settings, the framework provides a methodical approach to characterize the classical solution space of strongly coupled gauge theories.
Read the full abstract

Combinatorics

The maximum number of $k$-cliques of 7-connected 1-planar graphs

In 2023, Gollin, Hendrey, Methuku, Tompkins and Zhang determined the maximum number of cliques in general 1-planar graphs with order $n$. Their extremal examples have connectivity at most three, except for a few small orders. At the high-connectivity end, we prove that every $n$-vertex 7-connected 1-planar graph has at most $4n-12$ edges, $4n-16$ triangles, and $n-6$ copies of $K_4$. Hence the total number of cliques is at most $10n-33$. All bounds are sharp for infinitely many values of $n$.
Read the full abstract

Statistics Theory · Cross-listed from cs.LG

Ordinal Credit Assignment: Multi-Step Reinforcement Learning from Comparisons Alone

Policy-gradient methods need a scalar reward, yet for many tasks no formula captures what we want, while judging which of two outcomes is better is easy. We study reinforcement learning that receives only such comparisons - no reward function, no reward model - in multi-step tasks. Groups of trajectories start from a shared state, and each action is credited by how its reward-to-go compares with those of other trajectories at the same time step. We show the expected update is policy gradient with reward-to-go replaced by its win rate against the population still running at that time, weighted by the chance an opponent is still running; in deterministic environments the update ranks actions by true value and the optimal policy is stable, whereas under stochastic outcomes it prefers actions that win more often rather than those with higher mean. Label noise near ties or from position bias leaves the expected update unchanged; only noise that also flips clear comparisons halves the signal. A critic trained from the same comparisons removes the state confound without changing the expected update. In a pre-registered study over six environments with ten seeds per claim, comparisons cost no detectable performance relative to scalar returns at the same granularity, learning a reward model from the same comparisons is not better, and ten percent of comparisons suffice when spent on a few time points with all pairs. With real LLM judges, comparisons are 7-10 points more accurate than pointwise scores, and the gap grows with the stronger judge. Trained end-to-end with an LLM judge on a requirement the hand-written reward omits, policies satisfy it in all five seeds but land far less often than with oracle comparisons, because the judge is near chance on the near-tied failures dominating early training. Comparisons do not close the gap to PPO with scalar rewards on HalfCheetah.
Read the full abstract

Combinatorics

On the dimension of the space generated by characteristic vectors of $q$-Steiner systems

Fix a prime power $q$ and parameters $1\leq t\leq k\leq n$, the corresponding Steiner system in the Grassmann scheme, or the $q$-Steiner system, is a collection $\mathfrak{B}$ of $k$-dimensional subspaces of $\mathbb{F}_{q}^n$ such that for each $t$-dimensional subspace $T$, there exists exactly one element of $\mathfrak{B}$ containing $T$. The dimension of Steiner systems in the Grassmann scheme is defined to be the dimension of the $\mathbb{Q}$-vector space spanned by the characteristic vectors of all these $q$-Steiner systems. In this paper, we prove that when a quadruple $(t,k,n,q)$ admits at least one $q$-Steiner system, the corresponding dimension is equal to ${n\brack k}_{q}-{n\brack t}_{q}+1$. This generalizes the 2019 work of Ghodrati \cite{ghodrati2019dimension} on ordinary Steiner systems.
Read the full abstract

Number Theory

A multidimensional Szemerédi theorem in integers

For any integer $n \geq 2$, let $(m_{1},\ldots,m_{n})$ be a strictly increasing $n$-tuple of positive integers. We show that any subset $A\subset [N]^n$ of density at least $(\log N)^{-c}$ contains a nontrivial configuration of the form \begin{equation*} \boldsymbol{x},\boldsymbol{x}+r^{m_{1}}\boldsymbol{e_{1}},\ldots,\boldsymbol{x}+r^{m_{n}}\boldsymbol{e_{n}}, \end{equation*} where $c=c(n,m_{1},\ldots,m_{n} )$ is a positive constant. This quantitative multidimensional Szemerédi theorem extends a recent two-dimensional result of Peluse, Prendiville, and Shao concerning the configuration of the form $(x,y),(x+r,y),\left(x,y+r^{2}\right)$. The theorem is obtained as a consequence of an effective “popular” version.
Read the full abstract

Analysis of PDEs

Hölder Stability from Exact Uniqueness for Finite-Dimensional Analytic Inverse Problems

We prove a stability theorem for finite-dimensional analytic inverse problems. Let \(U\subset\R^m\) be an open parameter set, let \(F(p)\) be a boundary measurement operator, and let \(R(p)\) be the finite-dimensional quantity to be recovered. If \(F\) is real analytic and \[ F(p)=F(q)\quad\Longrightarrow\quad R(p)=R(q), \] then \(R\) satisfies a Hölder stability estimate on every compact subset of \(U\). The proof uses a Hilbert–Schmidt scalarization of the operator equation \(F(p)=F(q)\) and the Łojasiewicz distance inequality. We also prove that, after fixing countable dense families of boundary inputs and tests, finitely many scalar matrix elements of the data give the same Hölder recovery on compact parameter sets. This finite-measurement conclusion is qualitative: the proof does not give an effective measurement list, exponent, or constant. The finite-measurement statement follows from finite determinacy of real analytic zero sets. We apply the result to local Neumann-to-Dirichlet data for piecewise constant anisotropic conductivities and to localized Dirichlet-to-Neumann data for piecewise homogeneous anisotropic elasticity.
Read the full abstract