Embedding a polytope in a lattice

We present a special similarity ofR ⁴ⁿ which maps lattice points into lattice points. Applying this similarity, we prove that if a (4n−1)-polytope is similar to a lattice polytope (a polytope whose vertices are all lattice points) inR ⁴ⁿ , then it is similar to a lattice polytope inR ⁴ⁿ⁻¹, generalizing a result of Schoenberg [4]. We also prove that ann-polytope is similar to a lattice polytope in someR ^N if and only if it is similar to a lattice polytope inR ²ⁿ⁺¹, and if and only if sin²(<ABC) is rational for any three verticesA, B, C of the polytope.     

(K, K′)-quasiconformal Harmonic Mappings

We prove that a harmonic diffeomorphism between two Jordan domains with C ² boundaries is a (K, K′) quasiconformal mapping for some constants K ≥ 1 and K′ ≥ 0 if and only if it is Lipschitz continuous. In this setting, if the domain is the unit disk and the mapping is normalized by three boundary points condition we give an explicit Lipschitz constant in terms of simple geometric quantities of the Jordan curve which surrounds the codomain and (K, K′). The results in this paper generalize and extend several recently obtained results.     

Note on induced subgraphs of the unit distance graphE n

The unit distance graphE ⁿ is the graph whose vertices are the points in Euclideann-space, and two vertices are adjacent if and only if the distance between them is 1. We prove that for anyn there is a finite bipartite graph which cannot be embedded inE ⁿ as an induced subgraph and that every finite graph with maximum degreed can be embedded inE ^N ,N=(d ³ –d)/2, as an induced subgraph.     

Two comments on Dvoretzky’s sphericity theorem

For any two positive integersk, l and anyɛ>0 there exists anN(k, l, ɛ) so that given anyl convex bodiesC ₁, …,C _l symmetric about the origin inE ⁿ withn≧N there exists a subspaceE ^k so that eachC _i intersectsE ^k, or has a projection intoE ^k, in a set which is nearly spherical (asphericity <ɛ). The measure of the totality ofE ^k which intersect a given body inE ⁿ in a nearly ellipsoidal set is considered and an affine invariant measure is introduced for that purpose.     

On Some Rational Triangles

We prove that every set of n ≥ 3 points in \mathbbR²{\mathbb{R}^2} can be slightly perturbed to a set of n points in \mathbbQ²{\mathbb{Q}^2} so that at least 3(n − 2) of mutual distances between those new points are rational numbers. Some special rational triangles that are arbitrarily close to a given triangle are also considered. Given a triangle ABC, we show that for each ε > 0 there is a triangle A′B′C′ with rational sides and at least one rational median such that |AA′|, |BB′|, |CC′| < ε and a Heronian triangle A′′B′′C′′ with three rational internal angle bisectors such that A^￠￠, B^￠￠, C^￠￠ ? \mathbbQ²{A^{\prime\prime}, B^{\prime\prime}, C^{\prime\prime} \in \mathbb{Q}^2} and |AA′′|, |BB′′|, |CC′′| < ε.     

Vertices of simple modules and normal subgroups ofp-solvable groups

Let π be a set of prime numbers andG a finite π-separable group. Let θ be an irreducible π′-partial character of a normal subgroupN ofG and denote by I_π′ (G‖θ), the set of all irreducible π′-partial characters Φ ofG such that θ is a constituent of Φ_N. In this paper, we obtain some information about the vertices of the elements in I_π′ (G‖θ). As a consequence, we establish an analogue of Fong's theorem on defect groups of covering blocks, for the vertices of the simple modules (in characteristicsp) of a finitep-solvable group lying over a fixed simple module of a normal subgroup.     

On Cycles in 3-Connected Graphs

 Let G be a 3-connected graph of order n and S a subset of vertices. Denote by δ(S) the minimum degree (in G) of vertices of S. Then we prove that the circumference of G is at least min{|S|, 2δ(S)} if the degree sum of any four independent vertices of S is at least n+6. A cycle C is called S-maximum if there is no cycle C ^′ with |C ^′∩S|>|C∩S|. We also show that if ∑⁴ _i=1 d(a _i)≥n+3+|⋂⁴ _i=1 N(a _i)| for any four independent vertices a ₁, a ₂, a ₃, a ₄ in S, then G has an S-weak-dominating S-maximum cycle C, i.e. an S-maximum cycle such that every component in G−C contains at most one vertex in S. Received: March 9, 1998 Revised: January 7, 1999     

The cauchy problem at simply characteristic points andP-convexity

Summary Let Ω cR ⁿ be an open set and let P be a linear partial differential operator with constant coefficients inR ⁿ. Then Ω is said to be P-convex if for each f ε C^∞(Ω) there is a u ε D′(Ω) such that P(D)u=f. A complete geometric characterization of P-convex sets inR ³ is given when P is of principal type and when Ω has C²-boundary. As a step in the proof one also obtains necessary and sufficient conditions for uniqueness in the local Cauchy problem at simply characteristic points inR ³. The tools are a sophisticated use of the author's uniqueness cones on one hand and his semi-global nullsolutions on the other hand. Hints are given on the difficulties that may be encountered inR ⁿ for the same problem. Entrata in Redazione il 7 giugno 1978.     

Some results on the majorization theorem of connected graphs

Let π = (d ₁, d ₂, ..., d _n ) and π′ = (d′ ₁, d′ ₂, ..., d′ _n ) be two non-increasing degree sequences. We say π is majorizated by π′, denoted by π ⊲ π′, if and only if π ≠ π′, Σ _i=1 ⁿ d _i = Σ _i=1 ⁿ d′ _i , and Σ _i=1 ^j d _i ≤ Σ _i=1 ^j d′ _i for all j = 1, 2, ..., n. Weuse C _π to denote the class of connected graphs with degree sequence π. Let ρ(G) be the spectral radius, i.e., the largest eigenvalue of the adjacent matrix of G. In this paper, we extend the main results of [Liu, M. H., Liu, B. L., You, Z. F.: The majorization theorem of connected graphs. Linear Algebra Appl., 431(1), 553–557 (2009)] and [Bıyıkoğlu, T., Leydold, J.: Graphs with given degree sequence and maximal spectral radius. Electron. J. Combin., 15(1), R119 (2008)]. Moreover, we prove that if π and π′ are two different non-increasing degree sequences of unicyclic graphs with π ⊲ π′, G and G′ are the unicyclic graphs with the greatest spectral radii in C _π and C′ _π , respectively, then ρ(G) < ρ(G′).     

Interpolating sequences in the ball ofC n

LetB be the unit ball ofC ⁿ , I give necessary conditions on sequenceS of points inB to beH ^∞(B) interpolating in term of aC ⁿ valued holomorphic function zero onS (a substitute for the interpolating Blaschke product). These conditions are sufficient to prove that the sequenceS is interpolating for ∩ _p>1 (B) and is also interpolating forH ^p (B) for 1≤p<∞.     

Symmetric designs with bruck subdesigns

IfP is a finite projective plane of ordern with a proper subplaneQ of orderm which is not a Baer subplane, then a theorem of Bruck [Trans. AMS 78(1955), 464–481] asserts thatn≧m ²+m. If the equalityn=m ²+m were to occur thenP would be of composite order andQ should be called a Bruck subplane. It can be shown that if a projective planeP contains a Bruck subplaneQ, then in factP contains a designQ′ which has the parameters of the lines in a three dimensional projective geometry of orderm. A well known scheme of Bruck suggests using such aQ′ to constructP. Bruck’s theorem readily extends to symmetric designs [Kantor, Trans. AMS 146 (1969), 1–28], hence the concept of a Bruck subdesign. This paper develops the analoque ofQ′ and shows (by example) that the analogous construction scheme can be used to find symmetric designs.     

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.     

Sommets et normales concourantes des courbes convexes de largeur constante et singularités des hérissons

LetC be a convex curve of constant width and of classC ₄ ⁺ . It is known thatC has at least 6 vertices and its interior contains either a point through which infinitely many normals pass or an open set of points through each of which pass at least 6 normals. If all its vertices are nondegenerate, then: (i)C has exactly 6 vertices if, and only if, its evolute is the boundary of a topological disc through each interior point of which pass at least 6 normals; (ii) ifC has more than 6 vertices, then there exists an open set of points through each of which pass at least 10 normals. The proof: (i) expresses the number of normals passing through a point as a function of the index with respect to the evolute; (ii) relates this index to the number of singularities of the evolute (i.e. of vertices). Furthermore, we give formulas for counting singularities of generic hedgehogs in ℝ² and ℝ³.

     

Polytopal and nonpolytopal spheres an algorithmic approach

The convexity theory for oriented matroids, first developed by Las Vergnas [17], provides the framework for a new computational approach to the Steinitz problem [13]. We describe an algorithm which, for a given combinatorial (d − 2)-sphereS withn vertices, determines the setC _d,n(S) of rankd oriented matroids withn points and face latticeS. SinceS is polytopal if and only if there is a realizableM εC _d,n(S), this method together with the coordinatizability test for oriented matroids in [10] yields a decision procedure for the polytopality of a large class of spheres. As main new result we prove that there exist 431 combinatorial types of neighborly 5-polytopes with 10 vertices by establishing coordinates for 98 “doubted polytopes” in the classification of Altshuler [1]. We show that for alln ≧k + 5 ≧8 there exist simplicialk-spheres withn vertices which are non-polytopal due to the simple fact that they fail to be matroid spheres. On the other hand, we show that the 3-sphereM ₉₆₃ ⁹ with 9 vertices in [2] is the smallest non-polytopal matroid sphere, and non-polytopal matroidk-spheres withn vertices exist for alln ≧k + 6 ≧ 9.     

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

Polygons inscribed in a closed curve and a three-dimensional convex body

Here are samples of results obtained in the paper. Let γ be a centrally symmetric closed curve in ℝ ⁿ that does not contain its center of symmetry, O. Then γ is circumscribed about a square (with center O), as well as about a rhombus (also with center O) whose vertices split γ into parts of equal length. If n is odd, then there is a centrally symmetric equilateral 2n-link polyline inscribed in γ and lying in a hyperplane. Let K ⊂ ℝ³ be a convex body, and let x ∈ (0; 1). Then K is circumscribed about an affine-regular pentagonal prism P such that the ratio of the lateral edge l of P to the longest chord of K parallel to l is equal to x. Bibliography: 7 titles.     

Craig-Sakamoto's theorem for the Wishart distributions on symmetric cones

A version of Craig-Sakamoto's theorem says essentially that ifX is aN(O,I _n ) Gaussian random variable in ⁿ, and ifA andB are (n, n) symmetric matrices, thenXAX andXBX (or traces ofAXX andBXX) are independent random variables if and only ifAB=0. As observed in 1951, by Ogasawara and Takahashi, this result can be extended to the case whereXX is replaced by a Wishart random variable. Many properties of the ordinary Wishart distributions have recently been extended to the Wishart distributions on the symmetric cone generated by a Euclidean Jordan algebraE. Similarly, we generalize there the version of Craig's theorem given by Ogasawara and Takahashi. We prove that ifa andb are inE and ifW is Wishart distributed, then Tracea.W and Traceb.W are independent if and only ifa.b=0 anda.(b.x)=b.(a.x) for allx inE, where the. indicates Jordan product.Partially supported by NATO grant 92.13.47.     

Irrationality of linear combinations of eigenvectors

A givenn ×n matrix of rational numbers acts onC ^π and onQ ^π. We assume that its characteristic polynomial is irreducible and compare a basis of eigenvectors forC ^π with the standard basis forQ ^π. Subject to a hypothesis on the Galois group we prove that vectors from these two bases are as independent of each other as possible.     

Integral kašin splittings

Forx ∈ ℝ ⁿ andp≥1 put ‖x‖ _p :=(n ⁻¹Σ|x _i| ^p )^1/p . An orthogonal direct sum decomposition ℝ^2k =E⊕E ^⊥ where dimE=k and ‖x‖₂/‖x‖₁≤C is called here a (k, C)-splitting. By a theorem of Kašin there existsC>0 such that (k, C)-splittings exist for allk, and by the volume ratio method of Szarek one can takeC=32eπ. All proofs of existence of (k, C)-splittings heretofore given are nonconstructive. Here we investigate the representation of (k, C)-splittings by matrices with integral entries. For everyC>8e _1/2 π _−1/2 and positive integerk we specify a positive integerN(k, C) such that in the set ofk by 2k matrices with integral entries of absolute value not exceedingN(k, C) there exists a matrix with row span a summand in a (k, C)-splitting. We haveN(k, C)≤2^18k fork large enough depending onC. We explain in detail how to test a matrix for the property of representing a (k, C)-splitting. Taken together our results yield an explicit (if impractical) construction of (k, C)-splittings.     

Discrete fourier transform computation using prime Ramanujan numbers

Ramanujan numbers were introduced in [2] to implement discrete fourier transform (DFT) without using any multiplication operation. Ramanujan numbers are related to π and integers which are powers of 2. If the transform sizeN, is a Ramanujan number, then the computational complexity of the algorithms used for computing isO(N ²) addition and shift operations, and no multiplications. In these algorithms, the transform can be computed sequentially with a single adder inO(N ²) addition times. Parallel implementation of the algorithm can be executed inO(N) addition times, withO(N) number of adders. Some of these Ramanujan numbers of order-2 are related to the Biblical and Babylonian values of π [1]. In this paper, we analytically obtain upper bounds on the degree of approximation in the computation of DFT if JV is a prime Ramanujan number.