The Degree Profile in Some Classes of Random Graphs that Generalize Recursive Trees

We study the degree profile for a number of classes of random graphs that arise as generalizations of recursive trees, including random circuits and random recursive trees endowed with the power of choice. We investigate the distribution of the degrees of nodes that appear in various stages of the insertion process in each of these graph types. For these classes, we will see phase transitions in degrees depending on the stage—early stages are associated with normal distributions, intermediate stages are associated with the Poisson distribution and in the late stages the degrees become degenerate.     

Asymptotic Joint Normality of Counts of Uncorrelated Motifs in Recursive Trees

We study the fringe of random recursive trees, by analyzing the joint distribution of the counts of uncorrelated motifs. Our approach allows for finite and countably infinite collections. To be able to deal with the collection when it is infinitely countable, we use measure-theoretic themes. Each member of a collection of motifs occurs a certain number of times on the fringe. We show that these numbers, under appropriate normalization, have a limiting joint multivariate normal distribution. We give a complete characterization of the asymptotic covariance matrix. The methods of proof include contraction in a metric space of distribution functions to a fixed-point solution (limit distribution). We discuss two examples: the finite collection of all possible motifs of size four, and the infinite collection of rooted stars. We conclude with remarks to compare fringe-analysis with matching motifs everywhere in the tree.     

Asymptotic Joint Normality of Outdegrees of Nodes in Random Recursive Trees

We study the joint probability distribution of the number of nodes of outdegree 0, 1, and 2 in a random recursive tree. We complete the known partial list of exact means and variances for outdegrees up to two by obtaining exact combinatorial expressions for the remaining means, variances, and covariances. The joint probability distribution of the number of nodes of outdegree 0, 1, and 2 is shown to be asymptotically trivariate normal and the asymptotic covariance structure is explicitly determined. It is also shown how to extend the results (at least in principle) to obtain a limiting multivariate normal distribution for nodes of outdegree 0, 1, …, k.     

A Recursive Construction for 2-Designs

This paper contains two main results: given a symmetric (v, k, ) design, D, and a resolvable design which has the parameters of a residual design of D, there exists a symmetric (dv + 1, v, k) design, where d = (v - k)/(k - ), and d is a prime power; given a symmetric (v, k, ) design, D, and a resolvable design with the parameters of a derived design of D, there exists a 2 - (ek + v, 2k, k) design, where e = k/,and e is a prime power.     

自然数等幂和的一个新的通项递归公式

从几何观点出发,利用二项式定理推导出自然数等幂和的一个新的通项递归公式,比已有的组合逼近式、递推式更简洁有效.     

A Recursive Construction for New Symmetric Designs

We introduce a recursive construction of regular Handamard matrices with row sum 2h for h=±3ⁿ. Whenever q=(2h – 1)² is a prime power, we construct, for every positive integer m, a symmetric designs with parameters (4h²(q^m+1 – 1)/(q – 1), (2h² – h)q^m, (h² – h)q^m).     

On-line Construction of Two-Dimensional Suffix Trees

We say that a data structure is builton-lineif, at any instant, we have the data structure corresponding to the input we have seen up to that instant. For instance, consider the suffix tree of a stringx[1, n]. An algorithm building iton-lineis such that, when we have read the firstisymbols ofx[1, n], we have the suffix tree forx[1, i]. We present a new technique, which we refer to asimplicit updates, based on which we obtain: (a) an algorithm for theon-lineconstruction of the Lsuffix tree of ann×nmatrixA—this data structure is the two-dimensional analog of the suffix tree of a string; (b) simple algorithms implementing primitive operations forLZ1-typeon-line losslessimage compression methods. Those methods, recently introduced by Storer, are generalizations ofLZ1-typecompression methods for strings. For the problem in (a), we get nearly an order of magnitude improvement over algorithms that can be derived from known techniques. For the problem in (b), we do not get an asymptotic speed-up with respect to what can be done with known techniques; rather we show that our algorithms are a natural support for the primitive operations. This may lead to faster implementations of those primitive operations. To the best of our knowledge, our technique is the first one that effectively addresses problems related to theon-lineconstruction of two-dimensional suffix trees.     

递推数列的非线性表达式的构造

A type of nonlinear expressions of Lucas sequences are established inspired by Hsu [A nonlinear expression for Fibonacci numbers and its consequences.J.Math.Res.Appl.,2012,32(6):654–658].Using the relationships between the Lucas sequence and other linear recurring sequences satisfying the same recurrence relation of order 2,i.e.,the Horadam sequences,we may transfer the identities of Lucas sequences to the latter.     

强度m的对称正交表的递归构造

本文证明了Q~n空间的正交分划的存在性,对2水平正交表的递归构造方法进行了改进,通过对正交分划的构造提出了任意强度的高水平对称正交表的递归构造方法.     

Recursive Construction of Optimal Self-Concordant Barriers for Homogeneous Cones

We give a recursive formula for optimal dual barrier functions on homogeneous cones. This is done in a way similar to the primal construction of Güler and Tunçel (Math. Program. 81(1):55–76, 1998) by means of the dual Siegel cone construction of Rothaus (Bull. Am. Math. Soc. 64:85–86, 1958). We use invariance of the primal barrier function with respect to a transitive subgroup of automorphisms and the properties of the duality mapping, which is a bijection between the primal and the dual cones. We give simple direct proofs of self-concordance of the primal optimal barrier and provide an alternative expression for the dual universal barrier function.     

树的计数

阶数为n且不同构的树的个数称为树列t_n.对n阶错排做了划分,汇总计算了对称群的循环指数,结合树的结构特性和波利亚计数定理,给出了一种确定t_n的算法并证明了算法的合理性.计算表明,树列t_n={1,1,1,2,3,6,11,23,47,106,235,551,…}.     

树的Hk-cordial性

如果可以给图G的边用集合（±1,±2,.. ,±k）中的元素标号,使得对G每个顶点u,其标号,即所有与其相邻的边的标号之和,都落在集合（±1,±2,.. ,±k）中,且Ie（i）-e（-i）I≤1和lu（i）-u（-i）1≤1,其中t心）和e（i）（1≤i≤k）分别是标号为i的顶点数和边数,那么就称该图G为Hk-cordial的．本文证明了除了尥以外,每棵树都是H3-cordial的．     

The p-Bondage Number of Trees

Let p be a positive integer and G = (V, E) be a simple graph. A p-dominating set of G is a subset D  í  V{D\,{\subseteq}\, V} such that every vertex not in D has at least p neighbors in D. The p-domination number of G is the minimum cardinality of a p-dominating set of G. The p-bondage number of a graph G with (ΔG) ≥ p is the minimum cardinality among all sets of edges B í E{B\subseteq E} for which γ _p (G − B) > γ _p (G). For any integer p ≥ 2 and tree T with (ΔT) ≥ p, this paper shows that 1 ≤  b _p (T) ≤ (ΔT) − p + 1, and characterizes all trees achieving the equalities.     

The Height of Increasing Trees

Increasing trees have been introduced by Bergeron, Flajolet, and Salvy [1]. This kind of notion covers several well-know classes of random trees like binary search trees, recursive trees, and plane oriented (or heap ordered) trees. We consider the height of increasing trees and prove for several classes of trees (including the above mentioned ones) that the height satisfies EH _n ~ γlogn (for some constant γ > 0) and Var H _n =  O(1) as n → ∞. The methods used are based on generating functions. This research was supported by the Austrian Science Foundation FWF, project S9604, that is part of the Austrian National Research Network "Analytic Combinatorics and Probabilistic Number Theory".     

On the Recursive Sequence

The boundedness, global attractivity, oscillatory and asymptotic periodicity of the nonnegative solutions of the difference equation?in the title is investigated, where all the coefficients are nonnegative real numbers. The paper is motivated by an open problem proposed by Ladas [Open problems and conjectures, J. Differ. Equations?Appl., 5 (1999), 211–215].     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

完全二叉树模型中元素的CB秩

本文以完全二叉树理论的可量词消去为基础,介绍了该理论的可数原子模型 及饱和模型,并计算了一元、二元完全型的CB秩,从而给出了CB秩在该理论中的 几何解释.     

The Number of Spanning Trees in Self-Similar Graphs

The number of spanning trees of a graph, also known as the complexity, is computed for graphs constructed by a replacement procedure yielding a self-similar structure. It is shown that under certain symmetry conditions exact formulas for the complexity can be given. These formulas indicate interesting connections to the theory of electrical networks. Examples include the well-known Sierpiński graphs and their higher-dimensional analogues. Several auxiliary results are provided on the way—for instance, a property of the number of rooted spanning forests is proven for graphs with a high degree of symmetry.