Combinatorics
Perturbation of the largest matching root of hypergraphs
Jiang-Chao Wan and Yi Wang
The largest matching root of a $k$-graph is the largest real root of its matching
polynomial, which is equal to the maximum modulus of all the zeros of the matching
polynomial. In this paper, we investigate the perturbation of the largest matching root of $k$-graphs. We determine all $k$-graphs whose largest matching root attains the maximum among all $k$-cacti and linear $k$-cacti with a given number of cycles and edges, where a $k$-cactus is a $k$-graph in which every two distinct cycles have at most one vertex in common. To achieve this, we prove that the celebrated shifting operation of $k$-graphs, introduced by Erdős, Ko and Rado, does not decrease the largest matching root. This result extends a classical result by Csikvári (Electron. J. Combin. 18 (2011) $\#$P182) stating that the Kelmans transformation does not decrease the largest matching root of graphs.
Read the full abstract ▾
Number Theory
On Maximal Prime Gaps
Cheng-TIng Wang
In this paper, we show that the gap between a
prime number $p_n$ and its consecutive
prime $p_{n+1}$ is on the order of $\log^2{p_n}$; consequently, we show the existence of a
prime in certain types of intervals.
Mathematical Physics · Cross-listed from gr-qc
On the catastrophe time of fluids under the action of a gravitational field
D. Astesiano, G. Ortenzi and M.L. Ruggiero
Motivated by the central role of the Zel'dovich approximation in the description of
cosmic structure formation through gravitational collapse, we investigate Burgers-type dynamics in a spherically symmetric gravitational field. In the Newtonian setting, we derive perturbatively the catastrophe time for radial motion by imposing the loss of invertibility of the Lagrangian map. We show that the perturbative expansion is controlled by the dimensionless parameter $ \alpha=\mu/{r_0^3 v_0(r_0)'^2}, $ rather than by the local gravitational acceleration alone. Hence, the expansion remain valid even when
gravity is strong. We then extend the analysis to radial geodesic motion in Schwarzschild spacetime.
Read the full abstract ▾
Representation Theory
Spherical Twists for Gorenstein Orders and $G$-Hilb
Marina Godinho
This paper constructs derived autoequivalences of Gorenstein orders as twists around spherical functors. More precisely, given a Gorenstein order $A$ and a quotient $p \colon A \to B$, then we specify natural conditions on $B$ under which the twist around the corresponding derived restriction of scalars functor is a derived autoequivalence of $A$. In the process, we show that the associated cotwist is a shift of the Nakayama functor of $B$. These results, together with local-to-global technology, are then used construct new derived autoequivalences for skew group
algebras and $G$-
Hilbert schemes, and we apply this theory to explicit examples.
Read the full abstract ▾
Group Theory
Commutative decomposition of infinite symmetric groups and transformation monoids
Luna Elliott and Alex Levine
The commutative subgroup width of a group $G$ is the smallest $k$ such that there are abelian subgroups $A_0,A_1,\ldots,A_{k-1}\leq G$ with $G=A_0A_1\cdots A_{k-1}$. Commutative (inverse) submonoid width is defined analogously. In 2002, Abért showed, rather surprisingly, that the commutative subgroup width of the symmetric group on an infinite set is always finite. It was later shown by Seress that it is always bounded above by $14$. We answer a question of Seress and show that in fact the commutative subgroup width of $\operatorname{Sym}(\mathbb{N})$ is at most $9$. We improve the best known lower bound to $4$. We also study standard monoid analogues of the symmetric group; showing that the commutative submonoid widths of the full transformation monoid $\mathbb{N}^\mathbb{N}$, the partial transformation monoid $P_\mathbb{N}$ and the symmetric inverse monoid $I_\mathbb{N}$ are exactly $3$. We conclude by showing that the commutative inverse submonoid width of any infinite symmetric inverse monoid is always infinite.
Read the full abstract ▾
Optimization and Control
A Non-Monotone Preconditioned Trust-Region Method for Neural Network Training
Andrea Angino, Bindi Çapriqi, Shega Likaj et al. (+2 more)
Training deep neural networks at scale can benefit from domain decomposition, where the network is split into subdomains trained in parallel and coupled by a global trust-region mechanism. Building on the Additively Preconditioned Trust-Region Strategy (APTS), we propose a non-monotone variant with a nonlinear additive Schwarz preconditioner that combines parallel subdomain corrections with global coarse-space directions. A windowed acceptance criterion allows controlled objective increases, avoiding needless rejection of effective coarse steps. The resulting non-monotone APTS (NAPTS) preserves accuracy while reducing CPU time by 30% and cutting rejected steps to one third of those in APTS.
Read the full abstract ▾
All authors Andrea Angino, Bindi Çapriqi, Shega Likaj, Ken Trotti, Rolf Krause
Geometric Topology
The Euler obstruction of a $1$-form on a determinantal singularity
Anne Frühbis-Krüger and Hellen Santana
In this work, we investigate the connections between the local Euler obstruction and the Poincaré-
Hopf-Nash (PHN) index of a $1$-form in the setting of determinantal singularities. As an application, we provide explicit computations of the Euler obstruction of a function with a stratified isolated singularity at the origin defined on an IDS with rigid singularities.
Read the full abstract ▾
Information Theory
Construction of Minimal Ternary Linear Codes with Dimension $m+2$ Via Krawtchouk Polynomials
Haibo Liu, Xin Guo and Qunying Liao
Recently, minimal linear codes have been extensively studied due to their applications in secret sharing schemes, secure two-party computations, and so on. Constructing minimal linear codes violating the Ashikhmin-Barg condition and then determining their weight distributions have been interesting in coding theory and cryptography. In this paper, a generic construction for ternary linear codes with dimension $m+2$ is presented, where $m$ is an integer, and a necessary and sufficient condition for this ternary linear code to be minimal is derived. Based on this condition and Krawtchouk
Polynomials, a new class of minimal ternary linear codes violating the Ashikhmin-Barg condition are obtained, and then their complete weight enumerators are determined.
Read the full abstract ▾
Optimization and Control
Successive convex optimization for transformer encoder model predictive control
Xingxiao Chen and Mark Cannon
We propose a data-driven Model Predictive Control (MPC) framework that employs a
transformer encoder to generate multi-step predictions. To handle the nonconvex
attention mechanism, we derive difference of convex (DC) representations of the
transformer encoder components and embed them in a successive convex programming (SCP) iteration. Recursive feasibility and convergence of the SCP iterates are guaranteed, and each iterate yields a solution estimate satisfying the problem constraints. Under mild assumptions, the SCP iteration converges to a locally optimal solution of the MPC problem. The approach is illustrated on a
benchmark nonlinear control problem.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.LG
In-Context Learning for Data-Driven Censored Inventory Control
Sohom Mukherjee, Anh-Duy Pham, Richard Pibernik et al. (+1 more)
We study inventory control with decision-dependent censoring, focusing on the censored or repeated newsvendor (R-NV), where each order quantity determines whether demand is fully observed or censored by sales. Existing approaches based on parametric Thompson sampling (TS) can be brittle under prior mismatch, while offline imputation methods need not transfer to online learning. Motivated by the predictive view of decision making, we combine these ideas by taking oracle actions on learned completions of latent demand. We propose in-context generative posterior sampling (ICGPS), which uses modern generative models that are meta-trained offline and deployed online by in-context autoregressive generation. Theoretically, we show that the
Bayesian regret of ICGPS with a learned completion kernel is bounded by the
Bayesian regret of a TS
benchmark with the ideal completion kernel plus a deployment penalty scaling as $\sqrt{T}$ times the square root of the completion mismatch. This yields a plug-in template for operational problems with known TS regret bounds. For R-NV, we derive sublinear
Bayesian regret by reducing censored feedback to bandit convex optimization feedback. We also show that, under reasonable coverage and stability assumptions, the online completion mismatch is controlled by the offline censored predictive mismatch, so offline predictive quality transfers to online performance. Practically, we instantiate ICGPS with ChronosFlow, which combines a frozen time-series
transformer backbone with a trainable conditional normalizing-flow head for fast censoring-consistent sampling. In
benchmark experiments, ChronosFlow-ICGPS matches correctly specified TS, outperforms myopic and UCB-style baselines, and is robust to prior mismatch and distribution shift. ChronosFlow-ICGPS also performs well for the real-world SuperStore
dataset, especially under heavy censoring.
Read the full abstract ▾
All authors Sohom Mukherjee, Anh-Duy Pham, Richard Pibernik, Yunbei Xu
Algebraic Topology · Cross-listed from cs.LG
ToMAToMP: Robust and Multi-Parameter Topological Clustering
Ludo Andrianirina and Mathieu Carrière
Topological clustering, and its main
algorithm ToMATo, is a clustering method from Topological Data Analysis (TDA) which has been applied successfully in several applications during the last few years. This is due to its high versatility, as clusters are detected from the persistent components in the sublevel sets of any user-defined function (gene expression, pixel values, etc), and efficiency, as topological clustering enjoys robustness guarantees. However, ToMATo is also limited in several ways. First, a graph on the data points needs to be provided as a hyper-parameter of the method (whose fine-tuning is left to the user). Second, ToMATo is known to be very sensitive to outlier values in the function range. Finally, and most importantly, ToMATo can only handle one function at a time, whereas it is critical to use several functions in various applications. In this article, we introduce ToMAToMP: the first topological clustering method able to handle several functions at the same time with theoretical guarantees. More specifically, we leverage a recent tool from multi-parameter persistent homology, called MMA decomposition, to design our clustering
algorithm, and prove that it enjoys robustness properties. As corollaries, we show that it can be used to make ToMATo independent of graph tuning, and robust to outliers. Finally, we provide a set of numerical experiments showcasing the efficiency and quality of the clusterings produced by ToMAToMP, by showing strong improvement over non-topological and topological baselines for various
datasets.
Read the full abstract ▾
Information Theory
A class of asymptotically optimal authentication codes with secrecy
Haibo Liu, Chengzhi Wei and Qunying Liao
In this paper, a class of linear authentication codes with secrecy, which are equipped with simple encoding rules, is constructed. By means of a special Weil sum, the maximum success probabilities of impersonation attack (denoted by $P_I$) and of substitution attack (denoted by $P_S$) for these codes are explicitly derived. It is further proven that the codes are asymptotically optimal, in the sense that both the information theoretic bound and the combinatorial bound for authentication codes are asymptotically attained by $P_I$ and $P_S$.
Read the full abstract ▾
Numerical Analysis · Cross-listed from cond-mat.supr-con
T-E formulation-based modeling of thin HTS shell magnetization
Leonid Prigozhin and Vladimir Sokolovsky
Numerical methods for modeling thin-film magnetization are primarily focused on computing the current density distribution. The highly nonlinear current-voltage characteristic of type-II
superconductors significantly complicates the accurate computation of the electric field. The T-E formulation-based mixed finite element method, previously derived for flat superconducting films, enables the simultaneous, accurate determination of both variables. Another advantage of this method is that the computational domain is limited to the film itself: no meshing of the surrounding space is required. The thin-shell approximation reduces the problem to a two-dimensional one. This work extends the T-E formulation and numerical method to non-flat superconducting shells with a metal substrate. We validate the method with several test examples, including modeling the magnetization of a sphere. The method is then applied to a realistic model of a cylindrical
magnetic dynamo pump, and the generated open-
circuit voltage is computed.
Read the full abstract ▾
Spectral Theory
Reducibility of spectral curves of finite Jacobi pencils
B.Shapiro
We consider finite pencils of Jacobi
matrices \[ J_n(w)=A+wB, \] where $A$ is diagonal and $B$ is tridiagonal with zero diagonal. The spectral curve is the affine plane curve \[ \chi_n(\lambda,w)=\det(\lambda I+J_n(w))=0 . \] The main question is to describe when this curve is reducible. We prove generic irreducibility for fixed pairwise distinct diagonal entries and discuss several elementary reducibility mechanisms. Besides disconnected Jacobi chains, constant
eigenvalue branches, and reflection-symmetric components, one must also take into account reducibility caused by scalar diagonal blocks. We formulate a reducibility
conjecture and record low-dimensional evidence and counterexamples to several overly optimistic classifications. A central point of the picture is a codimension-growth principle: apart from the cutting divisors $b_i=0$, genuinely connected primitive reducibility should move to higher and higher codimension as the size of the chain grows.
Read the full abstract ▾
Combinatorics
Uniquely 2-colourable 4-cycle decompositions
Andrea C. Burgess, David A. Pike and Shahriyar Pourakbar-Saffar
A cycle system of order $n$ is a decomposition of the edges of the complete graph $K_n$ into cycles of a fixed length. A cycle system is said to be $k$-colourable if we can assign $k$ colours to its vertices so that no cycle is monochromatic. A $k$-colourable cycle system is uniquely $k$-colourable if its colouring is unique up to the permutation of colour classes. In this paper, we construct uniquely $2$-colourable $4$-cycle systems of order $n$ for all admissible $n\geq 49$, and also uniquely $2$-colourable $4$-cycle decompositions of $K_n - I$, for all admissible $n \geq 50$. These constructions contribute to the broader study of uniquely colourable cycle systems and open new directions for future research.
Read the full abstract ▾
Algebraic Geometry
Frobenius–Witt cotangent complexes
Kanau Shimada
We introduce the notion of the Frobenius–Witt cotangent complex, which can be considered as a derived variant of the module of Frobenius–Witt differentials defined by T. Saito. This new object also can be seen as an arithmetic variant of the notion of cotangent complex. We explain the suitability of these two viewpoints through a series of propositions. Furthermore, we establish a relationship between Frobenius–Witt cotangent complexes and the regularity of noetherian local rings, which can be considered as a derived variant of Saito's regularity criterion. This proof relies heavily on computations of Frobenius–Witt cotangent complexes in the case of perfectoid rings. We also study the deformation theory of delta structures using Frobenius–Witt cotangent complexes.
Read the full abstract ▾
Optimization and Control
Avoiding Bias in Clipped SGD for Overparameterized Models under Generalized Smoothness
Aleksandr Lobanov and Anastasia Koloskova
Modern machine learning is dominated by complex, overparameterized architectures capable of interpolating data and achieving zero training loss. For such models, we investigate the convergence properties of two popular modifications to standard SGD: clipped SGD and normalized SGD. We show that under overparameterization and a mild assumption on batch size, both clipped and normalized SGD do not suffer from the bias typically introduced by clipping, converging effectively at the same rate as their deterministic counterparts. This provides a rigorous theoretical justification for the empirical success of gradient clipping methods. In our analysis, we employ the $(L_0,L_1)$-smoothness condition, under which we obtain convergence rates that improve upon the best known results in prior work. Furthermore, we extend our analysis to specific challenging regimes, including heavy-tailed noise, $(H_0,H_1)$-smoothness (which is strictly weaker than standard assumptions in optimization literature) and the deterministic regime.
Read the full abstract ▾
General Topology
Persistent Homology of Biquandle Coloring Quivers
Hamdi Kayaslan
In this paper, we extend the notion of directed clique complex to quivers and introduce an associated homology theory. By applying this construction to biquandle coloring quivers, we obtain new invariants of links. We then introduce a quiver filtration-valued invariant of links induced by filtrations of biquandle endomorphism sets. We construct persistent homological invariants of links by applying persistence techniques to these quiver filtrations through the introduced homology theory.
Read the full abstract ▾
Differential Geometry
Fredholm Criteria for $G$-pseudodifferential Operators
Alexandre Baldare, Anton Yu. Savin and Elmar Schrohe
Let $G$ be a compact Lie group that acts smoothly on a closed
manifold $M$. Using a general Simonenko principle, we derive a novel criterion for the Fredholm property of $G$-pseudodifferential operators acting on Sobolev spaces of sections of vector bundles over $M$. In case the group is finite, we obtain a further characterization of the Fredholm property of $G$-pseudodifferential operators in terms of the invertibility of suitable symbols.
Read the full abstract ▾
Complex Variables
The sharp refined Bohr inequalities for a subclass of close-to-convex harmonic mappings
Ayush Kumar
Let $\mathcal{H}$ be the class of normalized complex valued harmonic functions $ f = h + \overline{g}$ defined on the unit disk $\mathbb{D}$, where $h$ and $g$ are analytic functions with the normalization conditions $h(0) = h'(0) - 1 = 0$ and $g(0) = 0$. For the class $R_H^{0}(\gamma, \delta, \lambda)$ ( $0 \leq \lambda < \gamma \leq \delta$) consisting of functions \( f = h+\bar{g} \in \mathcal{H}\) satisfying the condition $f_{\overline{z}}(0)=0$ and the inequality $ Re(\gamma h'(z)+\delta z h''(z) +(\frac{\delta - \gamma}{2})z^2 h'''(z)-\lambda)> |\gamma g'(z)+\delta z g''(z) +(\frac{\delta - \gamma}{2})z^2 g'''(z)|$, we obtain sharp improved Bohr Phenomenon, refined Bohr radius and the Bohr-Rogosinski inequality for the class $R_H^{0}(\gamma, \delta, \lambda)$.
Read the full abstract ▾
Commutative Algebra
On Numerical Semigroups with Fixed Quotient
Ignacio Ojeda and José Carlos Rosales
Let $\Delta$ be a numerical
semigroup and let $d\ge 2$ be an integer. We study the fiber of the quotient map \(S\mapsto S/d\) over $\Delta$. We describe its elements as
semigroups of the form $\langle X\rangle+d\Delta$, for suitable finite sets $X\subseteq\Delta$, and then analyze explicit and computable regions of this fiber. In particular, we introduce a family $\Delta_d(a)$ of multiples with prescribed quotient and compute its generators, classical invariants, Apéry sets, and presentations. We also show that this construction preserves Wilf's inequality and controls the depth. Finally, we introduce the $\mathcal{M}_d(\Delta)$-rank, determine its maximal value in the fiber, relate it to the ordinary
embedding dimension, characterize the rank-one elements, and give closed formulas for their Frobenius-type invariants and pseudo-Frobenius numbers.
Read the full abstract ▾
Numerical Analysis
A Least-Squares Weak Galerkin Finite Element Scheme for Cauchy Problems in Convection–Diffusion
Chunmei Wang and Shangyou Zhang
We introduce and rigorously analyze a least-squares weak Galerkin (LS-WG) finite element method for the severely ill-posed Cauchy problem of convection–
diffusion equations. The proposed framework utilizes weak derivatives defined on a class of discontinuous weak functions, enabling the natural treatment of complex boundary conditions and internal interfaces. A key advantage of the least-squares formulation is that it transforms the underlying non-self-adjoint operator into a discrete linear system that is inherently symmetric and positive definite (SPD). We demonstrate the
geometric flexibility of the method on arbitrary polygonal and polyhedral partitions. Furthermore, we establish the uniqueness of the numerical solution and derive optimal-order error estimates in a carefully defined discrete energy norm. Extensive numerical tests are presented to confirm the theoretical convergence rates and highlight the
algorithm's robustness and efficiency compared to standard Galerkin approaches.
Read the full abstract ▾
Numerical Analysis
Eigenbounds of symmetric positive definite tensors
Snigdhashree Nayak, Hemant Sharma and Nachiketa Mishra
This article introduces an algebraic framework for establishing
eigenvalue bounds for symmetric positive definite tensors by leveraging intrinsic invariants, specifically the trace and determinant (resultant). We derive a hierarchy of inequalities via the Arithmetic Mean-
Geometric Mean (AM-GM) inequality that yields progressively tighter upper and lower bounds for the tensor spectral radius and smallest
eigenvalue. A comprehensive comparative analysis demonstrates that our invariant-based approach significantly outperforms classical coordinate-dependent methods such as the Gershgorin circle
theorem. We explicitly show that our bounds remain robust and informative in scenarios where Gershgorin bounds fail, particularly for tensors with negative off-diagonal entries, where algebraic cancellations occur, and higher-order tensors, where combinatorial growth leads to loose estimates. Furthermore, we validate the practical utility of these bounds by applying them to certify the positive definiteness of Lyapunov functions in the stability analysis of nonlinear autonomous systems.
Read the full abstract ▾
Algebraic Geometry
Kuznetsov components ans transcendental motives of cubic fourfolds
Claudio Pedrini
Let $X \subset \P^5_{\C}$ be a smooth cubic fourfold.The Kuznetsov component $\sA_X$ is contained in the derived category $D^b(X)$ and the transcendental motive $t(X)$ is contained in the category of Chow motives $\sM_{rat}(\C))$. If $X$ and $Y$ are
Fourier -Mukai partners and hence the categories $\sA_X$ and $\sA_Y$ are equivalent, then their transcendental motives $t(X)$ and $t(Y)$ are isomorphic. The aim of this note is to consider families of special cubic fourfolds $X$ with their FM-partners $Y$ and to give an explicit description of the isomorphism between the transcendental motives, in the case $X$ and $Y$ are rational and when they are conjecturally irrational. We also prove that ,for special cubic fourfolds $X $ in countably many Hassett divisors, with a
symplectic automorphism of order 3, there exists another special cubic fourfold $Y$, an equivalence of categories $\sA^G_X \simeq \sA_{Y}$, where $\sA^G_X$ is the equivariant Kuznetsov component, and an isomorphism $t(X) \simeq t(Y)$.
Read the full abstract ▾
Statistics Theory · Cross-listed from stat.ME
Differentially private inference framework for Riemannian manifold data
Yangdi Jiang, Xiaotian Chang and Qirui Hu
We propose a novel and systematic differentially private (DP) inference framework for non-Euclidean data. First, we design two types of DP mechanisms for the Fréchet mean and variance for i.i.d. Riemannian
manifold-valued data, tailored to different
geometric structures and accompanied by analytic
privacy budgets calibrated to the geometry of the underlying
manifold. Second, we establish the consistency and central limit
theorems (CLTs) of the proposed DP
estimators, enabling a suite of statistical inference procedures under
privacy constraints. Furthermore, we provide comprehensive implementation guidelines and feasible procedures, including consistent DP
estimators of the asymptotic variance in the CLTs. Extensive numerical experiments support the proposed methodologies. Finally, we demonstrate the effectiveness of our approach on real-world medical image and sociological
datasets supported on two representative
manifolds.
Read the full abstract ▾
Complex Variables
On Convergence of Rational Hermite-Padé Approximants
Nikolay R. Ikonomov and Sergey P. Suetin
The main purpose of this paper is to compare the convergence properties of Padé approximants and rational Hermite-Padé approximants for some model class of multivalued analytic functions based of the inverse Zhoukovsky transform. We prove that in the class of analytic functions under consideration the rational Hermite-Padé approximants converge faster than the corresponding Padé approximants. In contrast to the classical vector potential-theoretic approach, which was introduced by A. A. Gonchar and E. A. Rakhmanov in 1981 and developed later by A. I. Aptekarev, V. N. Sorokin and others, the proofs here are based on some scalar mixed Green-logarithmic potential problems.
Read the full abstract ▾
Mathematical Physics · Cross-listed from quant-ph
Evolution of Gaussian mixed states under the Markovian master equation for a driven quantum oscillator
B. A. Tay
We study a generic
quantum Markovian master equation for a linearly displaced or driven harmonic oscillator. It was known that the displacement dynamics of Gaussian mixed states depends on the
unitary part of the Liouvillian, the decay rate of the system but not on the bath temperature. Here we further show that the fast-rotating modes do not affect the system's displacement dynamics under linear driving forces. Analytical solutions of the
quantum master equation are obtained for displaced Gaussian mixed states. Because the non-driven and driven Liouvillians are related by a
unitary displacement operator, they are expected to share the same exceptional points structure. At the exceptional points, the displacement of critically damped oscillator displays a characteristics
polynomial-in-time prefactor multiplied by an exponential decay. We discuss how external time-dependent forces affect the displacement dynamics using impulsive force and harmonic force as examples. The results obtained for constant driving remain valid in the presence of time-dependent driving.
Read the full abstract ▾
Combinatorics
The spectral radius of $k$-chromatic $r$-graphs
Xizhi Liu and Junchi Luo
For an $r$-uniform hypergraph $G$, let $\lambda^{(p)}(G)$ denote its $p$-spectral radius, defined as the maximum of the polyform of $G$ over the unit sphere in the $\ell_p$-norm. Let $Q_k^r(n)$ be the complete $k$-chromatic $r$-graph on $n$ vertices with color classes as equal as possible. Kang–Nikiforov–Yuan conjectured that, for every $p\ge1$ and $n>(r-1)k$, the $r$-graph $Q_k^r(n)$ is the unique maximizer of $\lambda^{(p)}$ among all $k$-chromatic $r$-graphs of order $n$. They also conjectured the corresponding explicit bound \[ \lambda^{(p)}(G) \le r!\left(\tbinom nr-k\tbinom{n/k}{r}\right)n^{-r/p}, \] with equality only in the divisible extremal case. The case $r=3$ was established in their work. This paper resolves the remaining cases $r\ge4$, and hence settles both
conjectures for all $r\ge3$. As a consequence, the same threshold gives an anti-Wilf-type spectral certificate: any $r$-graph of order $n$ whose $p$-spectral radius exceeds the displayed bound has chromatic number at least $k+1$.
Read the full abstract ▾
Numerical Analysis
Iterative Methods for Computing the T-Square Root of Third-Order Tensors
Hemant Sharma and Nachiketa Mishra
We develop and analyze iterative methods for computing the principal square root of third-order tensors under the T-product framework. Tensor extensions of the Newton iteration (quadratic convergence) and the Denman–Beavers iteration (
geometric convergence with simultaneous computation of the inverse square root) are proposed, with rigorous convergence guarantees established via the
Fourier-domain block-diagonalization of the T-product. We apply these methods to image processing, introducing Tensor Decorrelated Grayscale conversion, T-Whitening, and optimal color transfer under the T-product geometry. We also formulate the Tensor Bures–Wasserstein distance and prove it defines a valid metric on the space of T-positive definite tensors. Numerical experiments confirm rapid convergence and demonstrate that the proposed tensor-based techniques offer improved structural preservation and cross-channel decorrelation compared to classical methods.
Read the full abstract ▾
Optimization and Control · Cross-listed from cs.SI
Computing Absorbing-Frequency Centrality: Complexity, Estimators, and Scalable Algorithms for Stochastic Networks
Wencheng Bao, Eleftheria Kontou and Chrysafis Vogiatzis
In a
stochastic network, where edges fail and weights may vary across realizations, the node of highest betweenness is itself random. Absorbing-frequency centrality (AFC) scores each node by how often it is reported as the node of highest betweenness: the reported betweenness maximizer traces an absorbing Markov chain, and AFC is the normalized expected pre-absorption occupancy. Computing it exactly is intractable: we prove that evaluating even a single transition probability of the AFC chain is #P-hard, by a reduction from two-terminal network reliability, and that the expected absorption time and AFC scores inherit this hardness. We develop a
matrix estimator that builds the kernel row-wise and solves one linear system, and a parallelizable episode
estimator over absorption trajectories that is strongly consistent and asymptotically normal, with finite-sample guarantees tied to the empirical error decay. A computational study reports scalability on Erdős-Rényi, Watts-Strogatz, and Barabási-Albert graphs, and a monitor placement experiment in which AFC's advantage over pooled counting generally grows with reliability heterogeneity.
Read the full abstract ▾