Nonlinear Schrödinger equation for the twisted Laplacian in the critical case

In [6] and [7], we prove well-posedness of solution to the nonlinear Schrödinger equation associated to the twisted Laplacian on ? ⁿ for a general class of nonlinearities including power type with subcritical case 0 ≤ α < 2/n?1. In this paper, we consider the critical case α = 2/n?1 with n ≥ 2. Our approach is based on truncation of the given nonlinearity G, which is used in [3]. We obtain solution for the truncated problem. We obtain solution to the original problem by passing to the limit.     

Minimal <Emphasis Type="Italic">P</Emphasis>-symmetric period problem of first-order autonomous Hamiltonian systems

Let P ∈ Sp(2n) satisfying P ^k = I _2n . We consider the minimal P-symmetric period problem of the autonomous nonlinear Hamiltonian system \(\dot x\left( t \right) = JH'\left( {x\left( t \right)} \right)\). For some symplectic matrices P, we show that for any τ > 0, the above Hamiltonian system possesses a kτ periodic solution x with kτ being its period provided H satis Fies Rabinowitz's conditions on the minimal minimal P-symmetric period conjecture, together with that H is convex and H(Px) = H(x).     

Note edge-colourings of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">n,n</Emphasis></Subscript> with no long two-coloured cycles

Consider the set of all proper edge-colourings of a graph G with n colours. Among all such colourings, the minimum length of a longest two-coloured cycle is denoted L(n, G). The problem of understanding L(n, G) was posed by Häggkvist in 1978 and, specifically, L(n, K _n,n ) has received recent attention. Here we construct, for each prime power q ≥ 8, an edge-colouring of K _n,n with n colours having all two-coloured cycles of length ≤ 2q ², for integers n in a set of density 1 ? 3/(q ? 1). One consequence is that L(n, K _n,n ) is bounded above by a polylogarithmic function of n, whereas the best known general upper bound was previously 2n ? 4.     

Due-date assignment with asymmetric earliness–tardiness cost

The problem of minimizing the maximal weighted absolute lateness (MWAL) is known to be NP-hard. The due-date assignment part of MWAL for a given sequence has been shown in the literature to be solved on a single machine in O(n²) time. In this paper, we study a more general version of the problem with asymmetric cost (nonidentical earliness and tardiness weights). We introduce a linear-programming-based O(n) solution for this case. We also extend our proposed solution procedure to other machine settings such as flow-shop and parallel machines.     

On a new property of <Emphasis Type="Italic">n</Emphasis>-poised and <Emphasis Type="Italic">G</Emphasis><Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> sets

In this paper we consider n-poised planar node sets, as well as more special ones, called G C _n sets. For the latter sets each n-fundamental polynomial is a product of n linear factors as it always holds in the univariate case. A line ? is called k-node line for a node set \(\mathcal X\) if it passes through exactly k nodes. An (n + 1)-node line is called maximal line. In 1982 M. Gasca and J. I. Maeztu conjectured that every G C _n set possesses necessarily a maximal line. Till now the conjecture is confirmed to be true for n ≤ 5. It is well-known that any maximal line M of \(\mathcal X\) is used by each node in \(\mathcal X\setminus M, \)meaning that it is a factor of the fundamental polynomial. In this paper we prove, in particular, that if the Gasca-Maeztu conjecture is true then any n-node line of G C _n set \(\mathcal {X}\) is used either by exactly \(\binom {n}{2}\) nodes or by exactly \(\binom {n-1}{2}\) nodes. We prove also similar statements concerning n-node or (n ? 1)-node lines in more general n-poised sets. This is a new phenomenon in n-poised and G C _n sets. At the end we present a conjecture concerning any k-node line.     

Mappings of preserving <Emphasis Type="Italic">n</Emphasis>-distance one in <Emphasis Type="Italic">n</Emphasis>-normed spaces

We give a positive answer to the Aleksandrov problem in n-normed spaces under the surjectivity assumption. Namely, we show that every surjective mapping preserving n-distance one is affine, and thus is an n-isometry. This is the first time the Aleksandrov problem is solved in n-normed spaces with only the surjectivity assumption even in the usual case \(n=2\). Finally, when the target space is n-strictly convex, we prove that every mapping preserving two n-distances with an integer ratio is an affine n-isometry.     

A unified approach to singular problems arising in the membrane theory

We consider the singular boundary value problem \(({t^n}u't))' + {t^n}f(t,u(t)) = 0,{\rm{ }}\mathop {\lim }\limits_{t \to 0 + } {t^n}u'(t) = 0,{\rm{ }}{a_0}u(1) + {a_1}u'(1 - ) = A,\) where f(t, x) is a given continuous function defined on the set (0, 1]×(0,∞) which can have a time singularity at t = 0 and a space singularity at x = 0. Moreover, n ∈ ?, n ? >2, and a ₀, a ₁, A are real constants such that a ₀ ∈ (0,1), whereas a ₁,A ∈ [0,∞). The main aim of this paper is to discuss the existence of solutions to the above problem and apply the general results to cover certain classes of singular problems arising in the theory of shallow membrane caps, where we are especially interested in characterizing positive solutions. We illustrate the analytical findings by numerical simulations based on polynomial collocation.     

Asymptotic expansions of periodic solutions of ordinary differential equations with large high-frequency terms

We consider the problem on the periodic solutions of a system of ordinary differential equations of arbitrary order n containing terms oscillating at a frequency ω ? 1 with coefficients of the order of ω ^n/2. For this problem, we construct the averaged (limit) problem and justify the averaging method as well as another efficient algorithm for constructing the complete asymptotics of the solution.     

Exponentially Many Monochromatic <Emphasis Type="Italic">n</Emphasis>-Matchings in <Emphasis Type="Italic">K</Emphasis><Subscript>3<Emphasis Type="Italic">n</Emphasis>-1</Subscript>

Erdös et al and Gerencsér et al had shown that in any 2-edge-coloring of K _3n-1, there is a n-matching containing edges with the same color(we call such matching monochromatic matching). In this paper we show that for any 2-edge-coloring of K _3n-1 there exists a monochromatic subgraph H of K _3n-1 which contains exponentially many monochromatic n-matchings.     

Arithmetic Progressions in Linear Combinations of <Emphasis Type="Italic">S</Emphasis>-Units

M. Pohst asked the following question: is it true that every prime can be written in the form 2^u ± 3^v with some non-negative integers u, v? We put the problem into a general framework, and prove that the length of any arithmetic progression in t-term linear combinations of elements from a multiplicative group of rank r (e.g. of S-units) is bounded in terms of r, t, n, where n is the number of the coefficient t-tuples of the linear combinations. Combining this result with a recent theorem of Green and Tao on arithmetic progressions of primes, we give a negative answer to the problem of M. Pohst.     

The problem of a minimal ball enclosing <Emphasis Type="Italic">k</Emphasis> points

Under study is the problem of finding a ball of minimal radius enclosing at least k points of a given finite set in a Euclidean space. In the case of a fixed dimension of the space this problem is polynomially solvable, but in general its complexity has not been previously determined. We prove that the problem is NP-hard in the strong sense and obtain a polynomial-time approximation scheme (PTAS) that enables us to solve the problem with an arbitrary relative error ? in time \(O(n^{1/\varepsilon ^2 + 1} d)\), where n is the cardinality of the original set and d is the space dimension.     

Radar placement along banks of river

In this paper, we consider the Radar Placement and Power Assignment problem (RPPA) along a river. In this problem, a set of crucial points in the river are required to be monitored by a set of radars which are placed along the two banks. The goal is to choose the locations for the radars and assign powers to them such that all the crucial points are monitored and the total power is minimized. If each crucial point is required to be monitored by at least k radars, the problem is a k-Coverage RPPA problem (k-CRPPA). Under the assumption that the river is sufficiently smooth, one may focus on the RPPA problem along a strip (RPPAS). In this paper, we present an O(n ⁹) dynamic programming algorithm for the RPPAS, where n is the number of crucial points to be monitored. In the special case where radars are placed only along the upper bank, we present an O(kn ⁵) dynamic programming algorithm for the k-CRPPAS. For the special case that the power is linearly dependent on the radius, we present an O(n log n)-time \({2\sqrt 2}\)-approximation algorithm for the RPPAS.     

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.     

An approximation algorithm for finding a <Emphasis Type="Italic">d</Emphasis>-regular spanning connected subgraph of maximum weight in a complete graph with random weights of edges

An approximation algorithm is suggested for the problem of finding a d-regular spanning connected subgraph of maximum weight in a complete undirected weighted n-vertex graph. Probabilistic analysis of the algorithm is carried out for the problem with random input data (some weights of edges) in the case of a uniform distribution of the weights of edges and in the case of a minorized type distribution. It is shown that the algorithm finds an asymptotically optimal solution with time complexity O(n ²) when d = o(n). For the minimization version of the problem, an additional restriction on the dispersion of weights of the graph edges is added to the condition of the asymptotical optimality of the modified algorithm.     

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.     

The optimal solution set of the interval linear programming problems

Several methods exist for solving the interval linear programming (ILP) problem. In most of these methods, we can only obtain the optimal value of the objective function of the ILP problem. In this paper we determine the optimal solution set of the ILP as the intersection of some regions, by the best and the worst case (BWC) methods, when the feasible solution components of the best problem are positive. First, we convert the ILP problem to the convex combination problem by coefficients 0 ≤ λ _j , μ _ij , μ _i  ≤ 1, for i = 1, 2, . . . , m and j = 1, 2, . . . , n. If for each i, j, μ _ij  = μ _i  = λ _j  = 0, then the best problem has been obtained (in case of minimization problem). We move from the best problem towards the worst problem by tiny variations of λ _j , μ _ij and μ _i from 0 to 1. Then we solve each of the obtained problems. All of the optimal solutions form a region that we call the optimal solution set of the ILP. Our aim is to determine this optimal solution set by the best and the worst problem constraints. We show that some theorems to validity of this optimal solution set.     

Super (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis>)-edge-antimagic total labelings of complete bipartite graphs

An (a, d)-edge-antimagic total labeling of a graph G is a bijection f from V(G) ∪ E(G) onto {1, 2,…,|V(G)| + |E(G)|} with the property that the edge-weight set {f(x) + f(xy) + f(y) | xy ∈ E(G)} is equal to {a, a + d, a + 2d,...,a + (|E(G)| ? 1)d} for two integers a > 0 and d ? 0. An (a, d)-edge-antimagic total labeling is called super if the smallest possible labels appear on the vertices. In this paper, we completely settle the problem of the super (a, d)-edge-antimagic total labeling of the complete bipartite graph K_m,n and obtain the following results: the graph K_m,n has a super (a, d)-edge-antimagic total labeling if and only if either (i) m = 1, n = 1, and d ? 0, or (ii) m = 1, n ? 2 (or n = 1 and m ? 2), and d ∈ {0, 1, 2}, or (iii) m = 1, n = 2 (or n = 1 and m = 2), and d = 3, or (iv) m, n ? 2, and d = 1.     

The connected <Emphasis Type="Italic">p</Emphasis>-median problem on block graphs

In this paper, we study a variant of the p-median problem on block graphs G in which the p-median is asked to be connected, and this problem is called the connected p-median problem. We first show that the connected p-median problem is NP-hard on block graphs with multiple edge weights. Then, we propose an O(n)-time algorithm for solving the problem on unit-edge-weighted block graphs, where n is the number of vertices in G.     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.     

<Emphasis Type="Italic">C</Emphasis>*-simplicity of <Emphasis Type="Italic">n</Emphasis>-periodic products

The C*-simplicity of n-periodic products is proved for a large class of groups. In particular, the n-periodic products of any finite or cyclic groups (including the free Burnside groups) are C*-simple. Continuum-many nonisomorphic 3-generated nonsimple C*-simple groups are constructed in each of which the identity xⁿ = 1 holds, where n ≥ 1003 is any odd number. The problem of the existence of C*-simple groups without free subgroups of rank 2 was posed by de la Harpe in 2007.