The Morse–Sard theorem for Clarke critical values

The Morse–Sard theorem states that the set of critical values of a C^k$C^k$ smooth function defined on a Euclidean space R^d${\mathbb{R}}^d$ has Lebesgue measure zero, provided k≥d$k\ge d$. This result is hereby extended for (generalized) critical values of continuous selections over a compactly indexed countable family of C^k$C^k$ functions: it is shown that these functions are Lipschitz continuous and the set of their Clarke critical values is null.     

Asymptotic average shadowing property on compact metric spaces

We prove that if for a continuous map f$f$ on a compact metric space X$X$, the chain recurrent set, R(f)$R\left(f\right)$ has more than one chain component, then f$f$ does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f$f$ on a compact metric space X$X$ has the asymptotic average shadowing property and if A$A$ is an attractor for f$f$, then A$A$ is the single attractor for f$f$ and we have A=R(f)$A=R\left(f\right)$. We also study diffeomorphisms with asymptotic average shadowing property and prove that if M$M$ is a compact manifold which is not finite with dimM=2$dimM=2$, then the C¹$C^1$ interior of the set of all C¹$C^1$ diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω$\Omega$-stable diffeomorphisms.     

An upper bound for a valence of a face in a parallelohedral tiling

Consider a face-to-face parallelohedral tiling of R^d${\mathbb{R}}^d$ and a (d−k)$(d-k)$-dimensional face F$F$ of the tiling. We prove that the valence of F$F$ (i.e. the number of tiles containing F$F$ as a face) is not greater than 2^k$2^k$. If the tiling is affinely equivalent to a Voronoi tiling for some lattice (the so called Voronoi case), this gives a well-known upper bound for the number of vertices of a Delaunay k$k$-cell. Yet we emphasize that such an affine equivalence is not assumed in the proof.     

Uniqueness of the Cheeger set of a convex body

We prove that if C⊂R^N$C\subset {\mathbb{R}}^N$ is an open bounded convex set, then there is only one Cheeger set inside C$C$ and it is convex. A Cheeger set of C$C$ is a set which minimizes the ratio perimeter over volume among all subsets of C$C$.     

Physical measures and absolute continuity for one-dimensional center direction

For a class of partially hyperbolic C^k$C^k$, k>1$k>1$ diffeomorphisms with circle center leaves we prove the existence and finiteness of physical (or Sinai–Ruelle–Bowen) measures, whose basins cover a full Lebesgue measure subset of the ambient manifold. Our conditions hold for an open and dense subset of all C^k$C^k$ partially hyperbolic skew-products on compact circle bundles.     

On words that are concise in residually finite groups

A group-word w$w$ is called concise if whenever the set of w$w$-values in a group G$G$ is finite it always follows that the verbal subgroup w(G)$w\left(G\right)$ is finite. More generally, a word w$w$ is said to be concise in a class of groups X$X$ if whenever the set of w$w$-values is finite for a group G∈X$G\in X$, it always follows that w(G)$w\left(G\right)$ is finite. P. Hall asked whether every word is concise. Due to Ivanov the answer to this problem is known to be negative. Dan Segal asked whether every word is concise in the class of residually finite groups. In this direction we prove that if w$w$ is a multilinear commutator and q$q$ is a prime-power, then the word w^q$w^q$ is indeed concise in the class of residually finite groups. Further, we show that in the case where w=_γk$w={\gamma }_k$ the word w^q$w^q$ is boundedly concise in the class of residually finite groups. It remains unknown whether the word w^q$w^q$ is actually concise in the class of all groups.     

Stable extendibility of vector bundles over real projective spaces

Let F$\mathbb{F}$ be either the real number field R$\mathbb{R}$ or the complex number field C$\mathbb{C}$ and RPⁿ${\mathbb{RP}}^n$ the real projective space of dimension n. Theorems A and C in Hemmi and Kobayashi (2008) [2] give necessary and sufficient conditions for a given F$\mathbb{F}$-vector bundle over RPⁿ${\mathbb{RP}}^n$ to be stably extendible to RP^m${\mathbb{RP}}^m$ for every m?n$m?n$. In this paper, we simplify the theorems and apply them to the tangent bundle of RPⁿ${\mathbb{RP}}^n$, its complexification, the normal bundle associated to an immersion of RPⁿ${\mathbb{RP}}^n$ in R^n+r${\mathbb{R}}^{n+r}$(r>0)$(r>0)$, and its complexification. Our result for the normal bundle is a generalization of Theorem A in Kobayashi et al. (2000) [8] and that for its complexification is a generalization of Theorem 1 in Kobayashi and Yoshida (2003) [5].     

Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs

We say that a hypergraph H$H$ is hamiltonian chain saturated if H$H$ does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H$H$. In this paper, for each k≥3$k\ge 3$, we establish the right order of magnitude n^k−1$n^{k-1}$ for the size of the smallest k$k$-uniform hamiltonian chain saturated hypergraph. This solves an open problem of G.Y. Katona.     

Weak convergence of censored and reflected stable processes

It is shown that if a sequence of open n$n$-sets _Dk$D_k$ increases to an open n$n$-set D$D$ then reflected stable processes in _Dk$D_k$ converge weakly to the reflected stable process in D$D$ for every starting point x$x$ in D$D$. The same result holds for censored α$\alpha$-stable processes for every x$x$ in D$D$ if D$D$ and _Dk$D_k$ satisfy the uniform Hardy inequality. Using the method in the proof of the above results, we also prove the weak convergence of reflected Brownian motions in unbounded domains.     

Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.     

On the sum of two closed subspaces

If U,V$U,V$ are closed subspaces of a Fréchet space, then E$E$ is the direct sum of U$U$ and V$V$ if and only if E^′$E^{\prime }$ is the algebraic direct sum of the annihilators U^°$U^{°}$ and V^°$V^{°}$. We provide a simple proof of this (possibly well-known) result.     

Feedback vertex set on graphs of low clique-width

The Feedback Vertex Set problem asks whether a graph contains q$q$ vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if q$q$ vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph G$G$ of clique-width cw$cw$ and a cw$cw$-expression of G$G$, we solve the Minimum Feedback Vertex Set problem in time O(n²2^O(cwlogcw))$O\left(n^2{2}^{O(cwlogcw)}\right)$. Our algorithm applies dynamic programming on a so-called k$k$-module decomposition of a graph, as defined by Rao (2008) [29], which is easily derivable from ak$k$-expression of the graph. The related notion of module-width of a graph is tightly linked to both clique-width and NLC-width, and in this paper we give an alternative equivalent characterization of module-width.     

Partial rigidity of degenerate CR embeddings into spheres

In this paper, we study degenerate CR embeddings f$f$ of a strictly pseudoconvex hypersurface M⊂Cⁿ⁺¹$M\subset {\mathbb{C}}^{n+1}$ into a sphere S$\mathbb{S}$ in a higher dimensional complex space C^N+1${\mathbb{C}}^{N+1}$. The degeneracy of the mapping f$f$ will be characterized in terms of the ranks of the CR second fundamental form and its covariant derivatives. In 2004, the author, together with X. Huang and D. Zaitsev, established a rigidity result for CR embeddings f$f$ into spheres in low codimensions. A key step in the proof of this result was to show that degenerate mappings are necessarily contained in a complex plane section of the target sphere (partial rigidity). In the 2004 paper, it was shown that if the total rank d$d$ of the second fundamental form and all of its covariant derivatives is <n$<n$ (here, n$n$ is the CR dimension of M$M$), then f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$. The converse of this statement is also true, as is easy to see. When the total rank d$d$ exceeds n$n$, it is no longer true, in general, that f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$, as can be seen by examples. In this paper, we carry out a systematic study of degenerate CR mappings into spheres. We show that when the ranks of the second fundamental form and its covariant derivatives exceed the CR dimension n$n$, then partial rigidity may still persist, but there is a “defect” k$k$ that arises from the ranks exceeding n$n$ such that f(M)$f\left(M\right)$ is only contained in a complex plane of dimension n+d+k+1$n+d+k+1$. Moreover, this defect occurs in general, as is illustrated by examples.     

Oscillation of harmonic functions for subordinate Brownian motion and its applications

In this paper, we establish an oscillation estimate of nonnegative harmonic functions for a pure-jump subordinate Brownian motion. The infinitesimal generator of such subordinate Brownian motion is an integro-differential operator. As an application, we give a probabilistic proof of the following form of relative Fatou theorem for such subordinate Brownian motion X$X$ in a bounded κ$\kappa$-fat open set; if u$u$ is a positive harmonic function with respect to X$X$ in a bounded κ$\kappa$-fat open set D$D$ and h$h$ is a positive harmonic function in D$D$ vanishing on D^c$D^c$, then the non-tangential limit of u/h$u/h$ exists almost everywhere with respect to the Martin-representing measure of h$h$.     

A new upper bound on the acyclic chromatic indices of planar graphs

An acyclic edge coloring of a graph G$G$ is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a^′(G)$a^{\prime }\left(G\right)$ of G$G$ is the smallest integer k$k$ such that G$G$ has an acyclic edge coloring using k$k$ colors. It was conjectured that a^′(G)≤Δ+2$a^{\prime }\left(G\right)\le \Delta +2$ for any simple graph G$G$ with maximum degree Δ$\Delta$. In this paper, we prove that if G$G$ is a planar graph, then a^′(G)≤Δ+7$a^{\prime }\left(G\right)\le \Delta +7$. This improves a result by Basavaraju et al. [M. Basavaraju, L.S. Chandran, N. Cohen, F. Havet, T. Müller, Acyclic edge-coloring of planar graphs, SIAM J. Discrete Math. 25 (2011) 463–478], which says that every planar graph G$G$ satisfies a^′(G)≤Δ+12$a^{\prime }\left(G\right)\le \Delta +12$.     

Universal polynomials for Severi degrees of toric surfaces

The Severi variety parameterizes plane curves of degree d$d$ with δ$\delta$ nodes. Its degree is called the Severi degree. For large enough d$d$, the Severi degrees coincide with the Gromov–Witten invariants of CP²$\mathbb{C}{\mathbb{P}}^2$. Fomin and Mikhalkin (2010) [10] proved the 1995 conjecture that for fixed δ$\delta$, Severi degrees are eventually polynomial in d$d$.     

Cone isomorphisms and almost surjective operators

Let E$E$ be a Banach lattice and F$F$ a Banach space. A bounded linear operator T:E→F$T:E\to F$ is an isomorphism on the positive cone of E$E$ if and only if T^∗$T^{\ast }$ is almost surjective. A dual version of this theorem holds also. A bounded linear operator T:F→E$T:F\to E$ is almost surjective if and only if T^∗$T^{\ast }$ is an isomorphism on the positive cone of F^∗$F^{\ast }$.     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.