Coxeter matroid polytopes

If Δ is a polytope in real affine space, each edge of Δ determines a reflection in the perpendicular bisector of the edge. The exchange groupW (Δ) is the group generated by these reflections, and Δ is a (Coxeter) matroid polytope if this group is finite. This simple concept of matroid polytope turns out to be an equivalent way to define Coxeter matroids. The Gelfand-Serganova Theorem and the structure of the exchange group both give us information about the matroid polytope. We then specialize this information to the case of ordinary matroids; the matroid polytope by our definition in this case turns out to be a facet of the classical matroid polytope familiar to matroid theorists. This work was supported in part by NSA grant MDA904-95-1-1056.     

The lattice of flats and its underlying flag matroid polytope

LetM be a matroid andF the collection of all linear orderings of bases ofM, orflags ofM. We define the flag matroid polytope Δ(F). We determine when two vertices of Δ(F) are adjacent, and provide a bijection between maximal chains in the lattice of flats ofM and certain maximal faces of Δ(F). Supported in part by NSA grant MDA904-95-1-1056.     

A remark on sets having the Steinhaus property

A point set satisfies the Steinhaus property if no matter how it is placed on a plane, it covers exactly one integer lattice point. Whether or not such a set exists, is an open problem. Beck has proved [1] that any bounded set satisfying the Steinhaus property is not Lebesgue measurable. We show that any such set (bounded or not) must have empty interior. As a corollary, we deduce that closed sets do not have the Steinhaus property, fact noted by Sierpinski [3] under the additional assumption of boundedness.     

Euclideaness and final polynomials in oriented matroid theory

This paper deals with a geometric construction of algebraic non-realizability proofs for certain oriented matroids. As main result we obtain an algorithm which generates a (bi-quadratic) final polynomial [3], [5] for any non-euclidean oriented matroid. Here we apply the results of Edmonds, Fukuda and Mandel [6], [7] concerning non-degenerate cycling of linear programs in non-euclidean oriented matroids.     

Simultaneous estimation of parameters in exponential families

Summary The paper considers estimation of the natural parameter vector or the mean vector from independent distributions each belonging to the one-parameter discrete or absolutely continuous exponential family. The usual estimators (maximum likelihood, minimum variance unbiased or best invariant) are improved simultaneously under various weighted squared error losses. Research supported by the NSF Grant Number MCS-8202116.     

A matroid generalization of a result of Dirac

This paper generalizes a theorem of Dirac for graphs by proving that ifM is a 3-connected matroid, then, for all pairs {a,b} of distinct elements ofM and all cocircuitsC ^* ofM, there is a circuit that contains {a,b} and meetsC ^*. It is also shown that, although the converse of this result fails, the specified condition can be used to characterize 3-connected matroids.The author's research was partially supported by a grant from the National Security Agency.     

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.     

Isoperimetric inequalities in potential theory

Given a non-empty bounded domainG in ⁿ ,n2, letr ₀(G) denote the radius of the ballG ₀ having center 0 and the same volume asG. The exterior deficiencyd _e (G) is defined byd _e (G)=r _e (G)/r ₀(G)–1 wherer _e (G) denotes the circumradius ofG. Similarlyd _i (G)=1–r _i (G)/r ₀(G) wherer _i (G) is the inradius ofG. Various isoperimetric inequalities for the capacity and the first eigenvalue ofG are shown. The main results are of the form CapG(1+cf(d _e (G)))CapG ₀ and ₁(G)(1+cf(d _i (G)))₁(G ₀),f(t)=t ³ ifn=2,f(t)=t ³/(ln 1/t) ifn=3,f(t)=t ^(n+3)/2 ifn4 (for convex G and small deficiencies ifn3).     

Gated sets in metric spaces

The concept of a gated subset in a metric space is studied, and it is shown that properties of disjoint pairs of gated subsets can be used to investigate projections in Tits buildings.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday     

The natural Banach space for version independent risk measures

Risk measures, or coherent measures of risk, are often considered on the space L^∞$L^{\infty }$, and important theorems on risk measures build on that space. Other risk measures, among them the most important risk measure–the Average Value-at-Risk–are well defined on the larger space L¹$L^1$ and this seems to be the natural domain space for this risk measure. Spectral risk measures constitute a further class of risk measures of central importance, and they are often considered on some L^p$L^p$ space. But in many situations this is possibly unnatural, because any L^p$L^p$ with p>_p0$p>p_0$, say, is suitable to define the spectral risk measure as well. In addition to that, risk measures have also been considered on Orlicz and Zygmund spaces. So it remains for discussion and clarification, what the natural domain to consider a risk measure is?     

Measurable chromatic number of geometric graphs and sets without some distances in euclidean space

LetH be a set of positive real numbers. We define the geometric graphG _H as follows: the vertex set isR ⁿ (or the unit circleS ¹) andx, y are joined if their distance belongs toH. We define the measurable chromatic number of geometric graphs as the minimum number of classes in a measurable partition into independent sets. In this paper we investigate the difference between the notions of the ordinary and measurable chromatic numbers. We also prove upper and lower bounds on the Lebesgue upper density of independent sets.     

Atoms of families of sets

An atom of a familyF= (A _v :v∈I) of sets is a set of the form where 0⊂N⊆I. The note deals with upper and lower estimates of the possible number of non-empty atoms ofF in case theA _v are parallelopipeds ind-dimensional space. Some estimates are best possible. Dedicated to Tibor Gallai on his seventieth birthday     

Statistical theory of shape under elliptical models and singular value decompositions

The size-and-shape and shape distributions based on non-central and non-isotropic elliptical distributions are derived in this paper by using the singular value decomposition (SVD). The general densities require the computation of new integrals involving zonal polynomials. The invariance of the central shape distribution is also proved. Finally, some particular densities are applied in a classical data of Biology, and the inference based on exact distributions is performed after choosing the best model by using a modified BIC^∗ criterion.     

Minimizing submodular functions over families of sets

We consider the problem of characterizing the minimum of a submodular function when the minimization is restricted to a family of subsets. We show that, for many interesting cases, there exist two elementsa andb of the groundset such that the problem is equivalent to the problem of minimizing the submodular function over the sets containinga but notb. This leads to a polynomial-time algorithm for minimizing a submodular function over these families of sets. Our results apply, for example, to the families of odd cardinality subsets or even cardinality subsets separating two given vertices, or to the complement of a lattice family of subsets. We also derive that the second smallest value of a submodular function over a lattice family can be computed in polynomial-time. These results generalize and unify several known results.Research partially supported by NSF contract 9302476-CCR, Air Force contract F49620-92-J-0125 and DARPA contract N00014-92-J-1799.     

Borel sets and sectional matrices

Following the path trodden by several authors along the border between Algebraic Geometry and Algebraic Combinatorics, we present some new results on the combinatorial structure of Borel ideals. This enables us to prove theorems on the shape of thesectional matrix of a homogeneous ideal, which is a new invariant stronger than the Hilbert function. The authors were partially supported by the Consiglio Nazionale delle Ricerche (CNR).     

Cubes and orientability

We define and study a new class of matroids: cubic matroids. Cubic matroids include, as a particular case, all affine cubes over an arbitrary field. There is only one known orientable cubic matroid: the real affine cube. The main results establish as an invariant of orientable cubic matroids the structure of the subset of acyclic orientations with LV-face lattice isomorphic to the face lattice of the real cube or, equivalently, with the same signed circuits of length 4 as the real cube.     

Local-edge-connectivity in digraphs and oriented graphs

A digraph without any cycle of length two is called an oriented graph. The local-edge-connectivityλ(u,v) of two vertices u and v in a digraph or graph D is the maximum number of edge-disjoint u-v paths in D, and the edge-connectivity of D is defined as . Clearly, λ(u,v)?min{d⁺(u),d^-(v)} for all pairs u and v of vertices in D. Let δ(D) be the minimum degree of D. We call a graph or digraph D maximally edge-connected when λ(D)=δ(D) and maximally local-edge-connected when

λ(u,v)=min{d⁺(u),d^-(v)}     

Hypergraph families with bounded edge cover or transversal number

The transversal number, packing number, covering number and strong stability number of hypergraphs are denoted by τ, ν, ϱ and α, respectively. A hypergraph family t is called τ-bound (ϱ-bound) if there exists a “binding function”f(x) such that τ(H)≦f(v(H)) (ϱ(H)≦f(α(H))) for allH ∈ t. Methods are presented to show that various hypergraph families are τ-bound and/or ϱ-bound. The results can be applied to families of geometrical nature like subforests of trees, boxes, boxes of polyominoes or to families defined by hypergraph theoretic terms like the family where every subhypergraph has the Helly-property.     

Remarks on the density of sphere packings in three dimensions

This paper shows how the density of sphere packings of spheres of equal radius may be studied using the Delaunay decomposition. Using this decomposition, a local notion of density for sphere packings in ³ is defined. Conjecturally this approach should yield a bound of 0.740873... on sphere packings in ³, and a small perturbation of this approach should yield the bound of . The face-centered-cubic and hexagonal-close-packings provide local maxima (in a strong sense defined below) to the function which associates to every saturated sphere packing in ³ its density. The local measure of density coincides with the actual density for the face-centered cubic and hexagonal-close-packings.     

Remarks on my paper: packing of incongruent circles on the sphere

The paper [3] contains an upper bound to the weighted density of a packing of circles on the unit sphere with radii from a given finite set. This bound is attained by many packings and has applications to problems of solidity. In the present note it is shown that a certain condition imposed on the set of admissible radii can be removed by modifying the original proof of the theorem.