Darboux-integrable discrete systems

We extend Laplace’s cascade method to systems of discrete “hyperbolic” equations of the form u_i+1,j+1 = f(u_i+1,j, u_i,j+1 , u_i,j), where u_ij is a member of a sequence of unknown vectors, i, j ∊ ℤ. We introduce the notion of a generalized Laplace invariant and the associated property of the system being “Liouville.” We prove several statements on the well-definedness of the generalized invariant and on its use in the search for solutions and integrals of the system. We give examples of discrete Liouville-type systems. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 156, No. 2, pp. 207–219, August, 2008.     

Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

Maximum principle and propagation for intrinsicly regular solutions of differential inequalities structured on vector fields

We prove suitable versions of the weak maximum principle and of the maximum propagation for solutions u of a differential inequality Hu?0. Here H=_∑i,jai,j(z)ZiZj+Z₀ is a differential operator structured on the vector fields Zj's, whereas u belongs to an appropriate intrinsic class of regularity modelled on the Zj's.     

Active control of flexible systems

Since mechanically flexible systems are distributed-parameter systems, they are infinite-dimensional in theory and, in practice, must be modelled by large-dimensional systems. The fundamental problem of actively controlling very flexible systems is to control a large-dimensional system with a much smaller dimensional controller. For example, a large number of elastic modes may be needed to describe the behavior of a flexible satellite; however, active control of all these modes would be out of the question due to onboard computer limitations and modelling error. Consequently, active control must be restricted to a few critical modes. The effect of the residual (uncontrolled) modes on the closed-loop system is often ignored. In this paper, we consider the class of flexible systems that can be described by a generalized wave equation,u _tt+Au=F, which relates the displacementu(x,t) of a body Θ inn-dimensional space to the applied force distributionF(x,t). The operatorA is a time-invariant symmetric differential operator with a discrete, semibounded spectrum. This class of distributed parameter systems includes vibrating strings, membranes, thin beams, and thin plates. The control force distribution $$F(x,t) = \sum\limits_{i = 1}^M { \delta (x - x_i )f_i (t)} $$ is provided byM point force actuators located at pointsx _i on the body. The displacements (or their velocities) are measured byP point sensorsy _i(t)=u(z _j,t), oru _t(z _j,t),j=1, 2, ...,P, located at various pointsz _j along the body. We obtain feedback control ofN modes of the flexible system and display the controllability and observability conditions required for successful operation. We examine the control and observation spillover due to the residual modes and show that the combined effect of spillover can lead to instabilities in the closed-loop system. We suggest some remedies for spillover, including a straightforward phase-locked loop prefilter, to remove the instability mechanism. To illustrate the concepts of this paper, we present the results of some numerical studies on the active control of a simply supported beam. The beam dynamics are modelled by the Euler-Bernoulli partial differential equation, and the feedback controller is obtained by the above procedures. One actuator and one sensor (at different locations) are used to control three modes of the beam quite effectively. A fourth residual mode is simulated, and the destabilizing effect of control and observation spillover together on this mode is clearly illustrated. Once observation spillover is eliminated (e.g., by prefiltering the sensor outputs), the effect of control spillover alone on this system is negligible.     

Netlike partial cubes III. The median cycle property

A graph G has the Median Cycle Property (MCP) if every triple (u₀,u₁,u₂) of vertices of G admits a unique median or a unique median cycle, that is a gated cycle C of G such that for all i,j,k∈{0,1,2}, if x_i is the gate of u_i in C, then: {x_i,x_j}⊆I_G(u_i,u_j) if i≠j, and d_G(x_i,x_j)<d_G(x_i,x_k)+d_G(x_k,x_j). We prove that a netlike partial cube has the MCP if and only if it contains no triple of convex cycles pairwise having an edge in common and intersecting in a single vertex. Moreover a finite netlike partial cube G has the MCP if and only if G can be obtained from a set of even cycles and hypercubes by successive gated amalgamations, and equivalently, if and only if G can be obtained from K₁ by a sequence of special expansions. We also show that the geodesic interval space of a netlike partial cube having the MCP is a Pash-Peano space (i.e. a closed join space).     

Degeneracy of holomorphic curves in surfaces

LetX be a complex projective algebraic manifold of dimension 2 and let D₁, ..., D_u be distinct irreducible divisors onX such that no three of them share a common point. Let\(f:{\mathbb{C}} \to X\backslash ( \cup _{1 \leqslant i \leqslant u} D_i )\) be a holomorphic map. Assume thatu ? 4 and that there exist positive integers n₁, ... ,n_u,c such that n_in_J D _i.D_j) =c for all pairsi,j. Thenf is algebraically degenerate, i.e. its image is contained in an algebraic curve onX.     

Rearrangement inequalities for functionals with monotone integrands

The inequalities of Hardy-Littlewood and Riesz say that certain integrals involving products of two or three functions increase under symmetric decreasing rearrangement. It is known that these inequalities extend to integrands of the form F(u₁,…,u_m) where F is supermodular; in particular, they hold when F has nonnegative mixed second derivatives ∂_i∂_jF for all i≠j. This paper concerns the regularity assumptions on F and the equality cases. It is shown here that extended Hardy-Littlewood and Riesz inequalities are valid for supermodular integrands that are just Borel measurable. Under some nondegeneracy conditions, all equality cases are equivalent to radially decreasing functions under transformations that leave the functionals invariant (i.e., measure-preserving maps for the Hardy-Littlewood inequality, translations for the Riesz inequality). The proofs rely on monotone changes of variables in the spirit of Sklar's theorem.     

The one-dimensional wave equation with general boundary conditions

We show that a realization of the Laplace operator Au := u′′ with general nonlocal Robin boundary conditions α _j u′(j) + β _j u(j) + γ _1–j u(1 ? j) = 0, (j = 0, 1) generates a cosine family on L ^p (0, 1) for every \({p\,{\in}\,[1,\infty)}\). Here α _j , β _j and γ _j are complex numbers satisfying α ₀, α ₁ ≠ 0. We also obtain an explicit representation of local solutions to the associated wave equation by using the classical d’Alembert’s formula.     

Nash-solvable two-person symmetric cycle game forms

A two-person positional game form g (with perfect information and without moves of chance) is modeled by a finite directed graph (digraph) whose vertices and arcs are interpreted as positions and moves, respectively. All simple directed cycles of this digraph together with its terminal positions form the set A of the outcomes. Each non-terminal position j is controlled by one of two players i∈I={1,2}. A strategy x_i of a player i∈I involves selecting a move (j,j^′) in each position j controlled by i. We restrict both players to their pure positional strategies; in other words, a move (j,j^′) in a position j is deterministic (not random) and it can depend only on j (not on preceding positions or moves or on their numbers). For every pair of strategies (x₁,x₂), the selected moves uniquely define a play, that is, a directed path form a given initial position j₀ to an outcome (a directed cycle or terminal vertex). This outcome a∈A is the result of the game corresponding to the chosen strategies, a=a(x₁,x₂). Furthermore, each player i∈I={1,2} has a real-valued utility function u_i over A. Standardly, a game form g is called Nash-solvable if for every u=(u₁,u₂) the obtained game (g,u) has a Nash equilibrium (in pure positional strategies).A digraph (and the corresponding game form) is called symmetric if (j,j^′) is its arc whenever (j^′,j) is. In this paper we obtain necessary and sufficient conditions for Nash-solvability of symmetric cycle two-person game forms and show that these conditions can be verified in linear time in the size of the digraph.     

Global Hölder continuity of weak solutions to quasilinear divergence form elliptic equations

We derive global Hölder regularity for the -weak solutions to the quasilinear, uniformly elliptic equation

div(aij(x,u)Dju+ai(x,u))+a(x,u,Du)=0     

Δ-Monotone arrangements of real numbers

Given a set of M × N real numbers, can these always be labeled as x_i,j; i = 1,…, M; j = 1,…, N; such that x_i+1,j+1 ? x_i+1,j ? x_i,j+1 + x_ij ≥ 0, for every (i, j) where 1 ≤ i ≤ M ? 1, 1 ≤ j ≤ N ? 1? For M = N = 3, or smaller values of M, N it is shown that there is a “uniform” rule. However, for max(M, N) > 3 and min(M, N) ≥ 3, it is proved that no uniform rule can be given. For M = 3, N = 4 a way of labeling is demonstrated. For general M, N the problem is still open although, for a special case where all the numbers are 0's and 1's, a solution is given.     

The complete symmetry group of the generalised hyperladder problem

We further consider the n-dimensional ladder system, that is the homogeneous quadratic system of first-order differential equations of the form , i=1,n, where (a_ij)=(i+1−j), i,j=1,n introduced by Imai and Hirata (nlin.SI/0212007). We establish the most general system of first-order ordinary differential equations invariant under the algebra which characterises the ladder system of Imai and Hirata and the algebra of minimal dimension required to specify completely this most general system. We provide the complete symmetry group of the generalised hyperladder system and discuss its integrability.     

两类广义Petersen 图的Euler亏格

广义 Petersen 图 P(n, m) 是这样的一个图:它的顶点集是{u_i, v_i | i=0,1, ^… , n-1}, 边集是 {u_iu_i+1, v_iv_i+m, u_iv_i | i=0,1, ^…, n-1}, 这里 m, n 是正整数、加法是在模n 下且 m<|n/2| . 这篇文章证明了P(2m+1, m)(m≥ 2) 的 Euler 亏格是1, 并且 P(2m+2, m)(m≥ 5) 的 Euler 亏格是2.     

Least squares solutions to AX = B for bisymmetric matrices under a central principal submatrix constraint and the optimal approximation

A matrix A∈R^n×n is called a bisymmetric matrix if its elements a_i,j satisfy the properties a_i,j=a_j,i and a_i,j=a_n-j+1,n-i+1 for 1?i,j?n. This paper considers least squares solutions to the matrix equation AX=B for A under a central principal submatrix constraint and the optimal approximation. A central principal submatrix is a submatrix obtained by deleting the same number of rows and columns in edges of a given matrix. We first discuss the specified structure of bisymmetric matrices and their central principal submatrices. Then we give some necessary and sufficient conditions for the solvability of the least squares problem, and derive the general representation of the solutions. Moreover, we also obtain the expression of the solution to the corresponding optimal approximation problem.     

Representations for partially exchangeable arrays of random variables

Consider an array of random variables (X_i,j), 1 ≤ i,j < ∞, such that permutations of rows or of columns do not alter the distribution of the array. We show that such an array may be represented as functions f(α, ξ_i, η_j, λ_i,j) of underlying i.i.d, random variables. This result may be useful in characterizing arrays with additional structure. For example, we characterize random matrices whose distribution is invariant under orthogonal rotation, confirming a conjecture of Dawid.     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

Regular Steinhaus graphs of odd degree

A Steinhaus matrix is a binary square matrix of size n which is symmetric, with a diagonal of zeros, and whose upper-triangular coefficients satisfy a_i,j=a_i−1,j−1+a_i−1,j for all 2?i<j?n. Steinhaus matrices are determined by their first row. A Steinhaus graph is a simple graph whose adjacency matrix is a Steinhaus matrix. We give a short new proof of a theorem, due to Dymacek, which states that even Steinhaus graphs, i.e. those with all vertex degrees even, have doubly-symmetric Steinhaus matrices. In 1979 Dymacek conjectured that the complete graph on two vertices K₂ is the only regular Steinhaus graph of odd degree. Using Dymacek’s theorem, we prove that if (a_i,j)_1?i,j?n is a Steinhaus matrix associated with a regular Steinhaus graph of odd degree then its sub-matrix (a_i,j)_2?i,j?n−1 is a multi-symmetric matrix, that is a doubly-symmetric matrix where each row of its upper-triangular part is a symmetric sequence. We prove that the multi-symmetric Steinhaus matrices of size n whose Steinhaus graphs are regular modulo 4, i.e. where all vertex degrees are equal modulo 4, only depend on parameters for all even numbers n, and on parameters in the odd case. This result permits us to verify Dymacek’s conjecture up to 1500 vertices in the odd case.     

Constant‐sign solutions for singular systems of Fredholm integral equations

We consider the system of Fredholm integral equations where T>0 is fixed and the nonlinearities H_i(t, u₁, u₂, …, u_n) can be singular at t=0 and u_j=0 where j∈{1, 2, …, n}. Criteria are offered for the existence of constant‐sign solutions, i.e. θ_iu_i(t)≥0 for t∈[0, 1] and 1≤i≤n, where θ_i∈{1,?1} is fixed. We also include an example to illustrate the usefulness of the results obtained. Copyright © 2010 John Wiley & Sons, Ltd.     

A bijection between certain non-crossing partitions and sequences

We present a bijection between non-crossing partitions of the set [2n+1] into n+1 blocks such that no block contains two consecutive integers, and the set of sequences such that 1?s_i?i, and if s_i=j, then s_i-r?j-r for 1?r?j-1.     

Regularized semigroups,iterated Cauchy problems and equipartition of energy

The iterated Cauchy problem under consideration is $$\Pi _{k = 1}^n (d/dt - A_k )u(t) = 0(t \geqslant 0).(*)$$ Here {A ₁,..., A_n} are unbounded linear operators on a Banach space. The initial value problem for (*) is governed by a semigroup of some sort. When eachA _k is a (C ₀) semigroup generator, this semigroup is of class (C ₀) and was studied by J. T. Sandefur [26]. This result is extended to the case when eachA _k generates aC-regularized semigroup (withC independent ofk). This means one can solveu′=Au, u(0)=f∈C (Dom (A)) and getu(t)→0 wheneverC ^?1f→0; hereC is bounded and injective. When theA _k are commuting generator withA _k-A_j injective fork≠j, then the Goldstein-Sandefur d'Alembert formula [19] is extended, viz. solutions of (*) (with suitable restrictions on the initial data) are of the form \(u = \sum\nolimits_{i = 1}^n {u_i } \) whereu _i is a solution ofu′ _i=A_iu_i. Examples and applications are given. Included among the examples is the establishment of a form of equipartition of energy for the Laplace equation; equipartition of energy is wellknown for the wave equation. A final section of the paper deals with the absence of necessary conditions for equipartition of energy.