Facets with fixed defect of the stable set polytope

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     

Semidefinite bounds for the stability number of a graph via sums of squares of polynomials

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.      

Asymmetry of Convex Polytopes and Vertex Index of Symmetric Convex Bodies

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.     

Longest Cycles in Almost Claw-Free Graphs

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     

On an extremal family of circulant networks

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.     

Adaptive estimation of the intensity of inhomogeneous Poisson processes via concentration inequalities

 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     

Adjacency on the order polytope with applications to the theory of fuzzy measures

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.     

How many cyclic subpolytopes can a non-cyclic polytope have?

Acyclic d-polytope is ad-polytope that is combinatorially equivalent to a polytope whose vertices lie on the moment curve {(t, t ², …,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.     

Bounds on Special Subsets in Graphs, Eigenvalues and Association Schemes

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.     

Maximal admissible faces and asymptotic bounds for the normal surface solution space

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.     

The brick polytope of a sorting network

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.     

The number of faces of the tridiagonal Birkhoff polytope

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.     

Equipartite polytopes

A polytope P with 2n vertices is called equipartite if for any partition of its vertex set into two equal-size sets V ₁ and V ₂, there is an isometry of the polytope P that maps V ₁ onto V ₂. 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.     

Pathwise description of dynamic pitchfork bifurcations with additive noise

 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     

On the rank of mixed 0,1 polyhedra

For a polytope in the [0,1] ⁿ cube, Eisenbrand and Schulz showed recently that the maximum Chvátal rank is bounded above by O(n ²logn) 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     

Hamiltonian Submanifolds of Regular Polytopes

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 ²×S ². 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.     

Gaps in the numbers of vertices of cubical polytopes,I

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.     

Acyclic systems of representatives and acyclic colorings of digraphs

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     

Approximation for Minimum Triangulations of Simplicial Convex 3-Polytopes

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.     

Simple vertices of maximal minor polytopes

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.