Search results for "Combinatorics"
showing 10 items of 1770 documents
Fast and Simple Approximation of the Diameter and Radius of a Graph
2006
The increasing amount of data to be processed by computers has led to the need for highly efficient algorithms for various computational problems. Moreover, the algorithms should be as simple as possible to be practically applicable. In this paper we propose a very simple approximation algorithm for finding the diameter and the radius of an undirected graph. The algorithm runs in $O(m\sqrt{n})$ time and gives an additive error of $O(\sqrt{n})$ for a graph with n vertices and m edges. Practical experiments show that the results of our algorithm are close to the optimum and compare favorably to the 2/3-approximation algorithm for the diameter problem by Aingworth et al [1].
Abelian gradings on upper-triangular matrices
2003
Let G be an arbitrary finite abelian group. We describe all possible G-gradings on an upper-triangular matrix algebra over an algebraically closed field of characteristic zero.
Imprimitive groups highly transitive on blocks
2004
We classify imprimitive groups acting highly transitively on blocks and satisfying conditions common in geometry. They can be realized as suitable subgroups of twisted wreath products.
Entropy, transverse entropy and partitions of unity
1994
AbstractThe topological entropy of a transformation is expressed in terms of partitions of unity. The transverse entropy of a flow tangential to a foliation is defined and expresed in a similar way. The geometric entropy of a foliation of a Riemannian manifold is compared with the transverse entropy of its geodesic flow.
Tally languages accepted by alternating multitape finite automata
1997
We consider k-tape 1-way alternating finite automata (k-tape lafa). We say that an alternating automaton accepts a language L\(\subseteq\)(Σ*)k with f(n)-bounded maximal (respectively, minimal) leaf-size if arbitrary (respectively, at least one) accepting tree for any (w1, w2,..., wk) ∈ L has no more than $$f\mathop {(\max }\limits_{1 \leqslant i \leqslant k} \left| {w_i } \right|)$$ leaves. The main results of the paper are the following. If k-tape lafa accepts language L over one-letter alphabet with o(log n)-bounded maximal leaf-size or o(log log n)-bounded minimal leaf-size then the language L is semilinear. Moreover, if a language L is accepted with o(log log(n))-bounded minimal (respe…
Nearly tight bounds on the learnability of evolution
2002
Evolution is often modeled as a stochastic process which modifies DNA. One of the most popular and successful such processes are the Cavender-Farris (CF) trees, which are represented as edge weighted trees. The Phylogeny Construction Problem is that of, given /spl kappa/ samples drawn from a CF tree, output a CF tree which is close to the original. Each CF tree naturally defines a random variable, and the gold standard for reconstructing such trees is the maximum likelihood estimator of this variable. This approach is notoriously computationally expensive. We show that a very simple algorithm, which is a variant on one of the most popular algorithms used by practitioners, converges on the t…
Compactness of a conformal boundary of the Euclidean unit ball
2011
We study conformal metrics d‰ on the Euclidean unit ball B n : We assume that either the density ‰ associated with the metric d‰ satisfies a logarithmic volume growth condition for small balls or that ‰ satisfies a Harnack inequality and a suitable sub-Euclidean volume growth condition. We prove that the ‰-boundary @‰ B n is homeomorphic to S ni1 if and only if @‰ B n is compact. In the planar case, the compactness of @‰ B 2 is further equivalent to local connectivity of the ‰-boundary together with the boundedness of (B 2 ;d‰):
Complete weights andv-peak points of spaces of weighted holomorphic functions
2006
We examine the geometric theory of the weighted spaces of holomorphic functions on bounded open subsets ofC n ,C n ,H v (U) and\(H_{v_o } (U)\), by finding a lower bound for the set of weak*-exposed and weak*-strongly exposed points of the unit ball of\(H_{v_o } (U)'\) and give necessary and sufficient conditions for this set to be naturally homeomorphic toU. We apply these results to examine smoothness and strict convexity of\(H_{v_o } (U)\) and\(H_v (U)\). We also investigate whether\(H_{v_o } (U)\) is a dual space.
Fréchet Spaces of Holomorphic Functions without Copies of l 1
1996
Let X be a Banach space. Let Hw*(X*) the Frechet space whose elements are the holomorphic functions defined on X* whose restrictions to each multiple mB(X*), m = 1,2, …, of the closed unit ball B(X*) of X* are continuous for the weak-star topology. A fundamental system of norms for this space is the supremum of the absolute value of each element of Hw*(X*) in mB(X*), m = 1,2,…. In this paper we construct the bidual of l1 when this space contains no copy of l1. We also show that if X is an Asplund space, then Hw*(X*) can be represented as the projective limit of a sequence of Banach spaces that are Asplund.
On the Unit Ball of Operator-valued H 2-functions
2009
Let X be a complex Banach space and let H 2 (\( \mathbb{D} \), X) denote the space of X-valued analytic functions in the unit disc such that $$ \mathop {sup}\limits_{0 < r < 1} \int_0^{2\pi } {\left\| {F\left( {re^{it} } \right)} \right\|^2 \frac{{dt}} {{2\pi }} < \infty .} $$ It is shown that a function F belongs to the unit ball of H 2 ( \( \mathbb{D} \), X) if and only if there exist f∈H ∞ (\( \mathbb{D} \), X) and ϕ∈H ∞ (\( \mathbb{D} \)) such that $$ \left\| {f\left( z \right)} \right\|^2 + \left| {\varphi \left( z \right)} \right|^2 \leqslant 1 and F\left( z \right) = \frac{{f\left( z \right)}} {{1 - z\varphi \left( z \right)}} $$ for |z| < 1.