Papers

For a given $d$-regular graph $G$, a Maker-Breaker degree game is played by two players who alternately claim previously unclaimed edges of $G$. In the standard variant, the goal of Maker is to maximize the maximum degree of their induced subgraph, while Breaker aims to minimize it, or equivalently, to guarantee a certain minimum degree in their own subgraph. A classic pairing strategy shows that Breaker can secure at least $\lfloor d/4 \rfloor$ edges at every vertex of any $d$-regular graph. Breaking this bound for general or even for specific classes of graphs has been a long-standing open problem in combinatorial game theory; indeed, J. Beck characterized this challenge in his monograph as the first among the seven most humiliating open problems of positional game theory. In this paper, we improve the $d/4$ bound for some infinite graph families, such as the hypercube graph $Q_d$, grids and tori. We first show that Breaker can secure a degree of one at every vertex in $Q_3$, then lift this to higher dimensions, where Breaker can guarantee a degree of at least $\lfloor d/3 \rfloor$.

A classical problem in lattice path enumeration counts paths that remain on one side of a boundary line. We study several classes of paths where this boundary is porous and show that they are related through a single half-turn rotation bijection. As a first application, we enumerate minimal bridges by relating them to excursions: for positive integers $k$ and $n$, the number of paths from $(0,0)$ to $(kn,n)$ with unit right and up steps that avoid all other lattice points on the line $y=x/k$ is $\frac{k}{kn+n-1}\binom{kn+n}{n}$. The same bijection yields a relation between the ordinary generating functions for binomial coefficients and $k$-Catalan numbers through a dual edge-forbidden model, extends to forbidden strips containing the diagonal, and handles a rational-slope case involving Duchon paths. Finally, our bijection also proves that the number of bridges from $(0,0)$ to $(2n,2n)$ that avoid even diagonal points is $C_{2n}+4C_{2n-1}$, with $C_n$ the $n$th Catalan number. This complements a result of Shapiro.

In this work, we study the information bottleneck under perfect privacy, with particular emphasis on the active-rate regime, where the representation-rate constraint is binding and directly limits the achievable utility. The goal is to construct a representation that preserves utility-relevant information while remaining statistically independent of a sensitive variable. This exact independence requirement introduces an additional constraint beyond the classical rate-relevance tradeoff and must be explicitly incorporated into the optimization. To this end, we develop an alternating direction method of multipliers (ADMM)-based method tailored to the resulting problem structure. Under suitable regularity conditions, we establish global convergence of the generated sequence, characterize its convergence rate through the Kurdyka-Lojasiewicz exponent, and extend the analysis to inexact block updates.

Classical identification via a noisy channel is a communication task in which the receiver is not required to reconstruct the full transmitted message, but only to decide whether it coincides with a message of interest. This relaxation allows the number of identifiable messages to grow doubly exponentially with the blocklength. For quantum channels, the resulting (doubly exponential) identification capacity $C_{\mathrm{ID}}$ can strictly exceed the ordinary (exponential) transmission capacity $C$. In this paper, we prove that the entanglement-assisted transmission capacity $C_E$ is a strong converse bound for this task: $C_{\mathrm{ID}}\leq C_E$. For sufficiently low-noise channels, this bound can also be achieved via the Hayden-Winter (quantum) identification + fingerprinting codes. This yields an exact characterization $C_{\mathrm{ID}}=C_E$ of identification capacity for such channels. However, for general channels, we prove that this upper bound can be strict. We exhibit an explicit family of transpose-depolarizing channels for which $C_{\mathrm{ID}}<C_E$. As a consequence, we also obtain the first example of strict superadditivity of the identification capacity $C_{\mathrm{ID}}$.

In this paper, we will prove a result about the structure of polytopes whose floating bodies are not smooth. This will then be used to prove a result about the combinatorial structure of minimizers of the volume product.

We prove sharpness of the avalanche phase transition in the one-dimensional Bak–Sneppen model, for both the one-sided and isotropic update rules. In the one-sided model, the avalanche range is described by a nonlinear self-interacting jump process whose tails satisfy a triangular system. An extremal inequality for decreasing probability masses yields a polynomial lower bound on the range tail at the susceptibility threshold; this bound forces the appearance of infinite avalanches immediately above criticality and hence identifies the susceptibility and infinite-avalanche thresholds. A comparison of avalanche endpoints transfers this equality to the isotropic model. In both models, no infinite avalanche occurs at criticality, while the range has exponential moments at every strictly subcritical level. Combined with the range–duration and stationary-limit results of Meester and Znamenski, this identifies all three avalanche critical thresholds and proves the conjectured stationary product limit in both models.

We introduce sequential analogues of directed (parametrized) topological complexity, in the context of motion planning problems requiring a system to traverse a prescribed sequence of intermediate states while respecting directed dynamics and varying external parameters. We develop their basic theory, establish fundamental properties, and compute them for several classes of examples. Our computations show, in particular, that distinct directed structures on the same underlying space can have different values of this invariant.

We prove a double-sum analogue of Whipple's ${}_3F_2$ summation formula. As an application, we establish a restricted sum formula for multiple binomial sums, which arise as special cases of Igarashi's parametrized multiple zeta series.

The vortices that appear in Hitchin's pioneering study of Higgs bundles are interpreted as a new version of the abelian Higgs vortices more familiar to theoretical physicists. Their conformal covariance is made explicit.

For $n\ge2$, we classify the affine diffeomorphisms $f_{A,v}(x)=Ax+v$ on $\mathbb R^n$ that admit a complete Riemannian metric with respect to which they are Anosov. Such a metric exists if and only if $A$ is hyperbolic or $f_{A,v}$ has no fixed point, equivalently $v\notin\operatorname{Im}(I-A)$. In the latter case, $f_{A,v}$ is smoothly conjugate to a translation when $\det A>0$ and to White's map times the identity when $\det A<0$. We also determine the possible stable indices. In the hyperbolic case, the index is determined by the stable spectrum of $A$, whereas a map with no fixed point admits complete Anosov metrics of every stable index from $1$ to $n-1$. Along the $1$-eigenspace, every such metric must exhibit exponential growth of vector norms along one of the two half orbits. We then determine the interior and boundary of the Anosov-realizable locus in the affine parameter space and describe the corresponding change of the index spectrum near regular drift parameters. Finally, we show that Anosov-realizability is not open in the two-sided weak $C^1_{\mathrm{loc}}$ topology but is open in the two-sided strong Whitney $C^1$ topology.

We construct morphisms between smooth complex projective varieties that have singular fibers, but look topologically smooth. We use this to give negative answers to the following four conjectures and questions: the smoothness conjecture of Fernández~de~Bobadilla and Kollár, a question of Kollár and Pardon on universal covers, Kotschick's conjecture on 1-forms, and a conjecture of Schreieder on Aomoto complexes. Version 2 is a revised version of sections 1–6 of the original, no change in the results. A substantially expanded version of sections 7–8 of the original will be posted separately.

We establish a sharp prime orbit theorem for every homoclinic class of a $C^\infty$ diffeomorphism on a closed surface with positive topological entropy. Let $\mathcal{H}$ be a homoclinic class with topological entropy $h > 0$. Then there exists a constant $\chi_2 < 0$ such that for any $\chi_1 \in (0, h)$, \[ \lim_{\substack{l(\mathcal{H}) \mid n \\ n\to\infty}} \frac{\sharp P_{\chi_1,\chi_2}(n)}{e^{nh}} = l(\mathcal{H}). \] Here $P_{\chi_1,\chi_2}(n)$ stands for the set of period-$n$ saddle points in $\mathcal{H}$ with Lyapunov exponents lying outside the interval $[\chi_2,\chi_1]$, and $l(\mathcal{H})$ denotes the period associated with the homoclinic class $\mathcal{H}$.

In this paper, we present efficient search-to-decision reductions for the Linear Code Equivalence (LCE) and Generalised Code Equivalence (GCE) problems. Our methodology is inspired by the recent search-to-decision reduction for Permutation Code Equivalence. We demonstrate how to recover the permutation component of the equivalence using a decision oracle, and subsequently show one way of recovering the diagonal and field automorphism components in deterministic polynomial time by leveraging the elegant Engel-Schneider algorithm for diagonal equivalence.

In this article we show that an $\mathbb{A}^1$ bundle map or a vector bundle map $p: X \to Y$ induces trivial local fibration $\underline{Sing}(X) \to \underline{Sing}(Y)$. Using this, we first show that for Korus Russel threefolds of first kind $X$ the space $\underline{Sing}(X)$ is $\mathbb{A}^1$ local. Then we show that for any smooth affine complex surface $X$, the $\mathbb{A}^1$- connected component sheaf is homotopy invariant.

We show that any $d$-dimensional local ring $A$ with a dualizing complex, $\mathrm{depth} A=d-1$, and cyclic deficiency module $K^{d-1}(A)$ admits a maximal Cohen–Macaulay module. It is constructed as the unique nonzero cohomology module of the cone of the derived morphism induced by a surjection $A\to K^{d-1}(A)$. This gives new cases of the small Cohen–Macaulay conjecture. When $A$ is quasi-Gorenstein, this module is identified with the first syzygy of the canonical module $\omega_{A/xA}$, for any $x\in\operatorname{ann}_A K^{d-1}(A)$ that is regular on $A$. This recovers a theorem of Tavanfar and Shimomoto for quasi-Gorenstein deformations of a 3-dimensional quasi-Gorenstein local ring $A$ with $K^2(A)\cong k$. We also construct examples of section rings satisfying the hypotheses of our theorem.

We develop a general framework for studying generic homeomorphisms of compact metric spaces using combinatorial amalgamation methods inspired by Fraïssé theory. Our approach combines Rosendal's criterion for comeager conjugacy classes with combinatorial codings of compact spaces arising from the Bartoš-Bice-Vignati duality. We introduce a new amalgamation property, called weak minimal amalgamation, formulated in suitable paracategories encoding local dynamical data of homeomorphisms. This yields characterizations of the Rokhlin and the strong Rokhlin properties, i.e., the existence of dense and comeager conjugacy classes in homeomorphism groups of compact metric spaces. As applications, we reprove Hjorth's theorem that $\mbox{Homeo}_+([0,1])$ admits a generic homeomorphism, and establish the existence of generic homeomorphisms for the Cantor fan and the Lelek fan. Moreover, we show that generic homeomorphisms of these spaces have no Li–Yorke pairs, and therefore generically have zero topological entropy. More broadly, the paper develops new connections between combinatorial amalgamation properties and generic phenomena in topological group theory and topological dynamics.

Decision diagrams (DDs) have become a powerful tool for discrete optimization, supporting a wide range of algorithms that span cut-generation procedures, decomposition methods, and specialized branch-and-bound searches. Despite this growth, their adoption remains limited, partly because most existing DD code is tailored to a specific algorithm or application and is therefore hard to reuse. We introduce DD-suite, a cross-platform, open-source software package for building and manipulating DDs for discrete optimization. DD-suite is available in both Python and C++ through a shared modeling interface, and lets users construct exact, restricted, and relaxed DDs for any discrete optimization problem expressed in recursive form. The package implements the DD reduction procedure, shortest-path routines for obtaining primal and dual bounds, a visualization tool, and an extensive automated test suite. Furthermore, it includes extensive documentation, a support webpage, and ready-to-use examples for four combinatorial problems. Rather than a closed solver, DD-suite is designed as an extensible building block: users can add new construction mechanisms or run custom algorithms on top of the resulting diagram, as we illustrate with a DD-based cutting plane procedure embedded in a state-of-the-art mixed-integer programming solver. Our numerical experiments show that the C++ implementation is 5-6 times faster than the Python one while producing identical diagrams, and remains within a small constant factor of ddo, a specialized Rust framework, confirming that DD-suite combines an accessible, extensible codebase with competitive performance.

In this paper, we study compactness, rigidity, and related geometric properties of complete Kähler Ricci shrinkers through the polarized Fano fibration structure.

In this paper, we study the Couette-Taylor instability of a viscous fluid between two rotating cylinders in the small-gap, slow rescaled rotation rate, high Reynolds number regime, focusing on the very counter-rotating case $\mu < \mu_c \approx -0.8$ where the primary instability is non-axisymmetric. Starting from the Navier-Stokes equations, we derive a limit system that captures the leading-order dynamics and compute the critical Taylor number $T_c(\mu)$ together with the critical axial and azimuthal wavenumbers. Near criticality, the weakly nonlinear behaviour is governed by a system of two coupled complex Ginzburg-Landau equations. All coefficients of this amplitude system including the cubic nonlinear terms are evaluated numerically from the linearised eigenfunctions and the associated adjoint problem. The reduced equations admit helicoidal waves (travelling in both the axial and azimuthal directions) and ribbon waves (standing axially, travelling azimuthally), and their existence and stability criteria are discussed. We also examine more exotic spatially modulated solutions that satisfy a third-order dynamical system, whose complete classification remains an open challenge.

We prove multiple central limit theorems for serial tail dependence estimators in heavy-tailed long memory linear time series. The main theoretical tools are two novel multivariate reduction principles for partial sums of heavy-tailed long memory linear time series, subordinated over sliding windows and above a threshold growing with sample size. This requires addressing several substantial difficulties, including handling a nonlinear, sample-size dependent, and multivariate subordination mechanism, the dependence between several overlapping linear processes, and the lack of higher-order moments of the marginal distribution. Despite these obstacles, our assumptions are mild and, in particular, the innovation process is allowed to have infinite variance. A key feature of our theory is that our second reduction principle holds uniformly in the threshold, allowing central limit theory for empirical extremograms with sample quantiles as thresholds. This question has received little attention in the literature on serial extremal dependence estimation even though the version of empirical extremograms with random thresholds is ubiquitous in practice. We compare our results in several respects with those that may be obtained under short-range dependence, thereby discovering markedly different convergence rates and limit laws in our long memory setting.

We study funnel control for linear infinite-dimensional passive systems whose controlled output is obtained by integrating the passive output. In mechanical applications, this corresponds to position control based on a measured passive velocity output. Within the system-node framework, we propose a nonlinear recursive funnel controller with a dynamic gain supervisor for systems with distributed or boundary control and observation. The supervisor automatically increases a damping gain whenever the normalized recursive error approaches a prescribed monitoring level. The controller uses the tracking error and its derivative, with the latter obtained directly from the passive output rather than by numerical differentiation. We prove global existence and uniqueness of the closed-loop trajectory, prescribed funnel performance, and global boundedness of the derivative tracking error and the passive output. Under an additional position-compatible strict dissipativity condition, the supervised gain is increased only finitely many times and eventually becomes constant. Consequently, the gain, the internal state, and the control input are globally bounded, and the recursive-error funnel margin is uniform in time. The results are illustrated by a boundary-actuated Euler-Bernoulli beam with uniformly positive distributed damping.

Kleene triples, introduced by Jalali, provide a representation of arbitrary Kleene algebras in terms of twist-products. We introduce modal Kleene algebras and modal Kleene triples, and establish a categorical equivalence between the corresponding categories, extending Jalali's duality to the modal setting. We study the centered case and show that Kleene algebras with implication can be naturally described within this framework by viewing implication as a family of modal operators. Finally, we develop a topological duality for modal Kleene triples.

We study a Restart POMDP (Partially Observable Markov Decision Process) on a general Borel state space, where the controller either lets the hidden state evolve unobserved or restarts the system and observes the new state. Exploiting a sufficient-statistic representation consisting of the last observed state and the elapsed time since restart, we reduce the problem to a fully observed MDP. Under a natural one-step cost deterioration condition, we prove that optimal policies have a threshold structure in the elapsed time for both the discounted and total undiscounted cost criteria. When the state space is partially ordered and the kernel is stochastically monotone, we further show that the optimal threshold is nonincreasing in the state. For the average cost criterion, under additional assumptions of geometric ergodicity and domination of the transient gain, we establish analogous threshold results via the vanishing discount approach, after showing the uniform boundedness of the optimal thresholds and relative value functions.

We consider a patrol problem in which a patroller moves among several geographically dispersed locations to detect attackers that arrive over time. Once the patroller arrives at a location, they can spend any amount of time searching for attackers at that location—and detect an attacker there with some location-dependent instantaneous detection rate—before moving to a different location. The objective of the patroller is to minimize the expected time an attacker stays undetected at a location, regardless of where and when the attack occurs. In the special case where travel times are negligible, we elucidate an optimal cyclic policy in which the patroller allocates a fixed fraction of their effort to each location continuously. The patrol problem becomes significantly more challenging when travel times cannot be ignored. We introduce two types of cyclic patrol patterns based on common patrol practice for perimeter patrol and border patrol, respectively, and derive formulae for the expected time to detect an attack in both cases. We also provide an algorithm for finding the best search time parameters in both of these cases. We give several examples where these cycle types perform well and numerically demonstrate that the optimal patrol policy depends highly on the structure and parameters of each patrol problem.

We investigate equilibrium configurations and dissipative dynamics of simplified disclination–dislocation systems in planar elasticity. We consider an edge dislocation interacting with a fixed wedge disclination in a circular domain. We derive the reduced interaction energy, characterize the equilibrium states and their stability, and study the associated dissipative evolution. The analysis reveals characteristic length scales and collision times arising from the competition between the dislocation and disclination contributions. In particular, the presence of the disclination produces a nontrivial modification of the dislocation dynamics and can hinder its motion. This behavior is consistent with experimental observations and provides a simple mathematical description of the interaction between rotational and translational defects.

Let $B_{n,k}$ be the graph obtained from the balanced complete bipartite graph on $n$ vertices by deleting a matching of size $k$. If $G$ is an $n$-vertex triangle-free graph with $\kappa(\comp G)\geq k$, we prove that $\rhoA(G)\leq\rhoA(B_{n,k})$ for $n\geq4k+2$, with equality precisely when $G\cong B_{n,k}$, and we compute $\rhoA(B_{n,k})$ explicitly. We also solve the bipartite problem for every $n\geq2k+1$, determine the boundary value $\operatorname{spex}_{\kappa}(2k,K_3;k)=k-1$, and settle the full problem for $k=2$. In particular, $B_{n,2}$ is uniquely extremal exactly from order $6$ onward. For $k=1$, equivalently when the complement is connected, $B_{n,1}=K_{\ceil{n/2},\floor{n/2}}-e$ is uniquely extremal for every $n\geq3$.

We study pure disjoint $(r,\delta)$-quantum locally recoverable codes (qLRCs) without assuming a stabilizer structure. We formulate local Knill–Laflamme conditions for recovery from up to $\delta-1$ erasures within a recovery block, and introduce blockwise Shor–Laflamme and unitary weight enumerators that capture how error weight is distributed across recovery sets. We establish several properties of these enumerators and use them to derive a Singleton-like bound that strengthens the known bound for disjoint $(r,\delta)$-qLRCs under a purity assumption, as well as a linear-programming upper bound on the code dimension. These results provide a non-stabilizer, weight-enumerator-based approach to the study of pure disjoint $(r,\delta)$-qLRCs.

The aim of this article is to describe an equationless method for determining the rational points on the non-split Cartan curve $X_{\rm{ns}}^+(N)$ of prime level $N \geqslant 13$. Instead of using a projective model for the modular curve, our method uses the moduli interpretation of the curve, namely we work directly with elliptic curves and Cartan level structures. To accomplish this, we use the geometric version of the quadratic Chabauty method. We show that this can be combined with algorithms for divisor arithmetic developed by Makdisi and Mascot so as to apply to modular curves. As an illustration, we rederive the set of rational points on the curve $X_{\rm{ns}}^+(13)$.

We prove that the $SL(2,\mathbb{C})$ character varieties of compact oriented surfaces and the generic relative $SL(2,\mathbb{C})$ character varieties of punctured surfaces admit divisorial log terminal (dlt) log Calabi-Yau compactifications. To do this, we establish a general result giving sufficient conditions for a compactification of an affine variety arising from a filtration of its algebra of regular functions to be log Calabi-Yau. We then apply this result to show that the compactifications constructed by Kutteri-Tehrani-Frohman in the compact case and by Tehrani-Frohman in the punctured case are log canonical and log Calabi-Yau.

In this work, we study $(r,t,x)$ quantum locally recoverable codes (qLRCs) with locality $r$, $t$ recovery sets per qudit, and intersection parameter $x$. We first show that, assuming the underlying classical codes have dual minimum distance at least two, a CSS code is an $(r,t,x)$-qLRC if and only if the underlying classical codes are $(r,t,x)$ classical LRCs (cLRCs) with common recovery sets. We then use subset-inclusion matrices to construct families of binary dual-containing $(r,t,x)$-cLRCs, which yield binary $(r,t,x)$-qLRCs via the CSS construction. For CSS $(r,t,x)$-qLRCs, we derive upper bounds on the dimension and rate, minimum-distance bounds in the pure case, and a Singleton-like dimension bound in the exact case. Finally, we show that these families attain high rates and nontrivial minimum distances.