A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope

For a convex body B in a vector space V, we construct its approximation P_k, k =1 , 2, . . ., using an intersection of a cone of positive semidefinite quadratic forms with an affine subspace. We show that P_k is contained in B for each k. When B is the Symmetric Traveling Salesman Polytope on n cities T_n, we show that the scaling of P_k by n/k + O(1/n) contains T_n for . Membership for P_k is computable in time polynomial in n (of degree linear in k). We also discuss facets of T_n that lie on the boundary of P_k and we use eigenvalues to evaluate our bounds.     

The Sine Representation of Centrally Symmetric Convex Bodies

The problem of the sine representation for the support function of centrally symmetric convex bodies is studied. We describe a subclass of centrally symmetric convex bodies which is dense in the class of centrally symmetric convex bodies. Also, we obtain an inversion formula for the sine-transform.     

中心对称向量与Skew对称矩阵

引入中心对称向量和中心反对称向量的概念,证明数域P上任意n维向量都可以唯一地表示成一个中心对称向量和一个中心反对称向量的和;给出数域P上Skew对称矩阵的概念,并讨论其性质.     

Approximation of Convex Bodies by Centrally Symmetric Bodies

We present an analog of the well-known theorem of F. John about the ellipsoid of maximal volume contained in a convex body. Let C be a convex body and let D be a centrally symmetric convex body in the Euclidean d-space. We prove that if D is an affine image of D of maximal possible volume contained in C, then C a subset of the homothetic copy of D with the ratio 2d-1 and the homothety center in the center of D. The ratio 2d-1 cannot be lessened as a simple example shows.     

Packing and Covering with Centrally Symmetric Convex Disks

Given a convex disk K (a convex compact planar set with nonempty interior), let δ _L (K) and θ _L (K) denote the lattice packing density and the lattice covering density of K, respectively. We prove that for every centrally-symmetric convex disk K we have that $$ 1\le\delta_L(K)\theta_L(K)\le1.17225\ldots $$ The left inequality is tight and it improves a 10-year old result.     

Pairs of Convex Bodies with Centrally Symmetric Intersections of Translates

For a pair of convex bodies $K$ and $K$ in $E^d$, the $d$-dimensional intersections $K \cap (x + K),$ $x \in E^d,$ are centrally symmetric if and only if $K$ and $K$ are represented as direct sums $K = R \oplus P$ and $K = R \oplus P$ such that: (i) $R$ is a compact convex set of some dimension $m$, $0 \le m \le d,$ and $R = z - R$ for a suitable vector $z \in E^d$, (ii) $P$ and $P$ are isothetic parallelotopes, both of dimension $d-m$.     

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)

Cyclic Characters of Symmetric Groups

We consider characters of finite symmetric groups induced from linear characters of cyclic subgroups. A new approach to Stembridge's result on their decomposition into irreducible components is presented. In the special case of a subgroup generated by a cycle of longest possible length, this amounts to a short proof of the Krakiewicz-Weyman theorem.     

High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension

Let A be a d by n matrix, d < n. Let C be the regular cross polytope (octahedron) in Rⁿ. It has recently been shown that properties of the centrosymmetric polytope P = AC are of interest for finding sparse solutions to the underdetermined system of equations y = Ax [9]. In particular, it is valuable to know that P is centrally k-neighborly. We study the face numbers of randomly projected cross polytopes in the proportional-dimensional case where d ∼ δn, where the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rⁿ. We derive ρ_N(δ) > 0 with the property that, for any ρ < ρ_N(δ), with overwhelming probability for large d, the number of k-dimensional faces of P = AC is the same as for C, for 0 ≤ k ≤ ρd. This implies that P is centrally ⌊ ρ d ⌋-neighborly, and its skeleton Skel_{⌊ ρ d ⌋}(P) is combinatorially equivalent to Skel_{⌊ ρ d⌋}(C). We display graphs of ρ_N. Two weaker notions of neighborliness are also important for understanding sparse solutions of linear equations: weak neighborliness and sectional neighborliness [9]; we study both. Weak (k,ε)-neighborliness asks if the k-faces are all simplicial and if the number of k-dimensional faces f_k(P) ≥ f_k(C)(1 – ε). We characterize and compute the critical proportion ρ_W(δ) > 0 such that weak (k,ε) neighborliness holds at k significantly smaller than ρ_W · d and fails for k significantly larger than ρ_W · d. Sectional (k,ε)-neighborliness asks whether all, except for a small fraction ε, of the k-dimensional intrinsic sections of P are k-dimensional cross polytopes. (Intrinsic sections intersect P with k-dimensional subspaces spanned by vertices of P.) We characterize and compute a proportion ρ_S(δ) > 0 guaranteeing this property for k/d ∼ ρ < ρ_S(δ). We display graphs of ρ_S and ρ_W.     

Quantum Mechanical Equivalence of the Metrics of a Centrally Symmetric Gravitational Field

Theoretical and Mathematical Physics - We analyze the quantum mechanical equivalence of the metrics of a centrally symmetric uncharged gravitational field. We consider the static Schwarzschild...     

Cyclic Tableaux and Symmetric Functions

We introduce the notion of cyclic tableaux and develop involutions for Waring's formulas expressing the power sum symmetric function p_n in terms of the elementary symmetric function e_n and the homogeneous symmetric function h_n. The coefficients appearing in Waring's formulas are shown to be a cyclic analog of the multinomial coefficients, a fact that seems to have been neglected before. Our involutions also spell out the duality between these two forms of Waring's formulas, which turns out to be exactly the “duality between sets and multisets.” We also present an involution for permutations in cycle notation, leading to probably the simplest combinatorial interpretation of the Möbius function of the partition lattice and a purely combinatorial treatment of the fundamental theorem on symmetric functions. This paper is motivated by Chebyshev polynomials in connection with Waring's formula in two variables.     

Explicit Constructions of Centrally Symmetric k-Neighborly Polytopes and Large Strictly Antipodal Sets

We present explicit constructions of centrally symmetric $2$ -neighborly $d$ -dimensional polytopes with about $3^{d/2}\approx (1.73)^d$ vertices and of centrally symmetric $k$ -neighborly $d$ -polytopes with about $2^{{3d}/{20k^2 2^k}}$ vertices. Using this result, we construct for a fixed $k\ge 2$ and arbitrarily large $d$ and $N$ , a centrally symmetric $d$ -polytope with $N$ vertices that has at least $\left( 1-k^2\cdot (\gamma _k)^d\right) \genfrac(){0.0pt}{}{N}{k}$ faces of dimension $k-1$ , where $\gamma _2=1/\sqrt{3}\approx 0.58$ and $\gamma _k = 2^{-3/{20k^2 2^k}}$ for $k\ge 3$ . Another application is a construction of a set of $3^{\lfloor d/2 -1\rfloor }-1$ points in $\mathbb R ^d$ every two of which are strictly antipodal as well as a construction of an $n$ -point set (for an arbitrarily large $n$ ) in $\mathbb R ^d$ with many pairs of strictly antipodal points. The two latter results significantly improve the previous bounds by Talata, and Makai and Martini, respectively.     

匹配多面体的一个性质

证明了若M（G）为图G的匹配多面体,M1,M2为M（G）的两个距离为d的顶点,则M1,M2间有d条内部不相交的最短路．     

A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone

In this short communication, we observe that the Graphical Traveling Salesman Polyhedron is the intersection of the positive orthant with the Minkowski sum of the Symmetric Traveling Salesman Polytope and the polar of the metric cone. This follows almost trivially from known facts. There are nonetheless two reasons why we find this observation worth communicating: It is very surprising; it helps us understand the relationship between these two important families of polyhedra.     

The Number of Triangulations of the Cyclic Polytope C (n , n -4)

We show that the exact number of triangulations of the standard cyclic polytope C(n,n-4) is (n+4)2 ^(n-4)/2 -n if n is even and \left((3n+11)/2\right)2 ^(n-5)/2 -n if n is odd. These formulas were previously conjectured by the second author. Our techniques are based on Gale duality and the concept of virtual chamber. They further provide formulas for the number of triangulations which use a specific simplex. We also compute the maximum number of regular triangulations among all the realizations of the oriented matroid of C(n,n-4) . Received October 24, 2000, and in revised form July 8, 2001. Online publication November 7, 2001.     

A Polytope Approach to the Optimal Assembly Problem

The problem of assembling components into series modules to maximize the system reliability has been intensively studied in the literature. Invariably, the methods employed exploit special properties of the reliability function through standard analytical optimization techniques. We propose a geometric approach by exploiting the assembly polytope – a polytope generated by the potential assembly configurations. The new approach yields simpler proofs of known results, as well as new results about systems where the number of components in a module is not fixed, but subject to lower and upper bounds.     

Adjacent Extreme Points Of A Transportation Polytope

The adjacent extreme points of a Transportation Polytope are characterized by the circuit s contained in the support of its vertices. This result generalizes the Balinski and Russakoff [4] result on the Assignment Polytope     

The Minimal Number of Cyclic Generators of the Symmetric and Alternating Groups

The aim of this note is to find the minimal number of generators of the symmetric group S _n and alternating group A _n , when the generators are cycles of length at most k. The approach is constructive.     

循环多胞形$C^{3}(6)$的对偶和单形乘积上的小覆盖

计算了循环多胞形$C^{3}(6)$的对偶和单形乘积上(可定向)小覆盖的等变同胚类的个数