Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.     

Extremal hypergraph problems and convex hulls

Theprofile of a hypergraph onn vertices is (f ₀, f₁, ...,f _n) wheref _i denotes the number ofi-element edges. The extreme points of the set of profiles is determined for certain hypergraph classes. The results contain many old theorems of extremal set theory as particular cases (Sperner. Erdős—Ko—Rado, Daykin—Frankl—Green—Hilton).     

Intersecting sperner families and their convex hulls

Let ℱ be a family of subsets of a finite set ofn elements. The vector (f ₀, ...,f _n ) is called the profile of ℱ wheref _i denotes the number ofi-element subsets in ℱ. Take the set of profiles of all families ℱ satisfyingF ₁⊄F ₂ andF ₁∩F ₂≠0 for allF ₁,F ₂teℱ. It is proved that the extreme points of this set inR ⁿ⁺¹ have at most two non-zero components. Dedicated to Paul Erdős on his seventieth birthday     

The cross-section body, plane sections of convex bodies and approximation of convex bodies, I

For a convex body K ^d we investigate three associated bodies, its intersection body IK (for 0int K), cross-section body CK, and projection body IIK, which satisfy IKCKIIK. Conversely we prove CKconst₁(d)I(K–x) for some xint K, and IIKconst₂ (d)CK, for certain constants, the first constant being sharp. We estimate the maximal k-volume of sections of 1/2(K+(-K)) with k-planes parallel to a fixed k-plane by the analogous quantity for K; our inequality is, if only k is fixed, sharp. For L ^d a convex body, we take n random segments in L, and consider their Minkowski average D. We prove that, for V(L) fixed, the supremum of V(D) (with also nN arbitrary) is minimal for L an ellipsoid. This result implies the Petty projection inequality about max V((IIM)*), for M ^d a convex body, with V(M) fixed. We compare the volumes of projections of convex bodies and the volumes of the projections of their sections, and, dually, the volumes of sections of convex bodies and the volumes of sections of their circumscribed cylinders. For fixed n, the pth moments of V(D) (1p<) also are minimized, for V(L) fixed, by the ellipsoids. For k=2, the supremum (nN arbitrary) and the pth moment (n fixed) of V(D) are maximized for example by triangles, and, for L centrally symmetric, for example by parallelograms. Last we discuss some examples for cross-section bodies.Research (partially) supported by Hungarian National Foundation for Scientific Research, Grant No. 41.     

On a convex operator for finite sets

Let S be a finite set with m elements in a real linear space and let J_S be a set of m intervals in R. We introduce a convex operator co(S,J_S) which generalizes the familiar concepts of the convex hull, , and the affine hull, , of S. We prove that each homothet of that is contained in can be obtained using this operator. A variety of convex subsets of with interesting combinatorial properties can also be obtained. For example, this operator can assign a regular dodecagon to the 4-element set consisting of the vertices and the orthocenter of an equilateral triangle. For two types of families J_S we give two different upper bounds for the number of vertices of the polytopes produced as co(S,J_S). Our motivation comes from a recent improvement of the well-known Gauss-Lucas theorem. It turns out that a particular convex set co(S,J_S) plays a central role in this improvement.     

Degree and local connectivity in digraphs

It is shown that there is a digraphD of minimum outdegree 12m and μ(x, y; D)=11m, but every digraphD of minimum outdegreen contains verticesx ≠y withλ(x, y; D)≧n−1, whereμ(x, y; D) andλ(x, y; D) denote the maximum number of openly disjoint and edge-disjoint paths, respectively.     

On the volume of convex hulls of sets on spheres

We prove that for a measurable subset of S ^n–1 with fixed Haar measure, the volume of its convex hull is minimized for a cap (i.e. a ball with respect to the geodesic measure). We solve a similar problem for symmetric sets and n=2, 3. As a consequence, we deduce a result concerning Gaussian measures of dilatations of convex, symmetric sets in R ² and R ³.Partially supported by KBN (Poland), Grant No. 2 1094 91 01.     

Positions of convex bodies associated to extremal problems and isotropic measures

We show that there are close relations between extremal problems in dual Brunn-Minkowski theory and isotropic-type properties for some Borel measures on the sphere. The methods we use allow us to obtain similar results in the context of Firey-Brunn-Minkowski theory. We also study reverse inequalities for dual mixed volumes which are related with classical positions, such as ?-position or isotropic position.     

On the second differentiability of convex surfaces

Properties of pointwise second differentiability of real-valued convex functions in ⁿ are studied. Some proofs of the Busemann-Feller-Aleksandrov theorem are reviewed and a new proof of this theorem is presented.     

On triangulations of the convex hull ofn points

A setS ofn points in Euclideand-space determines a convex hull which can be triangulated into some numberm of simplices using the points ofS as vertices. We characterize those setsS for which all triangulations minimizem. This is used to characterize sets of points maximizing the volume of the smallest non-trivial simplex. This work was supported in part by NSF Grants MCS 81-02519 and MCS 82-03347. This work supported in part by NSF Grants MCS 81-02519 and MCS 82-03347 Dedicated to Paul Erdős on his seventieth birthday     

Harmonic symmetrization of convex sets and of Finsler structures,with applications to Hilbert geometry

David Hilbert discovered in 1895 an important metric that is canonically associated to an arbitrary convex domain Ω$\Omega$ in the Euclidean (or projective) space. This metric is known to be Finslerian, and the usual proof of this fact assumes a certain degree of smoothness of the boundary of Ω$\Omega$, and refers to a theorem by Busemann and Mayer that produces the norm of a tangent vector from the distance function. In this paper, we develop a new approach for the study of the Hilbert metric where no differentiability is assumed. The approach exhibits the Hilbert metric on a domain as a symmetrization of a natural weak metric, known as the Funk metric. The Funk metric is described as a tautological   weak Finsler metric, in which the unit ball in each tangent space is naturally identified with the domain Ω$\Omega$ itself. The Hilbert metric is then identified with the reversible tautological weak Finsler structure   on Ω$\Omega$, and the unit ball of the Hilbert metric at each point is described as the harmonic symmetrization of the unit ball of the Funk metric. Properties of the Hilbert metric then follow from general properties of harmonic symmetrizations of weak Finsler structures.     

The eccentric connectivity index of nanotubes and nanotori

Let G be a molecular graph. The eccentric connectivity index ξ^c(G) is defined as ξ^c(G)=∑_u∈V(G)deg_G(u)ε_G(u), where deg_G(u) denotes the degree of vertex u and ε_G(u) is the largest distance between u and any other vertex v of G. In this paper exact formulas for the eccentric connectivity index of TUC₄C₈(S) nanotube and TC₄C₈(S) nanotorus are given.     

Antipodal convex hypersurfaces

Motivated by a conjecture of Steinhaus, we consider the mapping F, associating to each point x of a convex hypersurface the set of all points at maximal intrinsic distance from x. We first provide two large classes of hypersurfaces with the mapping F single-valued and involutive. Afterwards we show that a convex body is smooth and has constant width if its double has the above properties of F, and we prove a partial converse to this result. Additional conditions are given, to characterize the (doubly covered) balls.     

The spherical conjecture in Minkowski geometry

We show that the shapes of convex bodies containing m translates of a convex body K, so that their Minkowskian surface area is minimum, tends for growing m to a convex body L.Received: 7 January 2002     

On typical degenerate convex surfaces

Various properties are given concerning geodesics on, and distance functions from points in, typical degenerate convex surfaces; i.e., surfaces obtained by gluing together two isometric copies of typical (in the sense of Baire category) convex bodies, by identifying the corresponding points of their boundaries.     

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.     

Section and projection means of convex bodies

This paper is concerned with various geometric averages of sections or projections of convex bodies. In particular, we consider Minkowski and Blaschke sums of sections as well as Minkowski sums of projections. The main result is a Crofton-type formula for Blaschke sums of sections. This is used to establish connections between the different averages mentioned above. As a consequence, we obtain results which show that, in some circumstances, a convex body is determined by the averages of its sections or projections.The research of the first author was supported in part by NSF grants DMS-9504249 and INT-9123373     

Splitting and pinching for convex sets

We consider noncompact, closed and convex sets with nonvoid interior in Euclidean space. It is shown that if such a set has one curvature measure sufficiently close to the boundary measure, then it is congruent to a product of a vector space and a compact convex body. Related stability and characterization theorems for orthogonal disc cylinders are proved. Our arguments are based on the Steiner-Schwarz symmetrization processes and generalized Minkowski integral formulas.     

Connected graphs containing a given connected graph as a unique greatest common subgraph

Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.