Representations of Menger (2, n)-Semigroups by Multiplace Functions

Investigation of partial multiplace functions by algebraic methods plays an important role in modern mathematics, where we consider various operations on sets of functions, which are naturally defined. The basic operation for n -place functions is an (n + 1)-ary superposition [ ], but there are some other naturally defined operations, which are also worth of consideration. In this article we consider binary Mann's compositions ⊕₁,…,⊕ _n for partial n-place functions, which have many important applications for the study of binary and n-ary operations. We present methods of representations of such algebras by n-place functions and find an abstract characterization of the set of n-place functions closed with respect to the set-theoretic inclusion.

Communicated by V. Artamonov.     

Projection representable relations on Menger (2, n)-semigroups

Abstract characterizations of relations of nonempty intersection, inclusion end equality of domains for partial n-place functions are presented. Representations of Menger (2, n)-semigroups by partial n-place functions closed with respect to these relations are investigated.     

A Characterization of (2, n)-Semigroup of n-Place Functions and De Morgan (2, n)-Semigroup of n-Place Functions

In this article, by defining n Mann's compositions and one unary operation on the set of n-place functions over some set, we construct a De Morgan (2, n)-semigroup of n-place functions and so find an abstract characterization of this algebras.     

Stabilizers of Functional Menger Systems

A functional Menger system is a set of n-place functions containing n projections and closed under the so-called Menger's composition of n-place functions. We give the abstract characterization for subsets of these functional systems which contain functions having one common fixed point.     

Orthogonal art galleries with interior walls

Consider an art gallery formed by a polygon on n vertices with m pairs of vertices joined by interior diagonals, the interior walls. Suppose that all walls (interior as well as exterior) are horizontal or vertical and each interior wall has an arbitrarily placed, arbitrarily small doorway. We show that the minimum number of guards that suffice to guard all such art galleries with n vertices and m interior walls is min{⌊(n+2m)/4⌋,⌊(n+3⌊n/2⌋+m-2)/8⌋}.     

On σ-commutativity in Menger algebras of n-place functions

We present an abstract characterization of various types of Menger algebras of n-place functions allowing certain permutations of variables.     

Defect location clustering schemes

Algorithms for clustering n objects typically require O(n²) operations. This report presents a special approach for a certain class of data that requires O(n) operations and O(n) storage. Such data commonly occur when a microscopic signal structure is imposed on a medium with potential for macroscopic defects, and the signal elements are then checked sequentially for error. The algorithm can be used to cluster other classes of data in O(n log n) operations. An application to videodisc defect consolidation is presented.     

Near-Boundary Asymptotics for Correlation Kernels

We discuss asymptotic formulas for the correlation kernel corresponding to a (more or less) general potential Q in the plane. If K _n is such a kernel, there is a known asymptotic formula K _n (z,z)=nΔQ(z)+B ₁(z)+n ^?1 B ₂(z)+? valid for z in the interior of a certain compact set known as the “droplet” corresponding to Q (on which ΔQ>0). On the other hand, if z is in the exterior of the droplet, K _n (z,z) converges to zero exponentially in n. Results of this type are useful in random matrix theory and conformal field theory; they have recently been used to prove the Gaussian field convergence in the interior of the droplet for fluctuations of eigenvalues of random normal matrices. To be able to extend such results beyond the interior, it becomes necessary to have a certain uniformity of estimates as z approaches the boundary either from the interior or from the exterior. Such estimates have to our knowledge hitherto not been known on a rigorous level. This note intends to fill this gap. We will consider applications in later publications. Our treatment of the (interior) asymptotics relies in an essential way on previous work due to Berman, Berndtsson, and Sjöstrand (Ark. Mat. 46, 2008), and Berman (Indiana Univ. Math. J. 58, 2009). We hope that this note can to some extent be regarded as a contribution to that work.     

The Maximum Number of Edges in Geometric Graphs with Pairwise Virtually Avoiding Edges

Let G be a geometric graph on n vertices that are not necessarily in general position. Assume that no line passing through one edge of G meets the relative interior of another edge. We show that in this case the number of edges in G is at most 2n?3.     

On the <Emphasis Type="Italic">n</Emphasis>-th row of the graded Betti table of an <Emphasis Type="Italic">n</Emphasis>-dimensional toric variety

We prove an explicit formula for the first nonzero entry in the n-th row of the graded Betti table of an n-dimensional projective toric variety associated with a normal polytope with at least one interior lattice point. This applies to Veronese embeddings of \(\mathbb {P}^n\). We also prove an explicit formula for the entire n-th row when the interior of the polytope is one-dimensional. All results are valid over an arbitrary field k.     

Average running time of the fast Fourier transform

We compare several algorithms for computing the discrete Fourier transform of n numbers. The number of “operations” of the original Cooley-Tukey algorithm is approximately 2nA(n), where A(n) is the sum of the prime divisors of n. We show that the average number of operations satisfies $\text{1}\text{x}\text{)∑}{}_{\mathrm{n\le x}}\text{2n A(n) ～ (}\text{π}{}^2\text{9}\text{)(}\text{x}{}^2\text{log}\text{x}\text{)}$. The average is not a good indication of the number of operations. For example, it is shown that for about half of the integers n less than x, the number of “operations” is less than n^1.61. A similar analysis is given for Good's algorithm and for two algorithms that compute the discrete Fourier transform in O(n log n) operations: the chirp-z transform and the mixed-radix algorithm that computes the transform of a series of prime length p in O(p log p) operations.     

AnO(\sqrt n L) iteration potential reduction algorithm for linear complementarity problems

This paper proposes an interior point algorithm for a positive semi-definite linear complementarity problem: find an (x, y)∈? ²ⁿ such thaty=Mx+q, (x,y)?0 andx ^T y=0. The algorithm reduces the potential function $$f(x,y) = (n + \sqrt n )\log x^T y - \sum\limits_{i = 1}^n {\log x_i y_i } $$ by at least 0.2 in each iteration requiring O(n ³) arithmetic operations. If it starts from an interior feasible solution with the potential function value bounded by \(O(\sqrt n L)\) , it generates, in at most \(O(\sqrt n L)\) iterations, an approximate solution with the potential function value \( - O(\sqrt n L)\) , from which we can compute an exact solution in O(n ³) arithmetic operations. The algorithm is closely related with the central path following algorithm recently given by the authors. We also suggest a unified model for both potential reduction and path following algorithms for positive semi-definite linear complementarity problems.     

A variation of Menger's theorem for long paths

In this paper we prove a Mengerian theorem for long paths, namely, that if in order to cut every uv-path of length at least n (n ≥ 2), in a diagraph D, we need to remove at least h points, then there exist {$\text{h}\text{(3n ? 5)}$} interior disjoint uv-paths in D of length at least n. Some variations and applications of this theorem are given as well.     

Soldering and point splitting

Several results concerning the generation of all the n-connected graphs from P_n+1 are presented. Necessary and sufficient conditions for two types of operations, soldering and point splitting, to preserve n-connectivity are given.     

Column-to-row operations on partitions: Garden of Eden partitions

Conjugation and the Bulgarian solitaire move are the extreme cases of general column-to-row operations on integer partitions. Each operation generates a state diagram on the partitions of n. Garden of Eden states are those with no preimage under the operation in question. In this note, we determine the number of Garden of Eden partitions for all n and column-to-row operations.     

A polynomial algorithm for a two-machine no-wait job-shop scheduling problem

This paper considers the no-wait scheduling of n jobs, where each job is a chain of unit processing time operations to be processed alternately on two machines. The objective is to minimize the mean flow time. We propose an O(n⁶)-time algorithm to produce an optimal schedule. It is also shown that if zero processing time operations are allowed, then the problem is NP-hard in the strong sense.     

Generalizations of a combinatorial lemma of Kelly

Two sets in R^m are said to be n-separated if, for every n distinct points p₁,…, p_n of one set, there is a point of the other in the relative interior of the convex cover of {p₁,…, p_n. We obtain some results concerning the dimension of the flat spanned by the union of n-separated sets and pose several further questions.     

On the maximum empty rectangle problem

Given a rectangle A and a set S of n points in A, we consider the problem, called the maximum empty rectangle problem, of finding a maximum area rectangle that is fully contained in A and does not contain any point of S in its interior. An O(n²) time algorithm is presented. Furthermore, it is shown that if the points of S are drawn randomly and independently from A, the problem can be solved in O(n(log n)²) expected time.     

The universality of the quantum Fourier transform in forming the basis of quantum computing algorithms

The quantum Fourier transform (QFT) is a powerful tool in quantum computing. The main ingredients of QFT are formed by the Walsh-Hadamard transform H and phase shifts P(·), both of which are 2×2 unitary matrices as operators on the two-dimensional 1-qubit space. In this paper, we show that H and P(·) suffice to generate the unitary group U(2) and, consequently, through controlled-U operations and their concatenations, the entire unitary group U(2ⁿ) on n qubits can be generated. Since any quantum computing algorithm in an n-qubit quantum computer is based on operations by matrices in U(2ⁿ), in this sense we have the universality of the QFT.     

Persistence and stability of solutions of Hamilton-Jacobi equations

Given a convergent sequence of Hamiltonians (Hn) and a convergent sequence of initial data (gn) for the first-order evolutionary Hamilton-Jacobi equation, we look for conditions ensuring that the sequences (un) and (vn) of Lax solutions and Hopf solutions respectively converge. The convergences we deal with are variational convergences. We take advantage of several recent results giving criteria for the continuity of usual operations.