The inequalities that determine the bargaining setM 1 (i)

It is well-known that the payoffs of the various bargaining sets of a cooperativen-person game are finite unions of closed convex polyhedra. In this paper, the system of inequalities that determines these polyhedra for the bargaining setM ₁ ⁽ⁱ⁾ is expressed in explicit form. It turns out that this system also expresses the condition that certain games, derived from the original game and from the potential payoffs, have full-dimensional cores.     

Some two-character sets

Some new examples of two-character sets with respect to planes of PG(3, q ²), q odd, are constructed. They arise from three-dimensional hyperbolic quadrics, from the geometry of an orthogonal polarity commuting with a unitary polarity. The last examples arise from the geometry of the unitary group PSU(3, 3) acting on the split Cayley hexagon H(2).     

A multidimensional generalization of Lagrange’s theorem on continued fractions

A multidimensional geometric analog of Lagrange’s theorem on continued fractions is proposed. The multidimensional generalization of the geometric interpretation of a continued fraction uses the notion of a Klein polyhedron, that is, the convex hull of the set of nonzero points in the lattice ? ⁿ contained inside some n-dimensional simplicial cone with vertex at the origin. A criterion for the semiperiodicity of the boundary of a Klein polyhedron is obtained, and a statement about the nonempty intersection of the boundaries of the Klein polyhedra corresponding to a given simplicial cone and to a certain modification of this cone is proved.     

A linear regression model for imprecise response

A linear regression model with imprecise response and p real explanatory variables is analyzed. The imprecision of the response variable is functionally described by means of certain kinds of fuzzy sets, the LR fuzzy sets. The LR fuzzy random variables are introduced to model usual random experiments when the characteristic observed on each result can be described with fuzzy numbers of a particular class, determined by 3 random values: the center, the left spread and the right spread. In fact, these constitute a natural generalization of the interval data. To deal with the estimation problem the space of the LR fuzzy numbers is proved to be isometric to a closed and convex cone of R³ with respect to a generalization of the most used metric for LR fuzzy numbers. The expression of the estimators in terms of moments is established, their limit distribution and asymptotic properties are analyzed and applied to the determination of confidence regions and hypothesis testing procedures. The results are illustrated by means of some case-studies.     

Vector transversals

The max-flow min-cut theorem is used to give a necessary and sufficient condition for one or two finite families of finite non-negative vectors to have a (common) vector transversal. The duality theorem of linear programming is then used to prove the polymatroid intersection theorem for any finite number of polymatroids, which in turn is used to give a necessary and sufficient condition for any finite number of finite families of finite sets to have a common vector transversal. (This result was announced without proof in [D. R. Woodall, in “Combinatorics (Proceedings, 4th British Combinatorial Conference)” pp. 195–200, London Mathematical Society Lecture Note Series No. 13, Cambridge Univ. Press, London/New York 1974].) This provides a weak generalization of the well-known conditions of Hall and of Ford and Fulkerson for one and two families of sets, respectively, to have a (common) transversal. It also provides a stronger necessary condition than was previously known for three or more families of sets to have a common transversal.     

O-minimal Hauptvermutung for polyhedra I

Milnor discovered two compact polyhedra which are homeomorphic but not PL homeomorphic (a counterexample to the Hauptvermutung). He constructed the homeomorphism by a finite procedure repeated infinitely often. Informally, we call a procedure constructive if it consists of an explicit procedure that is repeated only finitely many times. In this sense, Milnor did not give a constructive procedure to define the homeomorphism between the two polyhedra. In the case where the homeomorphism is semialgebraic, the author and Yokoi proved that the polyhedra in R ⁿ are PL homeomorphic. In that article, the required PL homeomorphism was not constructively defined from the given homeomorphism. In the present paper we obtain the PL homeomorphism by a constructive procedure starting from the homeomorphism. We prove in fact that for any ordered field R equipped with any o-minimal structure, two definably homeomorphic compact polyhedra in R ⁿ are PL homeomorphic (the o-minimal Hauptvermutung theorem 1.1). Together with the fact that any compact definable set is definably homeomorphic to a compact polyhedron we can say that o-minimal topology is “tame”.     

A Fubini theorem

Let I₀ be the σ-ideal of subsets of a Polish group generated by Borel sets which have perfectly many pairwise disjoint translates. We prove that a Fubini-type theorem holds between I₀ and the σ-ideals of Haar measure zero sets and of meager sets. We use this result to give a simple proof of a generalization of a theorem of Balcerzak-Ros?anowski-Shelah stating that I₀ on N² strongly violates the countable chain condition.     

Convex bodies and multiplicities of ideals

We associate convex regions in ? ⁿ to m-primary graded sequences of subspaces, in particular m-primary graded sequences of ideals, in a large class of local algebras (including analytically irreducible local domains). These convex regions encode information about Samuel multiplicities. This is in the spirit of the theory of Gröbner bases and Newton polyhedra on the one hand, and the theory of Newton-Okounkov bodies for linear systems on the other hand. We use this to give a new proof as well as a generalization of a Brunn-Minkowski inequality for multiplicities due to Teissier and Rees-Sharp.     

A bilevel programming approach to the travelling salesman problem

We show that the travelling salesman problem is polynomially reducible to a bilevel toll optimization program. Based on natural bilevel programming techniques, we recover the lifted Miller-Tucker-Zemlin constraints. Next, we derive an O(n²) multi-commodity extension whose LP relaxation is comparable to the exponential formulation of Dantzig, Fulkerson and Johnson.     

Properties of P-sets and trapped compact convex sets

New properties of P-sets, which constitute a large class of convex compact sets in ? ⁿ that contains all convex polyhedra and strictly convex compact sets, are obtained. It is shown that the intersection of a P-set with an affine subspace is continuous in the Hausdorff metric. In this theorem, no assumption of interior nonemptiness is made, unlike in other known intersection continuity theorems for set-valued maps. It is also shown that if the graph of a set-valued map is a P-set, then this map is continuous on its entire effective set rather than only on the interior of this set. Properties of the so-called trapped sets are also studied; well-known Jung’s theorem on the existence of a minimal ball containing a given compact set in ? ⁿ is generalized. As is known, any compact set contains n + 1 (or fewer) points such that any translation by a nonzero vector takes at least one of them outside the minimal ball. This means that any compact set is trapped in the minimal ball. Compact sets trapped in any convex compact sets, rather than only in norm bodies, are considered. It is shown that, for any compact set A trapped in a P-set M ? ? ⁿ , there exists a set A ⁰ ? A trapped in M and containing at most 2n elements. An example of a convex compact set M ? ? ⁿ for which such a finite set A ⁰ ? A does not exist is given.     

Algorithmic and structural aspects of the P 3-Radon number

The generalization of classical results about convex sets in ? ⁿ to abstract convexity spaces, defined by sets of paths in graphs, leads to many challenging structural and algorithmic problems. Here we study the Radon number for the P ₃-convexity on graphs. P ₃-convexity has been proposed in connection with rumour and disease spreading processes in networks and the Radon number allows generalizations of Radon’s classical convexity result. We establish hardness results and describe efficient algorithms for trees.     

Coxeter complexes and graph-associahedra

Given a graph Γ, we construct a simple, convex polytope, dubbed graph-associahedra, whose face poset is based on the connected subgraphs of Γ. This provides a natural generalization of the Stasheff associahedron and the Bott-Taubes cyclohedron. Moreover, we show that for any simplicial Coxeter system, the minimal blow-ups of its associated Coxeter complex has a tiling by graph-associahedra. The geometric and combinatorial properties of the complex as well as of the polyhedra are given. These spaces are natural generalizations of the Deligne-Knudsen-Mumford compactification of the real moduli space of curves.     

On switching paths polyhedra

A class of integer polyhedra with totally dual integral (tdi) systems is proposed, which generalizes and unifies the “Switching Paths Polyhedra” of Hoffman (introduced in his generalization of Max Flow-Min Cut) and such polyhedra as the convex hull of (the incidence vectors of) all “path-closed sets” of an acyclic digraph, or the convex hull of all sets partitionable intok path-closed sets. As an application, new min-max theorems concerning the mentioned sets are given. A general lemma on when a tdi system of inequalities is box tdi is also given and used.     

Maximal sets with no solution to <Emphasis Type="Italic">x</Emphasis>+<Emphasis Type="Italic">y</Emphasis>=3<Emphasis Type="Italic">z</Emphasis>

In this paper, we are interested in a generalization of the notion of sum-free sets. We address a conjecture rst made in the 90s by Chung and Goldwasser. Recently, after some computer checks, this conjecture was formulated again by Matolcsi and Ruzsa, who made a rst signicant step towards it. Here, we prove the full conjecture by giving an optimal upper bound for the Lebesgue measure of a 3-sum-free subset A of [0; 1], that is, a set containing no solution to the equation x+y=3z where x, y and z are restricted to belong to A. We then address the inverse problem and characterize precisely, among all sets with that property, those attaining the maximal possible measure.     

Restricted Modules and Conjectures for Modules of Constant Jordan Type

We introduce the class of restricted k[A]-modules and p ^t -Jordan types for a finite abelian p-group A of exponent at least p ^t and a field k of characteristic p. For these modules, we generalize several theorems by Benson, verify a generalization of conjectures stated by Suslin and Rickard giving constraints on Jordan types for modules of constant Jordan type when t is 1. We state conjectures giving constraints on p ^t -Jordan types and show that many p ^t -Jordan types are realizable.     

On Finite Linear Systems Containing Strict Inequalities

This paper deals with linear systems containing finitely many weak and/or strict inequalities, whose solution sets are referred to as evenly convex polyhedral sets. The classical Motzkin theorem states that every (closed and convex) polyhedron is the Minkowski sum of a convex hull of finitely many points and a finitely generated cone. In this sense, similar representations for evenly convex polyhedra have been recently given by using the standard version for classical polyhedra. In this work, we provide a new dual tool that completely characterizes finite linear systems containing strict inequalities and it constitutes the key for obtaining a generalization of Motzkin theorem for evenly convex polyhedra.     

Conjectures on GCn sets

The paper gives a generalization of the counterexample of C. de Boor on ? ^d and provides an example of GC ₂ set in ?⁴ with three maximal hyperplanes. Also, a conjecture on the number of maximal lines of GC _n sets in ? ^d is discussed and proved that it is true in the case when n = 2, d = 3.     

Families of sets with locally bounded width

A family of sets ? islocally k- wide if and only if the width (as a poset ordered by inclusion) of ? is at mostk for everyx. The directed covering graph of a locally 1-wide family of sets is a forest of rooted trees. It is shown that if ? is a locallyk-wide family of subsets of {1,...,n}, then |?|≤(2k) ^k?1 n. The proof involves a counting argument based on families of closed sets associated with theSperner closures in the filters of ?. The Sperner closure ofU in ? is the intersection of the members of the greatest Sperner antichain of ? _U = {V ∈ ?|V ?U}. This closure operation is related to a generalization of maximality in posets.