Duality of Graded Graphs

A graph is said to be graded if its vertices are divided into levels numbered by integers, so that the endpoints of any edge lie on consecutive levels. Discrete modular lattices and rooted trees are among the typical examples. The following three types of problems are of interest to us:(1) path counting in graded graphs, and related combinatorial identities;(2) bijective proofs of these identities;(3) design and analysis of algorithms establishing corresponding bijections.This article is devoted to (1); its sequel [7] is concerned with the problems (2)–(3). A simplified treatment of some of these results can be found in [8].In this article, R.P. Stanley's [26, 27] linear-algebraic approach to (1) is extended to cover a wide range of graded graphs. The main idea is to consider pairs of graded graphs with a common set of vertices and common rank function. Such graphs are said to be dual if the associated linear operators satisfy a certain commutation relation (e.g., the Heisenberg one). The algebraic consequences of these relations are then interpreted as combinatorial identities. (This idea is also implicit in [27].)[7] contains applications to various examples of graded graphs, including the Young, Fibonacci, Young-Fibonacci and Pascal lattices, the graph of shifted shapes, the r-nary trees, the Schensted graph, the lattice of finite binary trees, etc. Many enumerative identities (both known and unknown) are obtained. Abstract of [7]. These identities can also be derived in a purely combinatorial way by generalizing the Robinson-Schensted correspondence to the class of graphs under consideration (cf. [5]). The same tools can be applied to permutation enumeration, including involution counting and rook polynomials for Ferrers boards. The bijective correspondences mentioned above are naturally constructed by Schensted-type algorithms. A general approach to these constructions is given. As particular cases we rederive the classical algorithm of Robinson, Schensted, and Knuth [20, 12, 21], the Sagan-Worley [17, 32] and Haiman [11] algorithms, the algorithm for the Young-Fibonacci graph [5, 15], and others. Several new applications are given.     

Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

A symmetry property for q-weighted Robinson–Schensted and other branching insertion algorithms

In [19], a \(q\) -weighted version of the Robinson–Schensted algorithm was introduced. In this paper, we show that this algorithm has a symmetry property analogous to the well-known symmetry property of the usual Robinson–Schensted algorithm. The proof uses a generalisation of the growth diagram approach introduced by Fomin [5–8]. This approach, which uses ‘growth graphs’, can also be applied to a wider class of insertion algorithms which have a branching structure, including some of the other \(q\) -weighted versions of the Robinson–Schensted algorithm which have recently been introduced by Borodin–Petrov [2].     

正定可对称化矩阵与预对称迭代算法

１．问题的提出 我们引入正定可对称化矩阵定义的背景是为了研究求解二阶椭圆型非自共轭方程的离散迭代有效算法、这类方程的椭圆型是本质的分析性质。是由二阶项决定的,在离散方程中表现为正定性;非自共轭性则是由方程中的一阶项引起的,在相当广泛一类问题中可通过变量代换化为自共轭。因此,我们称这类问题为正定可对称化问题。 例１．高维二阶常系数椭圆型方程其中 Ａ为常系数正定对称（ｓ．ｐ．ｄ）阵, 为正交阵, Ｄ是对角元素为正的对角阵。 先作变量代换,通过演算,偏微分方程对于新变量变成这里进而令可将原非自共轭偏微分算子…     

Semilattice decompositions of semigroups

The purpose of this paper is to develop a general theory of semilattice decompositions of semigroups from the point of view of obtaining theorems of the type: A semigroup S has propertyD if and only if S is a semilattice of semigroups having property β. As such we are able to extend the theories of Clifford [3], Andersen [1], Croisot [5], Tamura and Kimura [14], Petrich [9], Chrislock [2], Tamura and Shafer [15], Iyengar [7] and Weissglass and the author [10]. The root of our whole theory is Tamura's semilattice decomposition theorem [12, 13]. Of this, we give a new proof. The results of this paper were obtained by the author between January and July of 1971, while an undergraduate at the University of California, Santa Barbara.     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

Über den arithmetischen Rang quadratfreier Potenzproduktideale

In this paper we give an algorithm to compute an upper bound for the arithmetical rank of squarefree monomial ideals, i.e. the minimal number of hypersurfaces which cut out set-theoretically the variety of such an ideal. An apriori bound N – a=b+2 is obtained, where N means the number of variables, a the lowest degree in the ideal and b the lowest degree of syzygies in the first syzygy module (Thm. 2). These results sharpen more general results of [2] for the considered class of ideals by methods different from [1], [7].     

The integration of certain products of the multivariableH-function with a general class of polynomials

The authors present six general integral formulas (four definite integrals and two contour inegrals) for theH-function of several complex variables, which was introduced and studied in a series of earlier papers by H. M. Srivastava and R. Panda (cf., e.g., [25] through [29]; see also [14] through [18], [20], [24], [32], [34], [35], [37], and [38]). Each of these integral formulas involves a product of the multivariableH-function and a general class of polynomials with essentially arbitrary coefficients which were considered elsewhere by H. M. Srivastava [21]. By assigning suiatble special values to these coefficients, the main results (contained in Theorems 1, 2 and 3 below) can be reduced to integrals involving the classical orthogonal polynomials including, for example, Hermite, Jacobi [and, of course, Gegenbauer (or ultraspherical), Legendre, and Tchebycheff], and Laguerre polynomials, the Bessel polynomials considered by H. L. Krall and O. Frink [9], and such other classes of generalized hypergeometric polynomials as those studied earlier by F. Brafman [3] and by H. W. Gould and A. T. Hopper [8]. On the other hand, the multivariableH-functions occurring in each of our main results can be reduced, under various special cases, to such simpler functions as the generalized Lauricella hypergeometric functions of several complex variables [due to H. M. Srivastava and M. C. Daoust (cf. [22] and [23])] which indeed include a great many of the useful functions (or the products of several such functions) of hypergeometric type (in one and more variables) as their particular cases (see,e. g., [1], [10] and [39]). Many of the aforementioned applications of our integral formulas (contained in Theorems 1, 2 and 3 below) are considered briefly. Further usefulness of some of these consequences of Theorems 1 and 2 in terms of the classical orthogonal polynomials is illustrated by considering a simple problem involving the orthogonal expansion of the multivariableH-function in series of Jacobi polynomials. It is also shown how these general integrals are related to a number of results scattered in the literature. 0261 0262 V     

Ingham-Beurling type theorems with weakened gap conditions

Completing a series of works begun by Wiener [34], Paley and Wiener [28] and Ingham [9], a far-reaching generalization of Parseval"s identity was obtained by Beurling [4] for nonharmonic Fourier series whose exponents satisfy a uniform gap condition. Later this gap condition was weakened by Ullrich [33], Castro and Zuazua [5], Jaffard, Tucsnak and Zuazua [11] and then in [2] in some particular cases. In this paper we prove a general theorem which contains all previous results. Furthermore, applying a different method, we prove a variant of this theorem for nonharmonic Fourier series with vector coefficients. This result, partly motivated by control-theoretical applications, extends several earlier results obtained in [15] and [2]. Finally, applying these results we obtain an optimal simultaneous observability theorem concerning a system of vibrating strings. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Klein correspondence of line congruences immersed in an elliptic spaceS 3 onto the hyperquadricP 4

This article is devoted to the investigation and the construction of the Klein correspondence of line congruences referred to a specialized moving frame in a 3-dimensional elliptic spaceS ₃ to the hyperquadricP ⁴ of the Klein 5-dimensional elliptic spaceS ₅. The Klein correspondence is given and characterized by Theorems 1, 2. The methods adapted here are based on Cartan's differential calculus [1], [6].     

Combinatorial obstructions to the lifting of weaving diagrams

This paper deals with various connections of oriented matroids [3] and weaving diagrams of lines in space [9], [16], [27]. We encode the litability problem of a particular weaving diagramD onn lines by the realizability problem of a partial oriented matroid χ _D with2n elements in rank 4. We prove that the occurrence of a certain substructure inD implies that χD is noneuclidean in the sense of Edmonds, Fukuda, and Mandel [12], [14]. Using this criterion we construct an infinite class of minor-minimal noneuclidean oriented matroids in rank 4. Finally, we give an easy algebraic proof for the nonliftability of the alternating weaving diagram on a bipartite grid of 4×4 lines [16].     

An analog of Schensted's algorithm for Shifted Young Tableaux

Schensted [Canad. J. Math. 13 (1961)] constructed an algorithm giving a bijective correspondence between permutations and pairs of Young Tableaux. The author develops an analogous algorithm relating permutations and triples consisting of two Shifted Tableaux and a set. Various properties of this algorithm are also examined.     

The direct product of a hopfian group with a group with cyclic ccnter

In this paper we continue our study of hopficity begun in [1], [2], [3], [4] and [5]. LetA be hopfian and letB have a cyclic center of prime power order. We improve Theorem 4 of [2] by showing that ifB has finitely many normal subgroups which form a chain (we sayB isn-normal), thenAxB is hopfian. We then consider the case whenB is ap-group of nilpotency class 2 and show that in certain casesAxB is hopfian.     

On the Cavities and Rigid Inclusions Correspondence and the Cosserat Spectrum

The correspondence in two-dimensional elasticity between the stress fields of cavities and rigid inclusions has been obtained by Dundurs [1] and Markenscoff [3]. It was shown that if the limit of the stress of the inclusion boundary-value problem, which depends on the elastic constants, exists when the Poisson's ratio v tends to 1, then this solves the traction boundary-value problem for the cavity problem since it satisfies equilibrium and boundary conditions, and, by the uniqueness theorem, exists and is unique. In three dimensions the solution of the traction boundary-value problem of elasticity does depend on Poisson's ratio since the Beltrami-Mitchell compatability conditions for the stress depend on Poisson's ratio. So the similar argument for the correspondence between cavities and rigid inclusions cannot in principle be made. However, the Beltrami-Mitchell compatability conditions are independent of v if the dilatation is a constant or a linear function of the position. In this case we can show that the same result goes through for the correspondence. In order to investigate the behavior of the solutions in the vicinity of v = 1, we use some results obtained for the Cosserat spectrum by Mikhlin [4], Maz'ya and Mikhlin [3], see also [6]. The existence of the limit for 2D and 3D when v tends to 1 is proved on the basis of the fact that the eigenvalue ω = — 1 of the Cosserat spectrum is isolated.     

Concentration through large advection

In this paper we extend the elegant results of Chen, Lam and Lou [6, Section 2], where a concentration phenomenon was established as the advection blows up, to a general class of adventive–diffusive generalized logistic equations of degenerate type. Our improvements are really sharp as we allow the carrying capacity of the species to vanish in some subdomain with non-empty interior. The main technical devices used in the derivation of the concentration phenomenon are Proposition 3.2 of Cano-Casanova and López-Gómez [5], Theorem 2.4 of Amann and López-Gómez [1] and the classical Harnack inequality. By the relevance of these results in spatial ecology, complete technical details seem imperative, because the proof of Theorem 2.2 of [6] contains some gaps originated by an “optimistic” use of Proposition 3.2 of [5]. Some of the general assumptions of [6] are substantially relaxed.     

Approximation in eigenvalue problems for holomorphic fredholm operator functions I

The approximation of a holomorphic eigenvalue problem is considered. The main purpose is to present a construction by which the derivation of the asymptotic error estimations for the approximate eigenvalues of Fredholm operator functions can be reduced to the derivation of these estimations for the case of matrix functions. (Some estimations for the latter problem can be derived, in one's turn, from the error estimations for the zeros of the corresponding determinants.) The asymptotic error estimations are considered in part II of this paper, in [10]. By the presented construction also the stability of the algebraic multiplicity of eigenvalues by regular approximation is proved in Section 3

The presented construction, in essence, reproduces the constructions in [7] for the case of the compact approximation in subspaces and in [9] for the case of projection—like methods. It is simpler to use than similiar construction in [8], and allows unified consideration of the general case and the case of projection—like methods, what in [8, 9] was not achieved     

Symmetry in Generalized Quadrangles

In this paper, we describe some aspects of a Lenz(-Barlotti)-type classification of finite generalized quadrangles, which is being prepared by the author. Some new points of view are given. We also prove that each span-symmetric generalized quadrangle of order s > 1 with s even is isomorphic to $ \mathcal{Q} $ (4, s), without using the canonical connection (obtained by S. E. Payne in [15] between groups of order s ³ ? s with a 4-gonal basis and span-symmetric generalized quadrangle of order s. (The latter result was obtained for general s independently by W. M. Kantor in [10], and the author in [30] Finally, we obtain a classification program for all finite translation generalized quadrangles, which is suggested by the main results of [27], [30], [32], [35], [38] and [37].