Group Theory
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Thursday 2 April
We introduce the concept of relational depth of a finite semigroup $S$ whose $J$-classes form a chain. It captures how far down in the ideal structure one is obliged to go in order to define the semigroup by generators and defining relations. We determine the exact value for the relational depth of an arbitrary ideal in the full transformation monoid, symmetric inverse monoid and in the partial transformation monoid.
Optimization and Control
Probabilistic Modeling versus Robust Optimization: A tutorial based on a humanitarian logistics use case
This tutorial contrasts probabilistic modeling and robust optimization to determine decisions in humanitarian logistics, specifically supply chains subject to adversarial (natural and human) disruptions. Natural disruptions induce dispatch of long-haul relief supply movement as storm forecasts evolve. A two-step workflow: (i) computes an initial pre-staging plan from the most likely forecast, and (ii) evaluates that fixed plan across plausible deviations in the eventual landfall location. In this way, dispatch decisions balance lead time and improved forecast information. For last-mile distribution, we propose deliveries when transportation networks must be protected against the worst case. We apply an iterative robust routing method that detects high-concentration links and increases their effective cost to promote route diversification. A case study based on Typhoon Noru (2022) shows how the combined approach identifies an optimal dispatch time and then protects last-mile delivery from difficult-to-predict network disruptions that could jeopardize the entire supply-chain operation.
Read the full abstract
Combinatorics
Piecewise linear functions and neural network expressivity via discriminantal arrangements
We extend the hyperplane arrangement framework for neural network expressivity from the braid to discriminantal arrangements. Compatible piecewise linear functions are characterized by circuit relations and admit a matroidal description via Mobius inversion, with dimension equal to the number of independent sets. For circuits of size three, functions are determined by values on subsets of size at most two.
Read the full abstract
Number Theory
On a Conjecture about Sums Involving Farey Fractions
In this paper, we prove a conjecture by Daniele Mundici on the sum of squared distances between consecutive elements in the $Q$-th Farey sequence for $Q\in\mathbb{Z}$ and $Q\geq 2$.
Number Theory
Higher Order Dualities over Global Function Fields and Weighted Möbius Sums over $\mathbb{F}_q{[T]}$
Alladi's duality identities (1977) provide a fundamental relation between the smallest and the $k$-th largest prime factors of integers. In this paper, we establish Alladi-type duality identities over global function fields, extending a result of Duan, Wang, and Yi. We also prove the asymptotic vanishing of a function field analogue of the weighted Möbius sum $\sum \mu(n)\omega(n)/n$, where $\omega(n)$ denotes the number of distinct prime divisors of $n$. By estimating $\Psi_2(n,m)$, the number of monics of degree $n$ whose second largest prime divisor degree is at most $m$, we further show that this vanishing persists when the sum is restricted to monics with a unique prime divisor of smallest degree belonging to a set of primes with natural density. As a corollary, we show that the unrestricted sum decomposes into infinitely many sub-series, each vanishing asymptotically.
Read the full abstract
Dynamical Systems
Effective Stability of Near-Rectilinear Halo Orbits in the Earth-Moon System
Near-rectilinear halo orbits (NRHOs) around Earth-Moon L2 in the Circular Restricted 3-Body Problem (CR3BP) exhibit a complex dynamical landscape, featuring a band of normally elliptic orbits embedded within regions of strong instability. This coexistence of stable and unstable dynamics, amplified by the numerical sensitivity associated with close lunar passages, makes the long-term behavior of trajectories near NRHOs a delicate and intrinsically nonlinear problem. Understanding the effective stability of these elliptic orbits is therefore a critical challenge, lying at the intersection of local normal form theory and global instability mechanisms. To quantify finite-time confinement, we formulate a rigorous framework for effective stability using discrete Poincaré maps. By employing jet transport to compute high-order Taylor expansions, we construct explicit polynomial normal forms. We derive discrete Nekhoroshev-type estimates by identifying the normalization order, which balances the asymptotic convergence of the map's analyticity domain against the cumulative penalty of low-order small divisors. Applying this framework to the Earth-Moon system, we map the resulting geometric limits directly into physical spatial coordinates. Crucially, we demonstrate that for practical mission lifetimes (e.g., 10-50 years), the required stability is vastly shorter than the characteristic Nekhoroshev accumulation time. Consequently, the effective stability region is not constrained by the time-dependent exponential drift, but is instead governed entirely by the maximum analytical domain of the optimized normal form. These derived spatial envelopes establish explicit geometric boundaries for the intrinsic local stability of elliptic NRHOs, providing a rigorous mathematical characterization of their nonlinear confinement within the CR3BP.
Read the full abstract
Complex Variables
Remote temperature sensing in 2D and the Bergman kernel
We explore the problem of estimating the steady state temperature in a two-dimensional domain at a point knowing the temperature to high order at another point. We find connections to the Bergman kernel of the domain, Runge's theorem, and approximate null quadrature identities.
Rings and Algebras
A note on explicit homological invariants of graded double Ore extensions
We compute explicit homological invariants of a trimmed graded double Ore extension of the quantum plane. For a pilot family of type (14641), we determine the minimal graded free resolution and graded Betti numbers of the trivial right module and also compute linear resolutions for two natural cyclic right modules. This provides a concrete link between the PBW structure of the algebra and the homological behavior of its natural quotients.
Read the full abstract
Complex Variables
Zeros of random $P$-polynomials in $\mathbb{C}^d$ with exponential profiles
We study random multivariate $P$-polynomials in $\mathbb{C}^d$ with monomial supports constrained to $nP\cap\mathbb{Z}_+^d$ for a convex body $P\subset\mathbb{R}_+^d$, and deterministic coefficients admitting a uniform exponential profile $f$ on $P$. Assuming the tail condition $\mathbb{P}(\log(1+|\xi_0|)>t)=o(t^{-d})$ on the i.i.d. complex coefficients, we prove that the normalized potentials $\frac1n\log|\mathbf{P}_n|$ converge in probability in $L^1_{\mathrm{loc}}(\mathbb{C}^d)$ to a deterministic toric plurisubharmonic function $\Phi_{P,f}$, and consequently the normalized zero currents $\frac1n[Z_{\mathbf{P}_n}]$ converge weakly to the closed positive $(1,1)$-current $dd^c\Phi_{P,f}$. Under the stronger logarithmic moment assumption $\mathbb{E}[(\log(1+|\xi_0|))^d]<\infty$, we prove almost sure weak convergence of the zero currents along the full sequence for $d>2$, and along sparse subsequences for $d \le 2$. On $(\mathbb{C}^*)^d$, the limiting potential is given by $\Phi_{P,f}(z)=I_{P,f}(\operatorname{Log} z)$, where $I_{P,f}$ is the Legendre-Fenchel transform of the profile over $P$ and $\operatorname{Log} (z)=(\log|z_1|,\dots,\log|z_d|)$. These results extend the exponential-profile mechanism of Kabluchko and Zaporozhets from one complex variable to the genuinely multivariate $P$-polynomial setting under relaxed probabilistic assumptions, directly connecting random zero hypersurfaces with convex-analytic data determined by $(P,f)$.
Read the full abstract
Numerical Analysis
Simulation Platform To Evaluate Inversion Techniques For Magnetic Resonance Elastography Data
Magnetic Resonance Elastography (MRE) has become an essential tool in assessing the mechanical properties of soft tissues in-vivo, prompting significant progress in new inversion algorithms. This creates a need for a benchmarking framework to promote uniformity and accessibility. To address this, we introduce a comprehensive in-silico dataset acquired by solving the forward Finite Element calculations of shear wave propagation in a linear visco-elastic material. This dataset aims to serve as a platform for evaluating inversion schemes by providing data that can be used as input with known mechanical properties to these methods. It includes simulations on homogeneous cuboidal domains of varying spatial and temporal resolution, and an extension to more physiological variations, including material inhomogeneity and internal arterial pulsation. We present a comprehensive case study using simulated data as an input to a direct inversion (DI) scheme, which allows for an expedient local inversion into the underlying material parameters. When aiming to reconstruct the parameters describing the linear visco-elastic material behavior via DI, we find that due to compromised convergence properties of frequency-domain stencils, stemming from truncation and subtractive cancellation errors, the reconstruction accuracy depends non-monotonically on the spatial and temporal resolution of the measurement grid. For inhomogeneous domains, the reconstruction was successful with notable interface boundaries. In the presence of pressurized vascular inclusions, a general stiffening of the domain was noted, as the recovered shear modulus was higher than the one assumed in forward modeling. Our study highlights the potential of this dataset as a vital benchmarking tool for advancing the development and refinement of MRE techniques, contributing to more accurate and reliable assessment of soft tissue mechanics.
Read the full abstract
Mathematical Physics
Dimensional consistency in fractional differential equations with non singular kernels
The purpose of this article is to address the issues of dimensional consistency that arise in the process of replacing the ordinary time derivative operator by a fractional derivative operator in order to write a fractional differential equation. We show that by performing a simple change of variables fulfilling certain conditions ensures the consistency in physical dimensions for fractional differential equations with non singular kernels. An example of the proposed method is given.
Read the full abstract
Mathematical Physics · Cross-listed from quant-ph
Provable quantum thermalization without statistical averages
We develop a rigorous system-agnostic method to predict quantum thermalization in an overwhelming fraction of accessible pure states in a many-body system, entirely in terms of certain out-of-time-ordered correlators of few-body observables. In contrast to previous rigorous results on thermalization with semiclassical counterparts, our method is not limited to statistical averages of observables, such as time averages in ergodicity or state averages in mixing. Moreover, consistent with such approaches, we retain the advantage of not requiring a detailed knowledge of energy eigenstate structure or thermodynamically large times, which can become intractable for systems with more than a handful of particles. Our approach is centered on a geometric result that connects thermalization to the alignment of high dimensional subspaces in a Hilbert space, which is determined by the saturation of "controllably nonlocal" out-of-time-ordered correlators. We discuss the possibility of predicting quantum thermalization in almost all states at almost all times from finite-time observations of a single such correlator per observable. This formalism reduces the problem of establishing pure state quantum thermalization at finite times in almost all complex many-body states to a theoretically or experimentally accessible study of few-body correlators, even in thermodynamically large systems.
Read the full abstract
Optimization and Control
Scaled Relative Graphs in Normed Spaces
The paper extends the Scaled Relative Graph (SRG) framework of Ryu, Hannah, and Yin from Hilbert spaces to normed spaces. Our extension replaces the inner product with a regular pairing, whose asymmetry gives rise to directional angles and, in turn, directional SRGs. Directional SRGs are shown to provide geometric containment tests certifying key operator properties, including contraction and monotonicity. Calculus rules for SRGs under scaling, inversion, addition, and composition are also derived. The theory is illustrated by numerical examples, including a graphical analysis of the contractivity of Bellman operators using directional SRGs.
Read the full abstract
Number Theory
Almost Golomb Sequences
Golomb's sequence $(G(n))$ is the unique nondecreasing sequence of positive integers in which each $n$ appears exactly $G(n)$ times. It satisfies the global self-referential rule $G(G(n)+G(n-1)+\cdots+G(1))=n$, grows smoothly like a power of $n$ governed by the golden ratio, and is not $k$-regular for any $k\ge 2$. We introduce almost Golomb sequences, obtained by truncating the cumulative sum to a fixed size sliding window $r$: $a(a(n)+a(n-1)+\cdots+a(n-r+1))=n$. This finite-memory truncation completely changes the nature of the sequence. The smooth power law gives way to oscillatory linear growth, and the sequence becomes $r$-regular for every $r\ge 2$. For small values of $r$ we establish explicit denesting formulas, prove that $a(n)/n$ does not converge, and reveal the combinatorial structure including a cellular automaton and a palindromic substitution. When one varies $r$, the Golomb sequence itself reappears. We prove that the first $r$ terms of the order-$r$ sequence form a shifted copy of Golomb's sequence, and that this initial segment controls the maximum multiplicity across the whole family. For $r\ge 5$ in particular, the maximal multiplicity is exactly $G(r-1)$. The sequence that was truncated returns as the law governing the family it generated.
Read the full abstract
General Mathematics
Exact Formulas for Coprime Representations of Even Integers Avoiding a Prime
Fix a prime $p \ge 5$ and define $g(2n,p)=\#\{(h,k)\in\mathbb{Z}_{>0}^2 : h+k=2n,\; h\le k,\; \gcd(h,6p)=\gcd(k,6p)=1\}$. We derive explicit closed-form expressions for $g(2n,p)$ in terms of the canonical remainder operator $\delta_k(x)=x-k\lfloor x/k\rfloor$, elementary step functions, and the minimal solutions of the congruences $6x \equiv -1 \pmod{p}$ and $6x \equiv -5 \pmod{p}$. A key ingredient is an explicit formula for the minimal solution of $\delta_k(a_0 x)=b_0$ obtained via the Euclidean algorithm, which determines the excluded residue classes directly. The resulting formulas show that $g(2n,p)$ is piecewise affine along arithmetic progressions of $n$, governed by residue classes modulo $3$ and $p$. For fixed $p$, after precomputing two residue parameters in $O(\log p)$ time, each evaluation of $g(2n,p)$ requires only $O(1)$ operations, compared to $O(n)$ for direct enumeration. The formulas are validated computationally for all $2n \le 10^5$ and primes $p \in \{5,7,11,13,17,19,23\}$, with perfect agreement with brute-force enumeration.
Read the full abstract
Combinatorics
A construction of 2-arc-transitive non-solvable covers of complete graphs
We construct connected $2$-arc-transitive covers of complete graphs with non-abelian characteristically simple transformation groups. This solves the existence problem for non-solvable $2$-arc-transitive covers of complete graphs.
Read the full abstract
Probability
A weak transport approach to the Schrödinger-Bass bridge
We study the Schrödinger-Bass problem, a one-parameter family of semimartingale optimal transport problems indexed by $\beta>0$, whose limiting regimes interpolate between the classical Schrödinger bridge, the Brenier-Strassen problem, and, after rescaling, the martingale Benamou-Brenier (Bass) problem. For each $\beta>0$, we prove that the dynamic Schrödinger-Bass problem is equivalent to a static weak optimal transport (WOT) problem with explicit cost $C_{\mathrm{SB}}^\beta$. This yields primal and dual attainment, as well as a structural characterization of the optimal semimartingales. The cost $C_{\mathrm{SB}}^\beta$ is constructed via infimal convolution and deconvolution of the Schrödinger cost with the Wasserstein distance. In a broader setting, we show that such infimal convolutions preserve the WOT structure and inherit continuity, coercivity, and stability of both values and optimizers with respect to the marginals. Building on this formulation, we propose a dual ascent algorithm for numerical computation. We establish monotone improvement of the dual objective and convergence of the iteration to the unique optimizer under suitable integrability assumptions.
Read the full abstract
Numerical Analysis
A Positivity-Preserving Relaxation Algorithm
We combine Patankar-type methods with suitable relaxation procedures that are capable of ensuring correct dissipation or conservation of functionals such as entropy or energy while producing unconditionally positive and conservative approximations. To that end, we adapt the relaxation algorithm to enforce positivity by using either ideas from the dense output framework when a linear invariant must be preserved, or simply a geometric mean if the only constraint is positivity preservation. The latter merely requires the solution of a scalar nonlinear equation while former results in a coupled linear-nonlinear system of equations. We present sufficient conditions for the solvability of the respective equations. Several applications in the context of ordinary and partial differential equations are presented, and the theoretical findings are validated numerically.
Read the full abstract
Number Theory
Large values of exponential sums with multiplicative coefficients
In 1977 Montgomery and Vaughan gave tight bounds for exponential sums of the form $\sum_{n\leq x}f(n)e(n\alpha)$ where $f$ is a $1$-bounded multiplicative function and $\alpha\in\mathbb R$, close to the conjectured $\ll \frac{x}{\sqrt{q}}+ \frac{x}{\log x}$ where $\alpha$ is best approximated by $|\alpha-a/q|\leq 1/(qx)$, showing their results to be “best-possible” by observing that the first part of their bound is more-or-less attained when $f(n)=\chi(n), \alpha=\frac aq$ where $\chi$ is a primitive character mod $q$, and the second part when $f(p)=e(-\alpha p)$ for all large primes $p$. La Bretèche and Granville proved that when $\alpha$ lies on a major arc the exponential sum is significantly smaller unless $f$ “pretends to be” $\chi(n)n^{it}$ for some character $\chi$ and real number $|t|<\log x$; and herein we prove that when $\alpha$ lies on a minor arc, the exponential sum is significantly smaller unless $f(p)$ pretends to be $e(-hp\alpha)$ for primes $p\leq x$ for some bounded integer $h$. We also study exponential sums $\sum_{n\leq x, P^+(n)\leq y} f(n) e(n\alpha)$ restricted to $y$-smooth (or $y$-friable) integers $n$. We conjecture that this sum is $\ll \frac{\Psi(x, y)}{\sqrt{q}}+ \frac{\sqrt{xy}}{\log x} $ in a wide range of parameters, show that if true this is best possible, and prove an upper bound in a wide range that is only slightly weaker than the conjecture. Finally we study the logarithmically weighted exponential sums $\sum_{n\leq x} \frac{f(n)}{n} e(n\alpha)$. We conjecture that this sum is $\ll \frac{\log x}{\sqrt{q}}+\log q$ in a wide range of parameters, show that if true this is best possible, and prove an upper bound in a wide range that is only slightly weaker than the conjecture. Along the way, we will prove various technical results about multiplicative functions which may be of use elsewhere.
Read the full abstract
Classical Analysis and ODEs
Cesàro summability of Hölder functions and Talbot effect on rank one Riemannian symmetric spaces of compact type
On rank one Riemannian symmetric spaces of compact type (of dimension $\ge 2$), we first obtain a quantitative characterization of Hölder continuity in terms of Cesàro means. In addition to some approximation theoretic applications, we also apply it to study the celebrated physical phenomenon known as `Talbot effect' arising from diffraction theory. More precisely, for almost every fixed time instance, we study the Hölder continuity and the fractal profile of the Schrödinger propagation in terms of the decay of the Littlewood-Paley projections of the initial data. In the process, we also obtain oscillatory expansions of zonal spherical functions uniformly near the origin and near the cut locus respectively, which may be of independent interest.
Read the full abstract
Mathematical Physics
Commutator Estimates for Low-Temperature Fermi Gases
We investigate the semiclassical regularity of thermal equilibria in the presence of a harmonic potential at low temperature; that is, we obtain the asymptotic behavior of the Schatten norms of commutators of the one-body operators associated with these equilibria and the position and momentum operators. We also obtain upper bounds in the magnetic field case for the Fock-Darwin Hamiltonian. Our estimates, in particular, allow us to observe several regimes depending on the joint behavior of the Planck constant, the temperature, and the strength of the magnetic field.
Read the full abstract
Probability
Flexibility allocation in random bipartite matching markets: exact matching rates and dominance regimes
This paper studies how a fixed flexibility budget should be allocated across the two sides of a balanced bipartite matching market. We model compatibilities via a sparse bipartite stochastic block model in which flexible agents are more likely to connect with agents on the opposite side, and derive an exact variational formula for the asymptotic matching rate under any flexibility allocation. The derivation extends the local weak convergence framework of [BLS11] from single-type to multi-type unimodular Galton-Watson trees, reducing the matching rate to an explicit low-dimensional optimization problem. Using this formula, we analytically investigate when the one-sided allocation, which concentrates all flexibility on one side, dominates the two-sided allocation and vice versa, sharpening and extending the comparisons of [FMZ26] which relied on approximate algorithmic bounds rather than an exact characterization of the matching rate.
Read the full abstract
Optimization and Control · Cross-listed from cs.CV
AdamFlow: Adam-based Wasserstein Gradient Flows for Surface Registration in Medical Imaging
Surface registration plays an important role for anatomical shape analysis in medical imaging. Existing surface registration methods often face a trade-off between efficiency and robustness. Local point matching methods are computationally efficient, but vulnerable to noise and initialisation. Methods designed for global point set alignment tend to incur a high computational cost. To address the challenge, here we present a fast surface registration method, which formulates surface meshes as probability measures and surface registration as a distributional optimisation problem. The discrepancy between two meshes is measured using an efficient sliced Wasserstein distance with log-linear computational complexity. We propose a novel optimisation method, AdamFlow, which generalises the well-known Adam optimisation method from the Euclidean space to the probability space for minimising the sliced Wasserstein distance. We theoretically analyse the asymptotic convergence of AdamFlow and empirically demonstrate its superior performance in both affine and non-rigid surface registration across various anatomical structures.
Read the full abstract
Number Theory
Worse than square-root cancellation in Bateman-Horn's conjecture
We prove asymptotics for the average error term in Bateman-Horn's conjecture in the exponential range.
Optimization and Control · Cross-listed from cs.CC
The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
The complexity of finding second-order stationary points (SOSPs) in constrained settings has remained unclear and has been highlighted as an open question by the works of Hollender and Zampetakis [2023] and Kontogiannis et al. [2024]. In particular, under one established definition (SOSP1) where nonnegative curvature is required only along the null space of the active constraints [Bertsekas, 1997], the problem lies in TFNP, and algorithms with $O(poly(1/\epsilon))$ running times have been proposed. Under another established notion of stationarity (SOSP2) checking is coNP-hard in high dimensions. We investigate the computational landscape of finding SOSPs under polytope constraints. We prove that, even if promised that all KKT points lie a constant distance away from the domain's boundary–where SOSP1 and SOSP2 reduce to the standard unconstrained conditions–finding an approximate SOSP under either definition is PLS-hard, and the hardness continues to hold even in $[0,1]^2$. As a direct consequence, our result establishes a fundamental barrier on the continuity of SOSP-computing algorithms: unless PLS=CLS, no deterministic, iterative algorithm with a computationally efficient, continuous update rule can guarantee that every $\epsilon$-approximate fixed point is an $(\epsilon,\sqrt{\epsilon})$-SOSP, even under the above interior promise. We establish PLS-completeness by proving that the problem of finding approximate SOSP1 belongs to PLS in high dimensions. In addition, we prove that, for every fixed $d\ge 2$, finding an approximate SOSP2 is also PLS-complete, escaping the coNP-hardness which appears in high dimensions. We also establish PLS-hardness and a polynomial-time search reduction to LOCALOPT for finding $(r^{2+\gamma},r)$-local pure Nash equilibria, for every fixed rational $\gamma\in(0,1]$, in two-player nonconvex common-interest games with actions in $[0,1]$.
Read the full abstract
Information Theory
One-Shot Secret Sharing with Monotone Access Structures over Classical-Quantum Broadcast Channels
We consider a secret sharing setting with a monotone access structure involving a control node and $L$ users, connected via a classical-quantum broadcast channel whose input is controlled by the control node, referred to as the dealer. Unlike traditional secret sharing settings, where the dealer fully controls the shares given to each user, in our model, the dealer encodes the secret for transmission over the broadcast channel. This means that the shares received by users are perturbed by the channel and are not fully controlled by the dealer. Our main results are achievable one-shot secret sharing rates, as well as converse bounds for arbitrary monotone access structures. We further derive second-order and asymptotic achievable rates for arbitrary monotone access structures. In the special case where all shares are required to recover the secret, we show that our result coincides with the existing secret sharing capacity over classical channels.
Read the full abstract
Mathematical Physics
Tensor invariants for multipartite entanglement classification
Organising the space of entanglement structures of a multipartite quantum system is a much more challenging task than its bipartite version: while the local unitary (LU) orbit of a bipartite pure state can be conveniently characterized by its entanglement spectrum, invariants of multipartite entanglement structures are comparatively difficult to define and work with. The root cause of this difference is that the bipartite problem can be reduced to the analysis of matrix invariants, while its multipartite version is governed by a much richer space of tensor invariants. The present work explores the latter through the lens of so-called trace-invariants, which are in one-to-one correspondence with combinatorial objects known as colored graphs. We first explain why trace-invariant evaluations can serve as labels of LU-orbits of multipartite pure states, how this strategy extends to random states, and how the effect of local operations (LO) can be analyzed through such data. We then focus on entanglement classification within an (infinite-dimensional) subspace of reference states, whose basic building blocks are GHZ states of various dimensions. We show that relatively simple subclasses of trace-invariants are sufficient to separate the LU-orbits of reference states, and enable a complete (resp. an incomplete) characterization of their relations in the LO (resp. LOCC) resource theory of entanglement. Finally, we investigate how a (still infinite) subclass of reference states of local dimension N can be efficiently distinguished at leading and subleading orders in an asymptotic large-N expansion (among themselves, or from Haar-random states). This analysis relies crucially on combinatorial quantities associated to colored graphs, some of which have already played instrumental roles in the recent literature on random tensors. Results of broader relevance are reported along the way.
Read the full abstract
Combinatorics
S-packing chromatic critical paths and cycles
Let $S=(s_1,s_2,\ldots)$ be a non-decreasing sequence of positive integers. For a graph $G$ with vertex set $V(G)$, a labeling $\phi \colon V(G)\to \{1,\ldots,k\}$ is an $S$-packing $k$-coloring if, whenever two distinct vertices $u,v\in V(G)$ are assigned the same color $i$, their distance in $G$ is greater than $s_i$. The minimum $k$ for which $G$ admits such a coloring is the $S$-packing chromatic number of $G$. A graph $G$ is $\chi_S$-vertex-critical if $\chi_S(G-v) < \chi_S(G)$ for every $v \in V(G)$, and it is $\chi_S$-critical if $\chi_S(H) < \chi_S(G)$ holds for every proper subgraph $H$ of $G$. In this paper, the exact value of $\chi_S(P_n)$ is determined for every path of order $n$ and for every packing sequence $S$ where $s_i < 2^i$ holds for each entry $s_i$. As a consequence, $\chi_S$-critical and $\chi_S$-vertex-critical paths are identified for each such sequence $S$. In addition, we extend earlier results on $\chi_S$-critical cycles and provide a complete characterization of $\chi_S$-critical and $\chi_S$-vertex-critical cycles for packing sequences $S= (1, s_2, \dots )$ with $s_2 \in \{2,3\}$ and $s_3,s_4 \in \{4,5,6,7\}$.
Read the full abstract
Combinatorics
Random Turán Problems for Graphs with a Vertex Complete to One Part
Given a graph $F$, the random Turán problem asks to determine the maximum number of edges in an $F$-free subgraph of $G_{n,p}$. Prior to this work, the only bipartite graphs $F$ with known tight bounds included certain classes of complete bipartite graphs and theta graphs. We greatly expand upon these examples by proving tight bounds for a number of bipartite graphs which have a vertex complete to one part. We also prove new general upper bounds for this problem which in many cases do significantly better than the only previous known general upper bound due to Jiang and Longbrake. Our proofs utilize dependent random choice together with the recent technique of balanced vertex supersaturation in conjunction with hypergraph containers.
Read the full abstract
Algebraic Geometry
Plücker degrees of Quot schemes
We study the Plücker degree of the main component of the Quot scheme of length $l$ quotients of a locally free sheaf on a smooth projective scheme $\mathrm{S}$ of dimension $d\geqslant 1$. This degree is determined by classes in the Chow ring of the symmetric product $\mathrm{S}^{(l)}$, which are given by the pushforward of the powers of $c_{1}(\mathcal{O}^{[l]})$ with respect to the canonical morphism from the Quot scheme to $\mathrm{S}^{(l)}$. We describe a decomposition of these classes, allowing us to compute the (in a certain sense) leading term of the Plücker degree. We also obtain a higher-dimensional analogue of a classical result of Schubert.