Counting Split Interval Orders

A poset (X,) is a split interval order (a.k.a. unit bitolerance order, proper bitolerance order) if a real interval and a distinguished point in that interval can be assigned to each xX so that xy precisely when x's distinguished point precedes y's interval, and x's interval precedes y's distinguished point. For each |X|9, we count the split interval orders and identify all posets that are minimal forbidden posets for split interval orders. The paper is a companion to Counting Split Semiorders by Fishburn and Reeds (this issue).     

Geometrical Characterization of Strict Suns in ℓ∞(n)

A subset M of a normed linear space X is called a strict sun if, for any x X\M, the set of its nearest points from M is nonempty and for any point y M which is nearest to x, the point y is a nearest point from M to any point of the ray {x + (1 - )y | > 0\}. We give an intrinsic geometrical characterization of strict suns in the space (n).     

On a class of functions with equal infima over a domain and its boundary

In this paper, we present a class of functions:f:X such that inf _xX f(x)= , whereX is a nonempty, finitely compact and convex set in a vector space andB _x ={xX: y aff(X){x:[x, y]X={x}. Our main tool is a recent minimax theorem by Ricceri (Ref. 1).     

D'Alembert's functional equation on restricted domains

Summary In the class of functionalsf:X , whereX is an inner product space with dimX 3, we study the D'Alembert functional equationf(x + y) + f(x – y) = 2f(x)f(y) (1) on the restricted domainsX ₁ = {(x, y) X ²/x, y = 0} andX ₂ = {(x, y) X ²/x = y}. In this paper we prove that the equation (1) restricted toX ₁ is not equivalent to (1) on the whole spaceX. We also succeed in characterizing all common solutions if we add the conditionf(2x) = 2f²(x) – 1. Using this result, we prove the equivalence between (1) restricted toX ₂ and (1) on the whole spaceX. This research follows similar previous studies concerning the additive, exponential and quadratic functional equations.     

A general minimax theorem

This paper is concerned with minimax theorems for two-person zero-sum games (X, Y, f) with payofff and as main result the minimax equality inf supf (x, y)=sup inff (x, y) is obtained under a new condition onf. This condition is based on the concept of averaging functions, i.e. real-valued functions defined on some subset of the plane with min {x, y}< (x, y)x, y} forx y and (x, x)=x. After establishing some simple facts on averaging functions, we prove a minimax theorem for payoffsf with the following property: Forf there exist averaging functions and such that for any x₁, x₂ X, > 0 there exists x₀ X withf (x₀, y) > f (x₁,y),f (x₂,y))– for ally Y, and for any y₁, y₂ Y, > 0 there exists y₀ Y withf (x, y₀) (f (x, y₁),f (x, y₂))+. This result contains as a special case the Fan-König result for concave-convex-like payoffs in a general version, when we take linear averaging with (x, y)=x+(1–)y, (x, y)=x+(1–)y, 0 <, < 1.Then a class of hide-and-seek games is introduced, and we derive conditions for applying the minimax result of this paper.

---

Zusammenfassung In dieser Arbeit werden Minimaxsätze für Zwei-Personen-Nullsummenspiele (X, Y,f) mit Auszahlungsfunktionf behandelt, und als Hauptresultat wird die Gültigkeit der Minimaxgleichung inf supf (x, y)=sup inff (x, y) unter einer neuen Bedingung an f nachgewiesen. Diese Bedingung basiert auf dem Konzept mittelnder Funktionen, d.h. reellwertiger Funktionen, welche auf einer Teilmenge der Ebene definiert sind und dort der Eigenschaft min {x, y} < < (x, y)x, y} fürx y, (x, x)=x, genügen. Nach der Herleitung einiger einfacher Aussagen über mittelnde Funktionen beweisen wir einen Minimaxsatz für Auszahlungsfunktionenf mit folgender Eigenschaft: Zuf existieren mittelnde Funktionen und, so daß zu beliebigen x₁, x₂ X, > 0 mindestens ein x₀ X existiert mitf (x₀,y) (f (x ₁,y),f (x₂,y)) – für alley Y und zu beliebigen y₁, y₂ Y, > 0 mindestens ein y₀ Y existiert mitf (x, y₀) (f (x, y₁),f (x, y ₂))+ für allex X. Dieses Resultat enthält als Spezialfall den Fan-König'schen Minimaxsatz für konkav-konvev-ähnliche Auszahlungsfunktionen in einer allgemeinen Version, wenn wir lineare Mittelung mit (x, y)=x+(1–)y, (x, y)= x+(1–)y, 0 <, < 1, betrachten.Es wird eine Klasse von Suchspielen eingeführt, welche mit dem vorstehenden Resultat behandelt werden können.

     

Einige Aspekte in der Zuordnungstheorie

Zusammenfassung Gegeben seien endliche MengenX, Y undZ X × Y, Z _x ={y¦(x,y) Z},Z _y ={x¦(x,y) Z}.Man nenntA X (bzw.B Y)zuordenbar, wenn es eine Injektion:A Y (bzw.: B X) mit(x) Z _x (bzw.(y) Z _y ) gibt, und (A, B) mit #A=#B > 0 einZuordnungspaar, wenn eine Bijektionf:A B mitf(x)Z _x B (bzw.f ^–1 (y) Z _y A) existiert. Die Bijektionf heißtZuordnungsplan fürA, B.In der vorliegenden Arbeit werden Fragen nach der Existenz von optimal zuordenbaren Mengen und optimalen Zuordnungspaaren behandelt, wenn man auf den MengenX undY Ordnungen vorgibt, wobei auch Nebenbedingungen berücksichtigt werden. In manchen Fällen lassen sich anhand der Beweise Zuordnungspläne oder ihre Berechnungsvorschrift explizit angeben.Zum Schluß werden die Aussagen an konkreten, dem Bereich der Wirtschaftswissenschaften entnommenen Beispielen erläutert.

---

Summary LetX, Y be finite sets andZ X × Y, Z _x ={y¦(x,y) Z},Z _y ={x¦(x,y)Z}. A X (resp.B Y) is calledassignable if there is an injection: A Y (resp.: B X) with (x) Z _x (resp.(y) Z _y ), (A, B) with #A=#B > 0 anassigned pair if there is a bijection f:A B withf (x) Z _x B (resp.f ^–1(y) Z _y A). The bijectionf is called aplan forA andB.In this paper problems are discussed concerning the existence of optimal assignable sets and optimal assigned pairs ifX andY are totally ordered, additional constraints are also considered. In some cases the proofs give explicit constructions of plans. The results are illustrated by application to problems occurring in Operations Research.

---

---

Diese Arbeit ist mit Unterstützung des Sonderforschungsbereiches 72 an der Universität Bonn entstanden.     

A note on merging

For a finite poset P and x, yP let pr(x>y) be the fraction of linear extensions which put x above y. N. Linial has shown that for posets of width 2 there is always a pair x, y with 1/3 pr(x>y)2/3. The disjoint union C ₁C ₂ of a 1-element chain with a 2-element chain shows that the bound 1/3 cannot be further increased. In this paper the extreme case is characterized: If P is a poset of width 2 then the bound 1/3 is exact iff P is an ordinal sum of C ₁C ₂'s and C ₁'s.     

Linear Extensions of Semiorders: II

Let M _n (k) denote the family of posets on n points with k ordered pairs that maximize the number of linear extensions among all such posets. Fishburn and Trotter [2] prove that every poset in M _n (k) is a semiorder and identifies all semiorders in M _n (k) for k n. The present paper specifies M _n (k) for all k 2 n – 3.     

Cube Orders

A finite partially ordered set P =(X, ) is a cube order in R ^m if there is a map C from X into cubes in R ^m such that, for all x and y in X, x y if and only if C(x) C(y). It is proved that every finite poset with order dimension 2 m is a cube order in R ^m .     

Randomly Weighted Sums of Subexponential Random Variables with Application to Ruin Theory

Let {X _k , 1 k n} be n independent and real-valued random variables with common subexponential distribution function, and let {k, 1 k n} be other n random variables independent of {X _k , 1 k n} and satisfying a _k b for some 0 < a b < for all 1 k n. This paper proves that the asymptotic relations P (max_{1 m n k=1} ^m _k X _k > x) P (sum _k=1 ⁿ _k X _k > x) sum _k=1 ⁿ P ( _k X _k > x) hold as x . In doing so, no any assumption is made on the dependence structure of the sequence { _k , 1 k n}. An application to ruin theory is proposed.     

On the semimartingale representation of reflecting Brownian motion in a cusp

Summary LetC be the symmetric cusp {(x, y)²:–x yx ,x0} where >1. In this paper we decide whether or not reflecting Brownian motion inC has a semimartingale representation. Here the reflecting Brownian motion has directions of reflection that make constant angles with the unit inward normals to the boundary. Our results carry through for a wide class of asymmetric cusps too.     

Linear Discrepancy and Weak Discrepancy of Partially Ordered Sets

The linear discrepancy of a partially ordered set P=(X,) is the least integer k for which there exists an injection f: XZ satisfying (i) if xy then f(x)<f(y) and (ii) if xy then |f(x)–f(y)|k. This concept is closely related to the weak discrepancy of P studied previously. We prove a number of properties of linear and weak discrepancies and relate them to other poset parameters. Both parameters have applications in ranking the elements of a partially ordered set so that the difference in rank of incomparable elements is minimized.     

Remarks on osculating linear spaces to projective varieties

Let X P^N be an integral n-dimensional variety and m(X, P, i) (resp. m(X, i)), 1 i N - n + 1, the Hermite invariants of X measuring the osculating behaviour of X at P (resp. at its general point). Here we prove m(X, x) + m(X, y) m(X, x + y) and m(X, P, x) + m(X, y) m(X, P, x + y) for all integers x, y such that x + y N - n + 1, the case n = 1 being known (M. Homma, A. Garcia and E. Esteves).*Partially supported by MIUR and GNSAGA of INdAM (Italy).     

Symmetrische Permutationsmengen

A permutation set (M, I) consisting of a setM and a set of permutations ofM, is calledsymmetric, if for any two permutations, the existence of anx M with (x) (x) and ^–1 (x) = ^–1 (x) implies ^–1 = ^–1 , andsharply 3-transitive, if for any two triples (x ₁,x ₂,x ₃), (y ₁,y ₂,y ₃) M ³ with|{x ₁,x ₂,x ₃ }| = |{y ₁,y ₂,y ₃ }| = 3 there is exactly one permutation with(x ₁) =y ₁,(x ₂) =y ₂,(x ₃) =y ₃. The following theorem will be proved.THEOREM.Let (M, ) be a sharply 3-transitive symmetric permutation set with |M|3, such that contains the identity. Then is a group and there is a commutative field K such that and the projective linear group PGL(2, K) are isomorphic.     

Extension of the Zorn lemma to general nontransitive binary relations

Let be an irreflexive (strict) binary relation on a nonempty setX. Denote the completion of by , i.e.,yx ifxy does not hold. An elementx ^* X is said to be a maximal element of onX ifx ^* x, xX. In this paper, an extension of the Zorn lemma to general nontrasitive binary relations (may lack antisymmetry) is established and is applied to prove existence of maximal elements for general nontrasitive (reflexive or irreflexive) binary relations on nonempty sets without assuming any topological conditions or linear structures. A necessary and sufficient condition has been also established to completely characterize the existence of maximal elements for general irreflexive nontrasitive binary relations. This is the first such result available in the literature to the best of our knowledge. Many recent known existence sults in the literature for vector optimization are shown to be special cases of our result.This work was supported in part by AFSOR Grant 91-0097.The author is grateful to the referees and Professor P. L. Yu for their comments and suggestions that led to this improved paper.     

Présentations des groupes de Fischer (II)

In this paper we give Coxeter presentation (X, ) for the three Fischer groupsG=Fi₂₂, Fi₂₃, Fi₂₄; we apply methods exposed in the first part. Each of these groups is generated by a class of 3-transpositions (named here a Fischer class) in which elements ofX are chosen. A subset of is the set of all the relations (xy) ^m(x,y)=1, wherex andy are inX and wherem(x,y) means the order ofxy inG. We obtainG as a specified quotient of the Coxeter group (X, ) with the appropriate diagram .     

On a classical Nicoletti boundary value problem

We shall derive existence, uniqueness and comparison results for the functional differential equationx(t)=f(t, x), a. e.tI, with classical Nicoletti boundary conditionsx _i(t_i)=y _iX, iA, whereI is a real interval,A is a nonempty set andX is a Banach space.     

Epsilon efficiency

This paper considers the extension of -optimality for scalar problems to vector maximization problems, or efficiency problems, which havem objective functions defined on a set .It is shown that the natural extension of the scalar -optimality concepts [viz, given >0, given a solution setS, ifxS there exists an efficient solutiony with f(x)–f(y), and given an efficient solutiony, there exists anxS with f(x)–f(y)] do not hold for some methods used. Six concepts of -efficient sets are introduced and examined, to a very limited extent, in the context of five methods used for generating efficient points or near efficient points.In doing so, a distinction is drawn between methods in which the surrogate optimizations are carried out exactly, and those where terminal -optimal solutions are obtained.The author would like to thank the referees whose thoroughness was extremely helpful for the revised paper.     

Towards the reconstruction of posets

The reconstruction conjecture for posets is the following: Every finite posetP of more than three elements is uniquely determined — up to isomorphism — by its collection of (unlabelled) one-element-deleted subposets P–{x}:xV(P).We show that disconnected posets, posets with a least (respectively, greatest) element, series decomposable posets, series-parallel posets and interval orders are reconstructible and that N-free orders are recognizable.We show that the following parameters are reconstructible: the number of minimal (respectively, maximal) elements, the level-structure, the ideal-size sequence of the maximal elements, the ideal-size (respectively, filter-size) sequence of any fixed level of the HASSE-diagram and the number of edges of the HASSE-diagram.This is considered to be a first step towards a proof of the reconstruction conjecture for posets.Research partly supported by DAAD.     

Primitive Inner Illuminating Systems for Convex Bodies

A set X of boundary points of a (possibly unbounded) convex body KE ^d illuminating K from within is called primitive if no proper subset of X still illuminates K from within. We prove that for such a primitive set X of an unbounded, convex set KE ^d (distinct from a cone) one has X=2 if d=2, X6 if d=3, and that there is no upper bound for X if d4.