Optimization and Control
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Monday 13 April
The centralized circumcentered-reflection method (\cCRM) of Behling, Bello-Cruz, Iusem, and Santos~\cite{Behling:2024} is known to converge superlinearly for the feasibility problem $\operatorname{find}\;z\in X\cap Y$ under a $\mathcal{C}^1$ smoothness assumption on the boundaries of $X$ and $Y$. We sharpen this to a quantitative rate: when the boundaries are $\mathcal{C}^2$ near the limit point $\bar z$, \cCRM\ converges Q-quadratically, with an asymptotic constant \( 2\max(\kappa_X,\kappa_Y)/\omega \) governed by the boundary curvatures $\kappa_X,\kappa_Y$ at $\bar z$ and the local error-bound modulus $\omega$. The estimate matches Newton-type second-order behavior even though \cCRM\ uses only projections and circumcenters, and numerical experiments on equality-constrained and spectral feasibility problems exhibit the predicted quadratic rate, with \cCRM\ reaching machine precision in a handful of steps where alternating projections and Douglas–Rachford take many. The argument is local and does not require $X\cap Y$ to have nonempty interior in $\re^n$: it suffices that the sets share an affine hull $L=\aff(X)=\aff(Y)$ and meet with nonempty relative interior, which is the natural setting for equality-constrained and spectral feasibility problems, where the classical full-dimensional hypothesis necessarily fails. A $\mathcal{C}^1$ version of the argument recovers and extends the superlinear rate of~\cite{Behling:2024} to this lower-dimensional regime. The case $\aff(X)\neq\aff(Y)$ is identified as open.
Analysis of PDEs
$p$-variational capacity of interior condensers and geometric reduction by a fixed phase
We study the $p$-variational capacity of interior condensers in a bounded open set $\Omega\subset\mathbb R^n$ when both plates are determined by a single phase $\theta:\Omega\to\mathbb R$ in $W^{1,\infty}(\Omega)$ through sublevel and superlevel sets. By restricting the admissible class to potentials of the form $u=v\circ\theta$ and applying the coarea formula, the problem reduces to a one-dimensional variational functional in the level variable, governed by an energy weight that combines the gradient profile of $\theta$ and the geometry of its level sets. We obtain an explicit formula for the reduced problem, construct an explicit optimal profile, and deduce an upper bound for the full geometric capacity by fibered restriction. In addition, we derive estimates for the energy weight in terms of the gradient and the size of the fibers, and analyze the local effect of critical levels on the integrability of the reduced resistance. Finally, we present symmetric models in which the fibered reduction coincides with the full geometric capacity and, in the linear case, a quantitative tangential obstruction to that exactness.
Read the full abstract
Differential Geometry
On length-preserving and area-preserving inverse curvature flows in the hyperbolic plane
In this paper, we study the area-preserving and length-preserving $\kappa^\alpha$-type curvature flows of smooth, closed, convex curves in the two-dimensional hyperbolic plane $\mathbb H^2$ for $\alpha<0$ and prove that convexity is preserved along the flows. Assuming that the flows exist for all time, we show that the evolving curves converge smoothly to geodesic circles. Furthermore, we also derive a sufficient condition for global existence of the flows.
Read the full abstract
Numerical Analysis
Data-efficient extraction of optical properties from 3D Monte Carlo TPSFs using Bi-LSTM transfer learning
Time-Resolved Spectroscopy (TRS) is a powerful modality for non-invasive characterization of turbid media. However, extracting optical properties, absorption $\mu_a$ and reduced scattering $\mu_s'$, from 3D stochastic measurements remains computationally expensive for real-time applications. In this paper, we propose a data-efficient, physics-informed transfer learning strategy using a Bidirectional Long Short-Term Memory (Bi-LSTM) network. By leveraging a fast deterministic solver to establish a physical prior before fine-tuning on a restricted set of 3D Monte Carlo simulations, our model successfully bridges the analytical-to-stochastic domain gap. The proposed method eliminates the systematic bias of analytical models while maintaining a competitive error with near-instantaneous inference time.
Read the full abstract
Analysis of PDEs
Fourier-based potential theory without an explicit Green's function
Integral equation methods provide an effective framework for solving partial differential equations, but their applicability typically relies on the availability of explicit free-space Green's functions. For coupled systems arising in multiphysics applications, such Green's functions are generally not available, limiting the scope of classical potential theory-based approaches. In this work, we introduce a formulation of potential theory that avoids explicit use of Green's functions entirely, relying instead on the Fourier symbol of the governing operator. The central idea is a parabolic regularization of the symbol, which yields a decomposition of the solution into a smooth, nonlocal component and a spatially localized residual. For the localized component, we derive explicit asymptotic expansions for volume, single layer, and double layer potentials in powers of a length scale parameter $\varepsilon$. The coefficients are expressed in terms of local geometric quantities and derivatives of the source data. The derivation is carried out entirely in the Fourier domain and applies to the Poisson equation in two and three dimensions, as well as to a class of coupled strongly elliptic systems.
Read the full abstract
Probability
Maxima of stationary systems of randomly time-changed Lévy particles
In this work, we consider maxima of systems of randomly time-changed Lévy particles. We give a general construction to obtain infinite-dimensional classes $\{Z^{\alpha}\}$ of stationary max-infinitely divisible (max-id) processes. These classes are indexed by admissible mass functions $\alpha$, which induce state-dependent time changes of the underlying Lévy particles. This gives a generalization of the well-known (Lévy–)Brown–Resnick process $Z^{1}$. In contrast to $\alpha\equiv 1$, the variability of non-constant mass functions $\alpha$ changes the dependence structure of the max-id process and goes beyond the max-stable setting while preserving stationarity. We then explore the extent of the so-called max-domain of attraction (MDA) of a given (Lévy–)Brown–Resnick process $Z^1$, by studying convergence of rescaled maxima of independent copies of $Z^{\alpha}$ to $Z^1$. Thus, our work combines potential theory for Markov processes and extreme value theory to yield a novel, infinite-dimensional, and interpretable class $\{Z^{\alpha}\}$ of stationary processes in the MDA of a given (Lévy–)Brown–Resnick process $Z^{1}$. So far, results on the extent of such domains have been scarce in the literature.
Read the full abstract
Combinatorics
Spectral Turán problem for $t\mathcal{K}_{4}^{-}$-free unbalanced signed graphs
Let $tK_4$ denote the family of all graphs consisting of $t$ copies of $K_4$ that are allowed to share vertices and $t\mathcal{K}_{4}^{-}$ be the set of all unbalanced signed graphs whose underlying graphs are elements of $tK_4$. In this paper, we characterize the extremal graphs that achieve the maximum index and spectral radius among all $t\mathcal{K}_{4}^{-}$-free unbalanced signed graphs with given order.
Read the full abstract
Classical Analysis and ODEs
A generalization of Reifenberg's theorem in R^N for flat cones
In this paper we prove that if a closed set in R^N is close to a cone over a simplicial complex at each point and at each scale, then it is locally bi-Hölder equivalent to such a cone. This generalizes Reifenberg's Topological Disk Theorem in 1960 and G. David, T. De Pauw and T. Toro's result in 2008.
Read the full abstract
Probability
Stability of invariant measures of the stochastic Landau-Lifshitz-Bloch equation with vanishing noise
In this paper, we investigate the limiting dynamics of invariant measures of the stochastic Landau-Lifshitz-Bloch equation driven by the Stratonovich noise defined on the entire space $\R^2$. We first prove the set of all invariant measures of the stochastic equation for small noise is tight in $H^1(\R^2)$, and then prove every limit of a sequence of invariant measures of the stochastic equation must be an invariant measure of the limiting system as the noise intensity approaches zero. The main difficulty of the paper is to establish the tightness of solutions which is caused by the low regularity of solutions and the non-compactness of Sobolev embeddings on unbounded domains. To solve the problem, we first consider a family of higher-order perturbed viscous systems and then use the regularity as well as the uniform tail-ends estimates of the perturbed solutions to establish the tightness of solutions of the original equation by a limiting process.
Read the full abstract
Algebraic Geometry · Cross-listed from hep-th
GlobalCY I: A JAX Framework for Globally Defined and Symmetry-Aware Neural Kähler Potentials
We present GlobalCY, a JAX-based framework for globally defined and symmetry-aware neural Kähler-potential models on projective hypersurface Calabi–Yau geometries. The central problem is that local-input neural Kähler-potential models can train successfully while still failing the geometry-sensitive diagnostics that matter in hard quartic regimes, especially near singular and near-singular members of the Cefalú family. To study this, we compare three model families – a local-input baseline, a globally defined invariant model, and a symmetry-aware global model – on the hard Cefalú cases $\lambda=0.75$ and $\lambda=1.0$ using a fixed multi-seed protocol and a geometry-aware diagnostic suite. In this benchmark, the globally defined invariant model is the strongest overall family, outperforming the local baseline on the two clearest geometric comparison metrics, negative-eigenvalue frequency and projective-invariance drift, in both cases. The gains are strongest at $\lambda=0.75$, while $\lambda=1.0$ remains more difficult. The current symmetry-aware model improves projective-invariance drift relative to the local baseline, but does not yet surpass the plain global invariant model. These results show that global invariant structure is a meaningful architectural constraint for learned Kähler-potential modeling in hard quartic Calabi–Yau settings.
Read the full abstract
Statistics Theory · Cross-listed from econ.EM
Average Marginal Effects in One-Step Partially Linear Instrumental Regressions
We propose a novel procedure for estimating and conducting inference on average marginal effects in partially linear instrumental regressions using Reproducing Kernel Hilbert Space methods. Our procedure relies on a single regularization parameter. We obtain the consistency and asymptotic normality of our estimator. Since the variance of the limiting distribution has a complex analytical form, we propose a Bayesian bootstrap method to conduct inference and establish its validity. Our procedure is easy to implement and exhibits good finite-sample performance in simulations. Three empirical applications illustrate its implementation on real data, showing that it yields economically meaningful results.
Read the full abstract
Dynamical Systems
Frequency of patterns in smooth sequences over the alphabet \{1, 3\}
We provide an ergodic theory framework to study statistical properties of smooth sequences over the odd alphabet {1, 3}. The arithmetic nature of this alphabet yields a partition of the subshift of smooth sequences based on their local structure, defining a notion of type for those sequences. We describe the substitutive structure of the smaller subshifts obtained by fixing the sequence of types of the successive derivatives of smooth sequences, from which we obtain the unique ergodicity of all these subshifts. A direct consequence is that the asymptotic frequency of any finite pattern in a smooth sequence over {1, 3} is always well-defined and depends on its type sequence. Finally, we characterize the minimality of these subshifts, and propose some perspectives.
Read the full abstract
Probability
Quantitative Large Population Limit for Non Exchangeable Diffusions in Fisher Information
This paper builds upon the methods developed in [22] and [15] to investigate the large population behavior of non exchangeable systems of N diffusive particles when the interaction matrix converges (in some sense) to a graphon. We first prove that the particle system is well approximated in Fisher information by the so-called independent projection system by proving quantitative bounds on the relative Fisher information between the marginal laws of both systems. We then use a convenient equivalence between the independent projection system and a graphon mean field system to investigate its large population behavior by proving quantitative stability estimates for graphon mean field systems in both relative entropy and Fisher information.
Read the full abstract
Optimization and Control
Law-invariant BSDEs and dynamic risk measures: new characterizations
We provide a new characterization of law-invariant backward stochastic differential equations (i.e. BSDEs) with quadratic growth. This answers the open question raised in Xu–Xu–Zhou (2022) on necessary conditions for law-invariance of g-expectations, and extends the analysis to general (possibly non-deterministic) generators. We also introduce and compare several dynamic notions of law-invariance in continuous time, establishing precise relationships among them. As an application, we study dynamic risk measures. For cash-additive, normalized risk measures, we recover and extend to continuous time the Kupper–Schachermayer (2009) characterization obtained in discrete time, showing that law-invariance and strong time-consistency force an entropic structure. We further obtain a new characterization of cash non-additive law-invariant risk measures generated by BSDEs via a time-dependent certainty equivalent representation.
Read the full abstract
Numerical Analysis
DiLO: Decoupling Generative Priors and Neural Operators via Diffusion Latent Optimization for Inverse Problems
Diffusion models have emerged as powerful generative priors for solving PDE-constrained inverse problems. Compared with end-to-end approaches that learn inverse mappings from large paired observation–parameter datasets, decoupling the parameter prior from the forward physical model reduces reliance on paired data and improves flexibility. Fast neural operators can accelerate inference in such decoupled frameworks, but standard diffusion guidance evaluates them on partially denoised, non-physical intermediate states, introducing out-of-distribution (OOD) inputs. We therefore formulate the Manifold Consistency Requirement, under which the physical surrogate is evaluated only on fully denoised parameters. Based on this principle, we present Diffusion Latent Optimization (DiLO), which reformulates inference as deterministic optimization of the initial latent state and backpropagates measurement gradients through the full denoising trajectory. This avoids surrogate evaluations on partially denoised intermediate states while enabling accurate reconstruction. We establish asymptotic stationarity under bounded surrogate-gradient error. Experiments on Electrical Impedance Tomography, Inverse Scattering, and Inverse Navier-Stokes demonstrate DiLO's accuracy and robustness to noise. DiLO's code is available at \url{https://github.com/haibo-research/DiLO}.
Read the full abstract
Analysis of PDEs
The Plasma-Charge Model: Boundary Effects and Global Well-posedness
This article focuses on the Vlasov-Poisson system with point charges in bounded convex domains, accounting the interactions of point charges with the self-consistent electric field and the boundary, which were not addressed in the previous work \cite{Wu24}. We provide a rigorous characterization of the charge-boundary effect and establish the global well-posedness of the associated initial-boundary value problems under various boundary conditions. The analysis rests upon delicate estimates of the Green and Robin functions in convex domains, the Pfaffelmoser and Lions-Perthame methods for global well-posedness, and a desingularization argument that justifies the point-charge dynamics.
Read the full abstract
Combinatorics
The Turán number of the Cartesian product of a star and an edge
Let $C_k$ denote the cycle of length $k$, $S_t$ be a star with $t$ edges. And let $B_t$ be the graph consisting of $t$ copies of $C_4$ sharing one fixed edge. Equivalently, $B_t=K_2 \mathbin{\square} S_t$, which is the Cartesian product of a star with $t$ edges and an edge. Recently, Gao, Janzer, Liu and Xu [Israel J. Math. 269(2025)] proved that the Turán number of $K_2\mathbin{\square} C_{2l}$ is $\Theta(n^{\frac{3}{2}})$ for every $l\ge 4$. In this paper, we obtain upper and lower estimates for the Turán number of $B_t$ in both the general and bipartite settings for every $t\geq 2$. For the lower bound, we use random construction based on the extremal structure of $C_4$. These results imply that $\frac{1}{2\sqrt{2}}\leq \lim_{t\to \infty} \frac{\mathrm{ex}(n,B_t)}{\sqrt{t}}\leq \frac{1}{2}$, and $\frac{1}{4}\leq \lim_{t\to \infty} \frac{\mathrm{ex}_{bip}(n,B_t)}{\sqrt{t}}\leq \frac{1}{2\sqrt{2}}.$ In the case of $B_2$, we obtain sharper estimates. We show that the Turán number of $B_2$ is approximately between $(0.518+o(1))n^{\frac{3}{2}}$ and $(0.603+o(1))n^{\frac{3}{2}}$. And in the bipartite setting, it is approximately between $(0.385+o(1))n^{\frac{3}{2}}$ and $(0.468+o(1))n^{\frac{3}{2}}$. Moreover, in the bipartite setting, we give a more general result, which shows that for every tree $T$ with $t$ edges, the bipartite Turán number of $K_2\mathbin{\square}T$ is at most $\frac{\sqrt{t}}{2\sqrt{2}}(1+o(1))n^{\frac{3}{2}}$.
Read the full abstract
Statistics Theory
Subordinated Wright-Fisher Priors
A new class of time-dependent Dirichlet priors is introduced as a generalisation of the Wright-Fisher diffusion, allowing discontinuities in the trajectories, as well as non-Markovian memory. This class is obtained as a simple stochastic time-change (subordination), interpreted as a hyper-prior assigned to the operational time-clock of a Wright-Fisher diffusion. Explicit representations and exact sampling algorithms are obtained for prior and posterior distributions of the process and of its clock, given partially exchangeable data sampled at discrete time-points. Computability and conjugacy rely on a novel class of discrete dual processes, generalising existing results on duality and computable filters.
Read the full abstract
Combinatorics · Cross-listed from cs.CR
How to reconstruct (anonymously) a secret cellular automaton
We consider threshold secret sharing schemes based on cellular automata (CA) that allows for anonymous reconstruction, meaning that the secret can be recovered only as a function of the shares, without knowing the participants' identities. To this end, we revisit the basic characterization of $(2,n)$ threshold schemes based on CA in terms of Mutually Orthogonal Latin Squares (MOLS), and redefine the secret space as the MOLS family itself, showing that the new resulting scheme enables anonymous reconstruction of secret CA rules. Finally, we discuss the trade-off between the number of secret CA that can be shared and the computational complexity of the recovery phase.
Read the full abstract
Numerical Analysis
Numerical analysis for the Stokes problem with non-homogeneous Dirichlet boundary condition
The Stokes problem with non-homogeneous Dirichlet boundary condition is solved numerically using conforming discretizations and an approximation of the boundary datum in the corresponding trace space. Optimal discretization error estimates in various norms are derived. In the case of a homogeneous differential equation, all estimates of the velocity error are uniformly valid in the viscosity parameter for all conforming inf-sup stable discretizations. The theory accounts for the influence of corner singularities in the case of a non-convex domain. Several variants of the boundary data approximation are discussed. Moreover, the case of boundary data with very low regularity is studied, where a weak solution does not exist. The well-posedness of the very weak solution is investigated, and optimal discretization error estimates are derived. Numerical tests confirm the theory. The compatibility condition for the boundary data is not necessary for well-posedness of the weak and very weak formulations but it ensures that the solution satisfies the continuity equation in the distributional sense. In the same spirit, the compatibility condition is not necessary for the approximating boundary data; a good approximation of the original boundary data is important.
Read the full abstract
Analysis of PDEs · Cross-listed from eess.SY
Leader-Follower Density Control of Multi-Agent Systems with Interacting Followers: Feasibility and Convergence Analysis
We address density control problems for large-scale multi-agent systems in leader-follower settings, where a group of controllable leaders must steer a population of followers toward a desired spatial distribution. Unlike prior work, we explicitly account for follower-follower interactions, capturing realistic behaviors such as flocking and collision avoidance. Within a macroscopic framework based on partial differential equations governing the density dynamics, we derive (i) necessary and sufficient feasibility conditions linking the target distribution to interaction strength, diffusion, and leader mass, and (ii) a feedback control law guaranteeing local stability with an explicit estimate of the basin of attraction. Our analysis reveals sharp feasibility thresholds, phase transitions beyond which no control effort can achieve the desired configuration. Numerical simulations in one- and two-dimensional domains validate the theoretical results at the macroscopic level, and agent-based simulations on finite populations confirm the practical deployability of the proposed framework.
Read the full abstract
Information Theory
Generalized Roth–Lempel Codes: NMDS Characterization, Hermitian Self-Orthogonality, and Quantum Constructions
In their seminal 1989 work (IEEE Trans. Inf. Theory 35(3):655-657), Roth and Lempel constructed a well-known family of non-Reed-Solomon maximum distance separable (MDS) codes. For decades, this family of codes has attracted extensive research attention due to its algebraic structure, low-complexity decoding, and broad applications in cryptography and data storage. Most recently, in 2025, the generalized Roth-Lempel (GRL) framework unifies Roth-Lempel codes and its extensions under a flexible algebraic structure. However, explicit criteria for the near-MDS (NMDS) property of GRL codes have not been established, and no systematic construction of Hermitian self-orthogonal GRL codes has been reported, limiting their deployment in classical and quantum error correction. In this work, we make three contributions to address these gaps. First, we give explicit necessary and sufficient conditions for the NMDS property of the two most widely used subclasses of GRL codes. Second, we construct four new families of Hermitian self-orthogonal codes from GRL codes. Two of these families are NMDS, with parameters not covered by existing Hermitian self-orthogonal NMDS codes. Third, based on the proposed Hermitian self-orthogonal GRL codes, we construct four families of quantum GRL codes, including two infinite families of quantum NMDS codes that attain the quantum Singleton bound minus one. Compared to the known quantum error-correcting codes, we obtain many new or improved quantum error-correcting codes. This work bridges the gap between classical GRL code families and quantum error-correction applications.
Read the full abstract
Category Theory
Directed paths and Moore flows
This addendum extends prior work to the non-regular setting by introducing the tame realization of a precubical set as a multipointed $d$-space. Its execution paths are precisely the nonconstant tame $d$-paths in the geometric realization of the precubical set. The associated Moore flow induces a functor from precubical sets to Moore flows, which is naturally weakly equivalent, within the $h$-model structure, to a colimit-preserving functor whose image is included in the class of m-cofibrant Moore flows. For spatial (and thus proper) precubical sets, these functors coincide.
Read the full abstract
Optimization and Control
Incentive Design without Hypergradients: A Social-Gradient Method
In incentive design problems, a system planner seeks to steer self-interested agents toward a socially optimal Nash equilibrium by issuing incentives in the presence of information asymmetry, that is, uncertainty about the agents' cost functions. A common approach formulates the problem as a Mathematical Program with Equilibrium Constraints and optimizes incentives using hypergradients-the total derivatives of the planner's objective with respect to incentives. However, computing the hypergradient typically requires full or partial knowledge of equilibrium sensitivities to incentives, which is generally unavailable under information asymmetry. In this paper, we propose a hypergradient-free incentive law, called the social-gradient flow, for incentive design when the social cost depends on the agents' joint action. We prove that the social cost gradient is a descent direction for the planner's objective, irrespective of the agent cost landscape. In the idealized setting where equilibrium responses are observable, the social-gradient flow converges to the unique socially optimal incentive. When equilibria are not directly observable, the social-gradient flow emerges as the slow-timescale limit of a two-timescale interaction, in which agents' strategies evolve on a faster timescale. We establish that the joint strategy-incentive dynamics converge to the social optimum for any agent learning rule that asymptotically tracks the equilibrium. Finally, we validate theoretical results via numerical experiments.
Read the full abstract
Statistics Theory
Trends in tail dependence of heteroscedastic extremes
We consider multivariate extreme value statistics for independent but nonidentically distributed random vectors. In particular, the data may have varying tail copulas and also heteroscedastic marginal distributions. Assuming smoothly changing tail copulas, we propose a nonparametric estimator for the integrated tail copula and establish its asymptotic behavior. Notably, the heteroscedastic marginals do not affect the limiting processes. We use the main result for the integrated tail copula to test for a constant tail copula across all observations. Finally, a simulation study shows the good finite-sample behavior of our limit theorems as well as high power of the test.
Read the full abstract
Number Theory
The solvability of the inverse volcano problem over non-prime finite fields
For a finite field $\mathbf{F}_{p^k}$ and a prime $\ell \neq p$, consider the graph $G$ of $\ell$-isogenies between ordinary elliptic curves over $\mathbf{F}_{p^k}$. Kohel proved that the connected components of $G$ have a remarkable structure, now called an $\ell$-volcano graph. Bambury, Campagna, and Pazuki investigated the inverse volcano problem: given a volcano graph $V$, can one find it as a connected component of $G$ over $\mathbf{F}_{p^k}$? They gave a complete positive answer over $\mathbf{F}_p$, and described a specific counterexample over $\mathbf{F}_{p^2}$. In this paper, we generalise the results of Bambury-Campagna-Pazuki by providing a precise framework for the inverse volcano problem over $\mathbf{F}_{p^k}$. The solvability of the problem for an $\ell$-volcano graph $V$ of depth $d$ is typically determined by the relation between $d$ and the $\ell$-valuation $r$ of $k$. When $r$ is small in comparison to $d$, we prove that there are infinitely many primes $p$ solving the inverse problem for $V$. The situation where $r$ is large in comparison to $d$ is more delicate: in many cases we prove that the inverse problem for $V$ is unsolvable; in a few other cases the problem appears to be solvable, but our proof of this is conditional on a variant of the Cohen-Lenstra heuristics for class groups of imaginary quadratic fields. We provide some computational evidence in support of these modified heuristics.
Read the full abstract
Quantum Algebra
Wheel Classes in Kontsevich Graph Complex and Merkulov's Low-Valence Conjecture
We show that the wheel classes in the Kontsevich graph complex $GC_d$ admit representatives supported on graphs with only $3$- and $4$-valent vertices. This verifies that Merkulov's low-valence conjecture holds for the wheel classes. More precisely, for every $m \ge 2$, we prove that the wheel graph $W_{2m+1}$ is homologous to an explicit linear combination of $2^{m-2}$ graphs, each having only $3$- and $4$-valent vertices.
Read the full abstract
Combinatorics · Cross-listed from cs.DS
Above-Guarantee Algorithm for Properly Colored Trees
In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a spanning tree in which any two adjacent edges have distinct colors. Since finding such a tree is NP-hard in general, previous work often relied on minimum color degree conditions to guarantee the existence of properly colored spanning trees. While it is known that every connected edge-colored graph $G$ contains a properly colored tree of order at least $\min\{|V(G)|, 2\delta^c(G)\}$, where $\delta^c(G)$ denotes the minimum number of colors incident to a vertex, we study the algorithmic above-guarantee problem for properly colored trees. We provide a polynomial-time algorithm that constructs a properly colored tree of order at least $\min\{|V(G)|, 2\delta^c(G)+1\}$ in a connected edge-colored graph $G$, whenever such a tree exists.
Read the full abstract
Algebraic Geometry
NCCRs of cones over del Pezzo surfaces
Non-commutative crepant resolutions (NCCRs) are non-commutative versions of classical crepant resolutions in algebraic geometry. For 3-dimensional terminal Gorenstein singularities Iyama and Wemyss proved that all NCCRs are connected by mutations, which may be viewed as a non-commutative analogue of Kawamata's result that all crepant resolutions are connected by flops. In this paper we prove the corresponding result for a class of canonical Gorenstein singularities which are not terminal, namely anticanonical cones over del Pezzo surfaces. More precisely, we first obtain a classification of NCCRs of anticanonical del Pezzo cones, showing that every NCCR arises from a geometric helix on the corresponding del Pezzo surface. We then prove that all such geometric helices are connected to each other by mutations, up to simple operations which include tensoring by line bundles and shifts. A crucial ingredient in our proofs is the polygons that can be associated to exceptional collections on del Pezzo surfaces following the works of Hille and Perling. We obtain some interesting observations about these polygons which may be of independent interest.
Read the full abstract
Combinatorics
Coarse Balanced Separators in Fat-Minor-Free Graphs
Fat minors are a coarse analogue of graph minors where the subgraphs modeling vertices and edges of the embedded graph are required to be distant from each other, instead of just being disjoint. In this paper, we give a coarse analogue of the classic theorem that an $n$-vertex graph excluding a fixed minor admits a balanced separator of size $O(\sqrt{n})$. Specifically, we prove that for every integer $d$, real $\varepsilon>0$, and graph $H$, there exist constants $c$ and $r$ such that every $n$-vertex graph $G$ excluding $H$ as a $d$-fat minor admits a set $S \subseteq V(G)$ that is a balanced separator of $G$ and can be covered by $c n^{\frac{1}{2}+\varepsilon}$ balls of radius $r$ in $G$. Our proof also works in the weighted setting where the balance of the separator is measured with respect to any weight function on the vertices, and is effective: we obtain a randomized polynomial-time algorithm to compute either such a balanced separator, or a $d$-fat model of $H$ in $G$.