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.     

Some Erdös-Szekeres type results about points in space

The Erdös-Szekeres convexn-gon theorem states that for anyn3, there is a smallest integerf(n) such that any set of at leastf(n) points in the planeE ², no three collinear, contains the vertices of a convexn-gon. We consider three versions of this result as applied to convexly independent points and convex polytopes inE ^d >,d2.     

Convex nonagons with five intervertex distances

The vertices of a convex planar nonagon determine exactly five distances if and only if they are nine vertices of a regular 10-gon or a regular 11-gon. This result has important ties to related concerns, including the maximum number of points in the plane that determine exactly five distances and, for each n7, the samllest t for which there exists a convex n-gon whose vertices determine t distances and are not all on one circle.     

Circumscribed Polygons of Small Area

Given any plane strictly convex region K and any positive integer n≥3, there exists an inscribed 2n-gon Q _2n and a circumscribed n-gon P _n such that

Minimum costK-forest covers

A forest cover of a graph is a spanning forest for which each component has at least two nodes. IfK is a subset of nodes, aK-forest cover is a forest cover including exactly one node fromK in each component. AK-forest cover is of minimum cost if the sum of the costs of the edges is minimum. We present an0(n ² + ¦K¦² n) algorithm for determining the minimum costK-forest cover of a graph withn nodes. We show that the algorithm can also be used to determine, in0(n ² + ({K — K'¦ + _{deK'd v} )² _n ) time, the minimum costK-forest cover having degree equald _v each nodev of an arbitrary subsetK' ofK.     

Efficient Regular Polygon Dissections

We study the minimum number g(m,n) (respectively, p(m,n)) of pieces needed to dissect a regular m-gon into a regular n-gon of the same area using glass-cuts (respectively, polygonal cuts). First we study regular polygon-square dissections and show that n/2 -2 g(4,n) (n/2) + o(n) and n/4 g(n,4) (n/2) + o(n) hold for sufficiently large n. We also consider polygonal cuts, i.e., the minimum number p(4,n) of pieces needed to dissect a square into a regular n-gon of the same area using polygonal cuts and show that n/4 p(4,n) (n/2) + o(n) holds for sufficiently large n. We also consider regular polygon-polygon dissections and obtain similar bounds for g(m,n) and p(m,n).     

What can we do with only a pair of rusty compasses?

Compasses are called rusty, if one can draw only the unit circle with them. We prove that from two points A and B, with only rusty compasses, one can draw the points of k-section of AB, and all the vertices of a regular n-gon which has a side AB, where k is any integer greater than 1, and n=3, 4, 5, 6, 8, 12, 17, 257, ..., etc. Generally, let A be (0, 0) and let B be (, 0), then one can draw all the points (x, y) where x and y are any elements in some regular 2 ^m -extension of the rational field, for m=1, 2, 3, ...     

The Unit Distance Problem for Centrally Symmetric Convex Polygons

   Abstract. Let f(n) be the maximum number of unit distances determined by the vertices of a convex n -gon. Erdos and Moser conjectured that this function is linear. Supporting this conjecture we prove that f ^sym (n)

On the minimality of polygon triangulation

The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simplen-gon is equal ton+2w –d – 2, wherew is the number of holes andd is the maximum number of independent degenerate triangles of then-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-freen-gon. The algorithm takesO(nlog² n+DK ²) time, whereD is the maximum number of vertices lying on the same line in then-gon andK is the number of minimally degenerate triangles of then-gon.     

Universal Polynomial Majorants on Convex Bodies

Let K be a convex body in ^d (d2), and denote by B_n(K) the set of all polynomials p_n in ^d of total degree n such that |p_n|1 on K. In this paper we consider the following question: does there exist a p*_nB_n(K) which majorates every element of B_n(K) outside of K? In other words can we find a minimal γ1 and p*_nB_n(K) so that |p_n(x)|γ |p*_n(x)| for every p_nB_n(K) and x ^d\K? We discuss the magnitude of γ and construct the universal majorants p*_n for evenn. It is shown that γ can be 1 only on ellipsoids. Moreover, γ=O(1) on polytopes and has at most polynomial growth with respect to n, in general, for every convex body K.     

Optimally nested regularN-gons

Various sequences of polygons are described and the radii are determined when each successive member of the sequence is the largest next member of the sequence containing its predecessor, or else the smallest next member of the sequence containing its predecessor. In particular, a correct solution of the problem of finding the area of the circle that is the limit of the largest regularn-gon fitting inside a regular (n?1)-gon, starting from an equilateral triangle of unit area, is found to be 0.0753105.     

On the volume of equichordal sets

IfK is an equichordal set of chord length 1, i.e. ann-dimensional convex body with a pointp K such that every chord throughp has length 1, it can be shown that _n /2 ⁿ v(K) < _n /2, wherev(K) denotes the volume ofK and _n the volume of ann-dimensional unit ball. Explicit estimates are established for the deviation ofK from a ball of radius 1/2 ifv(K)– _n /2 ⁿ is small, and from a semiball of radius 1 if 1/2 _n –v(K) is small.Supported by National Science Foundation Research Grant DMS 8701893.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.     

On existence of finite universal Korovkin sets in the centre of group algebras

In this paper, we characterize compact groupsG as well as connected central topological groupsG for which the centreZ(L ¹(G)) admits a finite universal Korovkin set. Also we prove that ifG is a non-connected central topological group which has a compact open normal subgroupK such thatG=KZ, thenZ(L ¹(G)) admits a finite universal Korovkin set if is a finite-dimensional separable metric space or equivalentlyG is separable metrizable andG/K has finite torsion-free rank.     

Isomorphic Steiner symmetrization

This paper proves that there exist 3n Steiner symmetrizations that transform any convex set Kⁿ into an isomorphic Euclidean ball; i.e. if vol(K)=vol(D_n) where D_n is the standard Euclidean unit ball, then K can be transformed into a body K such that c₁D_nKc₂D_n, where c₁,c₂ are numerical constants. Moreover, for any c>2, cn symmetrizations are also enough.     

On the existence of Fagnano trajectories in convex polygonal billiards

We prove that an n-gon is pedal strong Fagnano trajectory in some convex polygonal billiard table if and only if it is a convex Poncelet n-gon.      

Equidissections of centrally symmetric octagons

Summary In 1970 Monsky proved that a square cannot be cut into an odd number of triangles of equal areas. In 1988 Kasimatis proved that if a regularn-gon,n 5, is cut intom triangles of equal areas, thenm is a multiple ofn. These two results imply that a centrally symmetric regular polygon cannot be cut into an odd number of triangles of equal areas. We conjecture that the conclusion holds even if the restriction regular is deleted from the hypothesis and prove that it does forn = 6 andn = 8.     

Separation of hypersurfaces

We give a generalization of results obtained in [15]. LetK ⁿ denote the set of embedded hypersurfaces in ⁿ⁺¹; for all xSⁿ and MK ⁿ we denote by C _x ^M the apparent contour ofM in the directionx. Then we give a sufficient condition on WSⁿ such that the map _W ^{K n}:K ⁿ P(T Sⁿ) , defined by _W ^{K n} (M)={C _w ^M ¦ wW}, is injective.     

Universal meromorphic approximation on Vitushkin sets

The paper proves the following result on universal meromorphic approximation: Given any unbounded sequence {λ _n } ? ?, there exists a function ?, meromorphic on ?, with the following property. For every compact set K of rational approximation (i.e. Vitushkin set), and every function f, continuous on K and holomorphic in the interior of K, there exists a subsequence {n _k } of ? such that $ \left\{ {\varphi \left( {z + \lambda _{n_k } } \right)} \right\} The paper proves the following result on universal meromorphic approximation: Given any unbounded sequence {λ _n } ⊂ ℂ, there exists a function ϕ, meromorphic on ℂ, with the following property. For every compact set K of rational approximation (i.e. Vitushkin set), and every function f, continuous on K and holomorphic in the interior of K, there exists a subsequence {n _k } of ℕ such that converges to f(z) uniformly on K. A similar result is obtained for arbitrary domains G ≠ ℂ. Moreover, in case {λ _n }={n} the function ϕ is frequently universal in terms of Bayart/Grivaux [3]. Original Russian Text ? W.Luh, T.Meyrath, M.Niess, 2008, published in Izvestiya NAN Armenii. Matematika, 2008, No. 6, pp. 66–75.     

The Smallest Parallelepiped of n Random Points and Peeling

Let n random points be given with uniform distribution in the d-dimensional unit cube [0,1]^d. The smallest parallelepiped A which includes all the n random points is dealt with. We investigate the asymptotic behavior of the volume of A as n tends to . Using a point process approach, we derive also the asymptotic behavior of the volumes of the k-th smallest parallelepipeds A _n ^(k) which are defined by iteration. Let A _n = A _n ⁽¹⁾ . Given A _n ^(k,-,1) delete the random points X _i which are on the boundary A _n ^(k,-,1) , and construct the smallest parallelepiped which includes the inner points of A _n ^(k,-,1) , this defines A _n ^(k) . This procedure is known as peeling of the parallelepiped A_n.