Dynamic partition trees

In this paper we study dynamic variants of conjugation trees and related structures that have recently been introduced for performing various types of queries on sets of points and line segments, like half-planar range searching, shooting, intersection queries, etc. For most of these types of queries dynamic structures are obtained with an amortized update time ofO(log² n) (or less) with only minor increases in query times. As an application of the method we obtain an output-sensitive method for hidden surface removal in a set ofn triangles that runs in timeO(nlogn+n ^· k ) where=log₂((1+5)/2) 0.695 andk is the size of the visibility map obtained.Research of the second author was partially supported by the ESPRIT II Basic Research Actions Program of the EC, under contract No. 3075 (project ALCOM).     

Efficient partition trees

We prove a theorem on partitioning point sets inE ^d (d fixed) and give an efficient construction of partition trees based on it. This yields a simplex range searching structure with linear space,O(n logn) deterministic preprocessing time, andO(n ^1?1/d (logn) ^O(1)) query time. WithO(nlogn) preprocessing time, where δ is an arbitrary positive constant, a more complicated data structure yields query timeO(n ^1?1/d (log logn) ^O(1)). This attains the lower bounds due to Chazelle [C1] up to polylogarithmic factors, improving and simplifying previous results of Chazelleet al. [CSW]. The partition result implies that, forr ^d≤n ^1?δ, a (1/r)-approximation of sizeO(r ^d) with respect to simplices for ann-point set inE ^d can be computed inO(n logr) deterministic time. A (1/r)-cutting of sizeO(r ^d) for a collection ofn hyperplanes inE ^d can be computed inO(n logr) deterministic time, provided thatr≤n ^1/(2d?1).     

Storing line segments in partition trees

We design two variants of partition trees, calledsegment partition trees andinterval partition trees, that can be used for storing arbitrarily oriented line segments in the plane in an efficient way. The raw structures useO(n logn) andO(n) storage, respectively, and their construction time isO(n logn). In our applications we augment these structures by certain (simple) auxiliary structures, which may increase the storage and preprocessing time by a polylogarithmic factor. It is shown how to use these structures for solving line segment intersection queries, triangle stabbing queries and ray shooting queries in reasonably efficient ways. If we use the conjugation tree as the underlying partition tree, the query time for all problems isO(n ), where=log₂(1+5)–10.695. The techniques are fairly simple and easy to understand.Research of the first author was partially supported by the ESPRIT II Basic Research Action of the EC under contract No. 3075 (Project ALCOM).Work by the third author has been supported in part by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grants DCR-83-20085 and CCR-89-01484, and by grants from the Digital Equipment Corporation, the IBM Corporation, the U.S.-Israeli Binational Science Foundation, the NCRD — the Israeli National Council for Research and Development, and the Fund for Basic Research in Electronics, Computers and Communication, administered by the Israeli Academy of Sciences.     

Weak cycle partition involving degree sum conditions

Let G be a graph of order n and k a positive integer. A set of subgraphs H={H₁,H₂,…,H_k} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H₁,…,H_k are vertex disjoint subgraphs of G such that and for all i, 1≤i≤k, H_i is a cycle or K₁ or K₂. If, in addition, for all i, 1≤i≤k, H_i is a cycle or K₁, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G has a k-DCP, except G≅C₅ and k=2. We prove that if G is a graph of order n≥k+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K₂∪K_n−2∪{e}, where e is an edge connecting V(K₂) and V(K_n−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}.     

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)     

Enumeration of coloured plane trees with a given type partition

Tutte's result for the number of planted plane trees with a given degree partition is rederived by a variety of methods and in particular by a simple piecewise construction technique. A theorem of Gordon and Temple is applied in order to give a general relationship between the number of planted plane trees and the number of rooted plane trees and the degree partition restriction is generalised to type partition. The piecewise construction method is successfully used to derive the number of planted plane trees with a given 2-colour degree partition, also derived by Tutte, and an algorithm for the k-coloured case is developed. This algorithm may be used to obtain more specific results. These models are relevant to the statistical mechanics of polymers and this is discussed briefly.     

Multiplicative properties of the partition function

A lower bound for the number of multiplicatively independent values ofp(n) forN ≤ n <N + R is given. The proof depends on the Hardy-Ramanujan formula and is of an elementary nature.     

Induced partition properties of combinatorial cubes

An induced version of the partition theorem for parameter-sets of R. L. Graham and B. L. Rothschild (Trans. Amer. Math. Soc.159 (1971), 257–291) is proven. This theorem generalizes the Graham-Rothschild theorem in the same way as the partition theorem for finite hypergraphs (F. G. Abramson and L. A. Harrington, J. Symblic Logic43 (1978), 572–600 and J. Ne?et?il and V. Rödl; J. Combin. Theory Ser. A22 (1977), 289–312; 34 (1983), 183–201) generalizes Ramsey's theorem. Some applications are given, e.g., an induced version of the Rado-Folkman-Sanders theorem and an induced version of the partition theorem for finite Boolean lattices. Also it turns out that the partition theorem for finite hypergraphs is an easy consequence of the induced partition theorem for parameter-sets.     

\ell -Adic properties of partition functions

Folsom, Kent, and Ono used the theory of modular forms modulo $\ell $ to establish remarkable “self-similarity” properties of the partition function and give an overarching explanation of many partition congruences. We generalize their work to analyze powers $p_r$ of the partition function as well as Andrews’s $spt$ -function. By showing that certain generating functions reside in a small space made up of reductions of modular forms, we set up a general framework for congruences for $p_r$ and $spt$ on arithmetic progressions of the form $\ell ^mn+\delta $ modulo powers of $\ell $ . Our work gives a conceptual explanation of the exceptional congruences of $p_r$ observed by Boylan, as well as striking congruences of $spt$ modulo 5, 7, and 13 recently discovered by Andrews and Garvan.     

Weak covering properties and selection principles

No convenient internal characterization of spaces that are productively Lindelöf is known. Perhaps the best general result known is Alster?s internal characterization, under the Continuum Hypothesis, of productively Lindelöf spaces which have a basis of cardinality at most _ℵ1${\aleph }_1$. It turns out that topological spaces having Alster?s property are also productively weakly Lindelöf. The weakly Lindelöf spaces form a much larger class of spaces than the Lindelöf spaces. In many instances spaces having Alster?s property satisfy a seemingly stronger version of Alster?s property and consequently are productively X, where X is a covering property stronger than the Lindelöf property. This paper examines the question: When is it the case that a space that is productively X is also productively Y, where X and Y are covering properties related to the Lindelöf property.     

Weak continuity properties of topologized groups

We explore (weak) continuity properties of group operations. For this purpose, the Novak number and developability number are applied. It is shown that if (G, ·, τ) is a regular right (left) semitopological group with dev(G) < Nov(G) such that all left (right) translations are feebly continuous, then (G, ·, τ) is a topological group. This extends several results in literature.     

Weak separation properties for self-similar sets

We develop a theory for self-similar sets in that fulfil the weak separation property of Lau and Ngai, which is weaker than the open set condition of Hutchinson.

     

Markovian trees: properties and algorithms

In this paper we introduce a structure called the Markovian tree (MT). We define the MT and explore its alternative representation as a continuous-time Markovian Multitype Branching Process. We then develop two algorithms, the Depth and Order algorithms to determine the probability of eventual extinction of the MT process. We show that both of these algorithms have very natural physically intuitive interpretations and are analogues of the Neuts and U algorithms in Matrix-analytic Methods. Furthermore, we show that a special case of the Depth algorithm sheds new light on the interpretation of the sample paths of the Neuts algorithm.     

Arithmetic properties of cubic and overcubic partition pairs

The Ramanujan Journal - Let b(n) denote the number of cubic partition pairs of n. We affirm a conjecture of Lin by proving that $$\begin{aligned} b(49n+37)\equiv 0 \pmod {49} \end{aligned}$$for all...     

Schrödinger operators on regular metric trees with long range potentials: Weak coupling behavior

Consider a regular d-dimensional metric tree Γ with root o. Define the Schrödinger operator −Δ−V, where V is a non-negative, symmetric potential, on Γ, with Neumann boundary conditions at o. Provided that V decays like |x|^−γ at infinity, where 1<γ?d?2, γ≠2, we will determine the weak coupling behavior of the bottom of the spectrum of −Δ−V. In other words, we will describe the asymptotic behavior of infσ(−Δ−αV) as α→0+.     

Weak separation axioms and weak covering properties

We identify some remnants of normality and call them rudimentary normality, generalize the concept of submetacompact spaces to that of a weakly subparacompact space and that of a weakly^? subparacompact space, and make a simultaneous generalization of collectionwise normality and screenability with the introduction of what is to be called collectionwise σ-normality. With these weak properties, we show that,1) on weakly subparacompact spaces, countable compactness = compactness, ω₁-compactness = Lindelöfness;2) on weakly subparacompact Hausdorff spaces with rudimentary normality, regularity = normality = countable paracompactness; and3) on weakly subparacompact regular T₁-spaces with rudimentary normality, collectionwise σ-normality = screenability = collectionwise normality = paracompactness.The famous Normal Moore Space Conjecture is thus given an even more striking appearance and Worrell and Wicke?s factorization of paracompactness (over Hausdorff spaces) along with Krajewski?s are combined and strengthened. The methodology extends itself to the factorization of paracompactness on locally compact, locally connected spaces in the manner of Gruenhage and on locally compact spaces in that of Tall, and to the factorization of subparacompactness and metacompactness in the genre of Katuta, Chaber, Junnila and Price and Smith and that of Boone, improving all of them.     

Weak normality properties and factorizations of normality

Summary Variants of δ-normality and δ-normal separation called weakly (functionally) δ-normal spaces are introduced and studied. This yields new factorizations of normality and δ-normality. A Urysohn type lemma and a Tietze type extension theorem for (weakly) functionally δ-normal spaces are obtained.     

Weak boundedness properties for maximal operators defined on weighted spaces

The purpose of this paper is to obtain characterizations of weak type (1,q) inequalities,q ≥ 1, for maximal operators defined on weighted spaces by means of the corresponding operator acting over Dirac deltas. We present a technical theorem which allows us to obtain characterizations for a pair of weights belonging to the classA ₁ of weights by means of the fractional maximal operator. Analogous results are obtained for the one-sided fractional maximal operator.