Club isomorphisms on higher Aronszajn trees

We prove the consistency, assuming an ineffable cardinal, of the statement that CH holds and any two normal countably closed ${\omega }_2$-Aronszajn trees are club isomorphic. This work generalizes to higher cardinals the property of Abraham–Shelah [1] that any two normal ${\omega }_1$-Aronszajn trees are club isomorphic, which follows from PFA. The statement that any two normal countably closed ${\omega }_2$-Aronszajn trees are club isomorphic implies that there are no ${\omega }_2$-Suslin trees, so our proof also expands on the method of Laver–Shelah [5] for obtaining the ${\omega }_2$-Suslin hypothesis.     

Spanning trees with pairwise nonadjacent endvertices

A spanning tree of a connected graph G is said to be an independency tree if all its endvertices are pairwise nonadjacent in G. We prove that a connected graph G has no independency tree if and only if G is a cycle, a complete graph or a complete bipartite graph the color classes of which have equal cardinality.     

A family of random trees with random edge lengths

We introduce a family of probability distributions on the space of trees with I labeled vertices and possibly extra unlabeled vertices of degree 3, whose edges have positive real lengths. Formulas for distributions of quantities such as degree sequence, shape, and total length are derived. An interpretation is given in terms of sampling from the inhomogeneous continuum random tree of Aldous and Pitman (1998). ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 176–195, 1999     

On family trees and subtrees of simple branching processes

We study the probability of occurrence of certain subtrees of the family tree of a Galton Watson branching process.     

Dominating and large induced trees in regular graphs

Recently Chen et al. [Tree domination in graphs, Ars Combin. 73 (2004) 193-203] asked for characterizations of the class of graphs and the class of regular graphs that have an induced dominating tree, i.e. for which there exists a dominating set that induces a tree.We give a somewhat negative answer to their question by proving that the corresponding decision problems are NP-complete. Furthermore, we prove essentially best-possible lower bounds on the maximum order of induced trees in connected cacti of maximum degree 3 and connected cubic graphs.Finally, we give a forbidden induced subgraph condition for the existence of induced dominating trees.     

A general decomposition approach for multi-criteria decision trees

In this paper, we address the dynamic and multi-criteria decision-making problems under uncertainty, generally represented by multi-criteria decision trees. Decision-making consists of choosing, at each period, a decision that maximizes the decision-maker outcomes. These outcomes should often be measured against a set of heterogeneous and conflicting criteria. Generating the set of non-dominated solutions is a common approach considered in the literature to solve the multi-criteria decision trees, but it becomes very challenging for large problems. We propose a new approach to solve multi-criteria decision trees without generating the set of all non-dominated solutions, which should reduce the computation time and the cardinality of the solution set. In particular, the proposed approach combines the advantages of decomposition with the application of multi-criteria decision aid (MCDA) methods at each decision node. A generalization of the Bellman’s principle of decomposition to the multi-criteria context is put forward. A decomposition theorem is therefore proposed. Under the sufficient conditions stated by the theorem, the principle of decomposition will generate the set of best compromise strategies. Seven MCDA methods are then characterized (lexicographic, weighted sum, multi-attribute value theory, TOPSIS, ELECTRE III, and PROMETHEE II) against the conditions of the theorem of decomposition and against other properties (neutrality, anonymous, fidelity, dominance, independency), in order to confirm or infirm their applicability with the proposed decomposition principle. Moreover, the relationship between independency and temporal consistence is discussed as well as the effects of incomparableness, rank reversals, and use of thresholds. Two conjectures resulted from this characterization.     

A bijective enumeration of tiered trees

Tiered trees were introduced by Dugan–Glennon–Gunnells–Steingrímsson as a generalization of intransitive trees that were introduced by Postnikov, the latter of which have exactly two tiers. Tiered trees arise naturally in counting the absolutely indecomposable representations of certain quivers, and enumerating torus orbits on certain homogeneous varieties over finite fields. By employing generating function arguments and geometric results, Dugan et al. derived an elegant formula concerning the enumeration of tiered trees, which is a generalization of Postnikov’s formula for intransitive trees. In this paper, we provide a bijective proof of this formula by establishing a bijection between tiered trees and certain rooted labeled trees. As an application, our bijection also enables us to derive a refinement of the enumeration of tiered trees with respect to level of the node 1.     

Asymptotics of trees with a prescribed degree sequence and applications

Let t be a rooted tree and n_bi(t) the number of nodes in t having i children. The degree sequence of t satisfies , where denotes the number of nodes in t. In this paper, we consider trees sampled uniformly among all plane trees having the same degree sequence ; we write for the corresponding distribution. Let be a list of degree sequences indexed by κ corresponding to trees with size . We show that under some simple and natural hypotheses on the trees sampled under converge to the Brownian continuum random tree after normalisation by . Some applications concerning Galton–Watson trees and coalescence processes are provided.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 290‐316, 2014     

Edge disjoint Steiner trees in graphs without large bridges

A set A of vertices of an undirected graph G is called k‐edge‐connected in G if for all pairs of distinct vertices a, b∈A, there exist k edge disjoint a, b‐paths in G. An A‐tree is a subtree of G containing A, and an A‐bridge is a subgraph B of G which is either formed by a single edge with both end vertices in A or formed by the set of edges incident with the vertices of some component of G ? A. It is proved that (i) if A is k·(? + 2)‐edge‐connected in G and every A‐bridge has at most ? vertices in V(G) ? A or at most ? + 2 vertices in A then there exist k edge disjoint A‐trees, and that (ii) if A is k‐edge‐connected in G and B is an A‐bridge such that B is a tree and every vertex in V(B) ? A has degree 3 then either A is k‐edge‐connected in G ? e for some e∈E(B) or A is (k ? 1)‐edge‐connected in G ? E(B). © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 188–198, 2009     

A new method for counting trees with vertex partition

A direct and elementary method is provided in this paper for counting trees with vertex partition instead of recursion, generating function, functional equation, Lagrange inversion, and matrix methods used before. This work was supported by the National Natural Science Foundation of China (Grant No. 10571013)     

A non-implication between fragments of Martin’s Axiom related to a property which comes from Aronszajn trees

We introduce a property of forcing notions, called the anti-, which comes from Aronszajn trees. This property canonically defines a new chain condition stronger than the countable chain condition, which is called the property .In this paper, we investigate the property . For example, we show that a forcing notion with the property does not add random reals. We prove that it is consistent that every forcing notion with the property has precaliber ℵ₁ and for forcing notions with the property fails. This negatively answers a part of one of the classical problems about implications between fragments of .     

A note on the probabilistic analysis of patricia trees

We consider random PATRICIA trees constructed from n i.i.d. sequences of independent equiprobable bits. We study the height H_n (the maximal distance between the root and a leaf), and the minimal fill-up level F_n (the minimum distance between the root and a leaf). We give probabilistic proofs of .     

两两NQD列大数定律的一个注记

利用两两NQD列三级数定理的思想和Chebyshev不等式,研究了两两NQD列在一类广泛条件下的弱大数定律和一类加强条件下的强大数定律,得到了与独立情形一致的结果,还特别讨论了同分布情形,推广了相关文献的结果．     

A non-metrizable compact linearly ordered topological space, every subspace of which has a -minimal base

A collection of subsets of a space is minimal if each element of contains a point which is not contained in any other element of . A base of a topological space is -minimal if it can be written as a union of countably many minimal collections. We will construct a compact linearly ordered space satisfying that is not metrizable and every subspace of has a -minimal base for its relative topology. This answers a problem of Bennett and Lutzer in the negative.

     

A study of random Weyl trees

We study binary search trees constructed from Weyl sequences {nθ}, n≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H_n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H_n∼(12/π²)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998