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.     

Convergence of probabilities for the second order monadic properties of a random mapping

We prove that the probability of each second order monadic property of a random mapping u_n converges as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 277–295, 1997     

A characterization of the identity function with equation f(p+q+r)=f(p)+f(q)+f(r)

Let f(n) be a multiplicative function such that there exists a prime p ₀ at which f does not vanish. In this paper, we prove that if f satisfies the equation f(p+q+r)=f(p)+f(q)+f(r) for all primes p, q and r, then f(n)=n for all integers n≥1.     

The length of random subsets of Boolean lattices

We form the random poset 𝒫(n, p) by including each subset of [n]={1,…,n} with probability p and ordering the subsets by inclusion. We investigate the length of the longest chain contained in 𝒫(n, p). For p≥e/n we obtain the limit distribution of this random variable. For smaller p we give thresholds for the existence of chains which imply that almost surely the length of 𝒫(n, p) is asymptotically n(log n−log log 1/p)/log 1/p. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 177–194, 2000     

The distribution of the root degree of a random permutation

Given a permutation ω of {1, …, n}, let R(ω) be the root degree of ω, i.e. the smallest (prime) integer r such that there is a permutation σ with ω = σ ^r . We show that, for ω chosen uniformly at random, R(ω) = (lnlnn − 3lnlnln n + O ^p (1))⁻¹ lnn, and find the limiting distribution of the remainder term. Research supported in part by NSF grants CCR-0225610, DMS-0505550 and ARO grant W911NF-06-1-0076. Research supported by NSF grant DMS-0406024.     

Linear Bounds of Degrees of Alternating Quotients of the (3, q,r) Triangle Groups

Abstract

In Everitt [Everitt, B. J. (2000). Alternating quotients of Fuchsian groups. J. Algebra 223: 457–476], it was shown, in particular, that each Fuchsian triangle group Δ(p, q, r) has among its homomorphic images all but finitely many of the alternating groups. Treating p, q as fixed, the methods of Everitt (2000) give a quadratic function N(r) of r such that A _n is an image of Δ(p, q, r) for every integer n ≥ N(r). We conjecture that there is a linear function of r with this property. In this paper, we will show that the conjecture holds for the Fuchsian triangle groups Δ(3, q, r).     

Perfect fractional matchings in random hypergraphs

Given an r-uniform hypergraph H = (V, E) on |V| = n vertices, a real-valued function f:E→R⁺ is called a perfect fractional matching if Σ_vϵe f(e) ≤ 1 for all vϵV and Σ_eϵE f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n→ infinity, at the very moment t₀ when the last isolated vertex disappears, the hypergraph H_t0 has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p(n) = (ln n + w(n))/ , where w(n) is any function tending to infinity with n, then with probability tending to 1 a random r-uniform hypergraph on n vertices with edge probability p has a perfect fractional matching. Similar results hold also for random r-partite hypergraphs. © 1996 John Wiley & Sons, Inc.     

The asymptotic distribution of long cycles in random regular graphs

The asymptotic distribution of the number of cycles of length l in a random r‐regular graph is determined. The length of the cycles is defined as a function of the number of vertices n, thus l=l(n), and the length satisfies l(n)→∞ as n→∞. The limiting distribution turns out to depend on whether l(n)/n→0 or l(n)/n→q, 0<q<1 as n→∞. In the first case the limit distribution is a weighted sum of Poisson variables while in the other case the limit distribution is similar to the limit distribution of Hamiltonian cycles in a random r‐regular graph. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15: 43–92, 1999     

The cycle structure of two rows in a random Latin square

Let L be chosen uniformly at random from among the latin squares of order n ≥ 4 and let r,s be arbitrary distinct rows of L. We study the distribution of σ_r,s, the permutation of the symbols of L which maps r to s. We show that for any constant c > 0, the following events hold with probability 1 ‐ o(1) as n → ∞: (i) σ_r,s has more than (log n)^1?c cycles, (ii) σ_r,s has fewer than 9 cycles, (iii) L has fewer than n^5/2 intercalates (latin subsquares of order 2). We also show that the probability that σ_r,s is an even permutation lies in an interval and the probability that it has a single cycle lies in [2n^‐2,2n^‐2/3]. Indeed, we show that almost all derangements have similar probability (within a factor of n^3/2) of occurring as σ_r,s as they do if chosen uniformly at random from among all derangements of {1,2,…,n}. We conjecture that σ_r,s shares the asymptotic distribution of a random derangement. Finally, we give computational data on the cycle structure of latin squares of orders n ≤ 11. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

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     

Modular Lie powers and the Solomon descent algebra

Let V be an r-dimensional vector space over an infinite field F of prime characteristic p, and let L_n(V) denote the nth homogeneous component of the free Lie algebra on V. We study the structure of L_n(V) as a module for the general linear group GL_r(F) when n=pk and k is not divisible by p and where r≥n. Our main result is an explicit 1-1 correspondence, multiplicity-preserving, between the indecomposable direct summands of L_k(V) and the indecomposable direct summands of L_n(V) which are not isomorphic to direct summands of V^⊗n. Our approach uses idempotents of the Solomon descent algebras, and in addition a correspondence theorem for permutation modules of symmetric groups. Second author supported by Deutsche Forschungsgemeinschaft (DFG-Scho 799).     

On triangle‐free random graphs

We show that for every k≥1 and δ>0 there exists a constant c>0 such that, with probability tending to 1 as n→∞, a graph chosen uniformly at random among all triangle‐free graphs with n vertices and M≥cn^3/2 edges can be made bipartite by deleting ⌊δM⌋ edges. As an immediate consequence of this fact we infer that if M/n^3/2→∞ but M/n²→0, then the probability that a random graph G(n, M) contains no triangles decreases as 2^−(1+o(1))M. We also discuss possible generalizations of the above results. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16: 260–276, 2000     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Topology of Random 2-Complexes

We study the Linial–Meshulam model of random two-dimensional simplicial complexes. One of our main results states that for p≪n ⁻¹ a random 2-complex Y collapses simplicially to a graph and, in particular, the fundamental group π ₁(Y) is free and H ₂(Y)=0, asymptotically almost surely. Our other main result gives a precise threshold for collapsibility of a random 2-complex to a graph in a prescribed number of steps. We also prove that, if the probability parameter p satisfies p≫n ^−1/2+ϵ , where ϵ>0, then an arbitrary finite two-dimensional simplicial complex admits a topological embedding into a random 2-complex, with probability tending to one as n→∞. We also establish several related results; for example, we show that for p<c/n with c<3 the fundamental group of a random 2-complex contains a non-abelian free subgroup. Our method is based on exploiting explicit thresholds (established in the paper) for the existence of simplicial embeddings and immersions of 2-complexes into a random 2-complex.     

The degree sequence of a random graph. I. The models

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and ½m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X₁,…,X_n) | ∑ X_i=m}, where X₁,…,X_n are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p=p(n), the distribution of the degree sequence can be approximated by {(X₁,…,X>_n) | ∑ X_i is even}, where X₁,…,X_n are independent random variables each having the distribution Binom (n−1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n^−k for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t=t(n) as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 97–117 (1997)     

On a class of transitive permutation groups of prime degreep=4n+1

SupposeG is a nonsolvable transitive permutation group of prime degreep, such that |N _G v(P)|=p(p−1) for some Sylowp-subgroupP ofG. Letq be a generator of the subgroup ofN _G (P), fixing one letter (it is easy to show that this subgroup is cyclic). Assume thatG contains an elementj such thatj ⁻¹ qj=q ^(p+1)/2. We shall prove that for almost all primesp of the formp=4n+1, a group that satisfies the above conditions must be the symmetric group on a set withp elements.     

The structure of the set of satisfying assignments for a random <Emphasis Type="Italic">k</Emphasis>-CNF

Let F _k (n, m) be a random k-CNF obtained by a random, equiprobable, and independent choice of m brackets from among all k-literal brackets on n variables. We investigate the structure of the set of satisfying assignments of F _k (n, m). A method is proposed for finding r(k, s)such that the probability of presence of ns-dimensional faces (0 < s < 1) in the set of satisfying assignments of the formula F _k s(n, r(k, s)n) goes to 1 as n goes to infinity. We prove the existence of a sequential threshold for the property of having ns-dimensional faces (0 < s < 1). In other words, there exists a sequence r _n (k, s) such that the probability of having an ns-dimensional face in the set of satisfying assignments of the formula F _k (n, r _n (k, s)(1 + d)n) goes to 0 for all d > 0 and to 1 for all d < 0. __________ Translated from Prikladnaya Matematika i Informatika, No. 26, pp. 61–95, 2007.     

Sur la singularité des produits de Riesz et des mesures spectrales associées à la somme des chiffres

Using a property of generalized characters, we first prove that two Riesz products with constant coefficients and distinct Fourier spectra are mutually singular. IfS _r (n) denotes the sum of digits in ther-adic representation of the integern, the same technique allows us to establish the mutual singularity of the spectral measures of the sequences: α(n)=exp[2iπaS _p (n)],β(n)=exp[2iπbS _q (n)], for every pair of integersp≠q, a, b being real numbers such thata(p−1)∉ {tiZ} andb(q−1)∉Z. This result has been proved by T. Kamae whenp andq are two relatively prime integers.      

On the number of queries necessary to identify a permutation

Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log₂n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log₂n).