A family of identities related to zero-sum and team games

We list and prove a family of binomial identities by calculating in two ways the probabilities of approximate saddlepoints occurring in random m×n matrices. The identities are easily seen to be equivalent to the evaluation of a family of Gauss ₂F₁ polynomials according to a formula of Vandermonde. We also consider some implications concerning the number of approximate pure strategy Nash equilibria we can expect in large matrix zero-sum and team games.     

Additive Maps Preserving Moore–Penrose Inverses of Matrices on Symmetric Matrix Spaces

Suppose F is a field of characteristic not 2. Let M_n F and S_n F be the n × n full matrix space and symmetric matrix space over F, respectively. All additive maps from S_n F to S_n F (respectively, M_n F) preserving Moore–Penrose inverses of matrices are characterized. We first characterize all additive Moore–Penrose inverse preserving maps from S_n F to M_n F, and thereby, all additive Moore–Penrose inverse preserving maps from S_n F to itself are characterized by restricting the range of these additive maps into the symmetric matrix space.     

Stochastic comparisons of order statistics from heterogeneous populations, with applications in reliability

The basic result of the paper states: Let F₁, …, F_n, F₁^′,…, F_n^′ have proportional hazard functions with λ₁ ,…, λ_n , λ₁^′ ,…, λ_n^′ as the constants of proportionality. Let X₍₁₎ ≤ … ≤ X_(n) (X₍₁₎^′ ≤ … ≤ X_(n)^′) be the order statistics in a sample of size n from the heterogeneous populations {F₁ ,…, F_n}({F₁^′ ,…, F_n^′}). Then (λ₁ ,…, λ_n) majorizes (λ₁^′ ,…, λ_n^′) implies that (X₍₁₎ ,…, X_(n)) is stochastically larger than (X₍₁₎^′ ,…, X_(n)^′). Earlier results stochastically comparing individual order statistics are shown to be special cases. Applications of the main result are made in the study of the robustness of standard estimates of the failure rate of the exponential distribution, when observations actually come from a set of heterogeneous exponential distributions. Further applications are made to the comparisons of linear combinations of Weibull random variables and of binomial random variables.     

Rank-one nonincreasing mappings on triangular matrices and some related preserver problems

Let T_n (F) be the algebra of all n×n upper triangular matrices over an arbitrary field F. We first characterize those rank-one nonincreasing mappings ψ: T_n (F)→T_m (F)n?m such that ψ(I_n ) is of rank n. We next deduce from this result certain types of singular rank-one r-potent preservers and nonzero r-potent preservers on T_n (F). Characterizations of certain classes of homomorphisms and semi-homomorphisms on T_n (F) are also given.     

Solvable Subgroups of Out(F n ) are Virtually Abelian

Let F _n be the free group of rank n, let Aut(F _n ) be its automorphism group and let Out(F _n ) be its outer automorphism group. We show that every solvable subgroup of Out(F _n ) has a finite index subgroup that is finitely generated and free Abelian. We also show that every Abelian subgroup of Out(F _n ) has a finite index subgroup that lifts to Aut(F _n ).     

Commuting Graphs of Matrix Algebras

The commuting graph of a ring R, denoted by Γ(R), is a graph whose vertices are all noncentral elements of R, and two distinct vertices x and y are adjacent if and only if xy = yx. The commuting graph of a group G, denoted by Γ(G), is similarly defined. In this article we investigate some graph-theoretic properties of Γ(M _n (F)), where F is a field and n ≥ 2. Also we study the commuting graphs of some classical groups such as GL _n (F) and SL _n (F). We show that Γ(M _n (F)) is a connected graph if and only if every field extension of F of degree n contains a proper intermediate field. We prove that apart from finitely many fields, a similar result is true for Γ(GL _n (F)) and Γ(SL _n (F)). Also we show that for two fields F and E and integers n, m ≥ 2, if Γ(M _n (F))?Γ(M _m (E)), then n = m and |F|=|E|.     

Compound Binomial Approximations

We consider the approximation of the convolution product of not necessarily identical probability distributions q _j I + p _j F, (j=1,...,n), where, for all j, p _j =1−q _j ∈[0, 1], I is the Dirac measure at point zero, and F is a probability distribution on the real line. As an approximation, we use a compound binomial distribution, which is defined in a one-parametric way: the number of trials remains the same but the p _j are replaced with their mean or, more generally, with an arbitrary success probability p. We also consider approximations by finite signed measures derived from an expansion based on Krawtchouk polynomials. Bounds for the approximation error in different metrics are presented. If F is a symmetric distribution about zero or a suitably shifted distribution, the bounds have a better order than in the case of a general F. Asymptotic sharp bounds are given in the case, when F is symmetric and concentrated on two points. An erratum to this article can be found at     

Linear Representations of the Automorphism Group of a Free Group

Let F _n be the free group on n ≥ 2 elements and Aut(F _n ) its group of automorphisms. In this paper we present a rich collection of linear representations of Aut(F _n ) arising through the action of finite-index subgroups of it on relation modules of finite quotient groups of F _n . We show (under certain conditions) that the images of our representations are arithmetic groups. Received: November 2006, Accepted: March 2007     

Forests of label-increasing trees

Label-increasing trees are fully labeled rooted trees with the restriction that the labels are in increasing order on every path from the root; the best known example is the binary case—no tree with more than two branches at the root, or internal vertices of degree greater than three—extensively examined by Foata and Schutzenberger in A Survey of Combinatorial Theory. The forests without branching restrictions are enumerated by number of trees by F_n(x) = x(x + 1)…(x + n ? 1), n >1 (F₀(x) = 1), whose equivalent: F_n(x) = Y_n(xT₁,…, xT_n), F_n(1)= T_{n + 1} = n!, is readily adapted to branching restriction.     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

Commensurations of Out(F<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>)

Let Out(F _n ) denote the outer automorphism group of the free group F _n with n>3. We prove that for any finite index subgroup Γ<Out(F _n ), the group Aut(Γ) is isomorphic to the normalizer of Γ in Out(F _n ). We prove that Γ is co-Hopfian: every injective homomorphism Γ→Γ is surjective. Finally, we prove that the abstract commensurator Comm(Out(F _n )) is isomorphic to Out(F _n ).     

Symmetric Hamilton cycle decompositions of complete graphs minus a 1‐factor

Let n≥2 be an integer. The complete graph K_n with a 1‐factor F removed has a decomposition into Hamilton cycles if and only if n is even. We show that K_n−F has a decomposition into Hamilton cycles which are symmetric with respect to the 1‐factor F if and only if n≡2, 4 mod 8. We also show that the complete bipartite graph K_{n, n} has a symmetric Hamilton cycle decomposition if and only if n is even, and that if F is a 1‐factor of K_{n, n}, then K_{n, n}−F has a symmetric Hamilton cycle decomposition if and only if n is odd. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:1‐15, 2010     

Linear operators preserving unitarily invariant norms of matrices

Let F _{m × n} be the set of all m × n matrices over the field F = C or R Denote by U_n (F) the group of all n × n unitary or orthogonal matrices according as F = C or F-R. A norm N() on F m ×n, is unitarily invariant if N(UAV) = N(A): for all A ∈ F _m×n U ∈ U _m (F). and V ∈ U_n (F). We characterize those linear operators T F _{m × n} → F _{m × n} which satisfy N (T(A)) = N(A)for all A ∈ F _{m × n}

for a given unitarily invariant norm N(). It is shown that the problem is equivalent to characterizing those operators which preserve certain subsets in F _{m × n} To develop the theory we prove some results concerning unitary operators on F _{m × n} which are of independent interest.     

All Binomial-Type Painlevé Equations of the Second Order and Degree Three or Higher

In this paper we construct all rational Painlevé-type differential equations which take the binomial form, (d²y/dx²)ⁿ = F(x,y,dy/dx), where n ≥ 3, the case n = 2 having previously been treated in Cosgrove and Scoufis [1]. While F is assumed to be rational in the complex variables y and y′ and locally analytic in x, it is shown that the Painlevé property together with the absence of intermediate powers of y″ forces F to be a polynomial in y and y′. In addition to the six classes of second-degree equations found in the aforementioned paper, we find nine classes of higher-degree binomial Painlevé equations, denoted BP-VII,..., BP-XV, of which the first seven are new. Two of these equations are of the third degree, two of the fourth degree, three of the sixth degree, and two of arbitrary degree n. All equations are solved in terms of the first, second or fourth Painlevé transcendents, elliptic functions, or quadratures. In the appendices, we discuss certain closely related classes of second-order nth equations (not necessarily of Painlevé type) which can also be solved in terms of Painlevé transcendents or elliptic functions.     

Maps preserving square-zero matrices on the algebra consisting of all upper triangular matrices

Let F be a field, T _n (F) (respectively, N _n (F)) the matrix algebra consisting of all n × n upper triangular matrices (respectively, strictly upper triangular matrices) over F. A ∈ T _n (F) is said to be square zero if A ² = 0. In this article, we firstly characterize non-singular linear maps on N _n (F) preserving square-zero matrices in both directions, then by using it we determine non-singular linear maps on T _n (F) preserving square-zero matrices in both directions.     

Size ramsey numbers of stars versus 4‐chromatic graphs

We investigate the asymptotics of the size Ramsey number î(K_1,nF), where K_1,n is the n‐star and F is a fixed graph. The author 11 has recently proved that r?(K_1,n,F)=(1+o(1))n² for any F with chromatic number χ(F)=3. Here we show that r?(K_1,n,F)≤ n²+o(n²), if χ (F) ≥ 4 and conjecture that this is sharp. We prove the case χ(F)=4 of the conjecture, that is, that r?(K_1,n,F)=(4+o(1))n² for any 4‐chromatic graph F. Also, some general lower bounds are obtained. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 220–233, 2003     

Additive Maps on Matrix Algebras Preserving Invertibility or Singularity

We characterize the additive singularity preserving almost surjective maps on Mn （F）, the algebra of all n×n matrices over a field F with char F=0. We also describe additive invertibility preserving surjective maps on Mn （F） and give examples showing that all the assunlptions in these two theorems are indispensable.     

Approximation Numbers of Identity Operators between Symmetric Sequence Spaces

We prove asymptotic formulas for the behavior of approximation quantities of identity operators between symmetric sequence spaces. These formulas extend recent results of Defant, Masty o, and Michels for identities l_pⁿF_n with an n-dimensional symmetric normed space F_n with p-concavity conditions on F_n and 1p2. We consider the general case of identities E_nF_n with weak assumptions on the asymptotic behavior of the fundamental sequences of the n-dimensional symmetric spaces E_n and F_n. We give applications to Lorentz and Orlicz sequence spaces, again considerably generalizing results of Pietsch, Defant, Masty o, and Michels.     

Class groups and Brauer groups

LetF be a global field,n a positive integer not divisible by the characteristic ofF. Then there exists a finite extensionE ofF whose class group has a cyclic direct summand of ordern. This theorem, in a slightly stronger form, is applied to determine completely, on the basis of the work of Fein and Schacher, the structure of the Brauer group Br(F()) of the rational function fieldF(t). As a consequence of this, an additional theorem of the above authors, together with a note at the end of the paper, imply that Br(F(t)) ≊ Br(F(t ₁, ···,t _n)), wheret ₁, ···,t _n are algebraically independent overF.