The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2

LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations $$\left\{ {(i_1 ,i_2 ,...,i_{n - 1} ,i_n ,),(i_n ,i_{n - 1} ,...,i_2 ,i_1 ,)} \right\}$$ is called ageometric permutation of S if there is a line that intersects all sets ofS in this order. We prove thatS can realize at most 2n?2 geometric permutations. This upper bound is tight.     

Covering graphs by the minimum number of equivalence relations

An equivalence graph is a vertex disjoint union of complete graphs. For a graphG, let eq(G) be the minimum number of equivalence subgraphs ofG needed to cover all edges ofG. Similarly, let cc(G) be the minimum number of complete subgraphs ofG needed to cover all its edges. LetH be a graph onn vertices with maximal degree ≦d (and minimal degree ≧1), and letG= \(\bar H\) be its complement. We show that $$\log _2 n - \log _2 d \leqq eq(G) \leqq cc(G) \leqq 2e^2 (d + 1)^2 \log _e n.$$ The lower bound is proved by multilinear techniques (exterior algebra), and its assertion for the complement of ann-cycle settles a problem of Frankl. The upper bound is proved by probabilistic arguments, and it generalizes results of de Caen, Gregory and Pullman.     

Directed graphs over topological spaces: Some set theoretical aspects

In this paper we shall consider problems of the following type. SupposeG is some set,U is some family of subsests ofG (e.g.G could be the Euclidean plane andU might be the family of all sets of Lebesgue measure zero), andG is any directed graph overG (i.e. any collection of ordered pairs of members ofG) such that for eachg∈G the set {h:<g,h>∈G} belongs to the familyU. How large a setSυG must there exist with the property that (S×S) ∩G=, i.e. such that it is totally disconnected? In many of the cases we shall consider (including the particular example above), the answer will turn out to be independent of the axioms of set theory and will remain so even after adjoining the negation of the continuum hypothesis.     

On optimal backward perturbation bounds for the linear least squares problem

Consider the linear least squares problem min _x ‖b?Ax‖₂ whereA is anm×n (m<n) matrix, andb is anm-dimensional vector. Lety be ann-dimensional vector, and let ηls(y) be the optimal backward perturbation bound defined by $$\eta _{LS} (y) = \inf \{ ||F||_F :y is a solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} .$$ . An explicit expression of ηls(y) (y≠0) has been given in [8]. However, if we define the optimal backward perturbation bounds ηmls(y) by $$\eta _{MLS} (y) = \inf \{ ||F||_F :y is the minimum 2 - norm solution to \mathop {min}\limits_x ||b - (A + F)x||_2 \} ,$$ , it may well be asked: How to derive an explicit expression of ηmls(y)? This note gives an answer. The main result is: Ifb≠0 andy≠0, then ηmls(y)=ηls (y).     

A characterization of the Wishart exponential families by an invariance property

E is the space of real symmetric (d, d) matrices, andS and \(\bar S\) are the subsets ofE of positive definite and semipositive-definite matrices. Let there be ap in $$\Lambda = \left\{ {\frac{1}{2},1,\frac{3}{2}, \ldots \frac{{d - 1}}{2}} \right\} \cup \left] {\frac{{d - 1}}{2}, + \infty } \right[$$ The Wishart natural exponential family with parameterp is a set of probability distributions on \(\bar S\) defined by $$F_p = \{ \exp [ - \tfrac{1}{2}Tr(\Gamma x)](det\Gamma )^p \mu _p (dx);\Gamma \in S\} $$ where μ_p is a suitable measure on \(\bar S\) . LetGL(?^d) be the subset ofE of invertible matrices. Fora inGL(?^d), define the automorphismg _a ofE byg _a(x)=^t axa, where ^t a is the transpose ofa. The aim of this paper is to show that a natural exponential familyF onE is invariant byg _a for alla inGL(?^d) if and only if there existsp in Λ such that eitherF=F _p, orF is the image ofF _p byx??x. (Theorem).     

Presentations of the amalgamated free product of two infinite cycles

LetH=〈a,b;a ^k =b ^l 〉, wherek,l≧2 andk+l>4. McCool and Pietrowski have proved that any pair of generators forH is Nielsen equivalent to a pairx=a ^r andy=b ^s where $$(a){\text{ }}gcd(r, s) = gcd(r, k) = gcd(s, l) = 1,$$ $$(b){\text{ }}0< 2r \leqq ks{\text{ }}and{\text{ }}0< 2s \leqq lr.$$ In terms ofx andy,H can be presented as $$G = \left\langle {x,{\text{ }}y;{\text{ }}x^{ks} = y^{lr} ,\left[ {x,{\text{ }}y^l } \right] = \left[ {x^k ,{\text{ }}y} \right] = 1} \right\rangle$$ and Zieschang has shown that ifr=1 ors=1, thenH can be defined by a single relation inx andy. We establish the exact converse of Zieschang's result, namely thatH is not defined by a single relation inx andy unlessr=1 ors=1. The proof is based on an observation of Magnus which associates polynomials with relators and some elementary facts about cyclotomic polynomials.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

The average quality of greedy-algorithms for the Subset-Sum-Maximization Problem

This paper deals with the quality of approximative solutions for the Subset-Sum-Maximization-Problem maximize $$\sum\limits_{i = l}^n {a_i x_i } $$ subject to $$\sum\limits_{i = l}^n {a_i x_i } \leqslant b$$ wherea _l,...,a_n,bεR⁺ andx _l,...x_nε{0,1}. produced by certain heuristics of a Greedy-type. Every heuristic under consideration realizes a feasible solution (x ₁, ..., x_n) whose objective value is less or equal the optimal value, which is of course not greater thanb. We use the gap between capacityb and realized value as an upper bound for the error made by the heuristic and as a criterion for quality. Under the stochastic model:a ₁, ..., a_n, b independent,a ₁...,a_n uniformly distributed on [0, 1], b uniformly distributed on [0,n] we derive the gap-distributions and the expected size of the gaps. The analyzed algorithms include four algorithms which can be done in linear time and four heuristics which require sorting, which means that they are done inO(nlnn) time.     

Binding number and Hamiltonian(g, f)-factors in graphs

A(g, f)-factorF of a graphG is called a Hamiltonian(g, f)-factor ifF contains a Hamiltonian cycle. The binding number ofG is defined by $bind(G) = \min \left\{ {\frac{{|N_G (X)|}}{{|X|}}|\not 0 \ne X \subset V(G), N_G (X) \ne V(G)} \right\}$ . Let G be a connected graph, and let a andb be integers such that 4 ≤ a <b. Letg, f be positive integer-valued functions defined onV(G) such that a ≤g(x) < f(x) ≤ b for everyx ∈V(G). In this paper, it is proved that if $bind(G) \geqslant \frac{{(a + b - 5)(n - 1)}}{{(a - 2)n - 3(a + b - 5)}}, \nu (G) \geqslant \frac{{(a + b - 5)^2 }}{{a - 2}}$ and for any nonempty independent subset X ofV(G), thenG has a Hamiltonian(g, f)-factor.     

Quasi-implication algebras,Part I: Elementary theory

Quasi-implication algebras (QIA's) are intended to generalize orthomodular lattices (OML's) in the same way that implication algebras (J. C. Abbott) generalize Boolean lattices. A QIA is defined to be a setQ together with a binary operation → satisfying the following conditions (a→b is denotedab). (Q1) $$\left( {ab} \right)a = a$$ (Q2) $$\left( {ab} \right)\left( {ac} \right) = \left( {ba} \right)\left( {bc} \right)$$ (Q3) $$\left( {\left( {ab} \right)\left( {ba} \right)} \right)a = \left( {\left( {ba} \right)\left( {ab} \right)} \right)b$$ Every OML induces a QIA, wherea → b=a ^⊥?(a?b). On the other hand, every QIA induces a join semi-lattice with a greatest element 1, where 1=aa,a≤b iffab=1, anda?b=((ab)(ba))a. A bounded QIA is defined to be a QIA with a least element 0 (w.r.t.≤). The QIA associated with any OML is bounded, the zero elements being the same. Conversely, every bounded QIA induces an OML, wherea ^⊥=a0, anda?b=((ab)(a0))0. The relationC of compatibility is defined so thataCb iffa≤ba, and it is shown that every compatible sub-QIA of a QIA is an implication algebra.     

On the uniform complete convergence of density function estimates

Letf be a uniformly continuous density function. LetW be a non-negative weight function which is continuous on its compact support [a, b] and ∫ _a ^b W(x)dx=1. The complete convergence of $$\mathop {\sup }\limits_{ - \infty< s< \infty } \left| {\frac{1}{{nb\left( n \right)}}\sum\limits_{k - 1}^n {W\left( {\frac{{s - X_k }}{{b\left( n \right)}}} \right)} - f\left( s \right)} \right|$$ to zero is obtained under varying conditions on the bandwidthsb(n), support or moments off, and smoothness ofW. For example, one choice of the weight function for these results is Epanechnikov's optimal function andnb ²(n)>n ^δ for some δ>0. The uniform complete convergence of the mode estimate is also considered.     

Spaces of compact operators and their dual spaces

LetE andF be reflexive Banach spaces andC the space of all compact linear operators fromE toF. A representation of the dual space ofC is given and it is proved thatC is either reflexive or nonconjugate. Applications of these results are also given.     

On All Fractional （a,b, k）-Critical Graphs

Let a,b,k,r be nonnegative integers with 1≤a≤b and r≥2.LetG be a graph of order n with n(a+b)(r(a+b)-2)+ak/a.In this paper,we first show a characterization for all fractional(a,b,k)-critical graphs.Then using the result,we prove that G is all fractional(a,b,k)-critical if δ(G)≥(r-1)b2/a+k and |NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b for any independent subset {x1,x2,...,xr} in G.Furthermore,it is shown that the lower bound on the condition|NG(x1)∪NG(x2)∪···∪NG(xr)|≥bn+ak/a+b is best possible in some sense,and it is an extension of Lu's previous result.     

On minor forms of Desargues and Pappus

Let Π be a projective plane coordinatized by a ternary ring (R, F). In addition to the two operations + and ·, defined bya+b =F(a,1,b and \(a \cdot b = F(a,b,0)\) , a third operation * is defined by \(a * b = F(1,a,b),\forall a,b \in R\) Several minor forms of the propositions of Desargues and Pappus are introduced in Π and their geometrical properties are developed. Several algebraic results are obtained in connection with these minor forms. For example, the first minor form of DesarguesD ₁ is proved to be equivalent to each of the following algebraic identities in every (R, F): (1) $$a \cdot c = c \cdot a \Rightarrow F(a,c,b) = F(c,a,b),$$ (2) $$a \cdot (1 + b) = a + a \cdot b,$$ (3) $$a * b = a + b$$ (4) $$F(x,m,k) = (x \cdot m) * k,\forall a,b,c,k,m,x \in R.$$ Some more algebraic identities are characterized byD ₂ andD ₃.     

A ℤ-Simplex Algorithm with partial updates

The Simplex primal and dual methods, for the solution of $$\max \left\{ {c^T x:Ax = b, x \geqslant 0} \right\},$$ were presented previously in terms of certain bases ? and \(\mathbb{Y}\) ofN(A) andR(A ^T ) respectively. In these implementations, called the ?-Simplex Algorithm and the \(\mathbb{Y}\) -Dual Method, the bases ? and \(\mathbb{Y}\) (giving the edges of the polyhedron in question at the given basic feasible solution) are updated at each iteration. In this paper we show that only partial updates of ? are needed in the ?-Simplex Algorithm, analogously to the partial updates in the Revised Simplex Algorithm. Similar results can be given for the \(\mathbb{Y}\) -Dual Method.     

Hadamard Inequality and a Refinement of Jensen Inequality for Set—Valued Functions

We present the following set-valued analogue of the Hadamard inequality: Let Y be a Banach space, I be an open interval and let F: I ? cl(Y) be a continuous and convex set-valued function. Then $${F(a)+F(b)\over 2}\subset{1\over b-a}\int_a^b\ F(x)dx\subset F \bigg({a+b\over 2}\bigg)$$ , for every a, b ∈ I, a < b. Some refinement of Jensen inequality for set-valued functions is also given.     

Minimum degree of bipartite graphs and the existence ofk-factors

LetG be a bipartite graph with bipartition (X, Y) andk a positive integer. If (i) $$\left| X \right| = \left| Y \right|,$$ (ii) $$\delta (G) \geqslant \left\lceil {\frac{{\left| X \right|}}{2}} \right\rceil \geqslant k,$$ \(\left| X \right| \geqslant 4k - 4\sqrt k + 1\) when |X| is odd and |X| ≥ 4k ? 2 when |X| is even, thenG has ak-factor.     

Local diameters of compact planar sets

Given a compact setS?E² andP ₁ εS, we consider sequencesP _i , 1<i<∞, such that $$h_i : = \left\| {P_i - P_{i + 1} } \right\| = \mathop {\max }\limits_{R \in S} \left\| {P_i - R} \right\|$$ . Callh=limh _i a local diameter ofS. It is realized by a line segmentPQS. In relation toD(S), the ordinary diameter ofS, we determine (with and without certain angular constraints) how smallh can be. For example, ifA, B ε S and the line segmentAB is a diameter ofS, we determine best possible lower bounds for ∥P?Q∥/∥A?B∥ in terms of the smallest angle formed by the lines extendingPQ andAB. Local diameters arise from the problem of computing generalized transfinite diameters. Moreover, information about local diameters provides both upper and lower bounds on the isoperimetric quotient ofS.     

On the combinatorial structure of Rauzy graphs

Let S _m ⁰ be the set of all irreducible permutations of the numbers {1, ??,m} (m ?? 3). We define Rauzy induction mappings a and b acting on the set S _m ⁰ . For a permutation ?? ?? S _m ⁰ , denote by R(??) the orbit of the permutation ?? under the mappings a and b. This orbit can be endowed with the structure of an oriented graph according to the action of the mappings a and b on this set: the edges of this graph belong to one of the two types, a or b. We say that the graph R(??) is a tree composed of cycles if any simple cycle in this graph consists of edges of the same type. An equivalent formulation of this condition is as follows: a dual graph R*(??) of R(??) is a tree. The main result of the paper is as follows: if the graph R(??) of a permutation ?? ?? S _m ⁰ is a tree composed of cycles, then the set R(??) contains a permutation ?? ₀: i ? m + 1 ? i, i = 1, ??,m. The converse result is also proved: the graph R(?? ₀) is a tree composed of cycles; in this case, the structure of the graph is explicitly described.