Bivariate Bonferroni inequalities

Summary LetA ₁,A ₂, ,A _m ,C ₁,C ₂, ,C _n be events on a given probability speace. LetV _m andU _n , respectively, be the numbers among theA _i 's andC _j 's which occur.Upper and lower bounds ofP(V _m 1, U _n 1) are obtained by means of the bivariate binomial moments. These extend recent univariate optimal Bonferroni-type inequalities.     

A distance constrainedp-facility location problem on the real line

LetV = {v ₁,, v _n } be a set ofn points on the real line (existing facilities). The problem considered is to locatep new point facilities,F ₁,, F _p , inV while satisfying distance constraints between pairs of existing and new facilities and between pairs of new facilities. Fori = 1, , p, j = 1, , n, the cost of locatingF _i at pointv _j isc _ij . The objective is to minimize the total cost of setting up the new facilities. We present anO(p ³ n ² logn) algorithm to solve the model.     

Robustness of positional scoring over subsets of alternatives

Positional score vectorsw=(w ₁,,w _m ) for anm-element setA, andv=(v ₁,,v _k ) for ak-element proper subsetB ofA, agree at a profiles of linear orders onA when the restriction toB of the ranking overA produced byw operating ons equals the ranking overB produced byv operating on the restriction ofs toB. Givenw ₁>w _mandv ₁>v _k , this paper examines the extent to which pairs of nonincreasing score vectors agree over sets of profiles. It focuses on agreement ratios as the number of terms in the profiles becomes infinite. The limiting agreement ratios that are considered for (m, k) in {(3,2),(4,2),(4,3)} are uniquely maximized by pairs of Borda (linear, equally-spaced) score vectors and are minimized when (w,v) is either ((1,0,,0),(1,,1,0)) or ((1,,,1,0),(1,0,,0)).This research was supported by the National Science Foundation, Grants SOC 75-00941 and SOC 77-22941.     

On the singular graph and the Weyr characteristic of anM-matrix

LetA be anM-matrix in standard lower block triangular form, with diagonal blocksA _ii irreducible. LetS be the set of indices such that the diagonal blockA is singular. We define the singular graph ofA to be the setS with partial order defined by > if there exists a chain of non-zero blocksA _i, A_ij, , A_l.Let ₁ be the set of maximal elements ofS, and define thep-th level _p ,p = 2, 3, , inductively as the set of maximal elements ofS \( _{1 p-1}). Denote by _p the number of elements in _p . The Weyr characteristic (associated with 0) ofA is defined to be (A) = ( ₁, ₂,, _h ), where ₁ + + _p = dim KerA ^p ,p = 1, 2, , and _h > 0, _h+1 = 0.Using a special type of basis, called anS-basis, for the generalized eigenspaceE(A) of 0 ofA, we associate a matrixD withA. We show that(A) = ( ₁, , _h) if and only if certain submatricesD _p,p+1 ,p = 1, , h – 1, ofD have full column rank. This condition is also necessary and sufficient forE(A) to have a basis consisting of non-negative vectors, which is a Jordan basis for –A. We also consider a given finite partially ordered setS, and we find a necessary and sufficient condition that allM-matricesA with singular graphS have(A) = ( ₁, , _h). This condition is satisfied ifS is a rooted forest.The work of the second-named author was partly supported by the National Science Foundation, under grant MPS-08618 A02.     

Generalized Eulerian numbers and the topology of the Hessenberg variety of a matrix

Let Agl(n, C) and let p be a positive integer. The Hessenberg variety of degree p for A is the subvariety Hess(p, A) of the complete flag manifold consisting of those flags S ₁ S _n–1 in ⁿ which satisfy the condition AS _i S _i+p ,for all i. We show that if A has distinct eigenvalues, then Hess(p, A) is smooth and connected. The odd Betti numbers of Hess(p, A) vanish, while the even Betti numbers are given by a natural generalization of the Eulerian numbers. In the case where the eigenvalues of A have distinct moduli, |₁|<<|₁|, these results are applied to determine the dimension and topology of the submanifold of U(n) consisting of those unitary matrices P for which A ₀=P ^-1 AP is in Hessenberg form and for which the diagonal entries of the QR-iteration initialized at A ₀ converge to a given permutation of ₁,_n.Research partially supported by the National Science Foundation under Grant ECS-8696108.     

Edge-isoperimetric inequalities in the grid

The grid graph is the graph on [k] ⁿ ={0,...,k–1} ⁿ in whichx=(x _i ) ₁ ⁿ is joined toy=(y _i ) ₁ ⁿ if for somei we have |x _i –y _i |=1 andx _j =y _j for allji. In this paper we give a lower bound for the number of edges between a subset of [k] ⁿ of given cardinality and its complement. The bound we obtain is essentially best possible. In particular, we show that ifA[k] ⁿ satisfiesk ⁿ /4|A|3k ⁿ /4 then there are at leastk ^n–1 edges betweenA and its complement.Our result is apparently the first example of an isoperimetric inequality for which the extremal sets do not form a nested family.We also give a best possible upper bound for the number of edges spanned by a subset of [k] ⁿ of given cardinality. In particular, forr=1,...,k we show that ifA[k] ⁿ satisfies |A|r ⁿ then the subgraph of [k] ⁿ induced byA has average degree at most 2n(1–1/r).Research partially supported by NSF Grant DMS-8806097     

The Braided product of Ockham algebras

In this paper we introduce an algebraic concept of the product of Ockham algebras called the Braided product. We show that ifL _i MS(i=1, 2, ,n) then the Braided product ofL _i(i=1, 2, ,n) exists if and only ifL ₁, ,L _n have isomorphic skeletons.     

On a Turán type problem of Erdös

Let L ^k be the graph formed by the lowest three levels of the Boolean lattice B _k , i.e.,V(L ^k )={0, 1,...,k, 12, 13,..., (k–1)k} and 0is connected toi for all 1ik, andij is connected toi andj (1i<jk).It is proved that if a graph G overn vertices has at leastk ^3/2 n ^3/2 edges, then it contains a copy of L ^k .Research supported in part by the Hungarian National Science Foundation under Grant No. 1812     

Card shuffling and a transformation on S n

Summary We consider two card shuffling schemes. The first, which has appeared in the literature previously ([G], [RB], [T]), is as follows: start with a deck ofn cards, and pick a random tuplet { 1, 2, , n} ⁿ ; interchange cards 1 andt ₁, then interchange cards 2 andt ₂, etc. The second scheme, which can be viewed as a transformation on the symmetric groupS _n , is given by the restriction of the former shuffling scheme to tuplest which form a permutation of {1, 2,,n}.We determine the bias of each of these shuffling schemes with respect to the sets of transpositions and derangements, and the expected number of fixed points of a permutation generated by each of these shuffling schemes. For the latter scheme we prove combinatorially that the permutation which arises with the highest probability is the identity. The same question is open for the former scheme. We refute a candidate answer suggested by numerical evidence [RB].This work was carried out in part while R.S. was visiting the Institute for Mathematics and its Applications and was partly supported through NSF Grant CCR-8707539.     

A structure theorem for sum form functional equations

Summary It is proved that, iff _ij:]0, 1[ C (i = 1, ,k;j = 1, ,l) are measurable, satisfy the equation (1) (with some functionsg _it, h_jt:]0, 1[ C), then eachf _ij is in a linear space (called Euler space) spanned by the functionsx x ^j(logx) ^k (x ]0, 1[;j = 1, ,M;k = 0, ,m _j – 1), where ₁, , _M are distinct complex numbers andm ₁, , m_M natural numbers. The dimension of this linear space is bounded by a linear function ofN.     

Nonabelian K-theory: The nilpotent class of K1 and general stability

A functorial filtration GL _n =S^–1L _n S⁰L _n S ⁱ L _n E _n of the general linear group GL _{n, n} 3, is defined and it is shown for any algebra A, which is a direct limit of module finite algebras, that S^–1 L _n (A)/S⁰L _n (A) is abelian, that S⁰L _n (A) S¹L _n (A) is a descending central series, and that S ⁱ L _n (A) = E _n(A) whenever i the Bass-Serre dimension of A. In particular, the K-functors k ₁ S ⁱ L _n =S ⁱ L _n /E _n are nilpotent for all i 0 over algebras of finite Bass-Serre dimension. Furthermore, without dimension assumptions, the canonical homomorphism S ⁱ L _n (A)/S ⁱ⁺¹ L _n (A)S ⁱ L _{n+ 1}(A)/S ⁱ⁺¹ L _{n + 1} (A) is injective whenever n i + 3, so that one has stability results without stability conditions, and if A is commutative then S⁰L _n (A) agrees with the special linear group SL _n (A), so that the functor S⁰L _n generalizes the functor SL _n to noncommutative rings. Applying the above to subgroups H of GL _n (A), which are normalized by E _n(A), one obtains that each is contained in a sandwich GL _n (A, ) H E _n(A, ) for a unique two-sided ideal of A and there is a descending S⁰L _n (A)-central series GL _n (A, ) S⁰L _n (A, ) S¹L _n (A, ) S ⁱ L _n (A, ) E _n(A, ) such that S ⁱ L _n (A, )=E _n(A, ) whenever i Bass-Serre dimension of A.Dedicated to Alexander Grothendieck on his sixtieth birthday     

The k-orbit reconstruction and the orbit algebra

Let (G, W) be a permutation group on a finite set W = {w ₁,..., w _n}. We consider the natural action of G on the set of all subsets of W. Let h ₀, h ₁,..., h _N be the orbits of this action. For each i, 1 i N, there exists k, 1 k n, such that h _i is a set of k-element subsets of W. In this case h _i is called a symmetrized k-orbit of the group (G, W) or simply a k-orbit. With a k-orbit h _i we associate a multiset H(h _i ) = % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyykJeoaaa!3690!\[\langle \]h _i ⁽¹⁾, h _i ⁽²⁾,..., h _i ^(k)% MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGGipm0dc9vqaqpepu0xbbG8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaGaeyOkJepaaa!36A1!\[\rangle \] of its (k – 1)-suborbits. Orbits h _i and h _j are called equivalent if H(h _i ) = H(h _j ). An orbit is reconstructible if it is equivalent to itself only. The paper concerns the k-orbit reconstruction problem and its connections with different problems in combinatorics. The technique developed is based on the notion of orbit and co-orbit algebras associated with a given permutation group (G, W).     

A statistical estimate of the structure of multi-extremal problems

The solution of ak-extremal problem is defined as the set of pairs (x _i ^* , _i),i = 1, ,k, where x _t ^* isi ^th local minimum and _i is the volume of the set of attraction of this minimum. A Bayesian estimate ofk and ( ₁ , , _k ) is constructed.This paper has been written while the author was a CNR visiting professor at the Institute of Mathematics of the Milano University.     

Verschärfung einer Ungleichung von Ky Fan

Summary In this paper we prove the following:IfA _n ,G _n andH _n (resp.A _n ,G _n andH _n ) denote the arithmetic, geometric and harmonic means ofa ₁,, a _n (resp. 1 –a ₁,, 1 –a _n ) and ifa _i (0, 1/2],i = 1,,n, then(G _n /G _n ) ⁿ (A _n /A _n ) ^n-1 H _n /H _n , (^*) with equality holding forn = 1,2. Forn 3 equality holds if and only ifa ₁ = =a _n . The inequality (^*) sharpens the well-known inequality of Ky Fan:G _n /G _n A _n /A _n .

     

On construction ofk-wise independent random variables

A 0–1probability space is a probability space (, 2,P), where the sample space -{0, 1} ⁿ for somen. A probability space isk-wise independent if, whenY _i is defined to be theith coordinate or the randomn-vector, then any subset ofk of theY _i 's is (mutually) independent, and it is said to be a probability spacefor p ₁,p ₂, ...,p _n ifP[Y _i =1]=p _i .We study constructions ofk-wise independent 0–1 probability spaces in which thep _i 's are arbitrary. It was known that for anyp ₁,p ₂, ...,p _n , ak-wise independent probability space of size always exists. We prove that for somep ₁,p ₂, ...,p _n [0,1],m(n,k) is a lower bound on the size of anyk-wise independent 0–1 probability space. For each fixedk, we prove that everyk-wise independent 0–1 probability space when eachp _i =k/n has size (n _k ). For a very large degree of independence —k=[n], for >1/2- and allp _i =1/2, we prove a lower bound on the size of . We also give explicit constructions ofk-wise independent 0–1 probability spaces.This author was supported in part by NSF grant CCR 9107349.This research was supported in part by the Israel Science Foundation administered by the lsrael Academy of Science and Humanities and by a grant of the Israeli Ministry of Science and Technology.     

A basis for the type 〈n〉 hyperidentities of the medial variety of semigroups

Summary The medical varietyMV of semigroups is the variety defined by the medial identityxyzw = xzyw. This variety is known to satisfy the medial hyperidentitiesF(G(x ₁₁ ,, x _1n ),, G(x _n1 ,, x _nn )) = G(F(x ₁₁ ,, x _n1 ),, F(x _1n ,, x _nn )), forn 1. Taylor has observed in [2] thatMV also satisfies some other hyperidentities, which are not consequences of the medial ones. In [4] the author introduced a countably infinite family of binary hyperidentities called transposition hyperidentities, which are natural generalizations of then = 2 medial hyperidentity. It was shown that this family is irredundant, and that no finite basis is possible for theMV hyperidentities with one binary operation symbol.In this paper, we generalize the concept of a transposition hyperidentity, and extend it to cover arbitrary arityn 2. We show that theMV hyperidentities with onen-ary operation symbol have no finite basis, but do have a countably infinite basis consisting of these transposition hyperidentities.Research supported by NSERC of Canada.     

Classification of reflexible regular embeddings and self-Petrie dual regular embeddings of complete bipartite graphs

In this paper, we classify the reflexible regular orientable embeddings and the self-Petrie dual regular orientable embeddings of complete bipartite graphs. The classification shows that for any natural number n, say (p₁,p₂,…,p_k are distinct odd primes and a_i>0 for each i?1), there are t distinct reflexible regular embeddings of the complete bipartite graph K_n,n up to isomorphism, where t=1 if a=0, t=2^k if a=1, t=2^k+1 if a=2, and t=3·2^k+1 if a?3. And, there are s distinct self-Petrie dual regular embeddings of K_n,n up to isomorphism, where s=1 if a=0, s=2^k if a=1, s=2^k+1 if a=2, and s=2^k+2 if a?3.     

A Lagrange multiplier rule with small convex-valued subdifferentials for nonsmooth problems of mathematical programming involving equality and nonfunctional constraints

It is shown that a Lagrange multiplier rule involving the Michel-Penot subdifferentials is valid for the problem: minimizef ₀(x) subject tof _i (x) 0,i = 1, ,m;f _i (x) = 0,i = m + 1,,n;x Q where all functionsf are Lipschitz continuous andQ is a closed convex set. The proof is based on the theory of fans.     

Facets of the clique partitioning polytope

A subsetA of the edge set of a graphG = (V, E) is called a clique partitioning ofG is there is a partition of the node setV into disjoint setsW ¹,,W ^k such that eachW _i induces a clique, i.e., a complete (but not necessarily maximal) subgraph ofG, and such thatA = _i=1 ^k 1{uv|u, v W _i ,u v}. Given weightsw ^e for alle E, the clique partitioning problem is to find a clique partitioningA ofG such that _eA w _e is as small as possible. This problem—known to be-hard, see Wakabayashi (1986)—comes up, for instance, in data analysis, and here, the underlying graphG is typically a complete graph. In this paper we study the clique partitioning polytope of the complete graphK _n , i.e., is the convex hull of the incidence vectors of the clique partitionings ofK _n . We show that triangles, 2-chorded odd cycles, 2-chorded even wheels and other subgraphs ofK _n induce facets of. The theoretical results described here have been used to design an (empirically) efficient cutting plane algorithm with which large (real-world) instances of the clique partitioning problem could be solved. These computational results can be found in Grötschel and Wakabayashi (1989).     

Properties of balanced and perfect matrices

In this paper we define wheel matrices and characterize some properties of matrices that are perfect but not balanced. A consequence of our results is that if a matrixA is perfect then we can construct a polynomial number of submatricesA _I,,A _n ofA such thatA is balanced if and only if all the submatricesA ₁,,A _n ofA are perfect. This implies that if the problem of testing perfection is polynomially solvable, then so is the problem of testing balancedness.Partial support under NSF Grants DMS-8606188, ECS-8800281 and DDM-8800281.