Ramified partition algebras

For each natural number n, poset T, and |T|–tuple of scalars Q, we introduce the ramified partition algebra P _n ^(T) (Q), which is a physically motivated and natural generalization of the partition algebra [24, 25] (the partition algebra coincides with case |T|=1). For fixed n and T these algebras, like the partition algebra, have a basis independent of Q. We investigate their representation theory in case ${{T=\underline{{2}}:=({1,2},\leq)}}$. We show that ${{P_n^{(\underline{{2}})$ (Q) is quasi–hereditary over field k when Q ₁ Q ₂ is invertible in k and k is such that certain finite group algebras over k are semisimple (e.g. when k is algebraically closed, characteristic zero). Under these conditions we determine an index set for simple modules of ${{P_n^{(\underline{{2}})$ (Q), and construct standard modules with this index set. We show that there are unboundedly many choices of Q such that ${{P_n^{(\underline{{2}})$ (Q) is not semisimple for sufficiently large n, but that it is generically semisimple for all n. We construct tensor space representations of certain non–semisimple specializations of ${{P_n^{(\underline{{2}})$ (Q), and show how to use these to build clock model transfer matrices [24] in arbitrary physical dimensions. Sadly Ahmed died before this work was completed. His memory lives on.     

两类惯量惟一的对称符号模式

§ 1　 IntroductionA sign pattern(matrix) A is a matrix whose entries are from the set{ +,-,0 } .De-note the setofall n× n sign patterns by Qn.Associated with each A=(aij)∈ Qnis a class ofreal matrices,called the qualitative class of A,defined byQ(A) ={ B =(bij)∈ Mn(R) |sign(bij) =aijfor all i and j} .　　 For a symmetric sign pattern A∈ Qn,by G(A) we mean the undirected graph of A,with vertex set { 1 ,...,n} and (i,j) is an edge if and only if aij≠ 0 .A sign pattern A∈ Qnis a do…     

Generating Random Vectors in (ℤ/<Emphasis Type="Italic">p</Emphasis>ℤ)<Superscript><Emphasis Type="Italic">d</Emphasis></Superscript> via an Affine Random Process

This paper considers some random processes of the form X _n+1=T X _n +B _n (mod p) where B _n and X _n are random variables over (ℤ/pℤ) ^d and T is a fixed d×d integer matrix which is invertible over the complex numbers. For a particular distribution for B _n , this paper improves results of Asci to show that if T has no complex eigenvalues of length 1, then for integers p relatively prime to det (T), order (log p)² steps suffice to make X _n close to uniformly distributed where X ₀ is the zero vector. This paper also shows that if T has a complex eigenvalue which is a root of unity, then order p ^b steps are needed for X _n to get close to uniformly distributed for some positive value b≤2 which may depend on T and X ₀ is the zero vector.     

On the basis property of root vectors of a perturbed self-adjoint operator

We study perturbations of a self-adjoint operator T with discrete spectrum such that the number of its points on any unit-length interval of the real axis is uniformly bounded. We prove that if ‖Bϕ _n ‖ ≤ const, where ϕ _n is an orthonormal system of eigenvectors of the operator T, then the system of root vectors of the perturbed operator T + B forms a basis with parentheses. We also prove that the eigenvalue-counting functions of T and T + B satisfy the relation |n(r, T) − n(r, T + B)| ≤ const.     

Properties of Random Triangulations and Trees

Let T _n denote the set of triangulations of a convex polygon K with n sides. We study functions that measure very natural ``geometric' features of a triangulation τ∈ T _n , for example, Δ _n (τ) which counts the maximal number of diagonals in τ incident to a single vertex of K . It is familiar that T _n is bijectively equivalent to B _n , the set of rooted binary trees with n-2 internal nodes, and also to P _n , the set of nonnegative lattice paths that start at 0 , make 2n-4 steps X _i of size 1, and end at X ₁ + . . . +X _2n-4 =0 . Δ _n and the other functions translate into interesting properties of trees in B _n , and paths in P _n , that seem not to have been studied before. We treat these functions as random variables under the uniform probability on T _n and can describe their behavior quite precisely. A main result is that Δ _n is very close to logn (all logs are base 2 ). Finally we describe efficient algorithms to generate triangulations in T _n uniformly, and in certain interesting subsets. Received August 18, 1997, and in revised form November 5, 1997.     

Formule de Rice en dimension d

Summary Let {x(t): tR ^d} a stochastic process with parameter in R ^d, and u a fixed real number. Denote by C _u, A_u, B_u respectively the random sets {t: x(t)= u}, {t: x(t)}, {t: x(t)>u}. The paper contains two main results for processes with continuously differentiable paths plus some additional requirements: First, a formula for the expectation of Q _T(A_u) and Q _T(B_u), where for a given bounded open set T in R ^d, Q_T(B) denotes the perimeter of B relative to T and second, sufficient conditions on the process, so that it does not have local extrema on the barrier u. The second result can also be used to interpret the first in terms of C _u.     

Stable n-pointed trees of projective lines

Stable n-pointed trees arise in a natural way if one tries to find moduli for totally degenerate curves: Let C be a totally degenerate stable curve of genus g ≥ 2 over a field k. This means that C is a connected projective curve of arithmetic genus g satisfyingo

1. (a) every irreducible component of C is a rational curve over κ.
2. (b) every singular point of C is a κ-rational ordinary double point.
3. (c) every nonsingular component L of C meets C−L in at least three points. It is always possible to find g singular points P₁,..., P_g on C such that the blow up C of C at P₁,..., P_g is a connected projective curve with the following properties:o
   1. (i) every irreducible component of C is isomorphic to P_k¹
   2. (ii) the components of C intersect in ordinary κ-rational double points
   3. (iii) the intersection graph of C is a tree.

The morphism φ : C → C is an isomorphism outside 2g regular points Q₁, Q₁′, Q_g, Q_g′ and identifies Q_i with Q_j′. is uniquely determined by the g pairs of regular κ-rational points (Q_i, Q_i′). A curve C satisfying (i)-(iii) together with n κ-rational regular points on it is called a n-pointed tree of projective lines. C is stable if on every component there are at least three points which are either singular or marked. The object of this paper is the classification of stable n-pointed trees. We prove in particular the existence of a fine moduli space B_n of stable n-pointed trees. The discussion above shows that there is a surjective map πB_2g → D_g of B_2g onto the closed subscheme D_g of the coarse moduli scheme M_g of stable curves of genus g corresponding to the totally degenerate curves. By the universal property of M_g, π is a (finite) morphism. π factors through B_2g = B_2g mod the action of the group of pair preserving permutations of 2g elements (a group of order 2^gg, isomorphic to a wreath product of S_g and ℤ/2ℤThe induced morphism π: B_2g → D_g is an isomorphism on the open subscheme of irreducible curves in D_g, but in general there may be nonequivalent choices of g singular points on a totally degenerated curve for the above construction, so π has nontrivial fibres. In particular, π is not the quotient map for a group action on B_2g. This leads to the idea of constructing a Teichmüller space for totally degenerate curves whose irreducible components are isomorphic to B_2g and on which a discontinuous group acts such that the quotient is precisely D_g; π will then be the restriction of this quotient map to a single irreducible component. This theory will be developped in a subsequent paper.In this paper we only consider stable n-pointed trees and their moduli theory. In 4 1 we introduce the abstract cross ratio of four points (not necessarily on the same projective line) and show that for a field κ the κ-valued points in the projective variety B_n of cross ratios are in 1 − 1 correspondence with the isomorphy classes of stable n-pointed trees of projective lines over κ. We also describe the structure of the subvarieties B(T, ψ) of stable n-pointed trees with fixed combinatorial type.We generalize our notion in 4 2 to stable n-pointed trees of projective lines over an arbitrary noetherian base scheme S and show how the cross ratios for the fibres fit together to morphisms on S. This section is closely related to [Kn], but it is more elementary since we deal with a special case.4 3 contains the main result of the paper: the canonical projection B_{n + 1} → B_n is the universal family of stable n-pointed trees. As a by-product of the proof we find that B_n is a smooth projective scheme of relative dimension 2n - 3 over ℤ. We also compare B_n to the fibre product B_n−1 × _Bn-2 B_{n − 1} and investigate the singularities of the latter.In 4 4 we prove that the Picard group of B_n is free of rank 2ⁿ⁻1−(n+1)−n(n−3)/2.We also give a method to compute the Betti numbers of the complex manifold B_n(ℂ).In 4 5 we compare B_n to the quotient Q_n: = ℙ_ssⁿ/PGL₂ of semi-stable points in ℙ₁ⁿ for the action of fractional linear transformations in every component. This orbit space has been studied in greater detail by several authors, see [GIT], [MS], [G]. It turns out that B_n is a blow-up of Q_n, and we describe the blow-up in several steps where at each stage the obtained space is interpreted as a solution to a certain moduli problem.     

A general RLC system with complex values

We study a semilinear second-order ordinary differential equation for a complex valued function Q which describes the evolution of a generalized RLC system over an interval [0,?T?]. We solve the Dirichlet and periodic problems under appropriate conditions. Moreover, we give conditions in order to ensure that any solution satisfying an initial condition Q(0)?=?Q ₀, Q′(0)=?I ₀ is defined over [0,?T?].     

Covering minimum spanning trees of random subgraphs

We consider the problem of finding a sparse set of edges containing the minimum spanning tree (MST) of a random subgraph of G with high probability. The two random models that we consider are subgraphs induced by a random subset of vertices, each vertex included independently with probability p, and subgraphs generated as a random subset of edges, each edge with probability p. Let n denote the number of vertices, choose p ∈ (0, 1) possibly depending on n, and let b = 1/(1 ? p). We show that in both random models, for any weighted graph G, there is a set of edges Q of cardinality O(n log_bn) that contains the minimum spanning tree of a random subgraph of G with high probability. This result is asymptotically optimal. As a consequence, we also give a bound of O(kn) on the size of the union of all minimum spanning trees of G with some k vertices (or edges) removed. More generally, we show a bound of O(n log_bn) on the size of a covering set in a matroid of rank n, which contains the minimum‐weight basis of a random subset with high probability. Also, we give a randomized algorithm that calls an MST subroutine only a polylogarithmic number of times and finds the covering set with high probability. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

The 2-circle and 2-disk problems on trees

Our purpose here is to consider on a homogeneous tree two Pompeiutype problems which classically have been studied on the plane and on other geometric manifolds. We obtain results which have remarkably the same flavor as classical theorems. Given a homogeneous tree, letd(x, y) be the distance between verticesx andy, and letf be a function on the vertices. For each vertexx and nonnegative integern let Σ _n f(x) be the sum Σ _{d(x, y)=n} f(y) and letB _n f(x)=Σ _{d(x, y)≦n} f(y). The purpose is to study to what extent Σ _n f andB _n f determinef. Since these operators are linear, this is really the study of their kernels. It is easy to find nonzero examples for which Σ _n f orB _n f vanish for one value ofn. What we do here is to study the problem for two values ofn, the 2-circle and the 2-disk problems (in the cases of Σ _n andB _n respectively). We show for which pairs of values there can exist non-zero examples and we classify these examples. We employ the combinatorial techniques useful for studying trees and free groups together with some number theory.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees

We study some properties of subtree-prune-and-regraft (SPR) operations on leaflabelled rooted binary trees in which internal vertices are totally ordered. Since biological events occur with certain time ordering, sometimes such totally-ordered trees must be used to avoid possible contradictions in representing evolutionary histories of biological sequences. Compared to the case of plain leaf-labelled rooted binary trees where internal vertices are only partially ordered, SPR operations on totally-ordered trees are more constrained and therefore more difficult to study. In this paper, we investigate the unit-neighbourhood U(T), defined as the set of totally-ordered trees one SPR operation away from a given totally-ordered tree T. We construct a recursion relation for | U(T) | and thereby arrive at an efficient method of determining | U(T) |. In contrast to the case of plain rooted trees, where the unit-neighbourhood size grows quadratically with respect to the number n of leaves, for totally-ordered trees | U(T) | grows like O(n³). For some special topology types, we are able to obtain simple closed-form formulae for | U(T) |. Using these results, we find a sharp upper bound on | U(T) | and conjecture a formula for a sharp lower bound. Lastly, we study the diameter of the space of totally-ordered trees measured using the induced SPR-metric. Received May 18, 2004     

Combinatorial interpretations for TG(1, −1)

Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and T_G(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for T_G(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove T_G(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show T_G(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd K_{n + 1}‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012     

On the existence of automorphisms with simple Lebesgue spectrum

It is shown that ifT is a measure preserving automorphism on a probability space (Ω,B, m) which admits a random variable X₀ with mean zero such that the stochastic sequence X₀ o T_n,n ε ℤ is orthonormal and spans L₀ ²(Ω,B,m), then for any integerk ≠ 0, the random variablesX o T^nk,n ε ℤ generateB modulom.     

Embeddings and Other Mappings of Rooted Trees Into Complete Trees

Let T ⁿ be the complete binary tree of height n, with root 1 _n as the maximum element. For T a tree, define and . We disprove a conjecture of Kubicki, Lehel and Morayne, which claims that for any fixed n and arbitrary rooted trees T ₁ T ₂. We show that A(n; T) is of the form where l is the number of leaves of T, and each q _j is a polynomial. We provide an algorithm for calculating the two leading terms of q _l for any tree T. We investigate the asymptotic behaviour of the ratio A(n; T)/C(n; T) and give examples of classes of pairs of trees T ₁, T ₂ where it is possible to compare A(n; T ₁)/C(n; T ₁) and A(n; T ₂)/C(n; T ₂). By calculating these ratios for a particular class of pairs of trees, we show that the conjecture fails for these trees, for all sufficiently large n. Kubicki, Lehel and Morayne have proved the conjecture when T ₁, T ₂ are restricted to being binary trees. We also look at embeddings into other complete trees, and we show how the result can be viewed as one of many possible correlation inequalities for embeddings of binary trees. We also show that if we consider strict order-preserving maps of T ₁, T ₂ into T ⁿ (rather than embeddings) then the corresponding correlation inequalities for these maps also generalise to arbitrary trees.     

On the approximation of entire functions by trigonometric polynomials

Let a set B have the following properties: if z ∈ B, then z ± 2π ∈ B and the intersection of B with the vertical strip 0 ≤ Re x ≤ π is a closed and bounded set. In this paper we study the approximation of a continuous on B and 2π-periodic function f(z) by trigonometric polynomials T _n (z). We establish the necessary and sufficient conditions for the function f(z) to be entire and specify a formula for calculating its order. In addition, we describe some metric properties of periodic sets in a plane.     

Everywhere H?lder continuity of the spatial gradient of weak solutions to nonlinear parabolic systems

We consider weak solutions to the parabolic system ∂u ⁱ∂t−D _α A _i ^α (∇u)=B _i(∇u) in (i=1,...,) (Q=Ω×(0,T), R ⁿ a domain), where the functionsB _i may have a quadratic growth. Under the assumptionsn≤2 and ∇u ɛL _loc ^4+δ (Q; R ^nN ) (δ>0) we prove that ∇u is locally H?lder continuous inQ.     

The Asymptotic Distribution of Singular-Values with Applications to Canonical Correlations and Correspondence Analysis

Let X_n, n = 1, 2, ... be a sequence of p × q random matrices, p ≥ q. Assume that for a fixed p × q matrix B and a sequence of constants b_n → ∞, the random matrix b_n(X_n − B) converges in distribution to Z. Let ψ(X_n) denote the q-vector of singular values of X_n. Under these assumptions, the limiting distribution of b_n (ψ(X_n) − ψ(B)) is characterized as a function of B and of the limit matrix Z. Applications to canonical correlations and to correspondence analysis are given.     

On the diameter and radius of randon subgraphs of the cube

The n-dimensional cube Qⁿ is the graph whose vertices are the subsets of {1,…n}, with two vertices adjacent if and only if their symmetric difference is a singleton. Clearly Qⁿ has diameter and radious n. Write M = n2^n-1 = e(Qⁿ) for the size of Qⁿ. Let Q = (Q_t)_o^M be a random Qⁿ-process. Thus Q^t is a spanning subgraph of Qⁿ of size t, and Q_t is obtained from Q_t–1 by the random addition of an edge of Qⁿ not in Q_t–1, Let t^(k) = τ(Q;δ?k) be the hitting time of the property of having minimal degree at least k. We show that the diameter d_t = diam (Q_t) of Q_t in almost every Q? behaves as follows: d_t starts infinite and is first finite at time t⁽¹⁾, it equals n + 1 for t⁽¹⁾ ? t⁽²⁾ and d_t, = n for t ? t⁽²⁾. We also show that the radius of Q_t, is first finite for t = t⁽¹⁾, when it assumes the value n. These results are deduced from detailed theorems concerning the diameter and radius of the almost surely unique largest component of Q_t, for t = Ω(M). © 1994 John Wiley & Sons, Inc.     

Bipartite labeling of trees with maximum degree three

Let T = (V, E) be a tree with a properly 2‐colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, …, |V|} for which there exists a k such that whenever φ(u) ≤ k < φ(v), then u and v have different colors. The α‐size α(T) of the tree T is the maximum number of elements in the sets {|φ(u) − φ(v)|; uv ∈ E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201–215), A. Rosa and the second author proved that 5n/7 ≤ α(n) ≤ (5n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of (n). In this article, we investigate the α‐size of trees with maximum degree three. Let α₃(n) be the smallest α‐size among all trees with n vertices, each of degree at most three. We prove that α₃(n) ≥ 5n/6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture—it shows that every tree on n ≥ 12 vertices and with maximum degree three has “gracesize” at least 5n/6. Using a computer search, we also establish that α₃(n) ≥ n − 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:7–15, 1999