Fractional dimension of partial orders

Given a partially ordered setP=(X, ), a collection of linear extensions {L ₁,L ₂,...,L _r } is arealizer if, for every incomparable pair of elementsx andy, we havex<y in someL _i (andy<x in someL _j ). For a positive integerk, we call a multiset {L ₁,L ₂,...,L _t } ak-fold realizer if for every incomparable pairx andy we havex<y in at leastk of theL _i 's. Lett(k) be the size of a smallestk-fold realizer ofP; we define thefractional dimension ofP, denoted fdim(P), to be the limit oft(k)/k ask. We prove various results about the fractional dimension of a poset.Research supported in part by the Office of Naval Research.     

On a metric generalization of ramsey’s theorem

An increasing sequence of realsx=〈x _i :i<ω〉 is simple if all “gaps”x _i +1−x _i are different. Two simple sequencesx andy are distance similar ifx _i +1−x _i <x _j +1−x _j if and only ify _i +1−y _i <y _j +1−y _j for alli andj. Given any bounded simple sequencex and any coloring of the pairs of rational numbers by a finite number of colors, we prove that there is a sequencey distance similar tox all of whose pairs are of the same color. We also consider many related problems and generalizations. Partially supported by OTKA-4269. Partially supported by NSF grant STC-91-19999. Partially supported by OTKA-T-020914, NSF grant CCR-9424398 and PSC-CUNY Research Award 663472.     

Inequalities for the greedy dimensions of ordered sets

Every linear extension L: [x ₁<x ₂<...<x _m ] of an ordered set P on m points arises from the simple algorithm: For each i with 0i<m, choose x _i+1 as a minimal element of P–{x _j :ji}. A linear extension is said to be greedy, if we also require that x _i+1 covers x _i in P whenever possible. The greedy dimension of an ordered set is defined as the minimum number of greedy linear extensions of P whose intersection is P. In this paper, we develop several inequalities bounding the greedy dimension of P as a function of other parameters of P. We show that the greedy dimension of P does not exceed the width of P. If A is an antichain in P and |P–A|2, we show that the greedy dimension of P does not exceed |P–A|. As a consequence, the greedy dimension of P does not exceed |P|/2 when |P|4. If the width of P–A is n and n2, we show that the greedy dimension of P does not exceed n ²+n. If A is the set of minimal elements of P, then this inequality can be strengthened to 2n–1. If A is the set of maximal elements, then the inequality can be further strengthened to n+1. Examples are presented to show that each of these inequalities is best possible.Research supported in part by the National Science Foundation under ISP-80110451.Research supported in part by the National Science Foundation under ISP-80110451 and DMS-8401281.     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Arithmetic progressions in partially ordered sets

Van der Waerden's arithmetic sequence theorem—in particular, the density version of Szemerédi—is generalized to partially ordered sets in the following manner. Let w and t be fixed positive integers and >0. Then for every sufficiently large partially ordered set P of width at most w, every subset S of P satisfying |S||P| contains a chain a ₁, a ₂,..., a ₁ such that the cardinality of the interval [a _i, a _i+1] in P is the same for each i.Research supported by NSF grant DMS 8401281.Research supported by ONR grant N00014-85-K-0769.     

Greedy posets for the bump-minimizing problem

A bump (x _i,x _i+1) occurs in a linear extension L={x ₁<...n} of a poset P, if x _ii+1 in P. L. is greedy if x _ij for every j>i, whenever (x _i x _i+1) in a bump in L. The purpose of this paper is to give a characterization of all greedy posets. These are the posets for which every greedy linear extension has a minimum number of bumps.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Sharpening the LYM inequality

The level sequence of a Sperner familyF is the sequencef(F)={f _i (F)}, wheref _i (F) is the number ofi element sets ofF . TheLYM inequality gives a necessary condition for an integer sequence to be the level sequence of a Sperner family on ann element set. Here we present an indexed family of inequalities that sharpen theLYM inequality.Research supported in part by Alexander v. Humboldt-StiftungResearch supported in part by NSF under grant DMS-86-06225 and AFOSR grant OSR-86-0078Research supported in part by NSF grant CCR-8911388Research supported in part by OTKA 327 0113     

Repeated distances in space

Fori = 1,...,n letC(x_i, r_i) be a circle in the plane with centrex _i and radiusr _i. A repeated distance graph is a directed graph whose vertices are the centres and where (x _i, x_j) is a directed edge wheneverx _j lies on the circle with centrex _i. Special cases are the nearest neighbour graph, whenr _i is the minimum distance betweenx _i and any other centre, and the furthest neighbour graph which is similar except that maximum replaces minimum. Repeated distance graphs generalize to any dimension with spheres or hyperspheres replacing circles. Bounds are given on the number of edges in repeated distance graphs ind dimensions, with particularly tight bounds for the furthest neighbour graph in three dimensions. The proofs use extremal graph theory.Research supported by the Natural Science and Engineering Research Council grant number A3013 and the F.C.A.R. grant number EQ1678.     

Matrix Representations for Positive Noncommutative Polynomials

In real semialgebraic geometry it is common to represent a polynomial q which is positive on a region R as a weighted sum of squares. Serious obstructions arise when q is not strictly positive on the region R. Here we are concerned with noncommutative polynomials and obtaining a representation for them which is valid even when strict positivity fails. Specifically, we treat a ``symmetric' polynomial q(x, h) in noncommuting variables, {x<sub>1</sub>, . . . , } and {h<sub>1</sub>, . . . , } for which q(X,H) is positive semidefinite whenever are tuples of selfadjoint matrices with ||X<sub>j</sub>|| ≤ 1 but H<sub>j</sub> unconstrained. The representation we obtain is a Gram representation in the variables h where P<sub>q</sub> is a symmetric matrix whose entries are noncommutative polynomials only in x and V is a ``vector' whose entries are polynomials in both x and h. We show that one can choose P_q such that the matrix P_q(X) is positive semidefinite for all ||X_j|| ≤ 1. The representation covers sum of square results ([Am. Math. (to appear); Linear Algebra Appl. 326 (2001), 193–203; Non commutative Sums of Squares, preprint]) when g_x = 0. Also it allows for arbitrary degree in h, rather than degree two, in the main result of [Matrix Inequalities: A Symbolic Procedure to Determine Convexity Automatically to appear IOET July 2003] when restricted to x-domains of the type ||X_j|| ≤ 1. Partially supported by NSF, DARPA and Ford Motor Co. Partially supported by NSF grant DMS-0140112 Partially supported by NSF grant DMS-0100367     

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.     

The Embedding Theorem for Cantor Varieties

Let m and n be fixed integers, with 1 m < n. A Cantor variety C _m,n is a variety of algebras with m n-ary and n m-ary basic operations which is defined in a signature ={g₁,...,g_m,f₁,...,f_n} by the identities f_ig₁x₁,...,x_n),...,g_mx₁,...,x_n) = x_i, _i=1,...,n, g_jf₁x₁,...,x_m),...,f_nx₁,...,x_m)) = x_j, _j=1,...,m. We prove the following: (a) every partial C _m,n-algebra A is isomorphically embeddable in the algebra G= A; S(A) of C _m,n; (b) for every finitely presented algebra G= A; S in C _m,n, the word problem is decidable; (c) for finitely presented algebras in _{C m}, the occurrence problem is decidable; (d) _{C m,n} has a hereditarily undecidable elementary theory.     

Sphere orders

Ann-sphere order is a finite partially ordered set representable by containment ofn-spheres in Euclidean (n+1)-space. We present a sequence {P _i } of ordered sets such that eachP _i is ann-sphere order only forni; one consequence is that we are able to determine the dimension of a Euclidean space-time manifold from the finite suborders of its causality order.Research supported by ONR grant N00014 85-K-0769.     

Trace formulas for a class of subnormal tuples of operators

Trace formulas are established for the product of commutators related to subnormal tuple of operators (S ₁,...,S _n ) with minimal normal extension (N ₁,...,N _n ) satisfying conditions that sp(S _j )/sp(N _j ) is simply-connected with smooth boundary Jordan curve sp(N _i ) and [S _j ^* ,S _j ]^1/2 L ¹,j=1, 2,...,n.Some complete unitary invariants related to the trace formulas are found.This work is supported in part by NSF Grant no. DMS-9101268.     

On the number of antipodal or strictly antipodal pairs of points in finite subsets ofR d,II

The paper is a continuation of [MM], namely containing several statements related to the concept of antipodal and strictly antipodal pairs of points in a subsetX ofR ^d , which has cardinalityn. The pointsx _i, x_jX are called antipodal if each of them is contained in one of two different parallel supporting hyperplanes of the convex hull ofX. If such hyperplanes contain no further point ofX, thenx _i, x_j are even strictly antipodal. We shall prove some lower bounds on the number of strictly antipodal pairs for givend andn. Furthermore, this concept leads us to a statement on the quotient of the lengths of longest and shortest edges of speciald-simplices, and finally a generalization (concerning strictly antipodal segments) is proved.Research (partially) supported by Hungarian National Foundation for Scientific Research, grant no. 1817     

Temperely-Lieb Algebras and the Four-Color Theorem

The Temperley–Lieb algebra T_n with parameter 2 is the associative algebra over Q generated by 1,e₀,e₁, . . .,e_n, where the generators satisfy the relations if |i–j|=1 and e_ie_j=e_je_i if |i–j|2. We use the Four Color Theorem to give a necessary and sufficient condition for certain elements of T_n to be nonzero. It turns out that the characterization is, in fact, equivalent to the Four Color Theorem.* Partially supported by NSF under Grant DMS-9802859 and by NSA under grant MDA904-97-1-0015. Partially supported by NSF under Grant DMS-9623031 and by NSA under Grant MDA904-98-1-0517.     

A new approach to the dynamic maintenance of maximal points in a plane

A pointp _i=(x _i, y_i) in thex–y plane ismaximal if there is no pointp _j=(x _j, y_j) such thatx _j>x_i andy _j>y_i. We present a simple data structure, a dynamic contour search tree, which contains all the points in the plane and maintains an embedded linked list of maximal points so thatm maximal points are accessible inO(m) time. Our data structure dynamically maintains the set of points so that insertions takeO(logn) time, a speedup ofO(logn) over previous results, and deletions takeO((logn)²) time.The research of the first author was partially supported by the National Science Foundation under Grant No. DCR-8320214 and by the Office of Naval Research on Contract No. N 00014-86-K-0689. The research of the second author was partially supported by the Office of Naval Research on Contract No. N 00014-86-K-0689.     

Majorization of Gaussian processes and geometric applications

Summary Let (x _i ^* ) _i=1 ⁿ denote the decreasing rearrangement of a sequence of real numbers (x _i ) _i=1 ⁿ . Then for everyij, and every 1kn, the 2-nd order partial distributional derivatives satisfy the inequality, . As a consequence we generalize the theorem due to Fernique and Sudakov. A generalization of Slepian's lemma is also a consequence of another differential inequality. We also derive a new proof and generalizations to volume estimates of intersecting spheres and balls in ⁿ proved by Gromov.Supported by NSF grant # DMS 8909745, and the USA-Israel Binational Science Foundation grant # 86-00074, and grant for the Promotion of Research at the Technion     

Lyapunov exponent for the parabolic anderson model with lévy noise

We consider the asymptotic almost sure behavior of the solution of the equationwhere {Y_x:x Z^d} is a field of independent Lévy processes and is the discrete Laplacian.Research of the first two authors supported in part by a grant from NSF, of the third author by JSPS Grant-in-Aid for Scientific Research, Kiban(C) 13640103     

Regularity of the Bergman Projection on Forms and Plurisubharmonicity Conditions

Let be a smoothly bounded domain. Suppose Ω has a defining function, such that the sum of any q eigenvalues of its complex Hessian is non-negative. We show that this implies global regularity of the Bergman projection, B _j-1, and the -Neumann operator, N _j , acting on (0,j)-forms, for .Research of the first author was partially supported by a Rackham Fellowship.Research of the second author was partially supported by an NSF grant.     

On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles

Let ₁,..., _m bem simple Jordan curves in the plane, and letK ₁,...,K _m be their respective interior regions. It is shown that if each pair of curves _i , _j ,i j, intersect one another in at most two points, then the boundary ofK= _i ^=1m K _i contains at most max(2,6m – 12) intersection points of the curves ₁, and this bound cannot be improved. As a corollary, we obtain a similar upper bound for the number of points of local nonconvexity in the union ofm Minkowski sums of planar convex sets. Following a basic approach suggested by Lozano Perez and Wesley, this can be applied to planning a collision-free translational motion of a convex polygonB amidst several (convex) polygonal obstaclesA ₁,...,A _m . Assuming that the number of corners ofB is fixed, the algorithm presented here runs in timeO (n log² n), wheren is the total number of corners of theA _i 's.Work on this paper by the second author has been supported in part by a grant from the Bat-Sheva Fund at Israel. Work by the fourth author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation.