On Schensted's construction and the multiplication of schur functions

In this paper, certain aspects of Schensted's construction are examined and a generalization is described. From this generalization, the Littlewood-Richardson rule for the multiplication of Schur functions is derived by purely combinatorial methods.     

An algorithm for the quadratic assignment problem using Bender's decomposition

A well known method used for solving quadratic assignment problems proceeds by the construction of an equivalent much larger linear assignment problem with many side constraints. The disadvantage of this method lies in the weakness of the bounds obtained by solving the linear problem. An alternate linearization has been suggested using a general method of Glover. In this paper the mixed integer program obtained by Glover's method is discussed and a solution using Bender's decomposition is proposed.     

A generalization of Berwick's unit algorithm

In 1913 W. E. H. Berwick published an algorithm for finding the fundamental unit of a cubic field with negative discriminant. His method relied heavily on the geometry of such fields and was less efficient than the well-known algorithm of Voronoi. In the present paper we show that the use of cubic geometry is not necessary and also that Berwick's method can be generalized. We present a periodic algorithm for finding a maximal set of independent units in an arbitrary algebraic number field.     

Collinear subsets of lattice point sequences—An analog of Szemerédi's theorem

Szemerédi's theorem states that given any positive number B and natural number k, there is a number n(k, B) such that if n ? n(k, B) and 0 < a₁ < … < a_n is a sequence of integers with a_n ? Bn, then some k of the a_i form an arithmetic progression. We prove that given any B and k, there is a number m(k, B) such that if m ? m(k, B) and u₀, u₁, …, u_m is a sequence of plane lattice points with ∑_i=1^m…u_i ? u_i?1… ? Bm, then some k of the u_i are collinear. Our result, while similar to Szemerédi's theorem, does not appear to imply it, nor does Szemerédi's theorem appear to imply our result.     

Kuratowski's and Wagner's theorems for matroids

In an earlier paper we proved the following theorem, which provides a strengthening of Tutte's well-known characterization of regular (totally unimodular) matroids: A binary matroid is regular if it does not have the Fano matroid or its dual as a series-minor (parallel-minor). In this paper we prove two theorems (Theorems 5.1 and 6.1) which provide the same kind of strengthening for Tutte's characterization of the graphic matroids (i.e., bond-matroids). One interesting aspect of these theorems is the introduction of the matroids of “type R”. It turns out that these matroids are, in at least two different senses, the smallest regular matroids which are neither graphic nor cographic (Theorems 6.2 and 6.3).     

Symplectic Shifted Tableaux and Deformations of Weyl's Denominator Formula for sp(2n)

A determinantal expansion due to Okada is used to derive both a deformation of Weyl's denominator formula for the Lie algebra sp(2n) of the symplectic group and a further generalisation involving a product of the deformed denominator with a deformation of flagged characters of sp(2n). In each case the relevant expansion is expressed in terms of certain shifted sp(2n)-standard tableaux. It is then re-expressed, first in terms of monotone patterns and then in terms of alternating sign matrices.     

An application of Carlitz's formula

In this note we establish a new transformation formula for the generalized hypergeometric function of two variables. On specializing its parameters, it yields the interesting result:

${}_4\text{F}{}_3\text{γ2β?γ1+}\text{1}\text{2}\text{α,}\text{1}\text{2}\text{+}\text{1}\text{2}\text{α;1}\text{1}\text{2}\text{(1+2β),2+α,1+β;}\text{=}\text{βΓ(2β)Γ(2β?α?γγ)}\text{(β?γ)Γ(2β?α)Γ(2β?γ)}$

. valid for Rl(2β ? α ? γ) > 0. When γ = ?n (a negative integer), it reduces to a result due to Professor Carlitz. Several other new summation formulae for ₅F₄(1), ₄F₃(1) and for the hypergeometric function of two variables are obtained.     

The Distributions of the Entries of Young Tableaux

Let T be a standard Young tableau of shape λ⊢k. We show that the probability that a randomly chosen Young tableau of n cells contains T as a subtableau is, in the limit n→∞, equal to f^λ/k!, where f^λ is the number of all tableaux of shape λ. In other words, the probability that a large tableau contains T is equal to the number of tableaux whose shape is that of T, divided by k!. We give several applications, to the probabilities that a set of prescribed entries will appear in a set of prescribed cells of a tableau, and to the probabilities that subtableaux of given shapes will occur. Our argument rests on a notion of quasirandomness of families of permutations, and we give sufficient conditions for this to hold.     

Comments on practical implementation of Gomory's fractional algorithm

Gomory's fractional algorithm is widely used for solving integer linear programming problems. It is strongly influenced by round off errors and consequently has the disadvantage that in many cases the optimal solution is not reached. The present note describes a simple modification of this algorithm. The essential feature of this modification consists in conserving the integral structure of the problem. Thus the influence of round off errors is avoided. The power of our method is illustrated by a numerical example.     

A simple version of Karzanov's blocking flow algorithm

Dinic has shown that the classic maximum flow problem on a graph of n vertices and m edges can be reduced to a sequence of at most n ? 1 so-called ‘blocking flow’ problems on acyclic graphs. For dense graphs, the best time bound known for the blocking flow problems is O(n²). Karzanov devised the first O(n²)-time blocking flow algorithm, which unfortunately is rather complicated. Later Malhotra, Kumar and Maheshwari devise another O(n²)-time algorithm, which is conceptually very simple but has some other drawbacks. In this paper we propose a simplification of Karzanov's algorithm that is easier to implement than Malhotra, Kumar and Maheshwari's method.     

An improvement on Nourein's method for the simultaneous determination of the zeroes of a polynomial (An algorithm)

In a recent paper [2], Nourein derived an iteration formula, which exhibited cubic convergence for the simultaneous determination of the zeroes of a polynomial. In this paper - following quite a different appraoch - we derive a method which can be viewed as an improvement on that of [2]. The derivation is based on the approximation of the polynomial in question by a Lagrange interpolation formula. We give the algorithm in ALGOL 60. For a given real polynomial, the algorithm caters for the general case of complex zeroes.     

All shortest distances in a graph. An improvement to Dantzig's inductive algorithm

Dantzig's inductive algorithm is one of the best solutions to find all shortest distances in a graph. A change in the order of computations makes it possible to improve that algorithm by exploiting nonexistent arcs.     

A q-Analog of the Hook Walk Algorithm for Random Young Tableaux

A probabilistic algorithm, called the q-hook walk, is defined. For a given Young diagram, it produces a new one by adding a random box with probabilities, depending on a positive parameter q. The corresponding Markov chain in the space of infinite Young tableaux is closely related to the knot invariant of Jones, constructed via traces of Hecke algebras. For q = 1, the algorithm is essentially the hook walk of Greene, Nijenhuis, and Wilf. The q-hook formula and a q-deformation of Young graph are also considered.S. Kerov: Supported by a grant from CRM (Université de Montréal), during its Operator Algebras year     

An improved version of Lloyd's theorem

The generalisation of Lloyd's theorem to distance-transitive graphs can be improved in the case of antipodal graphs by looking at the derived graph. In the case of binary perfect codes the roots of the Lloyd polynomial are even integers. This can be applied to give a short proof of the binary perfect code theorem.