Lagrangian submanifolds in complex projective space CP n

We first prove a basic theorem with respect to the moving frame along a Lagrangian immersion into the complex projective space CP ⁿ . Applying this theorem, we study the rigidity problem of Lagrangian submanifolds in CP ⁿ .     

Two graph isomorphism polytopes

The convex hull ψ_n,n of certain (n!)² tensors was considered recently in connection with graph isomorphism. We consider the convex hull ψ_n of the n! diagonals among these tensors. We show: 1. The polytope ψ_n is a face of ψ_n,n. 2. Deciding if a graph G has a subgraph isomorphic to H reduces to optimization over ψ_n. 3. Optimization over ψ_n reduces to optimization over ψ_n,n. In particular, this implies that the subgraph isomorphism problem reduces to optimization over ψ_n,n.     

Computing Hereditary Convex Structures

Color red and blue the n vertices of a convex polytope \(\mathcal{P}\) in ?³. Can we compute the convex hull of each color class in o(nlog?n) time? What if we have more than two colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of \(\mathcal{P}\) inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.     

On pedigree polytopes and Hamiltonian cycles

In this paper we define a combinatorial object called a pedigree, and study the corresponding polytope, called the pedigree polytope. Pedigrees are in one-to-one correspondence with the Hamiltonian cycles on K_n. Interestingly, the pedigree polytope seems to differ from the standard tour polytope, Q_n with respect to the complexity of testing whether two given vertices of the polytope are nonadjacent. A polynomial time algorithm is given for nonadjacency testing in the pedigree polytope, whereas the corresponding problem is known to be NP-complete for Q_n. We also discuss some properties of the pedigree polytope and illustrate with examples.     

A polyhedral study of triplet formulation for single row facility layout problem

The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183-190]. For any number of departments n, we prove that the dimension of the triplet polytope is n(n−1)(n−2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.     

Applied systems and cybernetics,volume III: Human systems,sociocybernetics, management and organizations: G.E. LASKER (Ed.) Proceedings of the international congress on applied Systems research and cybernetics; Pergamon Press,New York, 1981, xxx + 515 pages, $80.00

This note considers a special case of the assignment problem when n jobs are to be grouped together into a set of m categories (m > 3). Solving this particular case through the available transportation or assignment algorithms would entail a heavy computational burden, particularly in problems involving dense matrices. A preprocessing technique requiring sorting of (₂^m) n-arrays once is outlined, which is capable of reducing the dimension and eliminating several arcs for such a problem. The procedure offers an overall computational advantage over the other available algorithms applied directly. An illustrative example is included.     

Colorful polytopes and graphs

The paper investigates connections between abstract polytopes and properly edge colored graphs. Given any finite n-edge-colored n-regular graph G, we associate to G a simple abstract polytope P _G of rank n, the colorful polytope of G, with 1-skeleton isomorphic to G. We investigate the interplay between the geometric, combinatorial, or algebraic properties of the polytope P _G and the combinatorial or algebraic structure of the underlying graph G, focussing in particular on aspects of symmetry. Several such families of colorful polytopes are studied including examples derived from a Cayley graph, in particular the graphicahedra, as well as the flagadjacency polytopes and related monodromy polytopes associated with a given abstract polytope. The duals of certain families of colorful polytopes have been important in the topological study of colored triangulations and crystallization of manifolds.     

Homology classes that can be represented by embedded spheres in rational surfaces

The problem of embedding spheres in rational surfaces CP~2#nCP~2 is studied.For homology classes u=(b_1+k, b_2,…, b_n) with positive self-intersection numbers, anecessary and sufficient condition to detect its representability is given when k≤5.     

On the Skeleton of the Polytope of Pyramidal Tours

We consider the skeleton of the polytope of pyramidal tours. A Hamiltonian tour is called pyramidal if the salesperson starts in city 1, then visits some cities in increasing order of their numbers, reaches city n, and returns to city 1 visiting the remaining cities in decreasing order. The polytope PYR(n) is defined as the convex hull of the characteristic vectors of all pyramidal tours in the complete graph K _n . The skeleton of PYR(n) is the graph whose vertex set is the vertex set of PYR(n) and the edge set is the set of geometric edges or one-dimensional faces of PYR(n). We describe the necessary and sufficient condition for the adjacency of vertices of the polytope PYR(n). On this basis we developed an algorithm to check the vertex adjacency with linear complexity. We establish that the diameter of the skeleton of PYR(n) equals 2, and the asymptotically exact estimate of the clique number of the skeleton of PYR(n) is Θ(n²). It is known that this value characterizes the time complexity in a broad class of algorithms based on linear comparisons.     

An asymptotically exact algorithm for one modification of planar three-index assignment problem

An m-layer three-index assignment problem is considered which is a modification of the classical planar three-index assignment problem. This problem is NP-hard for m ? 2. An approximate algorithm, solving this problem for 1 < m < n/2, is suggested. The bounds on its quality are proved in the case when the input data (the elements of an m × n × n matrix) are independent identically distributed random variables whose values lie in the interval [a _n, b _n], where b _n > a _n > 0. The time complexity of the algorithm is O(mn ² + m ^7/2). It is shown that in the case of a uniform distribution (and also a distribution of minorized type) the algorithm is asymptotically exact if m = Θ(n ^{1 ? θ} ) and b _n/a _n = o(n ^θ) for every constant θ, 0 < θ < 1.     

Multiple point evaluation on combined tensor product supports

We consider the multiple point evaluation problem for an n-dimensional space of functions [???1,1[ ^d ?? spanned by d-variate basis functions that are the restrictions of simple (say linear) functions to tensor product domains. For arbitrary evaluation points this task is faced in the context of (semi-)Lagrangian schemes using adaptive sparse tensor approximation spaces for boundary value problems in moderately high dimensions. We devise a fast algorithm for performing m?≥?n point evaluations of a function in this space with computational cost O(mlog ^d n). We resort to nested segment tree data structures built in a preprocessing stage with an asymptotic effort of O(nlog ^d???1 n).     

Fractional perfect b-matching polytopes I: General theory

The fractional perfect b-matching polytope of an undirected graph G is the polytope of all assignments of nonnegative real numbers to the edges of G such that the sum of the numbers over all edges incident to any vertex v   is a prescribed nonnegative number _bv$b_v$. General theorems which provide conditions for nonemptiness, give a formula for the dimension, and characterize the vertices, edges and face lattices of such polytopes are obtained. Many of these results are expressed in terms of certain spanning subgraphs of G which are associated with subsets or elements of the polytope. For example, it is shown that an element u of the fractional perfect b-matching polytope of G is a vertex of the polytope if and only if each component of the graph of u either is acyclic or else contains exactly one cycle with that cycle having odd length, where the graph of u is defined to be the spanning subgraph of G whose edges are those at which u is positive.     

The p-Regular Partition Function Modulo p

Let b_?(n) denote the number of ?-regular partitions of n, where ? is a positive power of a prime p. We study in this paper the behavior of b_?(n) modulo powers of p. In particular, we prove that for every positive integer j, b_?(n) lies in each residue class modulo p^j for infinitely many values of n.     

On rational approximation of algebraic functions

We construct a new scheme of approximation of any multivalued algebraic function f(z) by a sequence {r_n(z)}_n∈N of rational functions. The latter sequence is generated by a recurrence relation which is completely determined by the algebraic equation satisfied by f(z). Compared to the usual Padé approximation our scheme has a number of advantages, such as simple computational procedures that allow us to prove natural analogs of the Padé Conjecture and Nuttall's Conjecture for the sequence {r_n(z)}_n∈N in the complement CP¹?D_f, where D_f is the union of a finite number of segments of real algebraic curves and finitely many isolated points. In particular, our construction makes it possible to control the behavior of spurious poles and to describe the asymptotic ratio distribution of the family {r_n(z)}_n∈N. As an application we settle the so-called 3-conjecture of Egecioglu et al. dealing with a 4-term recursion related to a polynomial Riemann Hypothesis.     

On the basis property of root elements of ordinary differential operators in the space L 2,n (a, b)

We study a spectral problem for a system of linear ordinary differential operators in the vector function space L _2,n (a, b) with parameter-dependent boundary conditions. We prove a theorem stating that the system of root functions of the problem is a basis with parentheses in L _2,n (a, b). Corollaries of the theorem are considered.