On a geometric property of perfect graphs

LetG be a graph,VP(G) its vertex packing polytope and letA(G) be obtained by reflectingVP(G) in all Cartersian coordinates. Denoting byA*(G) the set obtained similarly from the fractional vertex packing polytope, we prove that the segment connecting any two non-antipodal vertices ofA(G) is contained in the surface ofA(G) and thatG is perfect if and only ifA*(G) has a similar property.     

Cones of alternating and cut submodular set functions

We describe facets of the cones of alternating set functions and cut submodular set functions generated by directed and undirected graphs and by uniform even hypergraphs. This answers a question asked by L. Lovász at the Bonn Mathematical Programming Conference in 1982. We show that there is a network flow algorithm for minimizing a hypergraph cut set function.     

Puzzles and polytope isomorphisms

We show that an isomorphism between the graphs of two simple polytopes of arbitrary dimension can always be extended to an isomorphism between the polytopes themselves. It has been convenient to study the dual situation, involving what we like to call the puzzle of a simplicial polytope.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday.     

The perfectly Matchable Subgraph Polytope of an arbitrary graph

The Perfectly Matchable Subgraph Polytope of a graphG=(V, E), denoted byPMS(G), is the convex hull of the incidence vectors of thoseXV which induce a subgraph having a perfect matching. We describe a linear system whose solution set isPMS(G), for a general (nonbipartite) graphG. We show how it can be derived via a projection technique from Edmonds' characterization of the matching polytope ofG. We also show that this system can be deduced from the earlier bipartite case [2], by using the Edmonds-Gallai structure theorem. Finally, we characterize which inequalities are facet inducing forPMS(G), and hence essential.     

On cone of nonsymmetric positive semidefinite matrices

In this paper, we analyze and characterize the cone of nonsymmetric positive semidefinite matrices (NS-psd). Firstly, we study basic properties of the geometry of the NS-psd cone and show that it is a hyperbolic but not homogeneous cone. Secondly, we prove that the NS-psd cone is a maximal convex subcone of P₀-matrix cone which is not convex. But the interior of the NS-psd cone is not a maximal convex subcone of P-matrix cone. As the byproducts, some new sufficient and necessary conditions for a nonsymmetric matrix to be positive semidefinite are given. Finally, we present some properties of metric projection onto the NS-psd cone.     

Sets determined by finitely many X-rays

A measurable set in _n which is uniquely determined among all measurable sets (modulo null sets) by its X-rays in a finite set L of directions, or more generally by its X-rays parallel to a finite set L of subspaces, is called L-unique, or simply unique. Some subclasses of the L-unique sets are known. The L-additive sets are those measurable sets E which can be written E {x _n : _i f _i (x) * 0}. Here, denotes equality modulo null sets, * is either or >, and the terms in the sum are the values of ridge functions f _i orthogonal to subspaces S _i in L. If n=2, the L-inscribable convex sets are those whose interiors are the union of interiors of inscribed convex polygons, all of whose sides are parallel to the lines in L. Relations between these classes are investigated. It is shown that in _n each L-inscribable convex set is L-additive, but L-additive convex sets need not be L-inscribable. It is also shown that every ellipsoid in _n is unique for any set of three directions. Finally, some results are proved concerning the structure of convex sets in _n , unique with respect to certain families of coordinate subspaces.     

k-sets and random hulls

We re-examine the probabilistic analysis of Clarkson and Shor [5] involvingk-sets of point sets and related structures. By studying more carefully the equations that they derive, we are able to obtain refined analysis of these quantities, which lead to a collection of interesting relationships involvingk-sets, convex hulls of random samples, and generalizations of these constructs.Work on this paper has been supported by Office of Naval Research Grant N00014-89-J-3042 and N00014-90-J-1284, by National Science Foundation Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

Discrepancy and approximations for bounded VC-dimension

Let (X, ) be a set system on ann-point setX. For a two-coloring onX, itsdiscrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in . We show that if for anym-point subset the number of distinct subsets induced by onY is bounded byO(m ^d) for a fixed integerd, then there is a coloring with discrepancy bounded byO(n ^1/2–1/2d(logn)^1+1/2d ). Also if any subcollection ofm sets of partitions the points into at mostO(m ^d) classes, then there is a coloring with discrepancy at mostO(n ^1/2–1/2dlogn). These bounds imply improved upper bounds on the size of -approximations for (X, ). All the bounds are tight up to polylogarithmic factors in the worst case. Our results allow to generalize several results of Beck bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.Work of J.M. and E.W. was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract no. 3075 (project ALCOM). L.W. acknowledges support from the Deutsche Forschungsgemeinschaft under grant We 1265/1-3, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen.     

Geradenanordnungen Mit Maximaler Anzahl Vierseitiger Flächen

Ohne Zusammenfassung

---

     

Integer cells in convex sets

Every convex body K in Rⁿ has a coordinate projection PK that contains at least cells of the integer lattice PZⁿ, provided this volume is at least one. Our proof of this counterpart of Minkowski's theorem is based on an extension of the combinatorial density theorem of Sauer, Shelah and Vapnik-Chervonenkis to Zⁿ. This leads to a new approach to sections of convex bodies. In particular, fundamental results of the asymptotic convex geometry such as the Volume Ratio Theorem and Milman's duality of the diameters admit natural versions for coordinate sections.     

Kinematic formulas for finite lattices

In analogy to valuation characterizations and kinematic formulas of convex geometry, we develop a combinatorial theory of invariant valuations and kinematic formulas for finite lattices. Combinatorial kinematic formulas are shown to have application to some probabilistic questions, leading in turn to polynomial identities for Möbius functions and Whitney numbers.     

Cogenerators for convex spaces

We give cogenerators for the categories of convex (= finitely superconvex), finitely positively convex, and absolute convex (= finitely totally convex) spaces introduced by Pumplün and Röhrl.Dedicated to our academic teacher Dieter Pumplün on the occasion of his sixtieth birthday.     

A comparison between two distinct continuous models in projective cluster theory: The median and the tight-span construction

It is possible to consider two variants of cluster theory: Inaffine cluster theory, one considers collections ofsubsets of a given setX of objects or states, whereas inprojective cluster theory, one considers collections ofsplits (orbipartitions) of that set. In both contexts, it can be desirable to produce acontinuous model, that is, a spaceT encompassing the given setX which represents in a well-specified and more or less parsimonious way all possibleintermediate objects ortransition states compatible with certain restrictions derived from the given collection of subsets or splits. We investigate an interesting and intriguing relationship between two such constructions that appear in the context of projective cluster theory: TheBuneman construction and thetight-span (or justT)construction.     

The maximal monotonicity of the subdifferentials of convex functions: Simons' problem

In the paper we deal with the problem when the graph of the subdifferential operator of a convex lower semicontinuous function has a common point with the product of two convex nonempty weak and weak^* compact sets, i.e. when graph (Q × Q ^*) 0. The results obtained partially solve the problem posed by Simons as well as generalize the Rockafellar Maximal Monotonicity Theorem.     

Harmonic functions on nilpotent groups

For a probability measure on a locally compact groupG which is not supported on any proper closed subgroup, an elementF ofL (G) is called -harmonic if F(st)d(t)=F(s), for almost alls inG. Constant functions are -harmonic and it is known that for abelianG all -harmonic functions are constant. For other groups it is known that non constant -harmonic functions exist and the question of whether such functions exist on nilpotent groups is open, though a number of partial results are known. We show that for nilpotent groups of class 2 there are no non constant -harmonic functions. Our methods also enable us to give new proofs of results similar to the known partial results.     

On toric h-vectors of centrally symmetric polytopes

We prove tight lower bounds for the coefficients of the toric h-vector of an arbitrary centrally symmetric polytope generalizing previous results due to R. Stanley and the author using toric varieties. Our proof here is based on the theory of combinatorial intersection cohomology for normal fans of polytopes developed by G. Barthel, J.-P. Brasselet, K. Fieseler and L. Kaup, and independently by P. Bressler and V. Lunts. This theory is also valid for nonrational polytopes when there is no standard correspondence with toric varieties. In this way we can establish our bounds for centrally symmetric polytopes even without requiring them to be rational. Received: 24 March 2004