An Optimal Algorithm for the <Emphasis Type="Italic">k</Emphasis>-Fixed-Endpoint Path Cover on Proper Interval Graphs

In this paper we consider the k-fixed-endpoint path cover problem on proper interval graphs, which is a generalization of the path cover problem. Given a graph G and a set T of k vertices, a k-fixed-endpoint path cover of G with respect to T is a set of vertex-disjoint simple paths that covers the vertices of G, such that the vertices of T are all endpoints of these paths. The goal is to compute a k-fixed-endpoint path cover of G with minimum cardinality. We propose an optimal algorithm for this problem with runtime O(n), where n is the number of intervals in G. This algorithm is based on the Stair Normal Interval Representation (SNIR) matrix that characterizes proper interval graphs. In this characterization, every maximal clique of the graph is represented by one matrix element; the proposed algorithm uses this structural property, in order to determine directly the paths in an optimal solution.     

Explicit subspace designs

A subspace design is a collection {H ₁, H ₂, ...,H _M } of subspaces of \(\mathbb{F}_q^m\) with the property that no low-dimensional subspace W of \(\mathbb{F}_q^m\) intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal rate list-decodable codes over constant-sized large alphabets and sub-logarithmic (and even smaller) list size. Subspace designs are the only non-explicit part of their construction. In this paper, we give explicit constructions of subspace designs with parameters close to the probabilistic construction, and this implies the first deterministic polynomial time construction of list-decodable codes achieving the above parameters.Our constructions of subspace designs are natural and easily described, and are based on univariate polynomials over finite fields. Curiously, the constructions are very closely related to certain good list-decodable codes (folded RS codes and univariate multiplicity codes). The proof of the subspace design property uses the polynomial method (with multiplicities): Given a target low-dimensional subspace W, we construct a nonzero low-degree polynomial P _W that has several roots for each H _i that non-trivially intersects W. The construction of P _W is based on the classical Wronskian determinant and the folded Wronskian determinant, the latter being a recently studied notion that we make explicit in this paper. Our analysis reveals some new phenomena about the zeroes of univariate polynomials, namely that polynomials with many structured roots or many high multiplicity roots tend to be linearly independent.     

Rates of decay in the classical Katznelson-Tzafriri theorem

The Katznelson-Tzafriri Theorem states that, given a power-bounded operator T, ∥Tⁿ(I ? T)∥ → 0 as n → ∞ if and only if the spectrum σ(T) of T intersects the unit circle T in at most the point 1. This paper investigates the rate at which decay takes place when σ(T) ∩ T = {1}. The results obtained lead, in particular, to both upper and lower bounds on this rate of decay in terms of the growth of the resolvent operator R(e^iθ, T) as θ → 0. In the special case of polynomial resolvent growth, these bounds are then shown to be optimal for general Banach spaces but not in the Hilbert space case.     

The construction of infinite families of any κ-tight optimal and singular κ-tight optimal directed double loop networks

The double loop network (DLN) is a circulant digraph with n nodes and outdegree 2. It is an important topological structure of computer interconnection networks and has been widely used in the designing of local area networks and distributed systems. Given the number n of nodes, how to construct a DLN which has minimum diameter? This problem has attracted great attention. A related and longtime unsolved problem is for any given non-negative integer k, is there an infinite family of k-tight optimal DLN? In this paper, two main results are obtained (1) for any k ≥ 0, the infinite families of k-tight optimal DLN can be constructed, where the number n(k,e,c) of their nodes is a polynomial of degree 2 in e with integral coefficients containing a parameter c. (2) for any k ≥ 0,an infinite family of singular k-tight optimal DLN can be constructed.     

On Balder’s Existence Theorem for Infinite-Horizon Optimal Control Problems

Balder’s well-known existence theorem (1983) for infinite-horizon optimal control problems is extended to the case in which the integral functional is understood as an improper integral. Simultaneously, the condition of strong uniform integrability (over all admissible controls and trajectories) of the positive part max{f₀, 0} of the utility function (integrand) f₀ is relaxed to the requirement that the integrals of f₀ over intervals [T, T′] be uniformly bounded above by a function ω(T, T′) such that ω(T, T′) → 0 as T, T′→∞. This requirement was proposed by A.V. Dmitruk and N.V. Kuz’kina (2005); however, the proof in the present paper does not follow their scheme, but is instead derived in a rather simple way from the auxiliary results of Balder himself. An illustrative example is also given.     

On <Emphasis Type="Italic">L</Emphasis><Superscript>1</Superscript>-estimates of derivatives of univalent rational functions

We study the growth of the quantity ∫_T|R′(z)|dm(z) for rational functions R of degree n which are bounded and univalent in the unit disk and prove that this quantity can grow like n ^γ , γ > 0, as n → ∞. Some applications of this result to problems of regularity of boundaries of Nevanlinna domains are considered. We also discuss a related result of Dolzhenko, which applies to general (non-univalent) rational functions.     

Bases of identities for semigroups of bounded rank transformations of a set

We complete the series of results by M. V. Sapir, M. V. Volkov and the author solving the Finite Basis Problem for semigroups of rank ≤ k transformations of a set, namely based on these results we prove that the semigroup T _k (X) of rank ≤ k transformations of a set X has no finite basis of identities if and only if k is a natural number and either k = 2 and |X| ∈ «3, 4» or k ≥ 3. A new method for constructing finite non-finitely based semigroups is developed. We prove that the semigroup of rank ≤ 2 transformations of a 4-element set has no finite basis of identities but that the problem of checking its identities is tractable (polynomial).     

Equivalence of two definitions of a generalized <Emphasis Type="Italic">L</Emphasis><Subscript><Emphasis Type="Italic">p</Emphasis></Subscript> solution to the initial-boundary value problem for the wave equation

In our previous papers, we introduced the notion of a generalized solution to the initial-boundary value problem for the wave equation with a boundary function µ(t) such that the integral ∫ ₀ ^T (T ? t)|µ(t)| ^p dt exists. Here we prove that this solution is a unique solution to the problem in L _p that satisfies the corresponding integral identity.     

An FPTAS for minimizing the product of two non-negative linear cost functions

We consider a quadratic programming (QP) problem (Π) of the form min x ^T C x subject to Ax ≥ b, x ≥ 0 where \({C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}\) and \({A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}\) . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and “rounding” the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0–1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.     

Asymptotic <Emphasis Type="Italic">T</Emphasis><Subscript><Emphasis Type="Italic">u</Emphasis></Subscript>-Toeplitzness of weighted composition operators on <Emphasis Type="Italic">H</Emphasis><Superscript>2</Superscript>

Given a unilateral forward shift S acting on a complex, separable, innite dimensional Hilbert space H, an asymptotically S-Toeplitz operator is a bounded linear operator T on H satisfying that {S* ⁿ TS ⁿ } is convergent with respect to one of the topologies commonly used in the algebra of bounded linear operators on H. In this paper, we study the asymptotic T _u -Toeplitzness of weighted composition operators on the Hardy space H², where u is a nonconstant inner function.     

Construction of optimal quadrature formulas for Fourier coefficients in Sobolev space $L_{2}^{(m)}(0,1)$

This paper studies the problem of construction of optimal quadrature formulas in the sense of Sard in the \(L_{2}^{(m)}(0,1)\) space for numerical calculation of Fourier coefficients. Using the S.L.Sobolev’s method, we obtain new optimal quadrature formulas of such type for N+1≥m, where N+1 is the number of nodes. Moreover, explicit formulas for the optimal coefficients are obtained. We study the order of convergence of the optimal formula for the case m=1. The obtained optimal quadrature formulas in the \(L_{2}^{(m)}(0,1)\) space are exact for P _m?1(x), where P _m?1(x) is a polynomial of degree m?1. Furthermore, we present some numerical results, which confirm the obtained theoretical results.     

Similarity Results for Operators of Class <Emphasis Type="Italic">C</Emphasis><Subscript>0</Subscript>

If T is a multiplicity-free contraction of class C ₀ with minimal function m _T , then it is quasisimilar to the Jordan block S(m _T ). In case m _T is a Blaschke product with simple roots forming a Carleson sequence, we show that the relation between T and S(m _T ) can be strengthened to similarity. Under the additional assumption that u(T) has closed range for every inner divisor \({u\in H^\infty}\) of m _T , the result also holds in the more general setting where the roots have bounded multiplicities.     

<Emphasis Type="Italic">T</Emphasis>-Coloring of Certain Networks

Given a graph G and a finite set T of non-negative integers containing zero, a T-coloring of G is a non-negative integer function f defined on V(G) such that \(|f(x)-f(y)|\not \in T\) whenever \((x,y)\in E(G)\). The span of T-coloring is the difference between the largest and smallest colors, and the T-span of G is the minimum span over all T-colorings f of G. The edge span of a T-coloring is the maximum value of \(|f(x)-f(y)|\) over all edges \((x,y)\in E(G)\), and the T-edge span of G is the minimum edge span over all T-colorings f of G. In this paper, we compute T-span and T-edge span of crown graph, circular ladder and mobius ladder, generalized theta graph, series-parallel graph and wrapped butterfly network.     

Elementary Graphs with Respect to <Emphasis Type="Italic">f</Emphasis>-Parity Factors

This note concerns the f-parity subgraph problem, i.e., we are given an undirected graph G and a positive integer value function \({f : V(G) \rightarrow \mathbb{N}}\), and our goal is to find a spanning subgraph F of G with deg _F ≤ f and minimizing the number of vertices x with \({\deg_F(x) \not\equiv f(x) \, {\rm mod} \, {2}}\) . First we prove a Gallai–Edmonds type structure theorem and some other known results on the f-parity subgraph problem, using an easy reduction to the matching problem. Then we use this reduction to investigate barriers and elementary graphs with respect to f-parity factors, where an elementary graph is a graph such that the union of f-parity factors form a connected spanning subgraph.     

Lower bounds for polynomials of many variables

A polynomial P(ξ) = P(ξ₁,..., ξ _n ) is said to be almost hypoelliptic if all its derivatives D ^ν P(ξ) can be estimated from above by P(ξ) (see [16]). By a theorem of Seidenberg-Tarski it follows that for each polynomial P(ξ) satisfying the condition P(ξ) > 0 for all ξ ∈ R ⁿ , there exist numbers σ > 0 and T ∈ R¹ such that P(ξ) ≥ σ(1 + |ξ|) ^T for all ξ ∈ R ⁿ . The greatest of numbers T satisfying this condition, denoted by ST(P), is called Seidenberg-Tarski number of polynomial P. It is known that if, in addition, P ∈ I _n , that is, |P(ξ)| → ∞ as |ξ| → ∞, then T = T(P) > 0. In this paper, for a class of almost hypoelliptic polynomials of n (≥ 2) variables we find a sufficient condition for ST(P) ≥ 1. Moreover, in the case n = 2, we prove that ST(P) ≥ 1 for any almost hypoelliptic polynomial P ∈ I₂.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

<Emphasis Type="Italic">M</Emphasis> <Subscript> <Emphasis Type="Italic">p</Emphasis> </Subscript>-supplemented subgroups of finite groups

A subgroup K of G is M_p-supplemented in G if there exists a subgroup B of G such that G = KB and TB < G for every maximal subgroup T of K with |K: T| = p^α. In this paper we prove the following: Let p be a prime divisor of |G| and let H be ap-nilpotent subgroup having a Sylow p-subgroup of G. Suppose that H has a subgroup D with D_p ≠ 1 and |H: D| = p_α. Then G is p-nilpotent if and only if every subgroup T of H with |T| = |D| is M_p-supplemented in G and N_G(T_p)/C_G(T_p) is a p-group.     

<Emphasis Type="Italic">c</Emphasis>-Semipermutable subgroups of finite groups

A subgroup is called c-semipermutable in G if A has a minimal supplement T in G such that for every subgroup T ₁ of T there is an element x ∈ T satisfying AT ₁ ^x = T ₁ ^x A. We obtain a few results about the c-semipermutable subgroups and use them to determine the structures of some finite groups.     

Approximation of an optimal control problem in coefficient for variational inequality with anisotropic <Emphasis Type="Italic">p</Emphasis>-Laplacian

We study an optimal control problem for a variational inequality with the so-called anisotropic p-Laplacian in the principle part of this inequality. The coefficients of the anisotropic p-Laplacian, the matrix A(x), we take as a control. The optimal control problem is to minimize the discrepancy between a given distribution \({y_d \in L^{2}(\Omega)}\) and the solutions \({y \in K \subset W^{1,p}_{0}(\Omega)}\) of the corresponding variational inequality. We show that the original problem is well-posed and derive existence of optimal pairs. Since the anisotropic p-Laplacian inherits the degeneracy with respect to unboundedness of the term \({|(A(x)\nabla y, \nabla y)_{\mathbb{R}^N}|^{\frac{p-2}{2}}}\), we introduce a two-parameter model for the relaxation of the original problem. Further we discuss the asymptotic behavior of relaxed solutions and show that some optimal pairs to the original problem can be attained by the solutions of two-parametric approximated optimal control problems.     

Inverse problem with nonlocal observation of finding the coefficient multiplying <Emphasis Type="Italic">u</Emphasis> <Subscript> <Emphasis Type="Italic">t</Emphasis> </Subscript> in the parabolic equation

We study the inverse problem of the reconstruction of the coefficient ?(x, t) = ?⁰(x, t) + r(x) multiplying u_t in a nonstationary parabolic equation. Here ?⁰(x, t) ≥ ?⁰ > 0 is a given function, and r(x) ≥ 0 is an unknown function of the class L_∞(Ω). In addition to the initial and boundary conditions (the data of the direct problem), we pose the problem of nonlocal observation in the form ∫₀^Tu(x, t) dμ(t) = χ(x) with a known measure dμ(t) and a function χ(x). We separately consider the case dμ(t) = ω(t)dt of integral observation with a smooth function ω(t). We obtain sufficient conditions for the existence and uniqueness of the solution of the inverse problem, which have the form of ready-to-verify inequalities. We suggest an iterative procedure for finding the solution and prove its convergence. Examples of particular inverse problems for which the assumptions of our theorems hold are presented.