Information Theory
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Tuesday 21 April
This paper develops a principled foundation for goal-oriented semantic communication for logical decision-making. Consider a setting where autonomous agents engage in collaborative perception. In such settings, the volume of sensory data and limited bandwidth often make transmission of raw observations infeasible, requiring intelligent selection of task-relevant information. Because these scenarios are safety-critical, the selection and decision processes must also be transparent and verifiable. To address this, we propose an explainable semantic communication framework grounded in a First-Order Logic (FOL) hierarchical representation of the world. We define semantic information, entropy, relative entropy, change in entropy, and mutual information by assigning an inductive logical probability measure over semantic structures in the language. Based on these definitions, we formulate a goal-oriented semantic communication objective through semantic rate-distortion theory and, equivalently, through the semantic information bottleneck principle. In this framework, task rules are represented as goal-oriented states, defined as a layer over the world states to capture decision-relevant abstractions. The resulting principle selects evidence that is most informative about these states, aiming to transmit only those FOL clauses most critical for decision-making while preserving logical verifiability. We demonstrate the effectiveness of the approach in a deduction-based safe path-following task within an FOL-based urban environment simulator with multiple dynamic agents.
Geometric Topology
Sutured manifold hierarchies and the Thurston norm
By the classical work of Thurston and Gabai, the Thurston norm of any compact oriented irreducible $3$-manifold with toroidal boundary is determined by finitely many taut sutured manifold hierarchies. We give an explicit procedure to extract this information from such hierarchies. This is achieved via the maw dual graph construction, which can be incorporated into a general method for computing the Thurston norm of a manifold. As an application, we compute the Thurston norm of the exterior of all alternating and some non-alternating pretzel links with three components. Using these computations, we give a negative answer to a question of Baker–Taylor. Namely, we exhibit an infinite family of manifolds, and an infinite family of knots in each manifold, such that the wrapping number associated with these knots is not a seminorm on the respective second real homology group. Next, we show that if a taut surface in a link exterior is disjoint from a boundary torus and does not represent a corner of the Thurston norm ball, then the corresponding link component is algebraically split from the rest of the link. Moreover, the surface remains norm-minimising under every non-longitudinal Dehn filling on that boundary component and, under an assumption of atoroidality, is a leaf of a taut foliation transverse to the filling core.
Read the full abstract
Analysis of PDEs
Particle Dynamics Driven by Charge Exchange
We introduce and analyse a mathematical model describing the dynamics of particles generated by charge-exchange interactions. The model extends the well-established exchange-driven growth model, previously studied in several works, by allowing for particle densities defined on the entire integer lattice. Despite the many similarities between the two models, substantial differences arise both in their qualitative behaviour and in their mathematical analysis. Under suitable assumptions on the kernel in the collision operator, we establish global well-posedness in the class of nonnegative densities with finite first moment. Moreover, under a detailed balance condition, we investigate the structure of equilibria and analyse their stability by means of entropy methods.
Read the full abstract
Numerical Analysis
Quadrature-Enhanced Monte Carlo fPINN Method for High-Dimensional Fractional PDEs
Fractional PDEs involving the fractional Laplacian on bounded domains are challenging because of hypersingular nonlocal kernels, exterior Dirichlet constraints, reduced boundary regularity, and the high computational cost in high dimensions. To address these issues, we first adopt a spatially varying radius with directional distance-to-boundary information, which yields a geometry-adaptive three-part decomposition of the fractional Laplacian: singular near-field, regular interior far-field, and analytical exterior far-field contributions. Then we employ Gauss-Jacobi quadrature for the singular radial integral, Gauss quadrature for the regular interior radial integral, and Monte Carlo sampling for the angular variables. A feature-enhanced physics-informed neural network trial space is finally used to tackle the low-regularity behavior near the boundary. Through the above steps, we obtain a quadrature-enhanced Monte Carlo fractional physics-informed neural network (QE-MC-fPINN) method. Numerical experiments on fractional Poisson equations and time-dependent fractional PDEs show that, on the tested benchmarks, the proposed method outperforms two representative MC-fPINN discretizations in accuracy and convergence, especially for solutions with strong boundary singularities.
Read the full abstract
Metric Geometry
Cartesian products of Sierpiński carpets do not attain their conformal dimension
It is a long-standing open question to determine whether the Sierpiński carpet attains its conformal dimension or not. While this problem remains unresolved, we prove that Cartesian products $\mathbb{S}^k$, where $\mathbb{S}$ is the Sierpiński carpet and $k \geq 2$, do not attain their conformal dimension. Our approach is based on the Sobolev spaces and energy measures on $\mathbb{S}$ – constructed by Shimizu, Kigami, and Murugan and Shimizu – together with a certain singularity result of energy measures from the theory of analysis on fractals. This work formulates a general non-attainment result of conformal dimension for product metric spaces $X^k$ for $k \geq 2$ in terms of self-similarity and energy measures of the factor $X$. It applies, in particular, to the cases where $X$ is the Sierpiński carpet, the Sierpiński gasket, the Menger sponge, and the Laakso diamond.
Read the full abstract
Analysis of PDEs
Shock wavefronts for parabolic equations with sign-changing diffusivity
We consider a reaction-diffusion equation in a one-dimensional space, where the diffusion coefficient changes sign from positive to negative and back to positive. The reaction term is bistable, with its interior zero located in the region where the diffusivity is negative. The model does not admit continuous wavefronts, i.e., continuous traveling waves that connect the steady states $0$ and $1$. We prove the existence of a family of shock wavefronts, that is, wavefronts with profiles exhibiting a jump discontinuity. We investigate the properties of these profiles and their propagation speeds. Finally, we apply the results to a recently proposed model describing the movement of a population composed of both isolated and grouped individuals.
Read the full abstract
Analysis of PDEs
Minimizers for the Cahn-Hilliard energy functional with the Flory-Huggins potential under strong anchoring conditions
In this paper, we theoretically and numerically study the minimizers for the Cahn-Hilliard energy with the Flory-Huggins potential under the strong anchoring condition, i.e., the Dirichlet boundary condition. We reveal bifurcation phenomena mediated by the boundary condition, the transition layer thickness, and the temperature of the system. Numerical simulations are also presented to approximate the minimizers of this energy by solving a gradient-flow equation, namely the Allen-Cahn equation constrained with strong anchoring conditions and random initial data. The effects of varying the transition layer thickness and temperature are presented to confirm the theoretical analysis.
Read the full abstract
Complex Variables
The right invariant metric on the analytic automorphism group of the unit open disk induced by maximal modulus
In this paper, we study the right invariant metric $d_{H^{\infty}}$ on the analytic automorphism group $\rm{Aut}(\mathbb{D})$ of the unit open disk $\mathbb{D}$ induced by maximal modulus, that is, $d_{H^{\infty}}(\varphi, \psi)=\sup_{z\in\mathbb{D}}|\varphi(z)-\psi(z)|$ for any $\varphi, \psi\in \rm{Aut}(\mathbb{D})$. We give the explicit formula of the right invariant metric $d_{H^{\infty}}$ and characterize the almost regular Finsler geometric structure of $(\rm{Aut}(\mathbb{D}), d_{H^{\infty}})$.
Read the full abstract
Representation Theory
Fractionally Calabi-Yau algebras and cluster tilting
We show that the class of twisted fractionally Calabi-Yau algebras of finite global dimension coincides with the stable endomorphism algebras of $d$-cluster tilting modules over $d$-representation-finite algebras. This is an application of our main result stating that an algebra $A$ of finite global dimension is twisted fractionally Calabi-Yau if and only if there exists $i$ such that the replicated algebra $A^{(i)}$ is a higher Auslander algebra if and only if there exist infinitely many $i$ such that $A^{(i)}$ is a higher Auslander algebra. This gives a new connection between the study of higher Auslander-Reiten theory and twisted fractionally Calabi-Yau algebras, and provides a new construction of large classes of higher Auslander algebras and higher representation-finite algebras. We give several applications such as an explicit characterisation of twisted $\frac{n}{2}$-Calabi-Yau algebras, and a triangle equivalence between the bounded derived category of a twisted fractionally Calabi-Yau algebra of finite global dimension and the $\mathbb{Z}$-graded stable module category of an associated higher preprojective algebra.
Read the full abstract
Numerical Analysis
Regularity Analysis and Tensor Neural Network Methods for Quasiperiodic Elliptic Equations
This paper investigates quasiperiodic elliptic equations using a well-established projection method, by which the original problem is reformulated as a degenerate periodic variational problem defined on a higher-dimensional torus. The main analytical difficulty lies in the degeneracy of the projected torus problem: the variational formulation is coercive in the projected Sobolev spaces induced by the projection matrix, but fails to be coercive with respect to the standard Sobolev norm. We establish the well-posedness and regularity estimates within these projected Sobolev spaces. However, such projected Sobolev regularity alone is insufficient for standard spectral approximation: we show that it may result in arbitrarily slow Fourier convergence. To overcome this limitation, under a Diophantine condition for the projection matrix, together with appropriate assumptions on the coefficients and source term, we derive improved Sobolev regularity of the solution in standard Sobolev spaces.This provides a systematic mechanism for justifying the Sobolev regularity required in Fourier spectral convergence analysis, rather than imposing it a priori. Consequently, the improved Sobolev regularity enables quantitative Fourier projection error estimates for quasiperiodic problems. Inspired by these analytical results, we propose an adaptive tensor neural network Galerkin method that is naturally tailored to this degenerate high-dimensional periodic problem. Thanks to its tensor-product structure, high-dimensional variational integrals can be fully decoupled into one-dimensional quadratures, avoiding Monte Carlo sampling and yielding accurate deterministic numerical results. Numerical experiments on several quasiperiodic elliptic problems demonstrate the accuracy and efficiency of the proposed method.
Read the full abstract
Optimization and Control · Cross-listed from cs.LG
Separating Geometry from Probability in the Analysis of Generalization
The goal of machine learning is to find models that minimize prediction error on data that has not yet been seen. Its operational paradigm assumes access to a dataset $S$ and articulates a scheme for evaluating how well a given model performs on an arbitrary sample. The sample can be $S$ (in which case we speak of “in-sample” performance) or some entirely new $S'$ (in which case we speak of “out-of-sample” performance). Traditional analysis of generalization assumes that both in- and out-of-sample data are i.i.d.\ draws from an infinite population. However, these probabilistic assumptions cannot be verified even in principle. This paper presents an alternative view of generalization through the lens of sensitivity analysis of solutions of optimization problems to perturbations in the problem data. Under this framework, generalization bounds are obtained by purely deterministic means and take the form of variational principles that relate in-sample and out-of-sample evaluations through an error term that quantifies how close out-of-sample data are to in-sample data. Statistical assumptions can then be used ex post to characterize the situations when this error term is small (either on average or with high probability).
Read the full abstract
Numerical Analysis
Adaptive refinement based on local approximation power of hierarchical spline spaces
We propose an adaptive refinement strategy for hierarchical B-splines that increases the approximation power of every marked cell by at least one. Here, the approximation power of a cell is the finest level $\ell$ such that all the B-splines of level $\ell$ that do not vanish on the cell belong to the hierarchical space. This increase can be achieved with the standard refinement of hierarchical meshes, in which each cell is subdivided at most once per step, provided that the regions formed at each level by the cells with this property are nested. We call the hierarchical meshes with this nesting property weakly admissible, characterize them, and prove that the proposed refinement preserves weak admissibility. We also prove a complexity estimate: the number of cells created along the adaptive process is bounded by a constant times the total number of marked cells. Moreover, we extend known local $L^q$ estimates for a multilevel quasi-interpolant on these meshes to Sobolev norms, showing that the local error bound on each active cell is governed by its approximation power, which supports using this quantity to drive the refinement. Numerical experiments illustrate the local gain of resolution produced by the proposed strategy, as well as its robustness with respect to the marking criterion and the marking parameter.
Read the full abstract
Representation Theory
Computing the Cousin-Zuckerman Resolution and the Lusztig-Vogan Bijection
The goal of this article is to give a proof of a result seemingly absent from the literature characterizing global sections of standard $\mathcal{D}$-modules on the flag variety. This characterization yields a mixture of the Langlands Classification of admissible representations with the Knapp-Zuckerman classification of tempered representations of a real reductive group. We use this result to compute the Cousin-Zuckerman resolution of the trivial representation in terms of standard $(\mathfrak{g},K)$-modules. Further, in the case of $GL(n,\mathbb{H})$ we use this to prove the Lusztig-Vogan bijection for $n=2,3$ and compute the lowest $K$-type map for the zero and principal orbits for general $n$ as well as the image of the trivial representation for even orbits.
Read the full abstract
Mathematical Physics
Fuzzy Geometries with an Internal Space
The product of a non-commutative matrix spectral triple with a simple two-dimensional internal space is considered. This is interpreted as a non-commutative spacetime that contains one charged Dirac fermion and its antiparticle. The inner fluctuations of a vacuum Dirac operator are calculated, using the standard technique of Connes' one-forms. This results in the non-commutative analogue of a gauge field, as expected, and also fluctuations of the spacetime geometry. In addition, the fluctuations include a derivative operator that depends on the particle charge. The integral over the fermions in the model is calculated, leading to some novel induced bosonic terms.
Read the full abstract
Algebraic Geometry
The Lefschetz Type Theorem For Fundamental Group Schemes
Let $k$ be a field, $X$ a connected scheme proper over $k$, $D\subsetneq X$ an ample effective connected divisor, $x\in D(k)$. For Tannakian categories $\mathcal{C}_X$ and $\mathcal{C}_D$ whose objects consist of vector bundles on $X$ and $D$ respectively, we establish general Tannakian criteria for the natural homomorphism \(\pi(\mathcal{C}_D,x)\to \pi(\mathcal{C}_X,x)\) to be faithfully flat, a closed immersion, or an isomorphism. As applications, under Langer type positivity assumptions, we prove that \(\pi^{\ast}(D,x)\longrightarrow \pi^{\ast}(X,x)\) is an isomorphism for $\ast\in\{S,N,EN,F, EF,Loc,ELoc,\acute{e}t,E\acute{e}t,uni\}$ over perfect fields.
Read the full abstract
Differential Geometry
Allard Regularity for Abelian Yang–Mills–Higgs Equation
We prove an Allard regularity theorem for critical points of the Abelian Yang-Mills-Higgs energy at critical coupling in every ambient dimension. A new cylindrical monotonicity formula for the full excess, based on an improved Modica inequality, converts the tilt-excess decay of De Philippis-Halavati-Pigati into rigidity of nontrivial entire critical points with almost unit density. This resolves their Gibbons conjecture without a local minimising assumption. Adapting the local vortex expansion and projected linear theory of Badran-del Pino, we obtain quantitative vortex approximation and uniform interior $C^{2,\alpha}$ estimates for the nodal sets. To pass to nonzero complex levels, we use a Hodge decomposition of the difference between the actual and approximate connections: curvature comparison controls the co-closed part, while the Coulomb condition gives estimates for the exact part and hence for the phase. In the Coulomb gauge with vanishing normal component on the outer boundary, this yields graphical $C^{2,\alpha}$ bounds for all levels $\{u_\varepsilon=t\}$, uniformly for $|t|\leq1-b$, in an interior tubular neighbourhood of the nodal set.
Read the full abstract
Analysis of PDEs
Existence of small semi-vortex solutions for the cubic nonlinear Schrödinger system with Rashba type Spin-Orbit coupling on $\mathbb{R}^2$
We consider the cubic nonlinear Schrödinger system with Rashba type Spin-Orbit Coupling (SOC) on $\mathbb{R}^2$. The system describes SO-coupled spinor BEC in physics. In the literature of physics, the small semi-vortex solutions, small ground state, and the so-called mixed mode, which are mixture of semi-vortex solutions, are investigated. The semi-vortex solutions cause from the resonance on the essential spectrum of the linear operator. In the present paper, we give mathematical proofs of the existence of the semi-vortex and the ground state by finding minimizers of the energy under small mass constraint based on concentration compactness argument. Moreover, we also discuss the mixed modes in the case where all the coefficients of the nonlinear terms are equal.
Read the full abstract
Statistics Theory · Cross-listed from cs.SI
Hypergraph Mining via Proximity Matrix
Hypergraphs serve as an effective tool widely adopted to characterize higher-order interactions in complex systems. The most intuitive and commonly used mathematical instrument for representing a hypergraph is the incidence matrix, in which each entry is binary, indicating whether the corresponding node belongs to the corresponding hyperedge. Although the incidence matrix has become a foundational tool for hypergraph analysis and mining, we argue that its binary nature is insufficient to accurately capture the complexity of node-hyperedge relationships arising from the fact that different hyperedges can contain vastly different numbers of nodes. Accordingly, based on the resource allocation process on hypergraphs, we propose a continuous-valued matrix to quantify the proximity between nodes and hyperedges. To verify the effectiveness of the proposed proximity matrix, we investigate three important tasks in hypergraph mining: link prediction, vital nodes identification, and community detection. Experimental results on numerous real-world hypergraphs show that simply designed algorithms centered on the proximity matrix significantly outperform benchmark algorithms across these three tasks.
Read the full abstract
Numerical Analysis
Singularities in phase separation models: a spectral element approach for the nonlocal Cahn-Hilliard equation
The nonlocal Cahn-Hilliard equation provides a natural extension of the classical model for phase separation by incorporating long-range interactions through a singular convolution kernel. While this formulation admits a rich existence and regularity theory, its numerical approximation remains challenging: discretisation of the nonlocal term leads to dense operators, and the singularity of the kernel requires special treatment in collocation-based schemes. In this work, we develop an efficient and error-controlled numerical framework for the nonlocal Cahn-Hilliard system with constant mobility, logarithmic potential, Newtonian interaction kernel, and no-flux boundary conditions. Our approach is based on a pseudospectral multishape method that accurately approximates the action of singular convolution operators. We present high-resolution numerical solutions for this nonlocal system of equations that can be achieved with limited computational resources.
Read the full abstract
Information Theory
Constructive Approaches to Perception-Aware Lossy Source Coding: Information-Theoretic Guidelines
Perception-aware lossy source coding has attracted significant recent interest. It augments the classical distortion criterion with an explicit perception constraint, thereby enabling more refined control over fidelity and perceptual quality. Despite rapid progress, the diversity of rate-distortion-perception formulations and their underlying assumptions remains poorly understood by many practitioners. In particular, there is often a tendency to rely heavily on the expressive power of deep neural networks and generative models without clear theoretical guidance, using fundamental limits merely as performance benchmarks rather than as sources of design insight. This tutorial paper aims to bridge this gap by surveying information-theoretic principles that can be leveraged to develop constructive approaches to perception-aware lossy source coding. We distill practical guidelines implied by rate-distortion-perception theory and demonstrate how they inform the design of implementable coding schemes. A simple unit-circle example is used as a pedagogical tool to illustrate key ideas, architectural principles, and tradeoffs in an intuitive and unified manner. Both one-shot and asymptotic settings are examined to highlight conceptual similarities and operational differences. We also clarify the role of common randomness and the notion of universal representation, and elucidate the connections between perception-aware and conventional lossy source coding. Overall, this tutorial provides a principled foundation for developing perception-aware compression systems that go beyond black-box model design.
Read the full abstract
Representation Theory
Verma Bases for finite dimensional Representations of the orthosymplectic Lie superalgebra $\mathfrak{spo}(4|1)$
We define the Verma vector system for each finite dimensional irreducible representation of the orthosymplectic Lie superalgebra $\mathfrak{spo}(4|1)$ with the highest weight $\lambda,$ via the conditions that making a tableau with shape $\lambda$ to be a Kashiwara-Nakashima tableau. We then show the linearly independence of this vector system. It turns out to be a basis of the finite dimensional irreducible representation $L(\lambda)$ of the orthosymplectic Lie superalgebra $\mathfrak{spo}(4|1)$ with the highest weight $\lambda,$ which analogs to the Verma basis of representations of $\mathfrak{sp}_4,$ called the Verma basis of the finite dimensional irreducible representation of $\mathfrak{spo}(4|1)$.
Read the full abstract
Mathematical Physics
Painlevé Asymptotics of the Focusing Nonlinear Schrödinger Equation with a Finite-Genus Algebro-Geometric Background
We investigate the Cauchy problem for the focusing nonlinear Schrödinger (NLS) equation \begin{equation} iq_t(x,t)+q_{xx}(x,t)+2|q(x,t)|^2q(x,t)=0,\quad x\in\mathbb{R},\quad t\ge0,\nonumber \end{equation} subject to initial data $ q(x,0)$ satisfying the asymptotic boundary conditions \begin{equation}\label{eq:boundary} q(x,0) \sim q^{alg}(x,0) \quad \text{as} \quad x \to \pm\infty,\nonumber \end{equation} where $q^{alg}(x,t)$ denote finite-genus algebro-geometric quasi-periodic solutions of the focusing NLS equation. Employing the Riemann–Hilbert (RH) approach combined with the Deift–Zhou nonlinear steepest descent method, we analyze the long-time asymptotic behavior of solutions to this Cauchy problem. Our analysis distinguishes between two cases based on the genus $n$ of the underlying hyperelliptic Riemann surface: (i) Odd genus backgrounds: When the background solutions $q^{alg}(x,0)$ correspond to hyperelliptic curves of odd genus $n = 2s+1$ $(s \in \mathbb{N}_0)$, we identify distinct asymptotic regions in the $(x,t)$-plane characterized by the variable $\xi = x/t$, within which the leading-order asymptotics is expressed in terms of the second Painlevé transcendent. (ii)Even genus backgrounds: When the background solutions $q^{alg}(x,0)$ correspond to hyperelliptic curves of even genus $n = 2s$ $(s \in \mathbb{N})$, the asymptotic behavior in regions selected by $\xi$ is described in terms of parabolic cylinder functions. Specifically, we derive the leading-order asymptotics and establish explicit error bounds for the solution $q(x,t)$ as $t \to +\infty$, uniformly for $x \in \mathbb{R}$.
Read the full abstract
Combinatorics
Cyclic Equalizability Characterized by Parikh Vectors
Cyclic equalizability is a notion introduced by Shinagawa and Nuida in 2025, in the study of card-based cryptography. Informally, a collection of words is cyclically equalizable if, by inserting the same letters at the same positions in all words, they can be transformed into words that are cyclic shifts of one another. Shinagawa and Nuida showed that two binary words of equal length are cyclically equalizable if and only if they have the same Hamming weight. They also posed the problem of characterizing cyclic equalizability over larger alphabets. In this paper, we completely characterize cyclic equalizability for two words over an arbitrary finite alphabet by proving that two words are cyclically equalizable if and only if they have the same Parikh vector.
Read the full abstract
Numerical Analysis
Scalable Multigrid Solver for the Helmholtz Equation: Real-Shifted Coarse Grid Correction
We present a convergent and scalable multigrid solver for high-frequency Helmholtz equations. Standard multigrid methods do not converge for high-frequency Helmholtz problems, and a common cure is adding a complex shift and using the shifted operator as a preconditioner. Nevertheless, the complex shift prevents scalability. In this work we present a new method that achieves scalable convergence of a 3-level cycle without a complex shift. Our key idea is real-shifting the coarsest grid Galerkin operator, to correct the numerical dispersion between the grids. We show that this real-shifted coarse grid correction leads to a scalable 3-level method, for problems with 12 grid points per wavelength on the fine grid, and a convergent cycle with very few iterations for 11 grid points per wavelength, using standard point-smoothers. For problems with 10 grid points per wavelength, our method combined with a modest complex shift outperforms the standard complex shifted Laplacian method by an order of magnitude. We demonstrate wavenumber independent convergence for heterogeneous geophysical media in 2D and 3D.
Read the full abstract
Representation Theory
Verma Bases and Kashiwara-Nakashima Tableaux of $\mathfrak{sp}_4$
We construct a one-to-one correspondence between the Verma basis vectors of a finite dimensional irreducible representation $L(\lambda)$ of the symplectic Lie algebra $\mathfrak{sp}_4$ and the Kashiwara-Nakashima tableaux of $\mathfrak{sp}_4$ with shape $\lambda $ naturally. We also give a proof of the linear independence of the Verma vector system directly.
Read the full abstract
Classical Analysis and ODEs
On Fourier decay and the distance set problem
We study the Falconer distance set problem in Euclidean space and obtain improved dimensional estimates under natural Fourier analytic assumptions cast in terms of the Fourier dimension and spectrum. Interestingly, under reasonably mild assumptions, we are able to beat the $d/2$ dimension threshold in dimensions $d \geq 5$. For example, we show that (in any ambient spatial dimension $d$) a Borel set with Fourier dimension at least $2$ has a distance set of full Hausdorff dimension. We also show that (in any ambient spatial dimension $d$) a Borel set with Fourier spectrum at least $d/4+1$ at $\theta=1/2$ has a distance set of full Hausdorff dimension. In particular, this can hold for sets with Fourier dimension zero (provided $d \geq 4$). We also consider pinned variants of these problems and construct examples that demonstrate the sharpness (or near sharpness) of our results.
Read the full abstract
Optimization and Control · Cross-listed from cs.CG
Maximum Solow–Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
We prove that, for every fixed $\theta_0>0$, selecting a subset of prescribed cardinality that maximizes the Solow–Polasky diversity indicator is NP-hard for finite point sets in $\mathbb{R}^2$ with the Euclidean metric, and therefore also for finite point sets in $\mathbb{R}^d$ for every fixed dimension $d \ge 2$. This strictly strengthens our earlier NP-hardness result for general metric spaces by showing that hardness persists under the severe geometric restriction to the Euclidean plane. At the same time, the Euclidean proof technique is different from the conceptually easier earlier argument for arbitrary metric spaces, and that general metric-space construction does not directly translate to the Euclidean setting. In the earlier proof one can use an exact construction tailored to arbitrary metrics, essentially exploiting a two-distance structure. In contrast, such an exact realization is unavailable in fixed-dimensional Euclidean space, so the present reduction requires a genuinely geometric argument. Our Euclidean proof is based on two distance thresholds, which allow us to separate yes-instances from no-instances by robust inequalities rather than by the exact construction used in the general metric setting. The main technical ingredient is a bounded-box comparison lemma for the nonlinear objective $\mathbf{1}^{\top}Z^{-1}\mathbf{1}$, where $Z_{ij}=e^{-\theta_0 d(x_i,x_j)}$. This lemma controls the effect of perturbations in the pairwise distances well enough to transfer the gap created by the reduction. The reduction is from Geometric Unit-Disk Independent Set. We present the main argument in geometric form for finite subsets of $\mathbb{R}^2$, with an appendix supplying the bit-complexity details needed for polynomial-time reducibility.
Read the full abstract
Dynamical Systems
Emergence of Multiple Crossing Limit Cycles in Planar Piecewise Systems with Isochronous Centers and Nonsmooth Switching Manifolds
Discontinuous piecewise differential systems exhibit dynamical behaviors with no counterpart in smooth systems, particularly in the presence of nonsmooth switching structures. In this work, we extend previous results for systems separated by a straight line to the case where the switching manifold is a nonregular curve, showing that the loss of regularity significantly increases the algebraic complexity of the closing conditions defining crossing limit cycles. As a consequence, we derive explicit upper bounds for the number of crossing limit cycles in planar systems formed by a linear Hamiltonian saddle and quadratic isochronous centers, and construct explicit examples exhibiting four crossing limit cycles in each case, thereby providing sharp constructive lower bounds. While the upper bounds follow from classical algebraic arguments, the realization of multiple crossing limit cycles requires solving nonlinear systems of high degree and remains highly nontrivial. These results highlight how nonsmooth switching manifolds enhance dynamical complexity and promote multistability in discontinuous piecewise systems
Read the full abstract
Algebraic Geometry
Algebraic Distance Optimization in Polyhedral Norms
We consider the distance minimization problem to a real algebraic variety $X \subseteq \RR^n$ when the metric is induced by a polyhedral norm. Each point in the variety has a Voronoi cell whose geometry depends on the normal space at the point and the inner normal fan of the polyhedral ball. For codimension-one varieties, we decompose $X$ into sets of points whose Voronoi cones have the same dimension, which is the expected dimension of their Voronoi cell. We prove that this decomposition is a stratification of $X$ and that each strata is a semialgebraic set. We conclude by giving an algebraic description of the medial axis, which is the locus of points whose minimal distance to $X$ is achieved at more than one point on $X$.
Read the full abstract
Combinatorics · Cross-listed from cs.SI
The eigenvector centrality of hypergraphs
A hypergraph is called uniform when every hyperedge contains the same number of vertices, otherwise, it is called non-uniform. In the real world, many systems give rise to non-uniform hypergraphs, such as email networks and co-authorship networks. A uniform hypergraph has a natural one-to-one correspondence with its adjacency tensor. In 2019, Benson proposed the eigenvector centrality of uniform hypergraphs via its adjacency tensor. In this paper, we define an adjacency tensor for hypergraphs and propose the eigenvector centrality for hypergraphs. When the hypergraph is uniform, our proposed eigenvector centrality reduces to Benson's. When each edge of the uniform hypergraph contains exactly two vertices, our proposed centrality reduces to the eigenvector centrality of graphs. We conducted experiments on several real-world hypergraph datasets. The results show that, compared to traditional centrality measures, the proposed centrality measure provides a unique perspective for identifying important vertices and can also effectively identify them.