共查询到20条相似文献,搜索用时 557 毫秒
1.
The stable set polytope of a graph is the convex hull of the 0-1 vectors corresponding to stable sets of vertices. To any
nontrivial facet ∑
v∈V
a(v)x
v
≤b of this polytope we associate an integer δ, called the defect of the facet, by δ=∑
v∈V
a(v)-2b. We show that for any fixed δ there is a finite collection of graphs (called “basis”) such that any graph with a facet of
defect δ contains a subgraph which can be obtained from one of the graphs in the basis by a simple subdivision operation.
Received: September 28, 1998 / Accepted: February 24, 2000?Published online April 20, 2000 相似文献
2.
Lovász and Schrijver (SIAM J. Optim. 1:166–190, 1991) have constructed semidefinite relaxations for the stable set polytope
of a graph G = (V,E) by a sequence of lift-and-project operations; their procedure finds the stable set polytope in at most α(G) steps, where α(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre (SIAM J. Optim. 11:796–817,
2001; Lecture Notes in Computer Science, Springer, Berlin Heidelberg New York, pp 293–303, 2001) and by de Klerk and Pasechnik
(SIAM J. Optim. 12:875–892), which are based on relaxing nonnegativity of a polynomial by requiring the existence of a sum
of squares decomposition. The hierarchy of Lasserre is known to converge in α(G) steps as it refines the hierarchy of Lovász and Schrijver, and de Klerk and Pasechnik conjecture that their hierarchy also
finds the stability number after α(G) steps. We prove this conjecture for graphs with stability number at most 8 and we show that the hierarchy of Lasserre refines
the hierarchy of de Klerk and Pasechnik.
相似文献
3.
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. 相似文献
4.
MingChu Li 《Graphs and Combinatorics》2000,16(2):177-198
Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove
several properties on longest cycles in almost claw-free graphs. In particular, we show the following two results.? (1) Every
2-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 2δ+4} and the bound 2δ+ 4 is best possible, thereby fully generalizing a result of Matthews and Sumner.? (2) Every 3-connected
almost claw-free graph on n vertices contains a cycle of length at least min {n, 4δ}, thereby fully generalizing a result of MingChu Li.
Received: September 17, 1996 Revised: September 22, 1998 相似文献
5.
E. A. Monakhova 《Journal of Applied and Industrial Mathematics》2011,5(4):595-600
The paper addresses the optimization problem for circulant networks of maximizing the number of vertices given the degree
and diameter of a graph. For the graphs in the best available extremal family of circulant networks, we improve the estimate
for diameter, which together with previous results for multiplicative circulant networks enables us to improve the lower bounds
for the attainable number of vertices of circulant networks of all dimensions k ≥ 4. 相似文献
6.
In this paper, we establish oracle inequalities for penalized projection estimators of the intensity of an inhomogeneous
Poisson process. We study consequently the adaptive properties of penalized projection estimators. At first we provide lower
bounds for the minimax risk over various sets of smoothness for the intensity and then we prove that our estimators achieve
these lower bounds up to some constants. The crucial tools to obtain the oracle inequalities are new concentration inequalities
for suprema of integral functionals of Poisson processes which are analogous to Talagrand's inequalities for empirical processes.
Received: 24 April 2001 / Revised version: 9 October 2002 /
Published online: 15 April 2003
Mathematics Subject Classification (2000): 60E15, 62G05, 62G07
Key words or phrases: Inhomogeneous Poisson process – Concentration inequalities – Model selection – Penalized projection estimator – Adaptive
estimation 相似文献
7.
In this paper we study the adjacency structure of the order polytope of a poset. For a given poset, we determine whether two vertices in the corresponding order polytope are adjacent. This is done through filters in the original poset. We also prove that checking adjacency between two vertices can be done in quadratic time on the number of elements of the poset. As particular cases of order polytopes, we recover the adjacency structure of the set of fuzzy measures and obtain it for the set of p-symmetric measures for a given indifference partition; moreover, we show that the set of p-symmetric measures can be seen as the order polytope of a quotient set of the poset leading to fuzzy measures. From this property, we obtain the diameter of the set of p-symmetric measures. Finally, considering the set of p-symmetric measures as the order polytope of a direct product of chains, we obtain some other properties of these measures, as bounds on the volume and the number of vertices on certain cases. 相似文献
8.
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. 相似文献
9.
Edwin R. van Dam 《Journal of Algebraic Combinatorics》1998,7(3):321-332
We give a bound on the sizes of two sets of vertices at a given minimum distance in a graph in terms of polynomials and the Laplace spectrum of the graph. We obtain explicit bounds on the number of vertices at maximal distance and distance two from a given vertex, and on the size of two equally large sets at maximal distance. For graphs with four eigenvalues we find bounds on the number of vertices that are not adjacent to a given vertex and that have µ common neighbours with that vertex. Furthermore we find that the regular graphs for which the bounds are tight come from association schemes. 相似文献
10.
Benjamin A. Burton 《Journal of Combinatorial Theory, Series A》2011,118(4):1410-1435
The enumeration of normal surfaces is a key bottleneck in computational three-dimensional topology. The underlying procedure is the enumeration of admissible vertices of a high-dimensional polytope, where admissibility is a powerful but non-linear and non-convex constraint. The main results of this paper are significant improvements upon the best known asymptotic bounds on the number of admissible vertices, using polytopes in both the standard normal surface coordinate system and the streamlined quadrilateral coordinate system.To achieve these results we examine the layout of admissible points within these polytopes. We show that these points correspond to well-behaved substructures of the face lattice, and we study properties of the corresponding “admissible faces”. Key lemmata include upper bounds on the number of maximal admissible faces of each dimension, and a bijection between the maximal admissible faces in the two coordinate systems mentioned above. 相似文献
11.
Vincent Pilaud 《European Journal of Combinatorics》2012,33(4):632-662
The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud & Pocchiola in their study of flip graphs on pseudoline arrangements with contacts supported by a given sorting network.In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes.Our brick polytopes include Hohlweg & Lange’s many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron. 相似文献
12.
Counting basic objects as the vertices of polyhedra is a demanding problem in general, even for the most basic structured
polytope. In this paper, we determine the number of q-faces for some q ≥ 1 of the polytope of tridiagonal doubly stochastic matrices. 相似文献
13.
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. 相似文献
14.
The slow drift (with speed ɛ) of a parameter through a pitchfork bifurcation point, known as the dynamic pitchfork bifurcation,
is characterized by a significant delay of the transition from the unstable to the stable state. We describe the effect of
an additive noise, of intensity σ, by giving precise estimates on the behaviour of the individual paths. We show that until
time after the bifurcation, the paths are concentrated in a region of size around the bifurcating equilibrium. With high probability, they leave a neighbourhood of this equilibrium during a time interval
, after which they are likely to stay close to the corresponding deterministic solution. We derive exponentially small upper
bounds for the probability of the sets of exceptional paths, with explicit values for the exponents.
Received: 7 August 2000 / Revised version: 19 April 2001 / Published online: 20 December 2001 相似文献
15.
For a polytope in the [0,1]
n
cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n
2logn) and bounded below by (1+ε)n for some ε>0. Chvátal cuts are equivalent to Gomory fractional cuts, which are themselves dominated by Gomory mixed integer
cuts. What do these upper and lower bounds become when the rank is defined relative to Gomory mixed integer cuts? An upper
bound of n follows from existing results in the literature. In this note, we show that the lower bound is also equal to n. This result still holds for mixed 0,1 polyhedra with n binary variables.
Received: March 15, 2001 / Accepted: July 18, 2001?Published online September 17, 2001 相似文献
16.
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. 相似文献
17.
A cubical polytope is a convex polytope of which very facet is a combinatorial cube. We ask for the numbers which occur as
vertex numbers ofd-dimensional cubical polytopes, and we show, as a first step, that every cubicald-polytope for evend≥4 has an even number of vertices. 相似文献
18.
A natural digraph analog of the graph theoretic concept of “an independent set” is that of “an acyclic set of vertices,” namely a set not spanning a directed cycle. By this token, an analog of the notion of coloring of a graph is that of decomposition of a digraph into acyclic sets. We extend some known results on independent sets and colorings in graphs to acyclic sets and acyclic colorings of digraphs. In particular, we prove bounds on the topological connectivity of the complex of acyclic sets, and using them we prove sufficient conditions for the existence of acyclic systems of representatives of a system of sets of vertices. These bounds generalize a result of Tardos and Szabó. We prove a fractional version of a strong‐acyclic‐coloring conjecture for digraphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 177–189, 2008 相似文献
19.
A minimum triangulation of a convex 3-polytope is a triangulation that contains the minimum number of tetrahedra over all
its possible triangulations. Since finding minimum triangulations of convex 3-polytopes was recently shown to be NP-hard,
it becomes significant to find algorithms that give good approximation. In this paper we give a new triangulation algorithm
with an improved approximation ratio 2 - Ω(1/\sqrt n ) , where n is the number of vertices of the polytope. We further show that this is the best possible for algorithms that only consider
the combinatorial structure of the polytopes.
Received August 5, 2000, and in revised form March 29, 2001, and May 3, 2001. Online publication October 12, 2001. 相似文献
20.
Themaximal minor polytope Π
m, n
is the Newton polytope of the product of all maximal minors of anm×n matrix of indeterminates. The family of polytopes {Π
m, n
} interpolates between the symmetric transportation polytope (form=n−1) and the permutohedron (form=2). Both transportation polytope and the permutohedron aresimple polytopes but in general Π
m, n
is not simple. The main result of this paper is an explicit construction of a class of simple vertices of Π
m, n
for generalm andn. We call themvertices of diagonal type. For every such vertexv we explicitly describe all the edges and facets of Π
m, n
which containv. Simple vertices of Π
m, n
have an interesting algebro-geometric application: they correspond tononsingular extreme toric degenerations of the determinantal variety ofm×n matrices not of full rank.
Andrei Zelevinsky was partially supported by the NSF under Grant DMS-9104867. 相似文献