A Characterization of Mixed Branching Greedoids

Branching greedoids have been defined and characterized for both directed and undirected rooted graphs. Such greedoids can be extended to rooted mixed graphs – graphs with both directed and undirected edges. These greedoids are characterized by a list of forbidden minors. If Ω is a rooted mixed graph, its mixed branching greedoid has the edges of Ω as its ground set and the collection of arborescences as its feasible sets. The set of mixed branching greedoids is exactly the set of local forest greedoids without

Convexity andq-gamma function

Inequalities and convexity properties known for the gamma function are extended to theq-gamma function, 0<q<1. Applying some classical inequalities for convex functions, we deduce monotonicity results for several functions involving theq-gamma function. Further applications to the probability theory are given.     

Klingenberg chain spaces

We propose a definition ofKlingenberg chain space, motivated by examples that are obtained from the action of the linear group on the projective line over an algebra over a local ring.     

The intrinsic dimensionality of graphs

We resolve the following conjecture raised by Levin together with Linial, London, and Rabinovich [Combinatorica, 1995]. For a graph G, let dim(G) be the smallest d such that G occurs as a (not necessarily induced) subgraph of ℤ_∞ ^d , the infinite graph with vertex set ℤ ^d and an edge (u, v) whenever ∥u − v∥_∞ = 1. The growth rate of G, denoted ρ _G , is the minimum ρ such that every ball of radius r > 1 in G contains at most r ^ρ vertices. By simple volume arguments, dim(G) = Ω(ρ _G ). Levin conjectured that this lower bound is tight, i.e., that dim(G) = O(ρ _G ) for every graph G. Previously, it was unknown whether dim(G) could be bounded above by any function of ρ _G . We show that a weaker form of Levin’s conjecture holds by proving that dim(G) = O(ρ _G log ρ _G ) for any graph G. We disprove, however, the specific bound of the conjecture and show that our upper bound is tight by exhibiting graphs for which dim(G) = Ω(ρ _G log ρ _G ). For several special families of graphs (e.g., planar graphs), we salvage the strong form, showing that dim(G) = O(ρ _G ). Our results extend to a variant of the conjecture for finite-dimensional Euclidean spaces posed by Linial and independently by Benjamini and Schramm. Supported by NSF grant CCR-0121555 and by an NSF Graduate Research Fellowship.     

Some Uses of the Farris Transform in Mathematics and Phylogenetics—A Review

In 1970, Farris introduced a procedure that can be used to transform a tree metric into an ultra metric. Since its discovery, Farris’ procedure has been used extensively within phylogenetics where it has become commonly known as the Farris transform. Remarkably, the Farris transform has not only been rediscovered several times within phylogenetics, but also in other fields. In this paper, we will review some of its various properties and uses. The paper is divided into four parts and, altogether, 12 sections. In the first part, we introduce a standardized scheme for classifying those dissimilarity mappings to which the Farris transform can be applied—a scheme that has evolved over the years, but has apparently not been spelled out before in sufficient detail. In the second part, we will discuss how a straightforward generalization of the Farris transform naturally arises in T-Theory. The third part describes how this generalized Farris transform can be used to approximate dissimilarities by tree metrics. And in the final part, we describe some further, “non-standard” applications of the Farris transform. Received November 24, 2004     

A short proof of Halin’s grid theorem

We give a short proof of Halin’s theorem that every thick end of a graph contains the infinite grid.     

On Limit Cycles Appearing by Polynomial Perturbation of Darbouxian Integrable Systems

We prove an existential finiteness result for integrals of rational 1-forms over the level curves of Darbouxian integrals. Received: May 2007, Revision: March 2008, Accepted: March 2008     

The Beckman-Quarles theorem for mappings from ℝ2 to $${\mathbb{F}}^2 $$ , where F is a subfield of a commutative field extending ℝ, where F is a subfield of a commutative field extending ℝ

Let F be a subfield of a commutative field extending ℝ. Let We say thatf : preserves distanced ≥ 0 if for eachx,y ∈ ℝ ∣x- y∣= d implies ϕ₂(f(x),f(y)) = d² . We prove that each unit-distance preserving mappingf : has a formI o (ρ,ρ), where is a field homomorphism and is an affine mapping with orthogonal linear part.     

Bijections Between Multiparking Functions, Dirichlet Configurations, and Descending R-Traversals

There are several combinatorial objects that are known to be in bijection with the spanning trees of a graph G. These objects include G-parking functions, critical configurations of G, and descending traversals of G. In this paper, we extend the bijections to generalizations of all three objects. Partially supported by NSF VIGRE grant # 9977354.     

The product of two von Neumann n-frames, its characteristic, and modular fractal lattices

Let L be a bounded lattice. If for each a₁ < b₁ ∈ L and a₂ < b₂ ∈ L there is a lattice embedding ψ: [a₁, b₁] → [a₂, b₂] with ψ(a₁) = a₂ and ψ(b₁) = b₂, then we say that L is a quasifractal. If ψ can always be chosen to be an isomorphism or, equivalently, if L is isomorphic to each of its nontrivial intervals, then L will be called a fractal lattice. For a ring R with 1 let denote the lattice variety generated by the submodule lattices of R-modules. Varieties of this kind are completely described in [16]. The prime field of characteristic p will be denoted by F_p. Let be a lattice variety generated by a nondistributive modular quasifractal. The main theorem says that is neither too small nor too large in the following sense: there is a unique , a prime number or zero, such that and for any n ≥ 3 and any nontrivial (normalized von Neumann) n-frame of any lattice in , is of characteristic p. We do not know if in general; however we point out that, for any ring R with 1, implies . It will not be hard to show that is Arguesian. The main theorem does have a content, for it has been shown in [2] that each of the is generated by a single fractal lattice L_p; moreover we can stipulate either that L_p is a continuous geometry or that L_p is countable. The proof of the main theorem is based on the following result of the present paper: if is a nontrivial m-frame and is an n-frame of a modular lattice L with m, n ≥ 3 such that and , then these two frames have the same characteristic and, in addition, they determine a nontrivial mn-frame of the same characteristic in a canonical way, which we call the product frame. Presented by E. T. Schmidt.     

On the almost sure central limit theorem and domains of attraction

We give necessary and sufficient criteria for a sequence (X _n) of i.i.d. r.v.'s to satisfy the a.s. central limit theorem, i.e.,

Dirac’s Theorem on Simplicial Matroids

We introduce the notion of k-hyperclique complexes, i.e., the largest simplicial complexes on the set [n] with a fixed k-skeleton. These simplicial complexes are a higher-dimensional analogue of clique (or flag) complexes (case k = 2) and they are a rich new class of simplicial complexes. We show that Dirac’s theorem on chordal graphs has a higher-dimensional analogue in which graphs and clique complexes get replaced, respectively, by simplicial matroids and k-hyperclique complexes. We prove also a higher-dimensional analogue of Stanley’s reformulation of Dirac’s theorem on chordal graphs.      

Kneser— Hecke— operators in coding theory

The Kneser-Hecke-operator is a linear operator defined on the complex vector space spanned by the equivalence classes of a family of self-dual codes of fixed length. It maps a linear self-dual codeC over a finite field to the formal sum of the equivalence classes of those self-dual codes that intersectC in a codi-mension 1 subspace. The eigenspaces of this self-adjoint linear operator may be described in terms of a coding-theory analogue of the Siegel Φ-operator.     

Some submersions of extrinsic hyperspheres of a Bochner-Kähler manifold

The purpose of this paper is to extend some known results on Riemannian submersions from extrinsic hyperspheres of an Einstein-Kähler manifold to the case of a Bochner-Kähler manifold.     

The Central value of the Rankin–Selberg L-Functions

Let f be a Maass form for SL which is fixed and u _j be an orthonormal basis of even Maass forms for SL , we prove an asymptotic formula for the average of the product of the Rankin–Selberg L-function of f and u _j and the L-function of u _j at the central value 1/2. This implies simultaneous nonvanishing results of these L-functions at 1/2. Received: November 2006, Revision: March 2007, Accepted: March 2007     

The symmetry axiom in Minkowski planes

We give a synthetic proof that in a symmetric Minkowski plane the rectangle axiom (G) holds. Dedicated to Professor Helmut Karzel     

Hilbert geometry of polytopes

It is shown that the Hilbert metric on the interior of a convex polytope is bilipschitz to a normed vector space of the same dimension. Supported by the Schweizerischer Nationalfonds grants SNF PP002-114715/1 and 200020-121506/1.     

On the Napoleon-Torricelli configuration in Affine Cayley-Klein planes

There are three affine Cayley-Klein planes (see [5]), namely, the Euclidean plane, the isotropic (Galilean) plane, and the pseudo-Euclidean (Minkow-skian or Lorentzian) plane. We extend the generalization of the well-known Napoleon theorem related to similar triangles erected on the sides of an arbitrary triangle in the Euclidean plane to all affine Cayley-Klein planes. Using the Ω_k-and anti-Ω_k-equilateral triangles introduced in [28], we construct the Napoleon and the Torricelli triangle of an arbitrary triangle in any affine Cayley-Klein plane. Some interesting geometric properties of these triangles are derived. The author is partially supported by grant VU-MI-204/2006.     

Infinite highly connected planar graphs of large girth

We construct infinite planar graphs of arbitrarily large connectivity and girth, and study their separation properties. These graphs have no thick end but continuum many thin ones. Every finite cycle separates them, but they corroborate Diestel’s conjecture that everyk-connected locally finite graph contains a possibly infinite cycle — see [3] — whose deletion leaves it (k — 3)-connected.     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.