On the asymptotic optimality of a solution of the euclidean problem of covering a graph by <Emphasis Type="Italic">m</Emphasis> nonadjacent cycles of maximum total weight

In the problem of covering an n-vertex graph by m cycles of maximum total weight, it is required to find a family of m vertex-nonadjacent cycles such that it covers all vertices of the graph and the total weight of edges in the cover is maximum. The paper presents an algorithm for approximately solving the problem of covering a graph in Euclidean d-space R^d by m nonadjacent cycles of maximum total weight. The algorithm has time complexity O(n³). An estimate of the accuracy of the algorithm depending on the parameters d, m, and n is substantiated; it is shown that if the dimension d of the space is fixed and the number of covering cycles is m = o(n), then the algorithm is asymptotically exact.     

A boundary Schwarz lemma on the classical domain of type <Emphasis Type="Italic">I</Emphasis>

Let R _I (m, n) be the classical domain of type I in ? ^m×n with 1 ≤ m ≤ n. We obtain the optimal estimates of the eigenvalues of the Fréchet derivative Df(\(\mathop Z\limits^ \circ \)) at a smooth boundary fixed point \(\mathop Z\limits^ \circ \)of R _I (m, n) for a holomorphic self-mapping f of R _I (m, n). We provide a necessary and sufficient condition such that the boundary points of R _I (m, n) are smooth, and give some properties of the smooth boundary points of R _I (m, n). Our results extend the classical Schwarz lemma at the boundary of the unit disk Δ to R _I (m, n), which may be applied to get some optimal estimates in several complex variables.     

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K _n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r ^(1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K _n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).     

Description of polygonal regions by polynomials of bounded degree

We show that every (possibly unbounded) convex polygon P in \({\mathbb{R}^2}\) with m edges can be represented by inequalities p ₁ ≥ 0, . . ., p _n ≥ 0, where the p _i ’s are products of at most k affine functions each vanishing on an edge of P and n = n(m, k) satisfies \({s(m, k) \leq n(m, k) \leq (1+\varepsilon_m) s(m, k)}\) with s(m,k) ? max {m/k, log₂ m} and \({\varepsilon_m \rightarrow 0}\) as \({m \rightarrow \infty}\). This choice of n is asymptotically best possible. An analogous result on representing the interior of P in the form p ₁ > 0, . . ., p _n >  0 is also given. For k ≤ m/log₂ m these statements remain valid for representations with arbitrary polynomials of degree not exceeding k.     

Abelian covers of graphs and maps between outer automorphism groups of free groups

We explore the existence of homomorphisms between outer automorphism groups of free groups Out(F _n ) → Out(F _m ). We prove that if n > 8 is even and n ≠ m ≤ 2n, or n is odd and n ≠ m ≤ 2n ? 2, then all such homomorphisms have finite image; in fact they factor through det : \({{\rm Out}(F_n) \to \mathbb{Z}/2}\) . In contrast, if m = r ⁿ (n ? 1) + 1 with r coprime to (n ? 1), then there exists an embedding \({{\rm Out}(F_n) \hookrightarrow {\rm Out}(F_m)}\) . In order to prove this last statement, we determine when the action of Out(F _n ) by homotopy equivalences on a graph of genus n can be lifted to an action on a normal covering with abelian Galois group.     

Multiple recurrence and convergence for hardy sequences of polynomial growth

We study the limiting behavior of multiple ergodic averages involving sequences of integers that satisfy some regularity conditions and have polynomial growth. We show that for “typical” choices of Hardy field functions a(t) with polynomial growth, the averages

${1 \over N}\sum\nolimits_{n = 1}^N {{f_1}({T^{[a(n)]}}x) \cdots {f_\ell }({T^{\ell [a(n)]}}x)} $

converge in mean and we determine their limit. For example, this is the case if a(t) = t ^3/2, t log t, or t ² + (log t)². Furthermore, if {a ₁(t), …, a _? (t)} is a “typical” family of logarithmico-exponential functions of polynomial growth, then for every ergodic system, the averages

${1 \over N}\sum\nolimits_{n = 1}^N {{f_1}({T^{[{a_1}(n)]}}x) \cdots {f_\ell }({T^{[{a_\ell }(n)]}}x)} $

converge in mean to the product of the integrals of the corresponding functions. For example, this is the case if the functions a _i (t) are given by different positive fractional powers of t. We deduce several results in combinatorics. We show that if a(t) is a non-polynomial Hardy field function with polynomial growth, then every set of integers with positive upper density contains arithmetic progressions of the form {m,m + [a(n)], …, m + ?[a(n)]}. Under suitable assumptions, we get a related result concerning patterns of the form {m,m + [a ₁(n)], …,m + [a _? (n)]}.

     

Some irreducibility and indecomposability results for truncated binomial polynomials of small degree

In this paper, we show that the truncated binomial polynomials defined by \(P_{n,k}(x)={\sum }_{j=0}^{k} {n \choose j} x^{j}\) are irreducible for each k≤6 and every n≥k+2. Under the same assumption n≥k+2, we also show that the polynomial P _n,k cannot be expressed as a composition P _n,k (x) = g(h(x)) with \(g \in \mathbb {Q}[x]\) of degree at least 2 and a quadratic polynomial \(h \in \mathbb {Q}[x]\). Finally, we show that for k≥2 and m,n≥k+1 the roots of the polynomial P _m,k cannot be obtained from the roots of P _n,k , where m≠n, by a linear map.     

Harmonic analysis associated with a discrete Laplacian

It is well known that the fundamental solution of

$${u_t}\left( {n,t} \right) = u\left( {n + 1,t} \right) - 2u\left( {n,t} \right) + u\left( {n - 1,t} \right),n \in \mathbb{Z},$$

with u(n, 0) = δ _nm for every fixed m ∈ Z is given by u(n, t) = e ^?2t I _n?m (2t), where I _k (t) is the Bessel function of imaginary argument. In other words, the heat semigroup of the discrete Laplacian is described by the formal series W _t f(n) = Σ _m∈Z e ^?2t I _n?m (2t)f(m). This formula allows us to analyze some operators associated with the discrete Laplacian using semigroup theory. In particular, we obtain the maximum principle for the discrete fractional Laplacian, weighted ? ^p (Z)-boundedness of conjugate harmonic functions, Riesz transforms and square functions of Littlewood-Paley. We also show that the Riesz transforms essentially coincide with the so-called discrete Hilbert transform defined by D. Hilbert at the beginning of the twentieth century. We also see that these Riesz transforms are limits of the conjugate harmonic functions. The results rely on a careful use of several properties of Bessel functions.

     

The knaster problem: More counterexamples

Given a continuous function\(f:\mathbb{S}^{n - 1} \to \mathbb{R}^m \) andn ?m + 1 pointsp ₁, …,p _{n?m + 1} ε\(p_1 ,...,p_{n - m + 1} \in \mathbb{S}^{n - 1} \), does there exist a rotation ? εSO(n) such thatf(?(p ₁)) = … =f(?(p _n?m+1))? We give a negative answer to this question form = 1 ifn ε {61, 63, 65} orn≥67 and form=2 ifn≥5.     

An extended class of stabilizable uncertain systems

The system of equations \(\frac{{dx}}{{dt}} = A\left( \cdot \right)x + B\left( \cdot \right)u\), where A(·) ∈ ?^{n × n}, B(·) ∈ ?^{n × m}, S(·) ∈ R^{n × m}, is considered. The elements of the matrices A(·), B(·), S(·) are uniformly bounded and are functionals of an arbitrary nature. It is assumed that there exist k elements \({\alpha _{{i_i}{j_l}}}\left( \cdot \right)\left( {l \in \overline {1,k} } \right)\) of fixed sign above the main diagonal of the matrix A(·), and each of them is the only significant element in its row and column. The other elements above the main diagonal are sufficiently small. It is assumed that m = n ?k, and the elements β_ij(·) of the matrix B(·) possess the property \(\left| {{\beta _{{i_s}s}}\left( \cdot \right)} \right| = {\beta _0} > 0\;at\;{i_s}\; \in \;\overline {1,n} \backslash \left\{ {{i_1}, \ldots ,{i_k}} \right\}\). The other elements of the matrix B(·) are zero. The positive definite matrix H = {h_ij} of the following form is constructed. The main diagonal is occupied by the positive numbers h_ii = h_i, \({h_{{i_l}}}_{{j_l}}\, = \,{h_{{j_l}{i_l}}}\, = \, - 0.5\sqrt {{h_{{i_l}}}_{{j_l}}} \,\operatorname{sgn} \,{\alpha _{{i_l}}}_{{j_l}}\left( \cdot \right)\). The other elements of the matrix H are zero. The analysis of the derivative of the Lyapunov function V(x) = x*H^–1x yields h_i\(\left( {i \in \overline {1,n} } \right)\) and λ_i ≤ 0 \(\left( {i \in \overline {1,n} } \right)\) such that for S(·) = H^?1ΛB(·), Λ = diag(λ₁, ..., λ_n), the system of the considered equations becomes globally exponentially stable. The control is robust with respect to the elements of the matrix A(·).     

A note on Jeśmanowicz’ conjecture

Je?manowicz [9] conjectured that, for positive integers m and n with m > n, gcd(m,n) = 1 and \({m\not\equiv n\pmod{2}}\), the exponential Diophantine equation \({(m^2-n^2)^x+(2mn)^y=(m^2+n^2)^z}\) has only the positive integer solution (x, y, z) = (2, 2, 2). We prove the conjecture for \({2 \| mn}\) and m + n has a prime factor p with \({p\not\equiv1\pmod{16}}\).     

On the extremal distance between two convex bodies

We consider the following modified version of the Banach-Mazur distance of convex bodies in \(\mathbb{R}^n :d\left( {K,L} \right) = \inf \left\{ {\left| \lambda \right|:\lambda \in \mathbb{R},\tilde K \subset \tilde L \subset \lambda \tilde K} \right\}\), where the infimum is taken over all non-degenerate affine images \(\tilde K\) and \(\tilde L\) of K and L. Gordon, Litvak, Meyer and Pajor in 2004 showed that for any two convex bodies d(K,L) ≤ n, moreover, if K is a simplex and L = ?L then d(K,L) = n. The following question arises naturally: Is equality only attained when one of the sets is a simplex? Leichtweiss in 1959, and later Palmon in 1992 proved that if d(K,B ₂ ⁿ ) = n, where B ₂ ⁿ is the Euclidean ball, then K is the simplex. We prove the affirmative answer to the question in the case when one of the bodies is strictly convex or smooth, thus obtaining a generalization of the result of Leichtweiss and Palmon.     

Stability of uncertain discrete systems

The uncertain system

$x_{n + 1} = A_n x_n , n = 0,1,2, \ldots ,$

is considered, where the coefficients a _ij (n) of the m×m matrix A _n are functionals of any nature subject to the constraints

$\begin{array}{*{20}c} {\left| {a_{i,i} (n)} \right| \leqslant \alpha _ * < 1,} \\ {\left| {a_{i,j} (n)} \right| \leqslant \alpha _0 for j \geqslant i + 1,} \\ {\left| {a_{i,j} (n)} \right| \leqslant \delta for j < i.} \\ \end{array} $

Such systems include, in particular, switched-type systems, whose matrix A can take values in a given finite set.By using a special Lyapunov function, a bound δ ≤ δ(α₀,α_*) ensuring the global asymptotic stability of the system is found. In particular, the system is stable if the last inequality is replaced by a _i,j (n) = 0 for j < i.It is shown that pulse-width modulated systems reduce to the uncertain systems under consideration; moreover, in the case of a pulse-width modulation of the first kind, the coefficients of the matrix A are functions of x(n), and in the case of a modulation of the second kind, they are functionals.     

Estimates for sums of moduli of blocks in trigonometric Fourier series

We consider the following two problems. Problem 1: what conditions on a sequence of finite subsets A _k ? ? and a sequence of functions λ _k : A _k → ? provide the existence of a number C such that any function f ∈ L ₁ satisfies the inequality ‖U _A,Λ(f)‖ _p ≤ C‖f‖₁ and what is the exact constant in this inequality? Here, \(U_{\mathcal{A},\Lambda } \left( f \right)\left( x \right) = \sum\nolimits_{k = 1}^\infty {\left| {\sum\nolimits_{m \in A_k } {\lambda _k \left( m \right)c_m \left( f \right)e^{imx} } } \right|}\) and c _m (f) are Fourier coefficients of the function f ∈ L ₁. Problem 2: what conditions on a sequence of finite subsets A _k ? ? guarantee that the function \(\sum\nolimits_{k = 1}^\infty {\left| {\sum\nolimits_{m \in A_k } {c_m \left( h \right)e^{imx} } } \right|}\) belongs to L _p for every function h of bounded variation?     

Dynamic control for non-linear systems with delay

We consider some class of non-linear systems of the form

$\dot x = A( \cdot )x + \sum\limits_{i = 1}^l {A_i ( \cdot )x(t - \tau _i (t)) + b( \cdot )u} ,$

where A(·) ∈ ? ^{n × n} , A _i (·) ∈ ? ^{n × n} , b(·) ∈ ? ⁿ , whose coefficients are arbitrary uniformly bounded functionals.

A special type of the Lyapunov-Krasovskii functional is used to synthesize dynamic control described by the equation

$\dot u = \rho ( \cdot )u + (m( \cdot ),x),$

where ρ(·) ∈ ?¹, m(·) ∈ ? ⁿ , which makes the system globally asymptotically stable. Also, the situation is considered where the control u enters into the system not directly but through a pulse element performing an amplitude-frequency modulation.

     

Multiset combinatorial batch codes

Batch codes, first introduced by Ishai, Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set of n data items on m servers, in such a way that any batch of k data items can be retrieved by reading at most some t symbols from each server. Combinatorial batch codes, are replication-based batch codes in which each server stores a subset of the data items. In this paper, we propose a generalization of combinatorial batch codes, called multiset combinatorial batch codes (MCBC), in which n data items are stored in m servers, such that any multiset request of k items, where any item is requested at most r times, can be retrieved by reading at most t items from each server. The setup of this new family of codes is motivated by recent work on codes which enable high availability and parallel reads in distributed storage systems. The main problem under this paradigm is to minimize the number of items stored in the servers, given the values of n, m, k, r, t, which is denoted by N(n, k, m, t; r). We first give a necessary and sufficient condition for the existence of MCBCs. Then, we present several bounds on N(n, k, m, t; r) and constructions of MCBCs. In particular, we determine the value of N(n, k, m, 1; r) for any \(n\ge \left\lfloor \frac{k-1}{r}\right\rfloor {m\atopwithdelims ()k-1}-(m-k+1)A(m,4,k-2)\), where \(A(m,4,k-2)\) is the maximum size of a binary constant weight code of length m, distance four and weight \(k-2\). We also determine the exact value of N(n, k, m, 1; r) when \(r\in \{k,k-1\}\) or \(k=m\).     

Almost everywhere divergence of lacunary subsequences of partial sums of fourier series

If an increasing sequence {n _m } of positive integers and a modulus of continuity ω satisfy the condition Σ _m=1 ^∞ ω(1/n _m )/m < ∞, then it is known that the subsequence of partial sums \(S_{n_m } \left( {f,x} \right)\) converges almost everywhere to f(x) for any function f ∈ H ₁ ^ω . We show that this sufficient convergence condition is close to a necessary condition for a lacunary sequence {n _m }.     

Modified boundary element method for problems on oscillations of flat membranes

In the space L ² of real-valued measurable 2π-periodic functions that are square summable on the period [0, 2π], the Jackson-Stechkin inequality

$$E_n (f) \leqslant \mathcal{K}_n (\delta ,\omega )\omega (\delta ,f), f \in L^2 $$

, is considered, where E _n (f) is the value of the best approximation of the function f by trigonometric polynomials of order at most n and ω(δ, f) is the modulus of continuity of the function f in L ² of order 1 or 2. The value

$$\mathcal{K}_n (\delta ,\omega ) = \sup \left\{ {\frac{{E_n (f)}}{{\omega (\delta ,f)}}:f \in L^2 } \right\}$$

is found at the points δ = 2π/m (where m ∈ ?) for m ≥ 3n ² + 2 and ω = ω ₁ as well as for m ≥ 11n ⁴/3 ? 1 and ω = ω ₂.

     

On a functional equation related to derivations in prime rings

In this paper we prove the following result. Let m ≥ 1, n ≥ 1 be fixed integers and let R be a prime ring with m + n + 1 ≤ char(R) or char(R) = 0. Suppose there exists an additive nonzero mapping D : R → R satisfying the relation 2D(x ^n+m+1) = (m + n + 1)(x ^m D(x)x ⁿ + x ⁿ D(x)x ^m ) for all \({x\in R}\). In this case R is commutative and D is a derivation.