Geometric Topology
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Sunday 30 August
We define a 'full' version of Khovanov-Rozansky homology: a chain complex CH(K) over F[U,V] whose chain homotopy type is a knot invariant and which has the property that setting U = V = 0 recovers the reduced Khovanov-Rozansky homology. We explore the algebraic structure of CH(K) and show that a variation of the structure theorem for knot Floer homology applies. This allows us to define counterparts to knot Floer concordance invariants $\tau$, $\epsilon$ and $\phi_j$ in the Khovanov-Rozansky setting.
Numerical Analysis
A variant of the block preconditioner for indefinite complex symmetric linear systems
In this paper, we propose an efficient preconditioner for solving indefinite complex symmetric linear systems within a block preconditioning framework. We analyze the convergence of the corresponding iterative method and investigate several spectral properties of the preconditioned matrix, including eigenvalue distributions and eigenvector structures. The new preconditioner is used to accelerate the convergence of the flexible version of GMRES. Numerical experiments are presented to illustrate the effectiveness of the proposed preconditioner, and comparisons with existing block preconditioners demonstrate its superior performance.
Read the full abstract
Analysis of PDEs
On Cauchy Problems for Parabolic Equations with Rough Coefficients
The presented work investigates the Cauchy problems for parabolic equations in both non-divergence and divergence forms with rough diffusion coefficients, which commonly arise in composite media, financial pricing, and viscous fluids. Under critical regularity settings, we establish the unique solvability in optimal fractional Sobolev spaces. The first key technical step lies in constructing an effective approximation scheme with truncated and mollified diffusion coefficients $a^\epsilon(t,x)$, for which we rigorously prove the uniform preservation of high-frequency smallness. By incorporating this approximation scheme with paraproduct decomposition, Fefferman-Stein maximal inequalities, Coifman-Meyer bilinear estimates, and refined Sobolev embeddings, we close the uniform a priori estimates and then pass to the limit. Furthermore, we prove that the threshold $s < \frac{1}{2}$ is sharp by constructing explicit counterexamples. These theoretical results provide a rigorous mathematical framework in the study of Cauchy problems for parabolic equations with rough coefficients.
Read the full abstract
Combinatorics
Equivariant Analytic Spectral Invariants of Aç{\i}kmeşe Lifts of Graphs with Self-Loops
We introduce and study equivariant analytic spectral invariants associated with the Aç{\i}kmeşe lift of a graph with self-loops $G_S$. The canonical $\mathbb{Z}_2$-action yields an orthogonal isotypic decomposition of the lifted Laplacian into the anti-symmetric part $\mathcal{L}(G_S)$ and the symmetric part $M_{sym}$, from which we prove that the spectrum of $\mathcal{L}(G_S)$ is exactly the even-indexed spectrum of the lifted Laplacian. We express twisted moments of these blocks as traces of the generalised twisted moment operator against the corresponding $\mathbb{Z}_2$-projections, and obtain a tight upper bound under certain restriction with a characterization of the equality case. We introduce the equivariant heat character and establish a trace-norm stability estimate. For the matrix element of the resolvent $(pI+\mathcal{L}(G_S))^{-1}$ associated with the loop vector, we derive a Laplace-transform identity for the equivariant heat character, a determinant formula, a spectral representation, and a Laurent expansion. We further characterize the case where $S$ is a union of connected components through resolvent and equivariant heat-character identities, and obtain explicit equivariant heat characters for joins of full-loop graphs and the line graph of a full-loop connected regular graph. Finally, we introduce the regularized equivariant heat integral and derive spectral and trace formulas for it.
Read the full abstract
Combinatorics
Recovering Laplacian Lattices from $L$-Functions of Graphs
We introduce $L$-functions associated with characters of the Jacobian of a finite graph, as a graph-theoretic analogue of the $L$-functions arising from unramified coverings of algebraic curves. These $L$-functions are defined using the Riemann–Roch structure on the graph and extend Lorenzini's two-variable zeta function. We show that if two connected graphs without bridges have isomorphic Jacobians and their $L$-functions agree under the induced correspondence of characters, then their Laplacian lattices coincide. We also show that these $L$-functions satisfy a functional equation. Finally, we give examples showing that neither the Jacobian nor the Lorenzini zeta function alone determines the Laplacian lattice.
Read the full abstract
Algebraic Geometry · Cross-listed from cs.CR
A New Algebraic Algorithm for LWE
The Learning With Errors (LWE) problem, introduced by Regev in 2005, is central to modern cryptography and post-quantum security. The algorithms to solve the search version of the problem, Search-LWE, can be broadly categorised into algebraic, combinatorial and lattice-based. In this work we propose a new algebraic algorithm for the Search-LWE problem. At a high level, the algorithm combines linear-algebraic techniques with S-polynomial-based methods from Groebner basis computation. We provide a direct complexity analysis of our algorithm, avoiding semi-regularity assumptions and complexity bounds derived from the degree of regularity. Our algorithm achieves a polynomial improvement in complexity over prior results that use Groebner basis methods to solve Search-LWE.
Read the full abstract
Functional Analysis
The Pego Theorem for the Hilbert–Schmidt Class
This paper establishes an operator-theoretic version of Pego's compactness theorem within the framework of quantum harmonic analysis on general locally compact abelian phase spaces. We show that a bounded set of Hilbert-Schmidt operators is precompact if and only if it is uniformly equicontinuous under phase-space shifts and its Fourier-Weyl transform is uniformly equicontinuous on the dual phase space. We provide applications to quantum physics.
Read the full abstract
Metric Geometry
Sylvester's four point problem for ball-convex bodies
We investigate Sylvester's classical four-point problem for ball-convex bodies, where convex hulls are replaced by intersections of balls of a fixed radius $R$. We show that the Efron–Buchta identities persist in this framework, so that the distribution of the number of vertices of the $R$-ball-convex hull of $n$ uniform random points is determined by the moments of the volumes of the hulls of its subsamples, and vice versa. For three and four uniform random points in an arbitrary planar ball-convex body, we determine the Sylvester probabilities of the $R$-ball-convex hull. We also give an extension of Groemer's inequality for the expected area of the ball-convex hull of $n$ random points and show that it is minimised by the disc of the same area. In particular, this yields an isoperimetric inequality for the ball-convex analogue of the affine length of the boundary curve. For the unit disc, we can express the Sylvester probabilities using dilogarithmic functions of the radius $R$, and give explicit values at $R=1$. As $R\to\infty$, these recover the classical Sylvester probabilities. As another consequence, we determine the exact distribution function of the circumradius of three uniform random points in he disc on $[1,\infty)$.
Read the full abstract
Probability
Cramér transform, half-space depth and threshold phenomena for convex bodies
We study the relationship between the Cramér transform and Tukey's half-space depth for log-concave probability measures. For the uniform probability measure $\mu_K$ on a convex body $K\subseteq\mathbb{R}^n$, we prove the sharp pointwise comparison $$\Lambda_K^*(x)\leq -\log q_K(x)\leq \Lambda_K^*(x)+\frac12\log n+C,\qquad x\in\operatorname{int}(K),$$ where $C$ is an absolute constant. The order $\log n$ is optimal, as shown by the Euclidean ball. The proof combines exponential tilting, one-dimensional log-concavity, and self-concordance of the Cramér transform. As consequences, we obtain sharp-order moment and tail estimates for $\Lambda_K^*$ and identify $\exp(\Lambda_K^*(x))$, up to polynomial factors in the dimension, with the number of independent samples needed for $x$ to be captured by their random convex hull. We also establish an $O(n^2)$ variance bound for the logarithmic half-space depth and use it to derive a general criterion for sharp thresholds of random convex hulls. In particular, this criterion applies to the uniform measures on $\ell_p$-balls for every $p>1$. These results establish a quantitative link between large-deviation cost, geometric depth, and sampling complexity in high-dimensional convex geometry.
Read the full abstract
Number Theory
$D(N)$-quadruples in upper-triangular $2\times2$ integer matrices
We introduce analogues of Diophantine $D(N)$-$m$-tuples in the noncommutative ring $M_2(\mathbb Z)$ of $2\times2$ integer matrices. Besides definitions based on the standard matrix product, we consider a symmetric version defined via the Jordan product $$A\circ B=\frac12(AB+BA).$$ Special attention is devoted to upper-triangular integer matrices $UT_2(\mathbb Z)$, where squares admit a particularly simple description. Motivated by the classical connection between representations of $n$ as a difference of two squares and the existence of $D(n)$-quadruples in commutative rings, we investigate the existence of Jordan $D(N)$-quadruples in $UT_2(\mathbb Z)$.
Read the full abstract
Mathematical Physics · Cross-listed from nlin.SI
Nijenhuis torsion and Frölicher-Nijenhuis brackets of recursion operators via their full-fledged forms
We present a novel approach to computing the Nijenhuis torsion and Frölicher-Nijenhuis brackets of recursion operators for symmetries, based on their full-fledged forms introduced by Jahnová and Vojčák (2024). In contrast to the conventional approach, which represents recursion operators as maps between shadows of nonlocal symmetries within a given covering, our method allows the Nijenhuis torsion to be computed directly from its defining formula, without requiring any additional mathematical constructions. The same framework can also be used to compute the Frölicher-Nijenhuis bracket of recursion operators and to verify their compatibility directly in their full-fledged forms. The procedure is illustrated by several examples of full-fledged recursion operators for symmetries of differential equations in four independent variables, including a new recursion operator for the four-dimensional universal hierarchy equation that, to the best of our knowledge, has not previously appeared in the literature. A notable feature of this new full-fledged recursion operator is that its shadow component does not appear to admit a reasonable representation in any of the standard conventional forms. Nevertheless, our approach allows us to prove directly that the Nijenhuis torsion of this operator vanishes. For the examples considered, the corresponding Frölicher-Nijenhuis brackets also vanish, confirming the compatibility of the respective pairs of recursion operators. This demonstrates that full-fledged forms provide an effective framework for studying the hereditary and compatibility properties of recursion operators, including highly nonlocal and/or multidimensional cases that are difficult to handle by existing methods.
Read the full abstract
Rings and Algebras
Congruence-simple multiplicatively idempotent semirings and multiplicative divisibility
We resolve two conjectures concerning multiplicatively idempotent semirings. First, we prove that every congruence-simple multiplicatively idempotent semiring is finite, and hence belongs to the finite classification of Kepka, Korbelář and Landsmann. Second, we prove that every finitely generated commutative multiplicatively divisible semiring is multiplicatively idempotent.
Read the full abstract
Representation Theory
Picture groups and green sequences from the perspective of Ringel–Hall algebras
Let $k$ be an algebraically closed field and let $\Lambda$ be a finite-dimensional associative $k$-algebra. We apply Joyce and Brideland's notion of Ringel–Hall algebra to prove results about picture spaces and picture groups. For instance, we construct a faithful group functor for $\Lambda$, i.e. a faithful functor from the $\tau$-cluster morphism category of $\Lambda$ into a groupoid. Consequently, by results of Hanson–Igusa, the picture space of $\Lambda$ is locally CAT(0) provided that the $\tau$-cluster morphism category of $\Lambda$ admits compatibility of last factors. We also show that green sequences are in bijection with certain positive expressions in the picture group, which generalizes a result of Igusa–Todorov beyond hereditary $k$-algebras.
Read the full abstract
Probability
Equilibrium fluctuations of the weakly asymmetric inclusion process
We prove that the stationary density fluctuation field of the one-dimensional weakly asymmetric simple inclusion process converges to the energy solution of the stochastic Burgers equation. The key technical ingredient is a second-order Boltzmann-Gibbs principle tailored to the microscopic current. As a consequence, we also obtain Ornstein-Uhlenbeck fluctuations for the symmetric inclusion process in a weakly condensing regime, a result of independent interest.
Read the full abstract
Mathematical Physics · Cross-listed from physics.flu-dyn
Solute dispersion in magnetically influenced multiphase flow through a porous tube: axial transport and microrotational effects
This study presents a theoretical investigation of generalized solute dispersion in magnetohydrodynamic multiphase tube flow with porous layers. A two-fluid analytical model is developed for applications in biofluid and environmental fluid dynamics. The model comprises a micropolar (non-Newtonian) fluid core representing the rotational behaviour of red blood cells and a Newtonian plasma periphery embedded with Brinkman and Darcy porous structures, corresponding to the glycocalyx and endothelial layers with distinct permeability characteristics. A transverse magnetic field is incorporated to investigate how magnetic-field-induced modifications of the carrier flow influence solute localisation, with potential relevance to magnetic nanoparticle-mediated drug delivery. Using the generalised dispersion framework of Sankarasubramanian & Gill, analytical solutions are derived to investigate how the coupled axial velocity field and associated microrotational dynamics influence solute transport. The analytical predictions are independently validated through Brownian dynamics simulations, demonstrating excellent agreement for the temporal evolution of the zeroth and first transport moments. The results reveal the previously unexplored influence of microrotational dynamics on solute concentration, convection coefficients and effective dispersion, providing new insights into the coupled roles of translational and rotational fluid motion in biofluid transport. This work bridges an important gap in the literature and establishes a generalized theoretical framework linking magnetic fields, micropolar fluids and porous arterial structures for biofluid transport, targeted drug delivery and clinical engineering applications.
Read the full abstract
Optimization and Control
Sharp Singularity-Degree Bounds for Equality-Generated SDP-RLT Relaxations of Binary Programs
Singularity degree is an important measure of semidefinite programming (SDP) degeneracy, but it is generally unavailable a priori from the problem data. We augment the Shor relaxation of nonempty binary sets $\{x\in\{0,1\}^n:Ax=b\}$ with the first-level Reformulation-Linearization Technique (RLT) equations generated by the defining linear equalities. For the resulting equality-generated SDP-RLT relaxation, we determine the exact worst-case singularity degree. If $\operatorname{rank}(A)=m$ and $0<m<n$, then the associated relaxation has singularity degree at most $\min\{m,n-m\}$, and this rank-nullity bound is attained for every possible rank in this range. Consequently, the worst-case singularity degree over this class is $\lfloor n/2\rfloor$ for $n\geq 2$. This is strikingly smaller than the sharp general bound $n$ for feasible SDP systems with matrix variables of order $n+1$ (Sturm, 2000, Example 2). Thus, for individual relaxations, rank and nullity provide an a priori bound on the otherwise inaccessible singularity degree and on the Hölder exponent in error bounds estimating distance to feasibility from constraint residuals.
Read the full abstract
Analysis of PDEs
Failure of a Brunn-Minkowski-type inequality for the Gaussian torsional rigidity
Let $u$ be the torsion function for the Ornstein-Uhlenbeck operator on a bounded domain $\Omega \subset \mathbb{R}^n$, i.e., the solution of $\Delta u - x \cdot \nabla u = -1$ in $\Omega$ with $u = 0$ on $\partial\Omega$. Let $T_\gamma(\Omega) = \int_\Omega u \, d\gamma$ be the Gaussian torsional rigidity. We prove that the Brunn-Minkowski-type inequality $T_\gamma((1-t)\Omega_0 + t\Omega_1)^{\alpha} \le (1-t) T_\gamma(\Omega_0)^{\alpha} + t T_\gamma(\Omega_1)^{\alpha}$ fails for every exponent $\alpha > 0$ and in every dimension $n \ge 2$, for a pair of convex bodies centrally symmetric with respect to the origin, which may be taken smooth with positive curvature. This answers Conjecture 1.4 for any $n \geq 2$, and Question~(Q), of Marín Sola and Salerno in the negative. The mechanism is a first-order lower bound for $T_\gamma$ at a ball $\Omega_0$ under Minkowski perturbations. When the perturbing body $\Omega_1$ has small torsion and large mean width, $T_\gamma((1-t)\Omega_0 + t\Omega_1)$ increases to first order. Since the Minkowski combination has larger torsion than both endpoints, no exponent can repair the inequality. For $n=1$, convexity with the optimal exponent $1/3$ holds on symmetric intervals by results of the same authors, \cite{MSS26}. We prove that the logarithm of the torsion is neither convex nor concave along Minkowski combinations of symmetric intervals, that no non-zero exponent yields concavity, and that convexity fails for every positive exponent when one set is a union of two intervals or when the sets are reflected off-center intervals.
Read the full abstract
Probability
Counterexamples to the site-percolation analogues of the Easo-Severo-Tassion cutset theorems
Easo, Severo and Tassion [EST25] proved two theorems about minimal edge cutsets in infinite graphs: that non-triviality of the uniform critical percolation parameter is equivalent to exponential growth of the number of minimal edge cutsets of size n separating a vertex from infinity, and that uniform transience is an alternative sufficient assumption. We show that the naive extensions of (the original contribution to) these theorems to site percolation and vertex cutsets are false; our counterexample involves modifying a rooted binary tree and replacing edges with gadgets that allow many choices for where to block (in constructing a cutset) one of two local routes, while keeping every vertex uniformly close to a supercritical, uniformly transient shortcut skeleton.
Read the full abstract
Number Theory
Average twin prime conjecture for elliptic curves in arithmetic progressions
In 1988, Koblitz conjectured an asymptotic formula for the number of primes $p \le x$ for which the reduction of an elliptic curve over $\mathbb{Q}$ has prime order. Building on the work of Balog, Cojocaru, and David, who proved this conjecture on average in 2011, we extend the result to primes $p$ lying in arithmetic progressions. Our asymptotic formula holds uniformly for moduli up to a fixed power of $\log x$. We also show that the resulting average constant matches the theoretical constant predicted by Lee, Mayle, and Wang in 2025 using Galois representations.
Read the full abstract
Mathematical Physics · Cross-listed from quant-ph
Exact Entanglement Swapping through Single-Occupancy Measurements in Gaussian Fermion States
We determine the exact entanglement structure of the conditional state obtained by measuring $m$ corresponding rungs ($m\leq N/2$) in two identical copies of an arbitrary half-filled free fermion Gaussian state and post-selecting the same normalized single-fermion state ($|\psi\rangle = u|10\rangle+v|01\rangle$, where 0 and 1 denote the fermion occupancy on each sites) on each rung. For $m<N/2$, the conditional wavefunction generally depends on the initial state. Nevertheless, whenever the selected outcome has nonzero probability, the state on the unmeasured sites remains Gaussian and factorizes exactly into $N-m$ different orthogonal modes including $m$ inter-copy entangling modes and $N-2m$ spectator modes localized in one copy. Consequently, the entanglement entropy between the unmeasured parts of the two copies is $S=m h_2(|v|^2)$, independent of the initial state, where $h_2(x)=-x\ln x-(1-x)\ln(1-x)$. The success probability is given by $P_m=\det C_L\det(I_m-C_L)=\det(C_{LR}C_{RL})$, determined solely by the initial correlations and independent of ($u$,$v$). Equal-weight Bell post-selection serves as a special case that achieves the maximal entanglement swapping.
Read the full abstract
Numerical Analysis
Advancements in Spectral Collocation Methods for High-Order Eigenvalue Problems
This paper focuses on computing spectral solutions for high-order eigenvalue problems using an efficient discretization method based on Chebfun spectral discretization algorithms and domain truncation. We solve several numerical eigenvalue problems, demonstrating both the accuracy and computational efficiency of the proposed approach.
Read the full abstract
Number Theory
Hecke Subalgebras and Local Newforms for the Metaplectic Double Cover of $\mathrm{SL}_2(\mathbb{Q}_p)$
Let $p$ be an odd prime, and let $\overline{\mathrm{SL}_2(\mathbb{Z}_p)}$ and $\overline{K_0(p^n)}$ denote the inverse images of $\mathrm{SL}_2(\mathbb{Z}_p)$ and the congruence subgroup $K_0(p^n)$ in the metaplectic double cover $\widetilde{\mathrm{SL}}_2(\mathbb{Q}_p)$. For $n\geq2$, we study the subalgebra of the genuine Hecke algebra $H(\widetilde{\mathrm{SL}}_2(\mathbb{Q}_p)//\overline{K_0(p^n)},\eta)$ consisting of functions supported in $\overline{\mathrm{SL}_2(\mathbb{Z}_p)}$, where $\eta$ is the genuine extension of either the trivial or the nontrivial quadratic character modulo $p$. We give an explicit basis and a presentation by generators and relations, and prove that this subalgebra is commutative of dimension $2n$. We give the multiplicity-free decomposition of $\operatorname{Ind}_{\overline{K_0(p^n)}}^{\overline{\mathrm{SL}_2(\mathbb{Z}_p)}}\eta$, determining the dimensions of its irreducible constituents and their associated Hecke eigenvalues. This Hecke subalgebra acts on the $(\overline{K_0(p^n)},\eta)$-fixed spaces in irreducible admissible genuine representations of $\widetilde{\mathrm{SL}}_2(\mathbb{Q}_p)$. We compute its action explicitly on newvectors of prescribed $\eta$-type in principal series, Steinberg, even Weil, and supercuspidal representations. For supercuspidal representations, we construct the vectors by compact induction and use Ishimoto's conductor and dimension formulas. Finally, we relate our operator $\mathcal{W}_{n-1}$ to Ishimoto's local realization of Ueda's twisting operator.
Read the full abstract
Analysis of PDEs
A partial data coefficient identification inverse problem for a semilinear damped wave operator
This manuscript deals with a coefficient identification inverse problem for a semilinear damped wave operator in a bounded domain of $\mathbb{R}^{1+d}\ (d\geq 2)$. We establish the unique recovery of the damping coefficient, zeroth-order linear term, and the coefficient of the power-type nonlinearity from the partial Dirichlet-to-Neumann map. We investigate the corresponding uniqueness problem under the assumption that the coefficients are known in a neighborhood of the boundary, while the Neumann boundary data are prescribed only on an arbitrarily small open subset of the boundary. The analysis is largely based on the unique continuation principle, Fourier Analysis and the higher-order linearization technique.
Read the full abstract
Differential Geometry
Torsion algebras of Hermitian manifolds and rigidity
We regard the Chern torsion of a Hermitian manifold as a skew-symmetric complex-bilinear product on its holomorphic tangent bundle. For a compact connected Chern–Kähler-like Hermitian manifold, we prove that this product satisfies the Jacobi identity pointwise. If, in addition, the Chern holomorphic sectional curvature is strongly quasi-positive, we show that the resulting torsion Lie algebra is nilpotent and must be abelian. Consequently, the metric is Kähler. The underlying complex manifold is therefore projective and rationally connected. For general Hermitian manifolds, we construct a metric with positive real bisectional curvature on a Hopf surface which is neither simply connected nor rationally connected.
Read the full abstract
Logic
Fixed points in abstract provability structures
We study fixed points in abstract provability structures (APSs), which were introduced by Beklemishev and Shamkanov as an order-theoretic framework for studying Gödel's second incompleteness theorem (G2). For one-variable APS terms built from the provability and refutability operations $\Box$ and $\boxtimes$, we investigate the existence and uniqueness of fixed points in terms of their degree. The degree of a term is the number of occurrences of $\boxtimes$. We prove that every term of degree two has a fixed point and establish a strict hierarchy among the fixed-point properties of the terms $\boxtimes\Box^k v$. We further show that suitable levels of this hierarchy guarantee the existence and uniqueness of fixed points for arbitrary one-variable APS terms of positive degree. We also obtain several G2-like non-refutability results, some of which depend only on whether the degree is even or odd. Finally, we consider APSs based on meet-semilattices. Under an additional condition, we obtain stronger fixed-point results and show that a parametrized fixed-point property implies an abstract form of Löb's theorem.
Read the full abstract
Analysis of PDEs
Proof of the planar Khavinson-Shapiro conjecture
Let $\Omega\subset\mathbb{R}^2$ be a bounded domain whose boundary is a finite union of pairwise disjoint Jordan curves. We prove the planar Khavinson–Shapiro conjecture in this setting: if every polynomial on $\mathbb{R}^2$ agrees on $\partial\Omega$ with a harmonic polynomial, then $\partial\Omega$ is an ellipse and $\Omega$ is its bounded interior.
Read the full abstract
Optimization and Control · Cross-listed from eess.SY
Finite Sample Identification of Analytic Nonlinear Systems
This paper studies the identification of linearly parameterized nonlinear (LPN) systems. Although LPN systems share the same linear parameterization structure as linear systems, they are more challenging to identify. In particular, previous work has shown, through a counterexample based on a piecewise-affine system, that non-active exploration is generally insufficient for LPN system identification. In this paper, we consider LPN systems with real-analytic feature functions. We show that non-active exploration is sufficient for the identification of this class of systems by establishing non-asymptotic convergence rates of least-squares estimation and set-membership estimation. In addition, we provide counterexamples to show that non-active exploration may not be sufficient for system identification for non-real-analytic systems, even if those systems are infinitely differentiable. We present numerical experiments to further support and validate our theoretical results.
Read the full abstract
Information Theory
The generalized covering radii of Melas codes
The generalized covering radii have recently emerged as fundamental parameters of linear codes with applications to database linear querying. In this paper, we study the generalized covering radii $\rho_t(M(m,q))$ of Melas codes $M(m,q)$ over any finite field $\mathbb{F}_q$. We determine $\rho_2(M(m,q))$ for all $q$, and for a general $t \ge 3$, we prove that $\rho_t(M(m,q)) \in \left\{2t,2t+1\right\}$ for $q \in \{2,3\}$ and $\rho_t(M(m,q))=2t$ for $q \ge 4$ whenever $m$ is sufficiently large. These results extend recent work on the covering radius of Melas codes.
Read the full abstract
Combinatorics · Cross-listed from cs.GT
Fair Division of Graphs: Beyond Traceability
In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally alters the problem, making it significantly more challenging than its classical counterpart. We focus on the fairness notion of $\mathrm{EF1}_{\mathrm{outer}}$, where envy can be eliminated by removing at most one vertex whose deletion does not disconnect the bundle – a critical constraint for applications such as land division and network allocation. Our first result extends prior work by establishing the existence of $\mathrm{EF1}_{\mathrm{outer}}$ allocations for an infinite family of non-traceable graphs (that is, graphs that do not admit a Hamiltonian path), answering a central open question and generalizing Bilò et al.'s result for traceable graphs. We then make progress on a conjecture concerning the $\mathrm{EF1}_{\mathrm{outer}}$ spectrum of trees due to Chen and Zwicker. Finally, we complement our structural results with algorithmic insights, showing that deciding the existence of an $\mathrm{EF1}_{\mathrm{outer}}$ allocation is NP-complete even for binary additive valuations, thereby resolving an open complexity question. Taken together, our results deepen the connection between graph theory and fair division, and offer new tools for studying fairness in structured resource environments.
Read the full abstract
Algebraic Geometry
Birational Automorphism Bounds for General-Type Foliations on Surfaces via Pluricanonical Indices
Let $\mathcal{F}$ be a canonical foliation of general type on a smooth projective surface $X$, and write $\mathrm{vol}(\mathcal{F}):=\mathrm{vol}(K_{\mathcal{F}})$. Let $G\subseteq\operatorname{Bir}(X,\mathcal{F})$ be a finite subgroup, and let $\mathcal{G}:=\mathcal{F}/G$ be the quotient foliation in the birational sense. For a canonical foliation $\mathcal{H}$, define its $r$-th pluricanonical index by \[ \delta_r(\mathcal{H}) := \min \bigl\{ m\in\mathbb{Z}_{>0} \mid h^0(mK_{\mathcal{H}})\geq r \bigr\}, \] where $\min\varnothing:=\infty$. For an arbitrary foliation, these indices are computed on any canonical birational model. If $\kappa(\mathcal{G})\geq0$, we prove \[ |G| \leq \begin{cases} 4\delta_1(\mathcal{G})\,\mathrm{vol}(\mathcal{F}), &\kappa(\mathcal{G})=0,\\[1mm] \displaystyle \frac{4}{3}\delta_2(\mathcal{G})\,\mathrm{vol}(\mathcal{F}), &\kappa(\mathcal{G})=1,\\[3mm] \delta_2(\mathcal{G})^2 \bigl(1+\delta_2(\mathcal{G})\bigr)\, \mathrm{vol}(\mathcal{F}), &\kappa(\mathcal{G})=2. \end{cases} \] Since $\operatorname{Bir}(X,\mathcal{F})$ is finite, one may in particular take $G=\operatorname{Bir}(X,\mathcal{F})$. When $\kappa(\mathcal{G})=0$ or $1$, the effective bounds $\delta_1(\mathcal{G})\leq12$ and $\delta_2(\mathcal{G})\leq42$ give \[ |G|\leq48\,\mathrm{vol}(\mathcal{F}) \qquad\text{and}\qquad |G|\leq56\,\mathrm{vol}(\mathcal{F}), \] respectively. The main new ingredient is a cluster formula for adjoint volumes, which yields index-dependent lower bounds for tangency-free foliated surface pairs whose underlying foliation has Kodaira dimension zero or one.