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.     

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.     

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

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 → ∞).     

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).     

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     

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.     

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.     

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     

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.     

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.     

Ideal einstein,conformally flat and semi-symmetric immersions

Recently, B. Y. Chen introduced a new intrinsic invariant of a manifold, and proved that everyn-dimensional submanifold of real space formsR ^m (ε) of constant sectional curvature ε satisfies a basic inequality δ(n ₁,…,n _k )≤c(n ₁,…,n _k )H ²+b(n ₁,…,n _k )ε, whereH is the mean curvature of the immersion, andc(n ₁,…,n _k ) andb(n ₁,…,n _k ) are constants depending only onn ₁,…,n _k ,n andk. The immersion is calledideal if it satisfies the equality case of the above inequality identically for somek-tuple (n ₁,…,n _k ). In this paper, we first prove that every ideal Einstein immersion satisfyingn≥n ₁+…+n _k +1 is totally geodesic, and that every ideal conformally flat immersion satisfyingn≥n ₁+…+n _k +2 andk≥2 is also totally geodesic. Secondly we completely classify all ideal semi-symmetric hypersurfaces in real space forms. The author was supported by the NSFC and RFDP.