The Number of Unlabeled Orders on Fourteen Elements

Lacking an explicit formula for the numbers T ₀(n) of all order relations (equivalently: T ₀ topologies) on n elements, those numbers have been explored only up to n=13 (unlabeled posets) and n=15 (labeled posets), respectively.In a new approach, we used an orderly algorithm to (i) generate each unlabeled poset on up to 14 elements and (ii) collect enough information about the posets on 13 elements to be able to compute the number of labeled posets on 16 elements by means of a formula by Erné. Unlike other methods, our algorithm avoids isomorphism tests and can therefore be parallelized quite easily. The underlying principle of successively adding new elements to small objects is applicable to lattices and other kinds of order structures, too.     

n-distributivity,dimension and Carathéodory's theorem

A. Huhn proved that the dimension of Euclidean spaces can be characterized through algebraic properties of the lattices of convex sets. In fact, the lattice of convex sets of isn+1-distributive but notn-distributive. In this paper his result is generalized for a class of algebraic lattices generated by their completely join-irreducible elements. The lattice theoretic form of Carathéodory's theorem characterizesn-distributivity in such lattices. Several consequences of this result are studied. First, it is shown how infiniten-distributivity and Carathéodory's theorem are related. Then the main result is applied to prove that for a large class of lattices beingn-distributive means being in the variety generated by the finiten-distributive lattices. Finally,n-distributivity is studied for various classes of lattices, with particular attention being paid to convexity lattices of Birkhoff and Bennett for which a Helly type result is also proved.Presented by J. Sichler.     

Combinatorial partitions of finite posets and lattices —Ramsey lattices

It is proved that for every finite latticeL there exists a finite latticeL such that for every partition of the points ofL into two classes there exists a lattice embeddingf:LL such that the points off(L) are in one of the classes.This property is called point-Ramsey property of the class of all finite lattices. In fact a stronger theorem is proved which implies the following: for everyn there exists a finite latticeL such that the Hasse-diagram (=covering relation) has chromatic number >n. We discuss the validity of Ramseytype theorems in the classes of finite posets (where a full discussion is given) and finite distributive lattices. Finally we prove theorems which deal with partitions of lattices into an unbounded number of classes.Presented by G. Grätzer.     

Cost operator algorithms for the transportation problem

A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T – 1) steps for primal nondegenerate transportation problems and [(2T + 1) min (m, n)] – 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) min (m, n) respectively.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research.     

The order dimension of multinomial lattices

Using the notion of Ferrers dimension of incidence structures, the order dimension of multi-nomial lattices (i.e. lattices of multi-permutations) is determined. In particular, it is shown that the lattice of all permutations on ann-element set has dimensionn–1.     

The Homology of Partitions with an Even Number of Blocks

Let denote the subposet obtained by selecting even ranks in the partition lattice . We show that the homology of has dimension , where is the tangent number. It is thus an integral multiple of both the Genocchi number and an André or simsun number. Using the general theory of rank-selected homology representations developed in [22], we show that, for the special case of , the character of the symmetric group S _2n on the homology is supported on the set of involutions. Our proof techniques lead to the discovery of a family of integers b _i(n), 2 i n, defined recursively. We conjecture that, for the full automorphism group S _2n, the homology is a sum of permutation modules induced from Young subgroups of the form , with nonnegative integer multiplicity b _i(n). The nonnegativity of the integers b _i(n) would imply the existence of new refinements, into sums of powers of 2, of the tangent number and the André or simsun number a _n(2n).Similarly, the restriction of this homology module to S _2n–1 yields a family of integers d _i(n), 1 i n – 1, such that the numbers 2^–i d _i(n) refine the Genocchi number G _2n . We conjecture that 2^–i d _i(n) is a positive integer for all i.Finally, we present a recursive algorithm to generate a family of polynomials which encode the homology representations of the subposets obtained by selecting the top k ranks of , 1 k n – 1. We conjecture that these are all permutation modules for S _2n .     

Loops mit distributiven und geometrischen Unterloopverbänden

The following facts are shown: A loop with a finite distributive subloop lattice is finite, monogenic and all its subloops are monogenic. Therefore, power-associative loops having finite distributive subloop lattices are cyclic groups. A loop G with its subloop lattice L(G) being a finite n-dimensional projective geometry is generated by at most n+1 elements. For all n IN, n4, there are power-associative loops whose subloop lattices are projective lines with n points. Furthermore, for a given projective planeP _n (desarguesian or non-desarguesian) of order n there exists a power-associative loopG with L(G) -P _n.     

Quasi-Differential Posets and Cover Functions of Distributive Lattices II: A Problem in Stanley’s <Emphasis Type="Italic">Enumerative Combinatorics</Emphasis>

A distributive lattice L with 0 is finitary if every interval is finite. A function f:₀₀ is a cover function for L if every element with n lower covers has f(n) upper covers. All non-decreasing cover functions have been characterized by the author ([2]), settling a 1975 conjecture of Richard P. Stanley. In this paper, all finitary distributive lattices with cover functions are characterized. A problem in Stanleys Enumerative Combinatorics is thus solved. 2000 Mathematics Subject Classification. 06A07, 06B05, 06D99, 11B39     

The (n + 1)2 m -ray algorithm: a new simplicial algorithm for the variational inequality problem on ℝ + m ×S n

In this paper we propose a variable dimension simplicial algorithm for solving the variational inequality problem on the cross product of the nonnegative orthant ₊ ^m of them-dimensional Euclidean space ^m and then-dimensional unit simplexS ⁿ of ⁿ⁺¹. Starting from an arbitrary point (u, v) є ₊ ^m ×S ⁿ, the algorithm generates a piecewise linear path in ₊ ^m ×S ⁿ. The path is traced by making alternately linear programming pivot operations and replacement steps in an appropriate simplicial subdivision of ₊ ^m ×S ⁿ. The algorithm differs from the thus far known algorithm in the number of directions in which it may leave the starting point. More precisely, the algorithm has (n+1)2 ^m rays to leave the starting point whereas the existing algorithm hasn+m+1 rays. A convergence condition is presented and the accuracy estimation of an approximate solution generated is also given.     

A new graph triconnectivity algorithm and its parallelization

We present a new algorithm for finding the triconnected components of an undirected graph. The algorithm is based on a method of searching graphs called open ear decomposition. A parallel implementation of the algorithm on a CRCW PRAM runs inO(log² n) parallel time usingO(n+m) processors, wheren is the number of vertices andm is the number of edges in the graph.A preliminary version of this paper was presented at the19th Annual ACM Symposium on Theory of Computing, New York, NY, May 1987.Supported by NSF Grant DCR 8514961.Supported by NSF Grant ECS 8404866 and the Semiconductor Research Corporation Grant 86-12-109.     

Über ein Problem von Mordell in der Geometrie der Zahlen

For a latticeL in ⁿ with determinantd(L), let (L) denote the supremum of the values 2^–2 V(P)/d(L), taken over theL-admissible parallelepidesP, symmetric with respect to the origin and with faces parallel to the coordinate-axes. In 1936, Mordell asked for the constants _n = min (L) over alln-dimensional lattices. In this paper we investigate isolated minima of (L) in all over alln-dimensional lattices. In this paper we (Satz 1) and some examples are given. In particular, forn<=4, the set of lattices with isolated turns out to be dense in the space of lattices. Conversely, the set of (algebraically generated) lattices with non-isolated is dense, at least in the case of a plane (Satz 2).     

An algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations

We present an algorithm for linear programming which requires O(((m+n)n ²+(m+n)^1.5 n)L) arithmetic operations wherem is the number of constraints, andn is the number of variables. Each operation is performed to a precision of O(L) bits.L is bounded by the number of bits in the input. The worst-case running time of the algorithm is better than that of Karmarkar's algorithm by a factor of .     

An optimal algorithm for generating equivalence relations on a linear array of processors

We describe a cost-optimal parallel algorithm for enumerating all partitions (equivalence relations) of the set {1, ...,n}, in lexicographic order. The algorithm is designed to be executed on a linear array of processors. It usesn processors, each having constant size memory and each being responsible for producing one element of a given set partition. Set partitions are generated with constant delay leading to anO(B _n) time solution, whereB _n is the total number of set partitions. The same method can be generalized to enumerate some other combinatorial objects such as variations. The algorithm can be made adaptive, i.e. to run on any prespecified number of processors. To illustrate the model of parallel computation, a simple case of enumerating subsets of the set {1, ...,n}, having at mostm (n) elements is also described.The research is partialy supported by NSERC operating grant OGPIN 007.     

Successive Minimization of the State Complexity of the Self-dual Lattices Using Korkin-Zolotarev Reduced Basis

This work presents a systematic method to successively minimize the state complexity of the self-dual lattices (in the sense that each section of the trellis has the minimum possible number of states fixing its preceding co-ordinates). This is based on representing the lattice on an orthogonal co-ordinate system corresponding to the Gram-Schmidt (GS) vectors of a Korkin-Zolotarev (KZ) reduced basis. As part of the computations, we give expressions for the GS vectors of a KZ basis of the K ₁₂, ₂₄, and BW _n lattices. It is also shown that for the complex representation of the ₂₄ and the BW _n lattices over the set of the Gaussian integers, we have: (i) the corresponding GS vectors are along the standard co-ordinate system, and (ii) the branch complexity at each section of the resulting trellis meets a certain lower bound. This results in a very efficient trellis representation for these lattices over the standard co-ordinate system.     

Nodes of large degree in random trees and forests

We study the asymptotic behavior of the number N_k,n of nodes of given degree k in unlabeled random trees, when the tree size n and the node degree k both tend to infinity. It is shown that N_k,n is asymptotically normal if and asymptotically Poisson distributed if . If , then the distribution degenerates. The same holds for rooted, unlabeled trees and forests. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A Monte Carlo study of the dependence of the growth parameter for trees on the lattice dimension in the Eden model

We use the Monte Carlo method to compute the number of trees with n edges in the Eden model on d-dimensional simple cubic lattices for d=2,3,4,6,8,10. We compare these numbers with the exact data derived by the enumeration method up to n=12 on the square lattice and up to n=10 on the cubic lattice. We find that for d3, the computed values of the growth parameter for trees agree with the values that we derived earlier by the expansion in inverse powers of 2d-1.     

Dimension and decomposition in modular upper-continuous lattices

Slim rectangular lattices are special planar semimodular lattices introduced by G. Grätzer and E. Knapp in 2009. They are finite semimodular lattices L such that the ordered set Ji L of join-irreducible elements of L is the cardinal sum of two nontrivial chains. After describing these lattices of a given length n by permutations, we determine their number, |SRectL(n)|. Besides giving recursive formulas, which are effective up to about n = 1000, we also prove that |SRectL(n)| is asymptotically (n - 2)! · \({e^{2}/2}\). Similar results for patch lattices, which are special rectangular lattices introduced by G. Czédli and E. T. Schmidt in 2013, and for slim rectangular lattice diagrams are also given.     

Globally Irreducible Representations of Finite Groups and Integral Lattices

The notion of globally irreducible representations of finite groups has been introduced by B. H. Gross, in order to explain new series of Euclidean lattices discovered recently by N. Elkies and T. Shioda using Mordell--Weil lattices of elliptic curves. In this paper we first give a necessary condition for global irreducibility. Then we classify all globally irreducible representations of L ₂(q) and ²B₂(q), and of the majority of the 26 sporadic finite simple groups. We also exhibit one more globally irreducible representation, which is related to the Weil representation of degree (pⁿ-1)/2 of the symplectic group Sp_2n(p) (p 1 (mod 4) is a prime). As a consequence, we get a new series of even unimodular lattices of rank 2(pⁿ–1). A summary of currently known globally irreducible representations is given.     

Regularities in congruential random number generators

Summary This paper suggests, as did an earlier one, [1] that points inn-space produced by congruential random number generators are too regular for general Monte Carlo use. Regularity was established in [1] for multiplicative congruential generators by showing that all the points fall in sets of relatively few parallel hyperplanes. The existence of many containing sets of parallel hyperplanes was easily established, but proof that the number of hyperplanes was small required a result of Minkowski from the geometry of numbers—a symmetric, convex set of volume 2 ⁿ must contain at least two points with integral coordinates. The present paper takes a different approach to establishing the coarse lattice structure of congruential generators. It gives a simple, self-contained proof that points inn-space produced by the general congruential generatorr _i+1 ar _i +b modm must fall on a lattice with unit-cell volume at leastm ^n–1 There is no restriction ona orb; this means thatall congruential random number generators must be considered unsatisfactory in terms of lattices containing the points they produce, for a good generator of random integers should have ann-lattice with unit-cell volume 1.     

The distribution of sublattices of ℤ m

Lattices , are similar if one can be transformed into the other by an angle-preserving linear map. Similarity classes of lattices of rankn may be parametrized by a fundamental domain of the action ofGL _n () on the generalized upper half-plane _n . Given 1<nm and, letN(D,T) be the number of sublattices of _n which have rankn, similarity class inD, and determinant T. Our most basic result will be thatN(D,T)c ₁(m, n)(D)T ^m asT for suitable setsD, where is the invariant measure on _n . The casen=2 had been dealt with by Roelcke and by Maass using the theory of modular forms.Herrn Professor Hlawka zum achtzigsten Geburtstag gewidmetSupported in part by NSF-DMS-9401426