共查询到20条相似文献,搜索用时 31 毫秒
1.
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
963
9
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. 相似文献
2.
Ido Shemer 《Israel Journal of Mathematics》1982,43(4):291-311
A 2m-polytopeQ isneighborly if eachm vertices ofQ determine a face. It is shown that the combinatorial structure of a neighborly 2m-polytope determines the combinatorial structure of every subpolytope. We develop a construction of “sewing a vertex onto
a polytope”, which, when applied to a neighborly 2m-polytope, yields a neighborly 2m-polytope with one more, vertex. Using this construction, we show that the numberg(2m+β,2m) of combinatorial types of neighborly 2m-polytopes with 2m+β vertices grows superexponentially as β→∞ (m≧2 fixed) and asm→∞ (β≧4 fixed). 相似文献
3.
This paper gives answers to a few questions concerning tilings of Euclidean spaces where the tiles are topological simplices with curvilinear edges. We investigate lattice triangulations of Euclidean 3-space in the sense that the vertices form a lattice of rank 3 and such that the triangulation is invariant under all translations of that lattice. This is the dual concept of a primitive lattice tiling where the tiles are not assumed to be Euclidean polyhedra but only topological polyhedra. In 3-space there is a unique standard lattice triangulation by Euclidean tetrahedra (and with straight edges) but there are infinitely many non-standard lattice triangulations where the tetrahedra necessarily have certain curvilinear edges. From the view-point of Discrete Differential Geometry this tells us that there are such triangulations of 3-space which do not carry any flat discrete metric which is equivariant under the lattice. Furthermore, we investigate lattice triangulations of the 3-dimensional torus as quotients by a sublattice. The standard triangulation admits such quotients with any number n ≥ 15 of vertices. The unique one with 15 vertices is neighborly, i.e., any two vertices are joined by an edge. It turns out that for any odd n ≥ 17 there is an n-vertex neighborly triangulation of the 3-torus as a quotient of a certain non-standard lattice triangulation. Combinatorially, one can obtain these neighborly 3-tori as slight modifications of the boundary complexes of the cyclic 4-polytopes. As a kind of combinatorial surgery, this is an interesting construction by itself. 相似文献
4.
Jonathan Spreer 《Discrete and Computational Geometry》2014,51(2):394-426
In this article we give combinatorial criteria to decide whether a transitive cyclic combinatorial d-manifold can be generalized to an infinite family of such complexes, together with an explicit construction in the case that such a family exists. In addition, we substantially extend the classification of combinatorial 3-manifolds with transitive cyclic symmetry up to 22 vertices. Finally, a combination of these results is used to describe new infinite families of transitive cyclic combinatorial manifolds and in particular a family of neighborly combinatorial lens spaces of infinitely many distinct topological types. 相似文献
5.
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. 相似文献
6.
LetP denote a polyhedral 2-manifold, i.e. a 2-dimensional cell-complex inR
d
(d≧3) having convex facets, such that set (P) is homeomorphic to a closed 2-dimensional manifold. LetE be any subset of odd valent vertices ofP, andc
E its cardinality. Then for the numberc
P(E) of facets containing a vertex ofE the inequality 2c
P(E)≧cE+1 is proved. This local combinatorial condition shows that several combinatorially possible types of polyhedral 2-manifolds
cannot exist. 相似文献
7.
A complete classification is given for neighborly combinatorial 3-manifolds with 9 vertices. It is found that there are 51 types, only one of which is not a sphere. 相似文献
8.
We show that there is a function α(r) such that for each constantr≧3, almost everyr-regular graph onn vertices has a hole (vertex induced cycle) of size at least α(r)n asn→∞. We also show that there is a function β(c) such that forc>0 large enough,G
n, p
,p=c/n almost surely has a hole of size at least β(c)n asn→∞. 相似文献
9.
Let τ be some triangulation of a planar polygonal domain Ω. Given a smooth functionu, we construct piecewise polynomial functionsv∈C
ρ(Ω) of degreen=3 ρ for ρ odd, andn=3ρ+1 for ρ even on a subtriangulation τ3 of τ. The latter is obtained by subdividing eachT∈ρ into three triangles, andv/T is a composite triangular finite element, generalizing the classicalC
1 cubic Hsieh-Clough-Tocher (HCT) triangular scheme. The functionv interpolates the derivatives ofu up to order ρ at the vertices of τ. Polynomial degrees obtained in this way are minimal in the family of interpolation schemes
based on finite elements of this type. 相似文献
10.
G. G. Lorentz 《Israel Journal of Mathematics》1978,29(2-3):132-140
The main theorem proved in this paper is as follows. There exist odd functionsf ɛC[−1,1] with the following property. LetP
n be the polynomial of best uniform approximation tof of degree≦n. Then for infinitely manyn,P
n has zero of orders(n)≧c logn atx=0.
This research has been supported by Grant MPS 75-09833 of the National Science Foundation. 相似文献
11.
Hao Li 《Graphs and Combinatorics》2000,16(3):319-335
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 ∑4
i=1
d(a
i)≥n+3+|⋂4
i=1
N(a
i)| for any four independent vertices a
1, a
2, a
3, a
4 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 相似文献
12.
Edward A. Bertram 《Israel Journal of Mathematics》1984,47(4):335-344
In 1955 R. Brauer and K. A. Fowler showed that ifG is a group of even order >2, and the order |Z(G)| of the center ofG is odd, then there exists a strongly real) elementx∈G−Z whose centralizer satisfies|C
G(x)|>|G|1/3. In Theorem 1 we show that every non-abeliansolvable groupG contains an elementx∈G−Z such that|C
G(x)|>[G:G′∩Z]1/2 (and thus|C
G(x)|>|G|1/3). We also note that if non-abelianG is either metabelian, nilpotent or (more generally) supersolvable, or anA-group, or any Frobenius group, then|C
G(x)|>|G|1/2 for somex∈G−Z. In Theorem 2 we prove that every non-abelian groupG of orderp
mqn (p, q primes) contains a proper centralizer of order >|G|1/2. Finally, in Theorem 3 we show that theaverage
|C(x)|, x∈G, is ≧c|G|
1/3 for metabelian groups, wherec is constant and the exponent 1/3 is best possible. 相似文献
13.
14.
David Barnette 《Israel Journal of Mathematics》1981,39(1-2):127-140
Ad-polytopeP is said to be neighborly provided each [d/2] vertices determine a face ofP. We construct a family ofd-polytopes that are dual to neighborly polytopes by means of facet splitting. We use this family to find a lower bound on
the number of combinatorial types of neighborly polytopes. We also show that all members of this family satisfy the famous
Hirsch conjecture.
Research supported by NSF Grant # MCS-07466. 相似文献
15.
H. Guggenheimer 《Israel Journal of Mathematics》1965,3(2):104-112
A complete proof is given for Schnirelmann’s theorem on the existence of a square inC
2 Jordan curves. The following theorems are then proved, using the same method: 1. On every hypersurface inR
n,C
3-diffeomorphic toS
n−1, there exist 2n points which are the vertices of a regular 2
n
-cellC
n. 2. Every planeC′ Jordan curve can beC′ approximated by a curve on which there are 2N distinct points which are the vertices of a centrally symmetric 2N-gon (anglesπ not excluded). 3. On every planeC
2 curve there exist 5 distinct points which are the vertices of an axially symmetric pentagon with given base anglesa, π/2≦a<π. (The angle at the vertex on the axis of symmetry might beπ).
Research supported by Grant AF-AFOSR-664-64, Air Force Office of Scientific Research. 相似文献
16.
Josef Cibulka 《Discrete and Computational Geometry》2010,43(2):402-411
Untangling is a process in which some vertices in a drawing of a planar graph are moved to obtain a straight-line plane drawing.
The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C
n
while keeping Ω(n
2/3) vertices fixed.
For any connected graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number
of vertices, maximum degree, and diameter of G. One consequence is that every 3-connected planar graph has a drawing δ such that at most O((nlog n)2/3) vertices are fixed in every untangling of δ. 相似文献
17.
Neighborly cubical polytopes exist: for any n≥ d≥ 2r+2 , there is a cubical convex d -polytope C
d
n
whose r -skeleton is combinatorially equivalent to that of the n -dimensional cube. This solves a problem of Babson, Billera, and Chan.
Kalai conjectured that the boundary of a neighborly cubical polytope C
d
n
maximizes the f -vector among all cubical (d-1) -spheres with 2
n
vertices. While we show that this is true for polytopal spheres if n≤ d+1 , we also give a counterexample for d=4 and n=6 .
Further, the existence of neighborly cubical polytopes shows that the graph of the n -dimensional cube, where n\ge5 , is ``dimensionally ambiguous' in the sense of Grünbaum. We also show that the graph of the 5 -cube is ``strongly 4 -ambiguous.'
In the special case d=4 , neighborly cubical polytopes have f
3
=(f
0
/4) log
2
(f
0
/4) vertices, so the facet—vertex ratio f
3
/f
0
is not bounded; this solves a problem of Kalai, Perles, and Stanley studied by Jockusch.
Received December 30, 1998. Online publication May 15, 2000. 相似文献
18.
We study dual pairs of combinatorial face-to-face cell decompositions of the real projective plane P
2
such that their canonically induced cell decompositions on the 2-sphere S
2 form dual pairs of combinatorical types of convex polyhedra, and such that these dual pairs share two natural properties
with those induced by dual pairs of Platonic solids: (1) Every Petrie polygon is a finite simple closed polygon of length
2(n-1) for some fixed n. (2) Every pair of Petrie polygons has precisely two common edges. Such pairs of face-to-face cell decompositions of the
projective plane are in one-to-one correspondence with n-element pseudoline arrangements. We study in particular those dual pairs of cell decompositions in which has only 3-valent vertices, i.e., via the above one-to-one correspondence: p
3-maximal pseudoline arrangements. A p
3
-maximal pseudoline arrangement with n elements in turn determines a neighborly 2-manifold with Euler characteristic χ = n(7-n)/6, and vice versa, this neighborly 2-manifold uniquely determines its generating p
3
-maximal pseudoline arrangement. We provide new inductive constructions for finding infinite example classes of p
3-maximal pseudoline arrangements from small existing ones, we describe an algorithm for generating them, we provide a complete
list of existence up to n = 40, and we discuss their properties.
Received July 18, 1996, and in revised form October 28, 1996. 相似文献
19.
Béla Bollobás 《Combinatorica》1982,2(3):223-228
We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc.
Dedicated to Tibor Gallai on his seventieth birthday 相似文献
20.
Summary Let Fn, n≧ 1, denote the sequence of generic filiform (connected, simply connected) Lie groups. Here we study, for each Fn, the infinite dimensional simple quotients of the group C*-algebra of (the most obvious) one of its discrete cocompact subgroups Dn. For Dn, the most attractive concrete faithful representations are given in terms of Anzai flows, in analogy with the representations
of the discrete Heisenberg group H3 ⊆G3 on L2(T) that result from the irrational rotation flows on T; the representations of Dn generate infinite-dimensional simple quotients An,θ of the group C*-algebra C*(Dn). For n>1, there are other infinite-dimensional simple quotients of C*(Dn) arising from non-faithful representations of Dn. Flows for these are determined, and they are also characterized and represented as matrix algebras over simple affine Furstenberg
transformation group C*-algebras of the lower dimensional tori. 相似文献