Renorming James tree space

We show that the James tree space can be renormed to be Lipschitz separated. This negatively answers the question of J. Borwein, J. Giles and J. Vanderwerff as to whether every Lipschitz separated Banach space is an Asplund space.

     

Renorming of spaces

If is a scattered Eberlein compact space, then admits an equivalent dual norm that is uniformly rotund in every direction. The same is shown for the dual to the Johnson-Lindenstrauss space .

     

Renorming of and the fixed point property

For any , let P_k denote the natural projections on ℓ₁. Let |||||| be an equivalent norm of ℓ₁ that satisfies all of the following four conditions:

(1) There are α>4 and a positive (decreasing) sequence (α_n) in (0,1) such that for any normalized block basis {f_n} of (ℓ₁,||||||) and xℓ₁ with P_k−1(x)=x and |||x|||<α_k,

(2) There are two strictly decreasing sequences {β_k} and {γ_k} with

such that for any normalized block basis {f_n} of (ℓ₁,||||||) and x with (I−P_k)(x)=x,

(3) For any , I−P_k=1.

(4) The unit ball of (ℓ₁,||||||) is σ(ℓ₁,c₀)-closed.

In this article, we prove that the space (ℓ₁,||||||) has the fixed point property for the nonexpansive mapping. This improves a previous result of the author.

An Asymptotic Property of Schachermayer's Space under Renorming

Let X be a Banach space with closed unit ball B. Given k , X is said to be k-β, respectively, (k + 1)-nearly uniformly convex ((k + 1)-NUC), if for every ε > 0 there exists δ, 0 < δ < 1, so that for every x B and every ε-separated sequence (x_n) B there are indices (n_i)^k_{i = 1}, respectively, (n_i)^{k + 1}_{i = 1}, such that (1/(k + 1))||x + ∑^k_{i = 1} x_ni|| ≤ 1 − δ, respectively, (1/(k + 1))||∑^{k + 1}_{i = 1} x_ni|| ≤ 1 − δ. It is shown that a Banach space constructed by Schachermayer is 2-β, but is not isomorphic to any 2-NUC Banach space. Modifying this example, we also show that there is a 2-NUC Banach space which cannot be equivalently renormed to be 1-β.     

Wiener Index of Trees: Theory and Applications

The Wiener index W is the sum of distances between all pairs of vertices of a (connected) graph. The paper outlines the results known for W of trees: methods for computation of W and combinatorial expressions for W for various classes of trees, the isomorphism–discriminating power of W, connections between W and the center and centroid of a tree, as well as between W and the Laplacian eigenvalues, results on the Wiener indices of the line graphs of trees, on trees extremal w.r.t. W, and on integers which cannot be Wiener indices of trees. A few conjectures and open problems are mentioned, as well as the applications of W in chemistry, communication theory and elsewhere.     

Potential Theory on Trees,Graphs and Ahlfors-regular Metric Spaces

We investigate connections between potential theories on a Ahlfors-regular metric space X, on a graph G associated with X, and on the tree T obtained by removing the “horizontal edges” in G. Applications to the calculation of set capacity are given.     

Renorming in the space of Bochner integrable functionsL 1(μ,X)

A sufficient condition is given when a subspaceL⊂L ₁(μ,X) of the space of Bochner integrable function, defined on a finite and positive measure space (S, Φ, μ) with values in a Banach spaceX, is locally uniformly convex renormable in terms of the integrable evaluations {∫ _A fdμ;f∈L}. This shows the lifting property thatL ₁(μ,X) is renormable if and only ifX is, and indicates a large class of renormable subspaces even ifX does not admit and equivalent locally uniformly convex norm.     

Some Finiteness Results in the Representation Theory of Isometry Groups of Regular Trees

Let G denote the isometry group of a regular tree of degree ≥3. The notion of congruence subgroup is introduced and finite generation of the congruence Hecke algebras is proven. Let U be congruence subgroup and (G; U) be the category of smooth representations of G generated by their U-fixed vectors. We also show that this subcategory is closed under taking subquotients. All these results are analogues of well-known results in the case of p-adic groups. It is also shown that the category of admissible representation of G is Noetherian in the sense that every subrepresentation of a finitely generated admissible representation is again finitely generated. Since we want to emphesize the similarities between these groups and p-adic groups, we give the same proofs which also work in the p-adic case whenever possible.     

完全二叉树理论的计算复杂度

完全二叉树的一阶理论已被证明具有量词消去的性质,进而计算了完全二叉树模型中元素的CB秩.本文利用有界Ehrenfeucht-Frassé博弈研究完全二叉树的一阶理论,证明了此理论的时间计算复杂度上界为22cn,空间计算复杂度上界为2dn(其中n为输入长度,c,d为合适的常数).     

Trees in tournaments

Letf(n) be the smallest integer such that every tournament of orderf(n) contains every oriented tree of ordern. Sumner has just conjectures thatf(n)=2n–2, and F. K. Chung has shown thatf(n)(1+o(1))nlog₂ n. Here we show thatf(n)12n andf(n)(4+o(1))n.     

Maximal Flow in Branching Trees and Binary Search Trees

A capacitated network is a tree with a non negative number, called capacity, associated to each edge. The maximal flow that can pass through a given path is the minimun capacity on the path. Antal and Krapivski (Phys Rev E 74:051110, 2006) study the distribution for the maximal flow from the root to a leaf in the case of a deterministic binary tree with independent and identically distributed random capacities. In this paper their result is extended to three classes of trees with a random number of children and dependent random capacities: binary trees with general capacities distribution, branching trees with exchangeable capacities and random binary search trees.     

Transversals in Trees

The total embedding polynomial of a graph G is the bivariate polynomial where is the number of embeddings, for into the orientable surface , and is the number of embeddings, for into the nonorientable surface . The sequence is called the total embedding distribution of the graph G; it is known for relatively few classes of graphs, compared to the genus distribution . The circular ladder graph is the Cartesian product of the complete graph on two vertices and the cycle graph on n vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders.     

On the Converse of the Theory of Groups Acting on Trees with Inversions

In this paper we show that if G is a group acting on a graph X with inversions such that G has a presentation induced by a fundamental domain for the action of G on X, then X is a tree. Received: January 3, 2007., Revised: August 10, 2007 and May 3, 2008., Accepted: October 17, 2008.     

Rooted Spanning Trees in Tournaments

A tournament of order n is an orientation of a complete graph with n vertices, and is specified by its vertex set V(T) and edge set E(T). A rooted tree is a directed tree such that every vertex except the root has in-degree 1, while the root has in-degree 0. A rooted k-tree is a rooted tree such that every vertex except the root has out-degree at most k; the out-degree of the root can be larger than k. It is well-known that every tournament contains a rooted spanning tree of depth at most 2; and the root of such a tree is also called a king in the literature. This result was strengthened to the following one: Every tournament contains a rooted spanning 2-tree of depth at most 2. We prove that every tournament of order n≥800 contains a spanning rooted special 2-tree in this paper, where a rooted special 2-tree is a rooted 2-tree of depth 2 such that all except possibly one, non-root, non-leaf vertices, have out-degree 2 in the tree. Revised: November 9, 1998     

Error Propagation in Game Trees

Game tree search is the core of most attempts to make computers play games. We present a fairly general theoretical analysis on how leaf evaluation errors influence the value estimation of a game position at the root. By an approach using prime factorization arguments in the ring of polynomials, we show that in this setting the maximum number of leaf-disjoint strategies proving a particular property is a key notion. This number precisely describes the quality of the heuristic game value in terms of the quality of the leaf evaluation heuristics. We extend this model to include random nodes (rolls of a die). Surprisingly, this changes the situation: utill the number of leaf-disjoint strategies ensures robustness against leaf evaluation errors, but the converse is not true. An average node may produce additional robustness similar to additional leaf-disjoint strategies. This work extends earlier ones which only deal with 0, 1 valued nodes, or without randomness.The first author was partially supported (associate member) by the graduate school ‘Effiziente Algorithmen und Mehrskalenmethoden’, Deutsche Forschungsgemeinschaft. The second author was partially supported by the Future and Emerging Technologies programme of the EU under contract numbers IST-1999-14186 (ALCOM-FT) and IST-2001-33116 (FLAGS).     

Protected Branches in Ordered Trees

In this paper, we consider the class of ordered trees and its two subclasses, bushes and planted trees, which consist of the ordered trees with root degree at least $2$ and with root degree $1$ respectively. In these three classes, we study the number of trees of size $n$ with $k$ protected (resp. unprotected) branches, and the total number of branches (resp. protected branches, unprotected branches) among all trees of size $n$. The explicit formulas as well as the generating functions are obtained. Furthermore, we find that, in each class, as $n$ goes to infinity, the proportion of protected branches among all branches in all trees of size $n$ approaches $ 1/3$.