Factorization of Lipschitz functions and absolute convergence of Vilenkin-Fourier series

LetG be a Vilenkin group (i.e., an infinite, compact, metrizable, zero-dimensional Abelian group). Our main result is a factorization theorem for functions in the Lipschitz spaces \(\mathfrak{L}\mathfrak{i}\mathfrak{p}\) (α,p; G). As colloraries of this theorem, we obtain (i) an extension of a factorization theorem ofY. Uno; (ii) a convolution formula which says that \(\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha , r; G) = \mathfrak{L}\mathfrak{i}\mathfrak{p} (\beta , l; G)*\mathfrak{L}\mathfrak{i}\mathfrak{p} (\alpha - \beta , r; G)\) for 0<β<α<∞ and 1≤r≤∞; and (iii) an analogue, valid for allG, of a classical theorem ofHardy andLittlewood. We also present several results on absolute convergence of Fourier series defined onG, extending a theorem ofC. W. Onneweer and four results ofN. Ja. Vilenkin andA. I. Rubinshtein. The fourVilenkin-Rubinshtein results are analogues of classical theorems due, respectively, toO. Szász, S. B. Bernshtein, A. Zygmund, andG. G. Lorentz.     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.     

Mehrfache gitterförmige Kreis- und Kugelanordnungen

LetG be a lattice inR ⁿ and letS ₁ ,S ₂ , ... be the family of unit spheres whose centres are the lattice-points ofG. This set is called ak-fold lattice packing (k-fold lattice covering) if each point ofR ⁿ lies in at most (at least)k of the open (closed) spheresS _i . Letd _k ⁿ be the density of the closestk-fold lattice packing and letD _k ⁿ be the density of the thinnestk-fold lattice covering ofR ⁿ . In the present paper we are considering the following problem: For which valuesn≧2 andk≧2 are the inequalitiesd _k ⁿ >kd ₁ ⁿ ,D _k ⁿ ₁ ⁿ valid?Theorem 1:For all pairs (n, k), n≧3, k≧2, with the exception of (3, k), (4, k), k=3, 5, 7, 9, 11 and (5, 3) we prove d _k ⁿ >kd ₁ ⁿ .Theorem 2:For each k≧3 is D _k ² ₁ ² . The proofs make use of the works ofBlundon, Danzer, Few andHeppes.     

Kombinatorische Beweise eines Satzes von Birman und Hilden und eines Satzes von Magnus mit der Theorie der automorphen Mengen und der zugehörigen Zopfgruppenoperationen

We deal with the well-known operation ofARTIN?S Braid GroupB _n on the free groupF _n by automorphisms, and give a proof for a theorem ofBIRMAN/HILDEN (here Satz B) by showing, that the images of the generators ofF _n underB _n are of a special form (Satz C). The theory ofBRIESKORN?S Automorphic Sets comes in here. With similar methods we give a proof of a theorem of Magnus saying thatB _n operates on a certain polynomial ring effectively by automorphisms (here Satz 9.2).     

Kantorovič operators of second order

The Kantorovi? operators of second order are introduced byQ _n f= =(B _n+2 F)″ whereF is the double indefinite integraloff andB _n+2 the (n+2)-th Bernstein operator. The operatorsQ _n will reveal a close affinity to the so-called modified Bernstein operatorsC _n introduced bySchnabl [10] on a quite different way. The article contains investigations concerning the asymptotic behavior ofQ _n ^kn f (asn → ∞), where (k _n) is a sequence of natural numbers.     

Minimal decompositions of graphs into mutually isomorphic subgraphs

SupposeG _n={G ₁, ...,G _k } is a collection of graphs, all havingn vertices ande edges. By aU-decomposition ofG _n we mean a set of partitions of the edge setsE(G _t ) of theG _i , sayE(G _t )== \(\sum\limits_{j = 1}^r {E_{ij} } \) E _ij , such that for eachj, all theE _ij , 1≦i≦k, are isomorphic as graphs. Define the functionU(G _n) to be the least possible value ofr aU-decomposition ofG _n can have. Finally, letU _k (n) denote the largest possible valueU(G) can assume whereG ranges over all sets ofk graphs havingn vertices and the same (unspecified) number of edges. In an earlier paper, the authors showed that $$U_2 (n) = \frac{2}{3}n + o(n).$$ In this paper, the value ofU _k (n) is investigated fork>2. It turns out rather unexpectedly that the leading term ofU _k (n) does not depend onk. In particular we show $$U_k (n) = \frac{3}{4}n + o_k (n),k \geqq 3.$$      

Combinatorial models for the finite-dimensional Grassmannians

Let ? ⁿ be a linear hyperplane arrangement in ? ⁿ . We define two corresponding posetsG _k (? ⁿ andV _k (? ⁿ ) of oriented matroids, which approximate the GrassmannianG _k (? ⁿ ) and the Stiefel manifoldV _k (? ⁿ ). The basic conjectures are that the “OM-Grassmannian”G _k (? ⁿ ) has the homotopy type ofG _k (? ⁿ ), and that the “OM-Stiefel bundle” Δπ: ΔV _k (? ⁿ ) → ΔG _k (? ⁿ ) is a surjective map. These conjectures can be proved in some cases: we survey the known results and add some new ones. The conjectures fail if they are generalized to nonrealizable oriented matroids ? ⁿ .     

A note on propositional proof complexity of some Ramsey-type statements

A Ramsey statement denoted ${n \longrightarrow (k)^2_2}$ says that every undirected graph on n vertices contains either a clique or an independent set of size k. Any such valid statement can be encoded into a valid DNF formula RAM(n, k) of size O(n ^k ) and with terms of size ${\left(\begin{smallmatrix}k\\2\end{smallmatrix}\right)}$ . Let r _k be the minimal n for which the statement holds. We prove that RAM(r _k , k) requires exponential size constant depth Frege systems, answering a problem of Krishnamurthy and Moll [15]. As a consequence of Pudlák??s work in bounded arithmetic [19] it is known that there are quasi-polynomial size constant depth Frege proofs of RAM(4 ^k , k), but the proof complexity of these formulas in resolution R or in its extension R(log) is unknown. We define two relativizations of the Ramsey statement that still have quasi-polynomial size constant depth Frege proofs but for which we establish exponential lower bound for R.     

Strong approximation by Fourier--Laplace series on the unit sphere S n-1

We study the strong approximation properties of the Cesáro means of order δ of the Fourier--Laplace expansion of functions integrable on the unit sphere S ^n-1, where δ ≥λ? (n-2)/2, the latter being the critical index for Cesáro summability of Fourier--Laplace series on S ^n-1. The main purpose of this paper is to extend known results from the unit circle S ¹to the general sphere S ^n-1 with n≥3. We prove six theorems. To prove Theorems 1-3, our machinery is based on the equiconvergent operator E ^δ _N (f) of the Cesáro means σ^δ _N (f) on S ^n-1 introduced by Wang Kunyang for δ>-1. We prove in Theorem 6 that E ^δ _N (f) is also equiconvergent with σ^δ _N (f) for δ>0 in the case of strong approximation. To prove Theorems 4 and 5, we rely on known equivalence relations between K-functionals and moduli of continuity.     

On repeated games with general information function

For a class of repeated two-person zero-sum games with incomplete information it was proved byAumann andMaschler that limν _n exists,ν _n being the value of the game withn repetitions. If the players know at each stage the moves done by both players at all previous stages,Aumann andMaschler could prove that the error termδ _n=¦ν _n — limν _n ¦ satisfiesδ _n≤c/√n for somec>0. It was then shown byZamir that this bound is the lowest possible. In this paper it is shown that if previous moves are not always announced,δ _n may be of higher order of magnitude e.g.δ _n≥c/n ^1/3 for somec>0. New upper bounds forδ _n are given for two classes of games.     

On the relation between finitely and infinitely repeated games with incomplete information

For a class of repeated two-person zero-sum games with incomplete information it was proved byAumann andMaschler that \(\mathop {\lim }\limits_{n \to \infty } v_n\) exists,Ν _n being the value of the game withn repetitions. As for the speed of convergenceAumann andMaschler showed that the error termδ _n=¦Ν _n?limΝ _n¦ is bounded from above byc/√n for some positive constantc. Both results have been generalized byMertens andZamir. It is shown in this paper that the above mentioned theorem about the speed of convergence is sharp in the sense that there are games in whichδ _n≥c′/√n for some positive constantc′. However there are games for which δ_n is of a lower order of magnitude, for instancec′(logn)/n≤δ _n≤c (logn)/n orc′/n≤δ _n≤c/n. Sufficient conditions are given here for games to belong to one of these categories as well as examples of games from each category.     

On the relation of generalized Valiron summability to Cesàro summability

A family (V _a ^k ) of summability methods, called generalized Valiron summability, is defined. The well-known summability methods (B_α,γ), (E _ρ, (T_α), (S _β) and (V _a) are members of this family. In §3 some properties of the (B _α,γ) and (V _a ^k ) transforms are established. Following Satz II of Faulhaber (1956) it is proved that the members of the (V _a ^k ) family are all equivalent for sequences of finite order. This paper is a good illustration of the use of generalized Boral summability. The following theorem is established: Theorem.If s _n (n ≥ 0) isa real sequence satisfying $$\mathop {lim}\limits_{ \in \to 0 + } \mathop {lim inf}\limits_{m \to \infty } \mathop {min}\limits_{m \leqslant n \leqslant m \in \sqrt m } \left( {\frac{{S_n - S_m }}{{m^p }}} \right) \geqslant 0(\rho \geqslant 0)$$ , and if s_n →s (V _a ^k ) thens _n → s (C, 2ρ).     

The weighted Grammar constraint

We introduce the WeightedGrammar constraint and propose propagation algorithms based on the CYK parser and the Earley parser. We show that the traces of these algorithms can be encoded as a weighted negation normal form (WNNF), a generalization of NNF that allows nodes to carry weights. Based on this connection, we prove the correctness and complexity of these algorithms. Specifically, these algorithms enforce domain consistency on the WeightedGrammar constraint in time O(n ³). Further, we propose that the WNNF constraint can be decomposed into a set of primitive arithmetic constraint without hindering propagation.     

Gleichverteilte Folgen und differenzierbare Funktionen

We generalize a result ofHlawka about sums of the form $$\sum\limits_{n = 1}^N {(f(x_n + 1/N) - f(n)} ),$$ where (x _n ) _n ∈? is a uniformly distributed sequence mod 1.     

Uniforme Räume mit einer linear geordneten Basis

A. K. Steiner undE. F. Steiner described the socalled natural topology κ on spacesA ^B of transfinite sequences (a _β), β∈B,a _β∈A [J. Math. Anal. Appl.19, 174–178 (1967)]. These spaces generalize Baire's zerodimensional sequence-spaces. Using these spaces (A ^B, κ), we generalize two well known theorems of F. Hausdorff, W. Hurewicz, C. Kuratowski and K. Morita on metric spaces and their Lebesgue-dimension respectively, both involving Baire's sequence spaces. Thus we obtain a topological characterization of uniform spaces \((X,\mathfrak{U})\) with a linearly ordered base \(\mathfrak{B}\) of \(\mathfrak{U}\) .     

ON possible Turán densities

The Turán density π(F) of a family F of k-graphs is the limit as n → ∞ of the maximum edge density of an F-free k-graph on n vertices. Let Π _∞ ^(k) consist of all possible Turán densities and let Π _fin ^(k) ? Π _∞ ^(k) be the set of Turán densities of finite k-graph families. Here we prove that Π _fin ^(k) contains every density obtained from an arbitrary finite construction by optimally blowing it up and using recursion inside the specified set of parts. As an application, we show that Π _fin ^(k) contains an irrational number for each k ≥ 3. Also, we show that Π _∞ ^(k) has cardinality of the continuum. In particular, Π _∞ ^(k) ≠ Π _fin ^(k) .     

A generalization of the katona theorem for crosst-intersecting families

LetX be ann-element set and letA and? be families of subsets ofX. We say thatA and? are crosst-intersecting if |A ∩ B| ≥ t holds for all A ∈A and for allB ∈ ?. Suppose thatA and ? are crosst-intersecting. This paper first proves a crosst-intersecting version of Harper's Theorem:

1. There are two crosst-intersecting Hamming spheresA ₀,? ₀ with centerX such that |A| ≤ |A ₀| and|?| ≤ |? ₀| hold.
2. Suppose thatt ≥ 2 and that the pair of integers (|A) is maximal with respect to direct product ordering among pairs of crosst-intersecting families. Then,A and? are Hamming spheres with centerX.

Using these claims, the following conjecture of Frankl is proven:

1. Ifn + t = 2k ? 1 then |A| |?| ≤ max \(\left\{ {\left( {K_k^n + \left( {_{k - 1}^{n - 1} } \right)} \right)^2 ,K_k^n K_{k - 1}^n } \right\}\) holds, whereK _l ⁿ is defined as \(\left( {_n^n } \right)\left( {_{n - 1}^n } \right) + \cdots + \left( {_l^n } \right).\)
2. Ifn + t = 2k then |A| |? ≤ (K _k ⁿ )² holds.

The extremal configurations are also determined.     

On the Fourier transformation on spaces of (p,q)-multipliers

LetG denote a locally compact abelian topological group. The aim of the present paper is to prove an “intermediate” result between two well-known results ofL. Hörmander andG. I. Gaudry concerning the structure of the spaces ?_G?μ?t ^p,q (G).     

Asymptotic behaviour of the minima to a class of optimization problems for differential inclusions

Denoting byS _k (ξ _k ) the set of solutions of the Cauchy problem $\dot x \in F_k (t,x),x(0) = \xi _k $ , fork∈N∪{∞}, we prove that, under appropriate assumptions, the sequence {S _k (ξ _k )} _{k ∈ N} converges toS _∞(∈_∞) in the Kuratowski sense as well as in the Mosco sense. This result together with some facts from Γ-convergence theory are used to prove a result concerning the existence and the asymptotic behavior of the minima to the optimization problem $$\min \int_0^T {[g_k (t,x(t)) + h_k (t,\dot x(t))]} dt + \psi _k (\xi ),x \in S_k (\xi ),\xi \in K$$ withK a compact subset ofR ⁿ .     

On Riemann sums and Lebesgue integrals

Call a sequence of positive integers(m _k ) _k=1 ^∞ a chain ifm _k devidesm _k+1 and that it has dimensiond if it is a subset of the set of least common multiples ofd chains. In this paper we give a new and elementary proof that iff∈L(logL)^d?1([0, 1)) and(m _k ) _k=1 ^∞ is of dimensiond then $$\mathop {\lim }\limits_{N \to \infty } \frac{1}{N}\sum\limits_{n = 1}^N {f\left( {\left\{ {x + \frac{n}{{m_N }}} \right\}} \right)} = \int_X {fd\mu , a.e.,} $$ with respect to Lebesgue measure. This result was first proved byL. Dubins andJ. Pitman [2] using martingale theory.