Angle orders,regular n-gon orders and the crossing number

A finite poset P(X,<) on a set X={ x ₁,...,x _m} is an angle order (regular n-gon order) if the elements of P(X,<) can be mapped into a family of angular regions on the plane (a family of regular polygons with n sides and having parallel sides) such that x _ij if and only if the angular region (regular n-gon) for x _i is contained in the region (regular n-gon) for x _j. In this paper we prove that there are partial orders of dimension 6 with 64 elements which are not angle orders. The smallest partial order previously known not to be an angle order has 198 elements and has dimension 7. We also prove that partial orders of dimension 3 are representable using equilateral triangles with the same orientation. This results does not generalizes to higher dimensions. We will prove that there is a partial order of dimension 4 with 14 elements which is not a regular n-gon order regardless of the value of n. Finally, we prove that partial orders of dimension 3 are regular n-gon orders for n3.This research was supported by the Natural Sciences and Engineering Research Council of Canada, grant numbers A0977 and A2415.     

Circle orders,N-gon orders and the crossing number

Let ={P ₁,...,P _m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P _i <P _j iff P _i is contained in P _j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.     

New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

Rank properties of certain semigroups

In this paper we consider certain ranks of some semigroups. These ranks are r ₁(S),r ₂(S),r ₃(S),r ₄(S) and r ₅(S) as defined below. We have r ₁≤r ₂≤r ₃≤r ₄≤r ₅. The semigroups are CL _n ,CL _m ×CL _n ,Z _n and SL _n . Here CL _n is a chain with n elements, Z _n is the zero semigroup on n elements and SL _n is the free semilattice generated by n elements and having 2 ⁿ −1 elements. We find many of the ranks for these classes of semigroups.     

Generating Sets of Finite Transformation Semigroups PK(n,r) and K (n,r)

Let P _n and T _n be the partial transformation and the full transformation semigroups on the set {1,…, n}, respectively. In this paper we find necessary and sufficient conditions for any set of partial transformations of height r in the subsemigroup PK(n, r) = {α ∈P _n : |im (α)| ≤r} of P _n to be a (minimal) generating set of PK(n, r); and similarly, for any set of full transformations of height r in the subsemigroup K(n, r) = {α ∈T _n : |im (α)| ≤r} of T _n to be a (minimal) generating set of K(n, r) for 2 ≤ r ≤ n ? 1.     

The idempotent-separating degree of a block-group

In this note we characterize the least positive integer n such that there exists an idempotent-separating homomorphism from a finite block-group S into the monoid of all partial transformations of a set with n elements. In particular, as for a fundamental semigroup S this number coincides with the smallest size of a set for which S can be faithfully represented by partial transformations, we obtain a generalization of Easdown’s result established for fundamental finite inverse semigroups. The author gratefully acknowledges support of FCT and FEDER, within the project POCTI-ISFL-1-143 of CAUL, and the fellowship SFRH/BSAB/244/2001.     

Repeated random insertion into a priority queue

The average cost of inserting n elements into an initially empty heap is analyzed, under the assumption that the n! orders in which the n elements can be inserted are equally likely. It is proved that this average, expressed in number of exchanges per insertion, is bounded by a constant about 1.7645.     

New negative Latin square type partial difference sets in nonelementary abelian 2-groups and 3-groups

A partial difference set having parameters (n ², r(n − 1), n + r ² − 3r, r ² − r) is called a Latin square type partial difference set, while a partial difference set having parameters (n ², r(n + 1), − n + r ² + 3r, r ² + r) is called a negative Latin square type partial difference set. Nearly all known constructions of negative Latin square partial difference sets are in elementary abelian groups. In this paper, we develop three product theorems that construct negative Latin square type partial difference sets and Latin square type partial difference sets in direct products of abelian groups G and G′ when these groups have certain Latin square or negative Latin square type partial difference sets. Using these product theorems, we can construct negative Latin square type partial difference sets in groups of the form where the s _i are nonnegative integers and s ₀ + s ₁ ≥ 1. Another significant corollary to these theorems are constructions of two infinite families of negative Latin square type partial difference sets in 3-groups of the form for nonnegative integers s _i . Several constructions of Latin square type PDSs are also given in p-groups for all primes p. We will then briefly indicate how some of these results relate to amorphic association schemes. In particular, we construct amorphic association schemes with 4 classes using negative Latin square type graphs in many nonelementary abelian 2-groups; we also use negative Latin square type graphs whose underlying sets can be elementary abelian 3-groups or nonelementary abelian 3-groups to form 3-class amorphic association schemes.      

Linked partitions and linked cycles

The notion of noncrossing linked partition arose from the study of certain transforms in free probability theory. It is known that the number of noncrossing linked partitions of [n+1] is equal to the n-th large Schröder number r_n, which counts the number of Schröder paths. In this paper we give a bijective proof of this result. Then we introduce the structures of linked partitions and linked cycles. We present various combinatorial properties of noncrossing linked partitions, linked partitions, and linked cycles, and connect them to other combinatorial structures and results, including increasing trees, partial matchings, k-Stirling numbers of the second kind, and the symmetry between crossings and nestings over certain linear graphs.     

On explicit factors of cyclotomic polynomials over finite fields

We study the explicit factorization of 2 ⁿ r-th cyclotomic polynomials over finite field \mathbbF_q{\mathbb{F}_q} where q, r are odd with (r, q) = 1. We show that all irreducible factors of 2 ⁿ r-th cyclotomic polynomials can be obtained easily from irreducible factors of cyclotomic polynomials of small orders. In particular, we obtain the explicit factorization of 2 ⁿ 5-th cyclotomic polynomials over finite fields and construct several classes of irreducible polynomials of degree 2 ^n–2 with fewer than 5 terms.     

Examples of amalgamated products

The rank of a groupG is the minimal number of elements that generateG. For any natural numbern we construct two groups,G ₁ of rankr(G ₁)=n andG ₂ of rankr(G ₂)=2n such that their amalgamated product over an infinite cyclic subgroup, malnormal in both factors, is generated by 2n=r(G ₁)+r(G ₂)−n elements. We also consider an example of an amalgamated product ofn factors: such thatr(G)=n +1, andr(A)≥1. This example realizes the lower bound given by Weidmann [W1] (see Theorem 2 in the present paper).     

Cycle-free partial orders and chordal comparability graphs

This paper studies a number of problems on cycle-free partial orders and chordal comparability graphs. The dimension of a cycle-free partial order is shown to be at most 4. A linear time algorithm is presented for determining whether a chordal directed graph is transitive, which yields an O(n ²) algorithm for recognizing chordal comparability graphs. An algorithm is presented for determining whether the transitive closure of a digraph is a cycle-free partial order in O(n+m _t)time, where m _tis the number of edges in the transitive closure.     

A bipartite analogue of Dilworth’s theorem for multiple partial orders

Let r be a fixed positive integer. It is shown that, given any partial orders <₁, …, <_r on the same n-element set P, there exist disjoint subsets A,BP, each with at least n^1−o(1) elements, such that one of the following two conditions is satisfied: (1) there is an such that every element of A is larger than every element of B in the partial order <_i, or (2) no element of A is comparable with any element of B in any of the partial orders <₁, …, <_r. As a corollary, we obtain that any family C of n convex compact sets in the plane has two disjoint subfamilies A,BC, each with at least n^1−o(1) members, such that either every member of A intersects all members of B, or no member of A intersects any member of B.     

Approximation of smooth functions on compact two-point homogeneous spaces

Estimates of Kolmogorov n-widths and linear n-widths , (1q∞) of Sobolev's classes , (r>0, 1p∞) on compact two-point homogeneous spaces (CTPHS) are established. For part of (p,q)[1,∞]×[1,∞], sharp orders of or were obtained by Bordin et al. (J. Funct. Anal. 202(2) (2003) 307). In this paper, we obtain the sharp orders of and for all the remaining (p,q). Our proof is based on positive cubature formulas and Marcinkiewicz–Zygmund-type inequalities on CTPHS.     

Unit and Proper Tube Orders

In 2005, we defined the n-tube orders, which are the n-dimensional analogue of interval orders in 1 dimension, and trapezoid orders in 2 dimensions. In this paper we consider two variations of n-tube orders: unit n-tube orders and proper n-tube orders. It has been proven that the classes of unit and proper interval orders are equal, and the classes of unit and proper trapezoid orders are not. We prove that the classes of unit and proper n-tube orders are not equal for all n ≥ 3, so the general case follows the situation in 2 dimensions.     

Representations of Integers as Sums of 32 Squares

In this paper, we derive a new explicit formula for r ₃₂(n), where r _k(n) is the number of representations of n as a sum of k squares. For a fixed integer k, our method can be used to derive explicit formulas for r _8k (n). We conclude the paper with various conjectures that lead to explicit formulas for r _2k (n), for any fixed positive integer k > 4.     

Approximation of functions by certain nonlinear integral operators

We study approximation properties of certain nonlinear integral operators L _n * obtained by a modification of given operators L _n . The operators L _n;r and L _n;r * of r-times differentiable functions are also studied. We give theorems on approximation orders of functions by these operators in polynomial weight spaces.     

On the deformation of linear r-fields

We study the question: For which (r,n) can a linear r-field on the (n-1)-sphere in an n-dimensional real linear space be deformed through a continuous path of linear r-fields into an orthonormal r-field. We provide complete answers for the cases: (r,n)=(2,4),(3,4), and provide several partial results for the cases (r,n)=(2,2m), where m is an even integer satisfying m4. Characterizations of linear r-fields are pivotal in the investigation.     

The Monoid of All Injective Order Preserving Partial Transformations on a Finite Chain

In this paper we study several structural properties of the monoids \poi _n of all injective order preserving partial transformations on a chain with n elements. Our main aim is to give a presentation for these monoids. January 27, 1999