Projective Valuations,D-Relations,and Ends of Λ-Trees

Abstract

A projective valuation on a set Eis a mapping w : E ⁴ → Λ ∪ {±∞}, where Λ is an ordered abelian group, satisfying certain axioms. A D-relation on Eis a four-place relation on E, again with certain properties. There is a projective valuation on the set of ends of a Λ-tree (and on any subset, by restriction) and we show, using a construction suggested by Tits in the case Λ = ?, that every projective valuation arises in this way. Every projective valuation wdefines a D-relation, and there is a simple geometric interpretation of the D-relation, given a Λ-tree defining w. Our main result is a converse, that any D-relation can be defined by a projective valuation, hence arises from an embedding into the set of ends of a Λ-tree.     

Non-nesting actions of Polish groups on real trees

We prove that if a Polish group G with a comeagre conjugacy class has a non-nesting action on an R-tree, then every element of G fixes a point.     

Chromaticity of two-trees

The graphs called 2-trees are defined by recursion. The smallest 2-tree is the complete graph on 2 vertices. A 2-tree on n + 1 vertices (where n ≥ 2) is obtained by adding a new vertex adjacent to each of 2 arbitrarily selected adjacent vertices in a 2-tree on n vertices. A graph G is a 2-tree on n(≥2) vertices if and only if its chromatic polynomial is equal to γ(γ - 1)(γ - 2)^n—2.     

Scale Free Properties of Random <Emphasis Type="Italic">k</Emphasis>-Trees

Scale free graphs have attracted attention as their non-uniform structure that can be used as a model for many social networks including the WWW and the Internet. In this paper, we propose a simple random model for generating scale free k-trees. For any fixed integer k, a k-tree consists of a generalized tree parameterized by k, and is one of the basic notions in the area of graph minors. Our model is quite simple and natural; it first picks a maximal clique of size k + 1 uniformly at random, it then picks k vertices in the clique uniformly at random, and adds a new vertex incident to the k vertices. That is, the model only makes uniform random choices twice per vertex. Then (asymptotically) the distribution of vertex degree in the resultant k-tree follows a power law with exponent 2 + 1/k, the k-tree has a large clustering coefficient, and the diameter is small. Moreover, our experimental results indicate that the resultant k-trees have extremely small diameter, proportional to o(log n), where n is the number of vertices in the k-tree, and the o(1) term is a function of k.     

Connected Factors and Spanning Trees in Graphs

 Let G be a graph, and g, f, f′ be positive integer-valued functions defined on V(G). If an f′-factor of G is a spanning tree, we say that it is f′-tree. In this paper, it is shown that G contains a connected (g, f+f′−1)-factor if G has a (g, f)-factor and an f′-tree. Received: October 30, 2000 Final version received: August 20, 2002     

On the Structure of Contractible Edges in <Emphasis Type="Italic">k</Emphasis>-connected Partial <Emphasis Type="Italic">k</Emphasis>-trees

Contraction of an edge e merges its end points into a new single vertex, and each neighbor of one of the end points of e is a neighbor of the new vertex. An edge in a k-connected graph is contractible if its contraction does not result in a graph with lesser connectivity; otherwise the edge is called non-contractible. In this paper, we present results on the structure of contractible edges in k-trees and k-connected partial k-trees. Firstly, we show that an edge e in a k-tree is contractible if and only if e belongs to exactly one (k + 1) clique. We use this characterization to show that the graph formed by contractible edges is a 2-connected graph. We also show that there are at least |V(G)| + k − 2 contractible edges in a k-tree. Secondly, we show that if an edge e in a partial k-tree is contractible then e is contractible in any k-tree which contains the partial k-tree as an edge subgraph. We also construct a class of contraction critical 2k-connected partial 2k-trees.     

On extremal sizes of locally k-tree graphs

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k ⩾ 0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k ⩾ 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between Ω(n) and O(n ²), where both bounds are asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.     

RIGIDITY AT INFINITY OF TREES AND EUCLIDEAN BUILDINGS

We show that if a group G acts isometrically on a locally finite leafless ?-tree inducing a two-transitive action on its ends, then this tree is determined by the action of G on the boundary. As a corollary we obtain that locally finite irreducible Euclidean buildings of dimension at least two are determined by their complete building at infinity.     

Two combinatorial properties of a class of simplicial polytopes

Letf(P _s ^d ) be the set of allf-vectors of simpliciald-polytopes. ForP a simplicial 2d-polytope let Σ(P) denote the boundary complex ofP. We show that for eachf ∈f(P _s ^d ) there is a simpliciald-polytopeP withf(P)=f such that the 11 02 simplicial diameter of Σ(P) is no more thanf ₀(P)−d+1 (one greater than the conjectured Hirsch bound) and thatP admits a subdivision into a simpliciald-ball with no new vertices that satisfies the Hirsch property. Further, we demonstrate that the number of bistellar operations required to obtain Σ(P) from the boundary of ad-simplex is minimum over the class of all simplicial polytopes with the samef-vector. This polytopeP will be the one constructed to prove the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes.     

On indecomposable trees in the boundary of outer space

Let T be an \mathbbR{\mathbb{R}}-tree, equipped with a very small action of the rank n free group F _n , and let H ≤ F _n be finitely generated. We consider the case where the action F_n \curvearrowright T{F_n \curvearrowright T} is indecomposable–this is a strong mixing property introduced by Guirardel. In this case, we show that the action of H on its minimal invarinat subtree T _H has dense orbits if and only if H is finite index in F _n . There is an interesting application to dual algebraic laminations; we show that for T free and indecomposable and for H ≤ F _n finitely generated, H carries a leaf of the dual lamination of T if and only if H is finite index in F _n . This generalizes a result of Bestvina-Feighn-Handel regarding stable trees of fully irreducible automorphisms.     

Characterization of partial 3-trees in terms of three structures

A characterization of partial 3-trees is given based on the elimination sequence of vertices. It is proved that a partial 3-tree contains a vertex set satisfying either of certain three kinds of neighborhood relations on vertices and that a graph is a partial 3-tree if and only if eliminating such a vertex set results in a partial 3-tree. These results yield anO(n ²) time algorithm to recognize 3-trees.     

Parity Splits by Triple Point Distances in X-Trees

At the conference Dress defined parity split maps by triple point distance and asked for a characterisation of such maps coming from binary phylogenetic X-trees. This article gives an answer to that question. The characterisation for X-trees can be easily described as follows: If all restrictions of a split map to sets of five or fewer elements is a parity split map for an X-tree, then so is the entire map. To ensure that the parity split map comes from an X-tree which is binary and phylogenetic, we add two more technical conditions also based on studying at most five points at a time. Received August 27, 2004     

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     

Degree sets ofk-trees: Smallk

Ak-tree is ak-uniform hypergraph constructed from a single edge by the successive addition of edges each containing a new vertex andk−1 vertices of an existing edge. We show that ifD is any finite set of positive integers which includes 1, thenD is the set of vertex degrees of somek-tree fork=2, 3, and 4, and that there is precisely one such set,D={1, 4, 6}, which is not the set of degrees of any 5-tree. We also show for eachk≧2 that such a setD is the set of degrees of somek-tree provided only thatD contains some elementd which satisfiesd≧k (k−1)−2 [k/2]+3.     

A k-Tree Containing Specified Vertices

A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let ${S \subseteq V(G)}A k-tree is a tree with maximum degree at most k. In this paper, we give sufficient conditions for a graph to have a k-tree containing specified vertices. Let k be an integer with k > 3. Let G be a graph of order n and let S í V(G){S \subseteq V(G)} with κ(S) ≥ 1. Suppose that for every l > κ(S), there exists an integer t such that 1 ￡ t ￡ (k-1)l+2 - ?\fracl-1k ?{1 \le t \leq (k-1)l+2 - \lfloor \frac{l-1}{k} \rfloor} and the degree sum of any t independent vertices of S is at least n + tl − kl − 1. Then G has a k-tree containing S. We also show some new results on a spanning k-tree as corollaries of the above theorem.     

McMullen's conditions and some lower bounds for general convex polytopes

We give a lower bound for the number of vertices of a generald-dimensional polytope with a given numberm ofi-faces for eachi = 0,..., d/2 – 1. The tightness of those bounds is proved using McMullen's conditions. Form greater than a small constant, those lower bounds are attained by simpliciali-neighbourly polytopes.     

On Urysohn’s ℝ-Tree

In the short note of 1927, Urysohn constructed the metric space R that is nowhere locally separable. There is no publication with indications that R is a (noncomplete) ?-tree that has valency c at each point. The author in 1989, as well as Polterovich and Shnirelman in 1997, constructed ?-trees isometric to R unaware of the paper by Urysohn. In this paper the author considers various constructions of the ?-tree R and of the minimal complete ?-tree of valency c including R, as well as the characterizations of ?-trees, their properties, and connections with ultrametric spaces.

     

Coordinatizing R-trees in terms of universal c-trees

A complete ℝ-treeT will be constructed such that, for everyxσT, the cardinality of the set of connected components ofT{x} is the same and equals a pre-given cardinalityc; by this construction simultaneously the valuated matroid of the ends of this ℝ-tree is given. In addition, for any arbitrary ℝ-tree, an embedding into such a “universalc-tree” (for suitablec) will be constructed.     

A note on a spanning 3-tree

A tree T is called a k-tree, if the maximum degree of T is at most k. In this paper, we prove that if G is an n-connected graph with independence number at most n + m + 1 (n≥1,n≥m≥0), then G has a spanning 3-tree T with at most m vertices of degree 3.     

On a problem of klee concerning convex polytopes

A non-simpliciald-polytope is shown to have strictly fewerk-faces ([(d−1)/2]≦k≦d−1) then some simpliciald-polytope with the same number of vertices; actual numerical bounds are given. This provides a strong affirmative answer to a problem of Klee.