Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the number of vertices of the stochastic tensor polytope
98
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper is devoted to the study of lower and upper bounds for the number of vertices of the polytope of $ntimes ntimes n$ stochastic tensors (i.e., triply stochastic arrays of dimension $n$). By using known results on polytopes (i.e., the Upper and Lower Bound Theorems), we present some new lower and upper bounds. We show that the new upper bound is tighter than the one recently obtained by Chang, Paksoy and Zhang [Ann. Funct. Anal. 7 (2016), no.~3, 386--393] and also sharper than the one in Linial and Lurias [Discrete Comput. Geom. 51 (2014), no.~1, 161--170]. We demonstrate that the analog of the lower bound obtained in such a way, however, is no better than the existing ones.
rate research
Read More
Given an integer $1leq j <n$, define the $(j)$-coloring of a $n$-dimensional hypercube $H_{n}$ to be the $2$-coloring of the edges of $H_{n}$ in which all edges in dimension $i$, $1leq i leq j$, have color $1$ and all other edges have color $2$. Cheng et al. [Proper distance in edge-colored hypercubes, Applied Mathematics and Computation 313 (2017) 384-391.] determined the number of distinct shortest properly colored paths between a pair of vertices for the $(1)$-colored hypercubes. It is natural to consider the number for $(j)$-coloring, $jgeq 2$. In this note, we determine the number of different shortest proper paths in $(j)$-colored hypercubes for arbitrary $j$.
The secondary polytope of a point configuration A is a polytope whose face poset is isomorphic to the poset of all regular subdivisions of A. While the vertices of the secondary polytope - corresponding to the triangulations of A - are very well studied, there is not much known about the facets of the secondary polytope. The splits of a polytope, subdivisions with exactly two maximal faces, are the simplest examples of such facets and the first that were systematically investigated. The present paper can be seen as a continuation of these studies and as a starting point of an examination of the subdivisions corresponding to the facets of the secondary polytope in general. As a special case, the notion of k-split is introduced as a possibility to classify polytopes in accordance to the complexity of the facets of their secondary polytopes. An application to matroid subdivisions of hypersimplices and tropical geometry is given.
Hakimi and Schmeichel determined a sharp lower bound for the number of cycles of length 4 in a maximal planar graph with $n$ vertices, $ngeq 5$. It has been shown that the bound is sharp for $n = 5,12$ and $ngeq 14$ vertices. However, it was only conjectured by the authors about the minimum number of cycles of length 4 for maximal planar graphs with the remaining small vertex numbers. In this note we confirm their conjecture.
A basic combinatorial invariant of a convex polytope $P$ is its $f$-vector $f(P)=(f_0,f_1,dots,f_{dim P-1})$, where $f_i$ is the number of $i$-dimensional faces of $P$. Steinitz characterized all possible $f$-vectors of $3$-polytopes and Grunbaum characterized the pairs given by the first two entries of the $f$-vectors of $4$-polytopes. In this paper, we characterize the pairs given by the first two entries of the $f$-vectors of $5$-polytopes. The same result was also proved by Pineda-Villavicencio, Ugon and Yost independently.
Let m,n be positive integers. Define T(m,n) to be the transportation polytope consisting of the m x n non-negative real matrices whose rows each sum to 1 and whose columns each sum to m/n. The special case B(n)=T(n,n) is the much-studied Birkhoff-von Neumann polytope of doubly-stochastic matrices. Using a recent asymptotic enumeration of non-negative integer matrices (Canfield and McKay, 2007), we determine the asymptotic volume of T(m,n) as n goes to infinity, with m=m(n) such that m/n neither decreases nor increases too quickly. In particular, we give an asymptotic formula for the volume of B(n).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
