共查询到20条相似文献,搜索用时 46 毫秒
1.
We consider the Newton polytope Σ(m,n) of the product of all minors of an m× n matrix of indeterminates. Using the fact that this polytope is the secondary polytope of the product Δ
m-1
×Δ
n-1
of simplices, and thus has faces corresponding to coherent polyhedral subdivisions of Δ
m-1
×Δ
n-1
, we study facets of Σ(m,n) , which correspond to the coarsest, nontrivial such subdivisions. We make use of the relation between secondary and fiber
polytopes, which in this case gives a representation of Σ(m,n) as the Minkowski average of all m × n transportation polytopes.
<lsiheader>
<onlinepub>7 August, 1998
<editor>Editors-in-Chief: &lsilt;a href=../edboard.html#chiefs&lsigt;Jacob E. Goodman, Richard Pollack&lsilt;/a&lsigt;
<pdfname>20n2p231.pdf
<pdfexist>yes
<htmlexist>no
<htmlfexist>no
<texexist>no
<sectionname>
</lsiheader>
Received August 7, 1996, and in revised form April 4, 1997. 相似文献
2.
Lieven Le Bruyn 《Israel Journal of Mathematics》1985,52(4):355-360
In this note we give a rational expression for the Poincaré series of Πm,2, the trace ring ofm generic 2×2 matrices. This result extends the computations of E. Formanek form⩽4. As a consequence, we prove that the Poincaré series satisfies the functional equation(IIm,2;1/t)=-t4m.P(IIm,2,t) (m>2) supporting the conjecture that Πm,2 is a Gorenstein ring.
Work supported by an NFWO/FNRS grant. 相似文献
3.
Jesús A. De Loera Edward D. Kim Shmuel Onn Francisco Santos 《Journal of Combinatorial Theory, Series A》2009,116(8):1306-1325
This paper discusses properties of the graphs of 2-way and 3-way transportation polytopes, in particular, their possible numbers of vertices and their diameters. Our main results include a quadratic bound on the diameter of axial 3-way transportation polytopes and a catalogue of non-degenerate transportation polytopes of small sizes. The catalogue disproves five conjectures about these polyhedra stated in the monograph by Yemelichev et al. (1984). It also allowed us to discover some new results. For example, we prove that the number of vertices of an m×n transportation polytope is a multiple of the greatest common divisor of m and n. 相似文献
4.
Fu Liu 《Journal of Combinatorial Theory, Series A》2013,120(7):1539-1561
We describe a perturbation method that can be used to reduce the problem of finding the multivariate generating function (MGF) of a non-simple polytope to computing the MGF of simple polytopes. We then construct a perturbation that works for any transportation polytope. We apply this perturbation to the family of central transportation polytopes of order , and obtain formulas for the MGFs of the feasible cone of each vertex of the polytope and the MGF of the polytope. The formulas we obtain are enumerated by combinatorial objects. A special case of the formulas recovers the results on Birkhoff polytopes given by the author and De Loera and Yoshida. We also recover the formula for the number of maximum vertices of transportation polytopes of order . 相似文献
5.
6.
Let λK
m,n be a bipartite multigraph with two partite sets having m and n vertices, respectively. A P
v-factorization of λK
m,n is a set of edge-disjoint P
v
-factors of λK
m,n which partition the set of edges of λK
m,n. When v is an even number, Ushio, Wang and the second author of the paper gave a necessary and sufficient condition for the existence
of a P
v
-factorization of λK
m,n. When v is an odd number, we proposed a conjecture. However, up to now we only know that the conjecture is true for v = 3. In this paper we will show that the conjecture is true when v = 4k − 1. That is, we shall prove that a necessary and sufficient condition for the existence of a P
4k−1-factorization of λK
m,n is (1) (2k − 1)m ⩽ 2kn, (2) (2k − 1)n ⩽ 2km, (3) m + n ≡ 0 (mod 4k − 1), (4) λ(4k − 1)mn/[2(2k − 1)(m + n)] is an integer. 相似文献
7.
Branko Grünbaum Tomáš Kaiser Daniel Král’ Moshe Rosenfeld 《Israel Journal of Mathematics》2010,179(1):235-252
A polytope P with 2n vertices is called equipartite if for any partition of its vertex set into two equal-size sets V
1 and V
2, there is an isometry of the polytope P that maps V
1 onto V
2. We prove that an equipartite polytope in ℝ
d
can have at most 2d+2 vertices. We show that this bound is sharp and identify all known equipartite polytopes in ℝ
d
. We conjecture that the list is complete. 相似文献
8.
We investigate polyhedral 2k-manifolds as subcomplexes of the boundary complex of a regular polytope. We call such a subcomplex k
-Hamiltonian if it contains the full k-skeleton of the polytope. Since the case of the cube is well known and since the case of a simplex was also previously studied
(these are so-called super-neighborly triangulations), we focus on the case of the cross polytope and the sporadic regular 4-polytopes. By our results the existence of 1-Hamiltonian
surfaces is now decided for all regular polytopes. Furthermore we investigate 2-Hamiltonian 4-manifolds in the d-dimensional cross polytope. These are the “regular cases” satisfying equality in Sparla’s inequality. In particular, we present
a new example with 16 vertices which is highly symmetric with an automorphism group of order 128. Topologically it is homeomorphic
to a connected sum of seven copies of S
2×S
2. By this example all regular cases of n vertices with n<20 or, equivalently, all cases of regular d-polytopes with d≤9 are now decided. 相似文献
9.
Polytopes which are orthogonal projections of regular simplexes 总被引:2,自引:0,他引:2
Toshio Kawashima 《Geometriae Dedicata》1991,38(1):73-85
We consider the polytopes which are certain orthogonal projections of k-dimensional regular simplexes in k-dimensional Euclidean space R
k
. We call such polytopes -polytopes. Every sufficiently symmetric polytope, such as a regular polytope, a quasi-regular polyhedron, etc., belongs to this class. We denote by P
m,n
all n-dimensional -polytopes with m vertices. We show that there is a one-to-one correspondence between the elements of P
m,n
and those of P
m,m–n–1 and that this correspondence preserves the symmetry of -polytopes. Using this duality, we determine some of the P
m,n
's. We also show that a -polytope is an orthogonal projection of a cross polytope if and only if it has central symmetry. 相似文献
10.
George Purdy 《Israel Journal of Mathematics》1978,30(1-2):54-56
If ann-dimensional polytope has facets of areaA
1,A
2, …,A
m, then 2A
i <A
1+…+A
m fori=1,…,m. We show here that conversely these inequalities also ensure the existence of a polytope having these areas. 相似文献
11.
Let K
m,n
be a complete bipartite graph with two partite sets having m and n vertices, respectively. A P
v
-factorization of K
m,n
is a set of edge-disjoint P
v
-factors of K
m,n
which partition the set of edges of K
m,n
. When v is an even number, Wang and Ushio gave a necessary and sufficient condition for existence of P
v
-factorization of K
m,n
. When k is an odd number, Ushio in 1993 proposed a conjecture. Very recently, we have proved that Ushio’s conjecture is true when
v = 4k − 1. In this paper we shall show that Ushio Conjecture is true when v = 4k − 1, and then Ushio’s conjecture is true. That is, we will prove that a necessary and sufficient condition for the existence
of a P
4k+1-factorization of K
m,n
is (i) 2km≤(2k+1)n, (ii) 2kn≤(2k+1)m, (iii) m+n≡0 (mod 4k+1), (iv) (4k+1)mn/[4k(m+n)] is an integer. 相似文献
12.
We study the vertices and facets of the polytopes of partitions of numbers. The partition polytope Pn is the convex hull of the set of incidence vectors of all partitions n=x1+2x2++nxn. We show that the sequence P1,P2,…,Pn,… can be treated as an embedded chain. The dynamics of behavior of the vertices of Pn, as n increases, is established. Some sufficient and some necessary conditions for a point of Pn to be its vertex are proved. Representation of the partition polytope as a polytope on a partial algebra—which is a generalization of the group polyhedron in the group theoretic approach to the integer linear programming—allows us to prove subadditive characterization of the nontrivial facets of Pn. These facets correspond to extreme rays of the cone of subadditive functions with additional requirements p0=pn and pi+pn−i=pn,1≤i<n. The trivial facets are explicitly indicated. We also show how all vertices and facets of the polytopes of constrained partitions—in which some numbers are forbidden to participate—can be obtained from those of the polytope Pn. All vertices and facets of Pn for n≤8 and n≤6, respectively, are presented. 相似文献
13.
The toric ideals of 3×3 transportation polytopes
Trc\mathsf{T}_{\mathbf{rc}}
are quadratically generated. The only exception is the Birkhoff polytope B
3.
If
Trc\mathsf{T}_{\mathbf{rc}}
is not a multiple of B
3, these ideals even have square-free quadratic initial ideals. This class contains all smooth 3×3 transportation polytopes. 相似文献
14.
A Polytope Related to Empirical Distributions, Plane Trees, Parking Functions, and the Associahedron 总被引:6,自引:0,他引:6
Abstract. The volume of the n -dimensional polytope
Π
n
(x):= {y ∈
R
n
: y
i
≥ 0 and y
1
+ · · · + y
i
≤ x
1
+ · · ·+ x
i
for all 1 ≤ i ≤ n }
for arbitrary x:=(x
1
, . . ., x
n
) with x
i
>0 for all i defines a polynomial in variables x
i
which admits a number of interpretations, in terms of empirical distributions, plane partitions, and parking functions.
We interpret the terms of this polynomial as the volumes of chambers in two different polytopal subdivisions of Π
n
(x) . The first of these subdivisions generalizes to a class of polytopes called sections of order cones. In the second subdivision
the chambers are indexed in a natural way by rooted binary trees with n+1 vertices, and the configuration of these chambers provides a representation of another polytope with many applications,
the associahedron . 相似文献
15.
The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output. 相似文献
16.
Given the integer polyhedronP
t
:= conv{x ∈ℤ
n
:Ax⩽b}, whereA ∈ℤ
m × n
andb ∈ℤ
m
, aChvátal-Gomory (CG)cut is a valid inequality forP
1 of the type λτAx⩽⌊λτb⌋ for some λ∈ℝ
+
m
such that λτA∈ℤ
n
. In this paper we study {0, 1/2}-CG cuts, arising for λ∈{0, 1/2}
m
. We show that the associated separation problem, {0, 1/2}-SEP, is equivalent to finding a minimum-weight member of a binary
clutter. This implies that {0, 1/2}-SEP is NP-complete in the general case, but polynomially solvable whenA is related to the edge-path incidence matrix of a tree. We show that {0, 1/2}-SEP can be solved in polynomial time for a
convenient relaxation of the systemAx<-b. This leads to an efficient separation algorithm for a subclass of {0, 1/2}-CG cuts, which often contains wide families of
strong inequalities forP
1. Applications to the clique partitioning, asymmetric traveling salesman, plant location, acyclic subgraph and linear ordering
polytopes are briefly discussed. 相似文献
17.
The spectrum of path factorization of bipartite multigraphs 总被引:1,自引:0,他引:1
Jian WANG~ Bei-liang DU~ 《中国科学A辑(英文版)》2007,50(7):1045-1054
LetλK_(m,n)be a bipartite multigraph with two partite sets having m and n vertices, respectively.A P_v-factorization ofλK_(m,n)is a set of edge-disjoint P_v-factors ofλK_(m,n)which partition the set of edges ofλK_(m,n).When v is an even number,Ushio,Wang and the second author of the paper gave a necessary and sufficient condition for the existence of a P_v-factorization ofλK_(m,n).When v is an odd number,we have proposed a conjecture.Very recently,we have proved that the conjecture is true when v=4k-1.In this paper we shall show that the conjecture is true when v = 4k 1,and then the conjecture is true.That is,we will prove that the necessary and sufficient conditions for the existence of a P_(4k 1)-factorization ofλK_(m,n)are(1)2km≤(2k 1)n,(2)2kn≤(2k 1)m,(3)m n≡0(mod 4k 1),(4)λ(4k 1)mn/[4k(m n)]is an integer. 相似文献
18.
Ido Shemer 《Israel Journal of Mathematics》1984,49(4):331-342
Acyclic d-polytope is ad-polytope that is combinatorially equivalent to a polytope whose vertices lie on the moment curve {(t, t
2, …,t
d):t∈R}. Every subpolytope of an even-dimensional cyclic polytope is again cyclic. We show that a polytope [or neighborly polytope]
withv vertices that is not cyclic has at mostd+1 [respectivelyd]d-dimensional cyclic subpolytopes withv−1 vertices, providedd is even andv≧d+5. 相似文献
19.
In (Gluskin, Litvak in Geom. Dedicate 90:45–48, [2002]) it was shown that a polytope with few vertices is far from being symmetric in the Banach–Mazur distance. More precisely,
it was shown that Banach–Mazur distance between such a polytope and any symmetric convex body is large. In this note we introduce
a new, averaging-type parameter to measure the asymmetry of polytopes. It turns out that, surprisingly, this new parameter
is still very large, in fact it satisfies the same lower bound as the Banach–Mazur distance. In a sense it shows the following
phenomenon: if a convex polytope with small number of vertices is as close to a symmetric body as it can be, then most of its vertices
are as bad as the worst one. We apply our results to provide a lower estimate on the vertex index of a symmetric convex body, which was recently introduced
in (Bezdek, Litvak in Adv. Math. 215:626–641, [2007]). Furthermore, we give the affirmative answer to a conjecture by Bezdek (Period. Math. Hung. 53:59–69, [2006]) on the quantitative illumination problem. 相似文献
20.
A. A. Ayzenberg V. M. Buchstaber 《Proceedings of the Steklov Institute of Mathematics》2011,275(1):15-46
We introduce spherical nerve complexes that are a far-reaching generalization of simplicial spheres, and consider the differential
ring of simplicial complexes. We show that spherical nerve complexes form a subring of this ring, and define a homomorphism
from the ring of polytopes to this subring that maps each polytope P to the nerve K
P
of the cover of the boundary ∂P by facets. We develop a theory of nerve complexes and apply it to the moment-angle spaces Z
P
of convex polytopes P. In the case of a polytope P with m facets, its moment-angle space Z
P
is defined by the canonical embedding in the cone ℝ≥
m
. It is well-known that the space Z
P
is homeomorphic to the polyhedral product (D
2, S
1)∂P* if the polytope P is simple. We show that the homotopy equivalence ZP @ (D2 ,S1 )KP \mathcal{Z}_P \simeq (D^2 ,S^1 )^{K_P } holds in the general case. On the basis of bigraded Betti numbers of simplicial complexes, we construct a new class of combinatorial
invariants of convex polytopes. These invariants take values in the ring of polynomials in two variables and are multiplicative
with respect to the direct product or join of polytopes. We describe the relation between these invariants and the well-known
f-polynomials of polytopes. We also present examples of convex polytopes whose flag numbers (in particular, f-polynomials) coincide, while the new invariants are different. 相似文献