Tiling Transitive Tournaments and Their Blow-ups

Let TT _k denote the transitive tournament on k vertices. Let TT(h,k) denote the graph obtained from TT _k by replacing each vertex with an independent set of size h≥1. The following result is proved: Let c ₂=1/2, c ₃=5/6 and c _k =1−2^{−k−log k} for k≥4. For every ∈>0 there exists N=N(∈,h,k) such that for every undirected graph G with n>N vertices and with δ(G)≥c _k n, every orientation of G contains vertex disjoint copies of TT(h,k) that cover all but at most ∈n vertices. In the cases k=2 and k=3 the result is asymptotically tight. For k≥4, c _k cannot be improved to less than 1−2^{−0.5k(1+o(1))}. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the general additive divisor problem

We obtain a new upper bound for the sum Σ _h≤H Δ _k (N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ _k (N, h) is the (expected) error term in the asymptotic formula for Σ _N<n≤2N d _k (n)d _k (n + h), and d _k (n) is the divisor function generated by ζ(s) ^k . When k = 3, the result improves, for H ≥ N ^1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3.     

Restricted Point Configurations with Many Collinear {k}-Tuplets

   Abstract. Given k≥ 3 , denote by t' _k (N) the largest integer for which there is a set of N points in the plane, no k+1 of them on a line such that there are t' _k (N) lines, each containing exactly k of the points. Erdos (1962) raised the problem of estimating the order of magnitude of t' _k (N) . We prove that

On the law of the iterated logarithm for permuted lacunary sequences

It is known that for any smooth periodic function f the sequence (f(2 ^k x)) _k≥1 behaves like a sequence of i.i.d. random variables; for example, it satisfies the central limit theorem and the law of the iterated logarithm. Recently Fukuyama showed that permuting (f(2 ^k x)) _k≥1 can ruin the validity of the law of the iterated logarithm, a very surprising result. In this paper we present an optimal condition on (n _k ) _k≥1, formulated in terms of the number of solutions of certain Diophantine equations, which ensures the validity of the law of the iterated logarithm for any permutation of the sequence (f(n _k x)) _k≥1. A similar result is proved for the discrepancy of the sequence ({n _k x}) _k≥1, where {·} denotes the fractional part.     

Modular curves and bases for the spaces of cuspidal modular forms

Let Γ⊂SL ₂(ℝ) be a Fuchsian group of the first kind. For a character χ of Γ→ℂ^× of finite order, we define the usual space S _m (Γ,χ) of cuspidal modular forms of weight m≥0. For each ξ in the upper half–plane and m≥3, we construct cuspidal modular forms Δ _k,m,ξ,χ ∈S _m (Γ,χ) (k≥0) which represent the linear functionals f?\fracd^kfdz^k|_z=xf\mapsto\frac{d^{k}f}{dz^{k}}|_{z=\xi} in terms of the Petersson inner product. We write their Fourier expansion and use it to write an expression for the Ramanujan Δ-function. Also, with the aid of the geometry of the Riemann surface attached to Γ, for each non-elliptic point ξ and integer m≥3, we construct a basis of S _m (Γ,χ) out of the modular forms Δ _k,m,ξ ,χ (k≥0). For Γ=Γ ₀(N), we use this to write a matrix realization of the usual Hecke operators T _p for S _m (N,χ).     

Decrease rate of the probabilities ofε-deviations for the means of stationary processes

The asymptotic behavior asn → ∞ of the normed sumsσn =n ⁻¹ Σ _k ⁼⁰ⁿ⁻¹ Xk for a stationary processX = (X _n ,n ∈ ℤ) is studied. For a fixedε > 0, upper estimates for P(sup _k≥n |σ _k | ≥ε) asn → ∞ are obtained. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 366–372, September, 1998.     

On the law of the iterated logarithm for the discrepancy of 〈n k x〉

By a well known result of Philipp (1975), the discrepancy D _N (ω) of the sequence (n _k ω) _k≥1 mod 1 satisfies the law of the iterated logarithm under the Hadamard gap condition n _{k + 1}/n _k ≥ q > 1 (k = 1, 2, …). Recently Berkes, Philipp and Tichy (2006) showed that this result remains valid, under Diophantine conditions on (n _k ), for subexpenentially growing (n _k ), but in general the behavior of (n _k ω) becomes very complicated in the subexponential case. Using a different norming factor depending on the density properties of the sequence (n _k ), in this paper we prove a law of the iterated logarithm for the discrepancy D _N (ω) for subexponentially growing (n _k ) without number theoretic assumptions. C. Aistleitner, Research supported by FWF grant S9603-N13. I. Berkes, Research supported by FWF grant S9603-N13 and OTKA grants K 61052 and K 67961. Authors’ addresses: C. Aistleitner, Institute of Mathematics A, Graz University of Technology, Steyrergasse 30, 8010 Graz, Austria; I. Berkes, Institute of Statistics, Graz University of Technology, Steyrergasse 17/IV, 8010 Graz, Austria     

A characteristic property of spheres

Summary We prove: Let S be a closed n-dimensional surface in an(n+1)-space of constant curvature (n ≥ 2); k₁ ≥ ... ≥ k_n denote its principle curvatures. Let φ(ξ₁, ..., ξ_n) be such that . Then if φ(k₁, ..., k_n)=const on S and S is subject to some additional general conditions (those(II ₀) or(II) n^o 1), S is a sphere. To Enrico Bompiani on his scientific Jubilee     

Trigonometric Approximation of SO(N) Loops

This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a Hölder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order $\mathcal{O}(n^{-\alpha+\epsilon})This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a H?lder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order O(n^-a+e)\mathcal{O}(n^{-\alpha+\epsilon}) for n≥k, where k=k(Q) is determined by topological properties of the loop and ε>0 is arbitrarily small. The convergence rate is therefore ε-close to the optimal achievable rate of approximation. The construction of polynomial loops involves higher-order splitting methods for the matrix exponential. A novelty in this work is the factorization technique for SO(N) loops which incorporates the loops’ topological aspects.     

Range of Brownian Motion with Drift

Let (B _δ (t)) _{t ≥ 0} be a Brownian motion starting at 0 with drift δ > 0. Define by induction S ₁=− inf _{t ≥ 0} B _δ (t), ρ₁ the last time such that B _δ (ρ₁)=−S ₁, S ₂=sup_{0≤ t ≤ρ 1} B _δ (t), ρ₂ the last time such that B _δ (ρ₂)=S ₂ and so on. Setting A _k =S _k +S _k+1; k ≥ 1, we compute the law of (A ₁,...,A _k ) and the distribution of (B _δ (t+ρ l) − B _δ (ρ _l ); 0 ≤ t ≤ ρ _l-1 − ρ _l )_{2 ≤ l ≤ k} for any k ≥ 2, conditionally on (A ₁,...,A _k ). We determine the law of the range R _δ (t) of (B _δ (s)) _{s≥ 0} at time t, and the first range time θ_δ (a) (i.e. θ_δ (a)=inf{t > 0; R _δ (t) > a}). We also investigate the asymptotic behaviour of θ _δ (a) (resp. R _δ (t)) as a → ∞ (resp. t → ∞).     

Large Vertex-Disjoint Cycles in a Bipartite Graph

Let s≥2 and k be two positive integers. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n≥s k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s. Received: March 2, 1998 Revised: October 26, 1998     

An Eberhard-Like Theorem for Pentagons and Heptagons

Eberhard proved that for every sequence (p _k ), 3≤k≤r, k≠6, of nonnegative integers satisfying Euler’s formula ∑ _k≥3(6−k)p _k =12, there are infinitely many values p ₆ such that there exists a simple convex polyhedron having precisely p _k faces of size k for every k≥3, where p _k =0 if k>r. In this paper we prove a similar statement when nonnegative integers p _k are given for 3≤k≤r, except for k=5 and k=7 (but including p ₆). We prove that there are infinitely many values p ₅,p ₇ such that there exists a simple convex polyhedron having precisely p _k faces of size k for every k≥3. We derive an extension to arbitrary closed surfaces, yielding maps of arbitrarily high face-width. Our proof suggests a general method for obtaining results of this kind.     

On the set of discrete subgroups of bounded covolume in a semisimple group

In this noteG is a locally compact group which is the product of finitely many groups G_s(k_s)(s∈S), where k_s is a local field of characteristic zero and G_s an absolutely almost simplek _s-group, ofk _s-rank ≥1. We assume that the sum of the r_s is ≥2 and fix a Haar measure onG. Then, given a constantc > 0, it is shown that, up to conjugacy,G contains only finitely many irreducible discrete subgroupsL of covolume ≥c (4.2). This generalizes a theorem of H C Wang for real groups. His argument extends to the present case, once it is shown thatL is finitely presented (2.4) and locally rigid (3.2).     

EMBEDDINGS OF ONE KIND OF GRAPHS

The purpose of this paper is to display a new kind of simple graphs which belong to B. inwhich any graph has its orientable genus n,n≥3. Furthermore, for any integer k,1≤k≤n,there exists a graph B^kn of B. such that the non-orientable genus of B^kn is k.     

Spanning k-Trees of n-Connected Graphs

A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg _G (u) + deg _G (v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree.     

Square-bounded partitions and Catalan numbers

For each integer k≥1, we define an algorithm which associates to a partition whose maximal value is at most k a certain subset of all partitions. In the case when we begin with a partition λ which is square-bounded, i.e. λ=(λ ₁≥⋅⋅⋅≥λ _k ) with λ ₁=k and λ _k =1, applying the algorithm ℓ times gives rise to a set whose cardinality is either the Catalan number c _ℓ−k+1 (the self dual case) or twice that Catalan number. The algorithm defines a tree and we study the propagation of the tree, which is not in the isomorphism class of the usual Catalan tree. The algorithm can also be modified to produce a two-parameter family of sets and the resulting cardinalities of the sets are the ballot numbers. Finally, we give a conjecture on the rank of a particular module for the ring of symmetric functions in 2ℓ+m variables.     

Maximality of entropy in finite von Neumann algebras

It is shown that the entropy function H(N ₁,…,N _k ) on finite dimensional von Neumann subalgebras of a finite von Neumann algebra attains its maximal possible value H(⋁ℓ=1k N _ℓ) if and only if there exists a maximal abelian subalgebra A of ⋁ℓ=1k N _ℓ such that A=⋁ℓ=1k(A∩N _ℓ). Oblatum 24-IV-1997 & 6-V-1997     

The signed <Emphasis Type="Italic">k</Emphasis>-domination number of directed graphs

Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d _D ⁻ ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N ⁻[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $ \sum\nolimits_{v \in V} {f(v)} $ \sum\nolimits_{v \in V} {f(v)} . The signed k-domination number for a digraph D is γ _kS (D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γ _kS (D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.     

Nearly perfect matchings in regular simple hypergraphs

For every fixedk≥3 there exists a constantc _k with the following property. LetH be ak-uniform,D-regular hypergraph onN vertices, in which no two edges contain more than one common vertex. Ifk>3 thenH contains a matching covering all vertices but at mostc _k ND ^−1/(k−1). Ifk=3, thenH contains a matching covering all vertices but at mostc ₃ ND ^−1/2ln^3/2 D. This improves previous estimates and implies, for example, that any Steiner Triple System onN vertices contains a matching covering all vertices but at mostO(N ^1/2ln^3/2 N), improving results by various authors. Research supported in part by a USA-Israel BSF grant. Research supported in part by a USA-Israel BSF Grant.     

Constrained Minkowski Sums: A Geometric Framework for Solving Interval Problems in Computational Biology Efficiently

In this paper, we introduce the notion of a constrained Minkowski sum: for two (finite) point-sets P,Q⊆ℝ² and a set of k inequalities Ax≥b, it is defined as the point-set (P ⊕ Q) _Ax≥b ={x=p+q∣p∈P,q∈Q,Ax≥b}. We show that typical interval problems from computational biology can be solved by computing a set containing the vertices of the convex hull of an appropriately constrained Minkowski sum. We provide an algorithm for computing such a set with running time O(Nlog N), where N=|P|+|Q| if k is fixed. For the special case where P and Q consist of points with integer x ₁-coordinates whose absolute values are bounded by O(N), we even achieve a linear running time O(N). We thereby obtain a linear running time for many interval problems from the literature and improve upon the best known running times for some of them. The main advantage of the presented approach is that it provides a general framework within which a broad variety of interval problems can be modeled and solved. T. Bernholt gratefully acknowledges the Deutsche Forschungsgemeinschaft for the financial support (SFB 475, “Reduction of complexity in multivariate data structures”).