Correlations for paths in random orientations of G(n,p) and G(n,m)

We study random graphs, both G( n,p) and G( n,m), with random orientations on the edges. For three fixed distinct vertices s,a,b we study the correlation, in the combine probability space, of the events $\{a\to s\}$ and $\{s\to b\}$ . For G(n,p), we prove that there is a $pc = 1/2$ such that for a fixed $p < pc$ the correlation is negative for large enough n and for $p > pc$ the correlation is positive for large enough n. We conjecture that for a fixed $n \ge 27$ the correlation changes sign three times for three critical values of p. For G(n,m) it is similarly proved that, with $p=m/({{n}\atop {2}})$ , there is a critical pc that is the solution to a certain equation and approximately equal to 0.7993. A lemma, which computes the probability of non existence of any $\ell$ directed edges in G(n,m), is thought to be of independent interest. We present exact recursions to compute \input amssym $\Bbb{P}(a\to s)$ and \input amssym $\Bbb{P}(a\to s, s\to b)$ . We also briefly discuss the corresponding question in the quenched version of the problem. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Quantum random walk on the dual of SU (n)

Summary We study a quantum random walk onA(SU(n)), the von Neumann algebra of SU(n), obtained by tensoring the basic representation of SU(n). Two classical Markov chains are derived from this quantum random walk, by restriction to commutative subalgebras ofA(SU(n)), and the main result of the paper states that these two Markov chains are related by means of Doob'sh-processes.     

On the asymptotic behavior of the independence number of a random (n,n)-tree

An (r, s)-tree is a connected, acyclic, bipartite graph withr light ands dark vertices. Uniform probability is assigned to the space,(r, s), of (r, s)-trees. In this paper, we apply the probabilistic method to determine bounds for the vertex and the edge independence numbers for almost all (n, n)-trees in(n,n). Consequently, we find that for almost all (n, n)-trees the percentage of dark vertices in a maximum matching is at least 72%.First author supported in part by grants from TGRC-KOSEF and BSRI 1409.     

A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time

We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n ² m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.This research was supported in part by NSF Grants DMS 85-12277 and CDR 84-21402 and ONR Contract N00014-87-K0214.     

Patterns in random binary search trees

In a randomly grown binary search tree (BST) of size n, any fixed pattern occurs with a frequency that is on average proportional to n. Deviations from the average case are highly unlikely and well quantified by a Gaussian law. Trees with forbidden patterns occur with an exponentially small probability that is characterized in terms of Bessel functions. The results obtained extend to BSTs a type of property otherwise known for strings and combinatorial tree models. They apply to paged trees or to quicksort with halting on short subfiles. As a consequence, various pointer saving strategies for maintaining trees obeying the random BST model can be precisely quantified. The methods used are based on analytic models, especially bivariate generating function subjected to singularity perturbation asymptotics. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 : 223–244, 1997     

On Pairs of Commuting Involutions in Sym(n) and Alt(n)

The number of pairs of commuting involutions in Sym(n) and Alt(n) is determined up to isomorphism. It is also proven that, up to isomorphism and duality, there are exactly two abstract regular polyhedra on which the group Sym(6) acts as a regular automorphism group.     

函数Sp(n2)与Sp(n)的关系

对于任意正整数n,设幂p的原数函数Sp(n)定义为Sp(n)=min{m:pn|m!},其中p为素数.本文目的是运用初等方法研究函数Sp(n2)与Sp(n)之间的关系,并得到一个有趣的恒等式.     

The odd primary homology of SU(n), Sp(n) and Spin(n)-gauge groups

For an odd prime $p$, we calculate the mod-$p$ homology of $SU\left(n\right)$-gauge groups over a simply-connected, closed 4-manifold for all $n\ge 2$. Similar calculations are obtained for the structure groups $Sp\left(n\right)$ when $n\ge 1$ and $Spin\left(n\right)$ for $n\ge 3$ (except for some cases when $n$ is even and $p=3$).     

On Minimal Generating Sets of E(D n ), A(D n) and I(D n ) with Even n

Let Dn be the dihedral group of order 2n. Denote by E(Dn) (resp. A(Dn), I(Dn)) the distributively generated nearring generated by the set of all endomorphisms (resp. automorphisms, inner automorphisms). In this paper, we determine for each one of the above three nearrings a minimal (additive) generating set. For E(Dn), this set contains the identity mapping and four other endomorphisms; for A(Dn), the identity mapping, one outer automorphism and one inner automorphisms; and for I(Dn), the identity mapping and two inner automorphisms.     

C (n)-cardinals

For each natural number n, let C ⁽ⁿ⁾ be the closed and unbounded proper class of ordinals α such that V _α is a Σ _n elementary substructure of V. We say that κ is a C ⁽ⁿ⁾ -cardinal if it is the critical point of an elementary embedding j : V → M, M transitive, with j(κ) in C ⁽ⁿ⁾. By analyzing the notion of C ⁽ⁿ⁾-cardinal at various levels of the usual hierarchy of large cardinal principles we show that, starting at the level of superstrong cardinals and up to the level of rank-into-rank embeddings, C ⁽ⁿ⁾-cardinals form a much finer hierarchy. The naturalness of the notion of C ⁽ⁿ⁾-cardinal is exemplified by showing that the existence of C ⁽ⁿ⁾-extendible cardinals is equivalent to simple reflection principles for classes of structures, which generalize the notions of supercompact and extendible cardinals. Moreover, building on results of Bagaria et?al. (2010), we give new characterizations of Vopeňka’s Principle in terms of C ⁽ⁿ⁾-extendible cardinals.     

On representations by determinants of P(n) and Pm(n)

P(n) and P_m(n) denote the number of (unordered) partitions of n and the number of partitions of n into m parts, respectively. For P(n), there exists a recursion formula which is shown in Eq. (3) and a complicated formula indicated in J. L. Doob et al. (“Hans Rademacher: Topic Analytic Number Theory,” Springer-Verlag, Berlin/New York, 1973, p. 275, which is accompanied with the error term. For P_m(n), there is no general rule known covering all m (Doob et al., p. 222). In this article, P(n) and P_m(n) are represented by determinants. Note that the determinant of the former agrees with the above recursion formula and the finite product of binomials analogous to Euler identity, which is indicated in (5), leads to the representation of the latter. The computation of determinant is a little troublesome, but it is very important that the representations themselves of the number of partitions are simple, if we make use of the determinant.     

Matchings in superpositions of (n,n)-bipartite trees

Pick two trees from among all “bipartite trees” with a fixed (n, n) two-coloring. We estimate the probability that the superposition of these two trees contains a perfect matching. As n →∞, this probability approaches 1. © 1994 John Wiley & Sons, Inc.