Martingale–coboundary decomposition for families of dynamical systems

We prove statistical limit laws for sequences of Birkhoff sums of the type ${\sum }_{j=0}^{n?1}{v}_n°T_n^j$ where $T_n$ is a family of nonuniformly hyperbolic transformations.The key ingredient is a new martingale–coboundary decomposition for nonuniformly hyperbolic transformations which is useful already in the case when the family $T_n$ is replaced by a fixed transformation T, and which is particularly effective in the case when $T_n$ varies with n.In addition to uniformly expanding/hyperbolic dynamical systems, our results include cases where the family $T_n$ consists of intermittent maps, unimodal maps (along the Collet–Eckmann parameters), Viana maps, and externally forced dispersing billiards.As an application, we prove a homogenisation result for discrete fast–slow systems where the fast dynamics is generated by a family of nonuniformly hyperbolic transformations.     

A note on the Hamilton–Waterloo problem with C8-factors and Cm-factors

In this paper, we almost completely solve the Hamilton–Waterloo problem with $C_8$-factors and $C_m$-factors where the number of vertices is a multiple of $8m$.     

Spanning cactus of a graph: Existence,extension, optimization,and approximation

We show that testing if an undirected graph contains a bridgeless spanning cactus is NP-hard. As a consequence, the minimum spanning cactus problem (MSCP) on an undirected graph with 0–1 edge weights is NP-hard. For any subgraph $S$ of $K_n$, we give polynomially testable necessary and sufficient conditions for $S$ to be extendable to a cactus in $K_n$ and the weighted version of this problem is shown to be NP-hard. A spanning tree is shown to be extendable to a cactus in $K_n$ if and only if it has at least one node of even degree. When $S$ is a spanning tree, we show that the weighted version can also be solved in polynomial time. Further, we give an $O\left(n^3\right)$ algorithm for computing a minimum cost spanning tree with at least one vertex of even degree on a graph on $n$ nodes. Finally, we show that for a complete graph with edge-costs satisfying the triangle inequality, the MSCP is equivalent to a general class of optimization problems that properly includes the traveling salesman problem and they all have the same approximation hardness.     

Large data well-posedness in the energy space of the Chern–Simons–Schrödinger system

We consider the initial-value problem for the Chern–Simons–Schrödinger system, which is a gauge-covariant Schrödinger system in ${\mathbb{R}}_t\times {\mathbb{R}}_x^2$ with a long-range electromagnetic field. We show that, in the Coulomb gauge, it is locally well-posed in $H^s$ for $s?1$, and the solution map satisfies a local-in-time weak Lipschitz bound. By energy conservation, we also obtain a global regularity result. The key is to retain the non-perturbative part of the derivative nonlinearity in the principal operator, and exploit the dispersive properties of the resulting paradifferential-type principal operator using adapted $U^p$ and $V^p$ spaces.     

Mayer control problem with probabilistic uncertainty on initial positions

In this paper we introduce and study an optimal control problem in the Mayer's form in the space of probability measures on ${\mathbb{R}}^n$ endowed with the Wasserstein distance. Our aim is to study optimality conditions when the knowledge of the initial state and velocity is subject to some uncertainty, which are modeled by a probability measure on ${\mathbb{R}}^d$ and by a vector-valued measure on ${\mathbb{R}}^d$, respectively. We provide a characterization of the value function of such a problem as unique solution of an Hamilton–Jacobi–Bellman equation in the space of measures in a suitable viscosity sense. Some applications to a pursuit-evasion game with uncertainty in the state space is also discussed, proving the existence of a value for the game.     

A linear time algorithm for the Koopmans–Beckmann QAP linearization and related problems

An instance of the quadratic assignment problem (QAP) with cost matrix $Q$ is said to be linearizable if there exists an instance of the linear assignment problem (LAP) with cost matrix $C$ such that for each assignment, the QAP and LAP objective function values are identical. The QAP linearization problem can be solved in $O\left(n^4\right)$ time. However, for the special cases of Koopmans–Beckmann QAP and the multiplicative assignment problem the input size is of $\Omega \left(n^2\right)$. We show that the QAP linearization problem for these special cases can be solved in $O\left(n^2\right)$ time. For symmetric Koopmans–Beckmann QAP, Bookhold [I. Bookhold, A contribution to quadratic assignment problems, Optimization 21 (1990) 933–943.] gave a sufficient condition for linearizability and raised the question if the condition is necessary. We show that Bookhold’s condition is also necessary for linearizability of symmetric Koopmans–Beckmann QAP.     

Γ-flatness and Bishop–Phelps–Bollobás type theorems for operators

The Bishop–Phelps–Bollobás property deals with simultaneous approximation of an operator T and a vector x at which T nearly attains its norm by an operator $T_0$ and a vector $x_0$, respectively, such that $T_0$ attains its norm at $x_0$. In this note we extend the already known results about the Bishop–Phelps–Bollobás property for Asplund operators to a wider class of Banach spaces and to a wider class of operators. Instead of proving a BPB-type theorem for each space separately we isolate two main notions: Γ-flat operators and Banach spaces with ${\mathrm{ACK}}_{\rho }$ structure. In particular, we prove a general BPB-type theorem for Γ-flat operators acting to a space with ${\mathrm{ACK}}_{\rho }$ structure and show that uniform algebras and spaces with the property β have ${\mathrm{ACK}}_{\rho }$ structure. We also study the stability of the ${\mathrm{ACK}}_{\rho }$ structure under some natural Banach space theory operations. As a consequence, we discover many new examples of spaces Y such that the Bishop–Phelps–Bollobás property for Asplund operators is valid for all pairs of the form ($X,Y$).     

Fixed-parameter algorithms for vertex cover P3

Let $P_{\ell }$ denote a path in a graph $G=(V,E)$ with $\ell$ vertices. A vertex cover $P_{\ell }$ set $C$ in $G$ is a vertex subset such that every $P_{\ell }$ in $G$ has at least a vertex in $C$. The Vertex Cover$P_{\ell }$ problem is to find a vertex cover $P_{\ell }$ set of minimum cardinality in a given graph. This problem is NP-hard for any integer $\ell ⩾2$. The parameterized version of Vertex Cover$P_{\ell }$ problem called $k$-Vertex Cover$P_{\ell }$ asks whether there exists a vertex cover $P_{\ell }$ set of size at most $k$ in the input graph. In this paper, we give two fixed parameter algorithms to solve the $k$-Vertex Cover$P_3$ problem. The first algorithm runs in time $O^1\left(1.7964^k\right)$ in polynomial space and the second algorithm runs in time $O^1\left(1.7485^k\right)$ in exponential space. Both algorithms are faster than previous known fixed-parameter algorithms.     

Inequalities from Poisson brackets

We introduce the notion of tropicalization for Poisson structures on ${\mathbb{R}}^n$ with coefficients in Laurent polynomials. To such a Poisson structure we associate a polyhedral cone and a constant Poisson bracket on this cone. There is a version of this formalism applicable to ${\mathbb{C}}^n$ viewed as a real Poisson manifold. In this case, the tropicalization gives rise to a completely integrable system with action variables taking values in a polyhedral cone and angle variables spanning a torus.As an example, we consider the canonical Poisson bracket on the dual Poisson–Lie group $G^1$ for $G=U\left(n\right)$ in the cluster coordinates of Fomin–Zelevinsky defined by a certain choice of solid minors. We prove that the corresponding integrable system is isomorphic to the Gelfand–Zeitlin completely integrable system of Guillemin–Sternberg and Flaschka–Ratiu.     

On the additive cyclic structure of quasi-cyclic codes

An index $?$, length $m?$ quasi-cyclic code can be viewed as a cyclic code of length $m$ over the field ${\mathbb{F}}_{q^{?}}$ via a basis of the extension ${\mathbb{F}}_{q^{?}}∕{\mathbb{F}}_q$. However, this cyclic code is only linear over ${\mathbb{F}}_q$, making it an additive cyclic code, or an ${\mathbb{F}}_q$-linear cyclic code, over the alphabet ${\mathbb{F}}_{q^{?}}$. This approach was recently used in Shi et al. (2017) [16] to study a class of quasi-cyclic codes, and more importantly in Shi et al. (2017) [17] to settle a long-standing question on the asymptotic performance of cyclic codes. Here, we answer one of the problems posed in these two articles, and characterize those quasi-cyclic codes which have ${\mathbb{F}}_{q^{?}}$-linear cyclic images under a basis of the extension ${\mathbb{F}}_{q^{?}}∕{\mathbb{F}}_q$. Our characterizations are based on the module structure of quasi-cyclic codes, as well as on their CRT decompositions into constituents. In the case of a polynomial basis, we characterize the constituents by using the theory of invariant subspaces of operators. We also observe that analogous results extend to the case of quasi-twisted codes.     

Uniqueness of degree-one Ginzburg–Landau vortex in the unit ball in dimensions N ≥ 7

For $\epsilon >0$, we consider the Ginzburg–Landau functional for ${\mathbb{R}}^N$-valued maps defined in the unit ball $B^N?{\mathbb{R}}^N$ with the vortex boundary data x on $?B^N$. In dimensions $N\ge 7$, we prove that, for every $\epsilon >0$, there exists a unique global minimizer $u_{\epsilon }$ of this problem; moreover, $u_{\epsilon }$ is symmetric and of the form $u_{\epsilon }(x)=f_{\epsilon }(|x|)\frac{x}{|x|}$ for $x\in B^N$.     

Almost split sequences for polynomial GrT-modules and polynomial parts of Auslander–Reiten components

In [8], Doty, Nakano and Peters defined infinitesimal Schur algebras, combining the approach via polynomial representations with the approach via $G_{r}T$-modules to representations of the algebraic group $G={\mathrm{GL}}_n$. We study analogues of these algebras and their Auslander–Reiten theory for reductive algebraic groups G and Borel subgroups B by considering the categories of polynomial representations of $G_{r}T$ and $B_{r}T$ as full subcategories of $\mathrm{mod}{G}_{r}T$ and $\mathrm{mod}{B}_{r}T$, respectively. We show that every component Θ of the stable Auslander–Reiten quiver ${\mathrm{\Gamma }}_s(G_{r}T)$ of $\mathrm{mod}{G}_{r}T$ whose constituents have complexity 1 contains only finitely many polynomial modules. For $G={\mathrm{GL}}_2,r=1$ and $T?G$ the torus of diagonal matrices, we identify the polynomial part of the stable Auslander–Reiten quiver of $G_{r}T$ and use this to determine the Auslander–Reiten quiver of the infinitesimal Schur algebras in this situation. For the Borel subgroup B of lower triangular matrices of ${\mathrm{GL}}_2$, the category of $B_{r}T$-modules is related to representations of elementary abelian groups of rank r. In this case, we can extend our results about modules of complexity 1 to modules of higher Frobenius kernels arising as outer tensor products.