The maximum number of edges in a 3-graph not containing a given star

Suppose that is a collection of 3-subsets of{1, 2,..., n} which does not contain ak-star (i.e.,k 3-sets any two of which intersect in the same singleton). Fork 3 andn n ₀ (k), the collections having largest possible sizes are determined.     

Covering a Finite Abelian Group by Subset Sums

Let G be an abelian group of order n. The critical number c(G) of G is the smallest s such that the subset sums set (S) covers all G for eachs ubset SG\{0} of cardinality |S|s. It has been recently proved that, if p is the smallest prime dividing n and n/p is composite, then c(G)=|G|/p+p–2, thus establishing a conjecture of Diderrich.We characterize the critical sets with |S|=|G|/p+p–3 and (S)=G, where p3 is the smallest prime dividing n, n/p is composite and n7p²+3p.We also extend a result of Diderrichan d Mann by proving that, for n67, |S|n/3+2 and S=G imply (S)=G. Sets of cardinality for which (S) =G are also characterized when n183, the smallest prime p dividing n is odd and n/p is composite. Finally we obtain a necessary and sufficient condition for the equality (G)=G to hold when |S|n/(p+2)+p, where p5, n/p is composite and n15p².* Work partially supported by the Spanish Research Council under grant TIC2000-1017 Work partially supported by the Catalan Research Council under grant 2000SGR00079     

Sur les plus grands facteurs premiers d'un entier

Let and, for each integern such that (n)k, denote byP _k (n) itsk ^th largest prime factor. Further, given a set of primesQ of positive density <1 satisfying a certain regularity condition, defineP(n, Q), as the largest prime divisor ofn belonging toQ, assuming thatP(n,Q)=+ if no such prime factor exists. We provide estimates of , fork2, and of . We also study the median value of the functionP(n,Q) and that of the functionP _k (n) for eachk1.     

Extremes of a Gaussian Process and the Constant H α

Consider a triangular array of standard Gaussian random variables {_n,i, i 0, n 1} such that {_n,i, i 0} is a stationary normal sequence for each n 1. Let _n,k = corr(_n,i,_n,i+k). If (1-_n,k)log n _k (0,) as n for some k, then the locations where the extreme values occur cluster and the limiting distribution of the maxima is still the Gumbel distribution as in the stationary or i.i.d. case, but shifted by a parameter measuring the clustering. Triangular arrays of Gaussian sequences are used to approximate a continuous Gaussian process X(t), t 0. The cluster behavior of the random sequence refers to the behavior of the extremes values of the continuous process. The relation is analyzed. It reveals a new definition of the constants H used for the limiting distribution of maxima of continuous Gaussian processes and provides further understanding of the limit result for these extremes.     

On convergence subsystems of orthonormal systems

It is proved that for any sequence {R _k} _k=1 of real numbers satisfyingR _kk (k1) andR _k=o(k log₂ k),k, there exists an orthonormal system {n _k(x)} _n=1 ,x (0;1), such that none of its subsystems {n _k(x)} _k=1 withn _kR_k (k1) is a convergence subsystem.     

Über nullstellenfreie Gebiete von ζ(itk) (s)

Let ^(itk) (s) denote thek-th derivative of the Riemann Zeta-function,s=+it, ,t real numbers,k1 rational integers. Using ideas fromT. C. Titchmarsh and from a paper ofR. Spira, lower bounds are derived for |^(itk)(s)|, |^(itk)(1-s) for >1 and some infinitely many, sufficiently large values oft. Further let be an algebraic number of degreen and heightH; then a lower bound for |^(itk)(its)|, dependent onn, H, k is established for alln,H1,k3, 2+7k/4 and all realt.     

On the chromatic uniqueness of the graphW(n,n − 2, k)

This paper shows that the graphW(n, n – 2, k) is chromatically unique for any even integern 6 and any integerk 1.     

The Law of the Logarithm for Weighted Sums of Independent Random Variables

Let X,X _n ;n1 be a sequence of real-valued i.i.d. random variables with E(X)=0. Assume B(u) is positive, strictly increasing and regularly-varying at infinity with index 1/2<1. Set b _n =B(n),n1. If

Quadrilaterals and pentagons in arrangements of lines

Let p _k denote the number of k-sided faces in an arrangement of n5 lines in the real projective plane. B. Grünbaum has shown that p ₄1/2n(n–3) and has conjectured that equality can occur only for simple arrangements. We prove this conjecture here. We also show that 4p ₄+5p ₅3n holds for every simple arrangement of n4 lines. This latter result is a strengthening of a theorem of T. O. Strommer.     

Two combinatorial problems on posets

Bialostocki proposed the following problem: Let nk2 be integers such that k|n. Let p(n, k) denote the least positive integer having the property that for every poset P, |P|p(n, k) and every Z _k -coloring f: P Z _k there exists either a chain or an antichain A, |A|=n and _aA f(a) 0 (modk). Estimate p(n, k). We prove that there exists a constant c(k), depends only on k, such that (n+k–2)²–c(k) p(n, k) (n+k–2)²+1. Another problem considered here is a 2-dimensional form of the monotone sequence theorem of Erdös and Szekeres. We prove that there exists a least positive integer f(n) such that every integral square matrix A of order f(n) contains a square submatrix B of order n, with all rows monotone sequences in the same direction and all columns monotone sequences in the same direction (direction means increasing or decreasing).     

On the unique finite (SI) decomposition of the Jordan operator ⊕ i=1 n S(θ) for certain inner function θ

In this paper, we have proven that for the Jordan blockS() withS() (SI), _i=1 ⁿ S() =S() ⁽ⁿ⁾ (n 1) has unique finite (SI) decomposition up to a similarity. As result, we obtain that ifV is a Volterra operator onH=L ²([0, 1]), thenV ⁽ⁿ⁾ has unique finite (SI) decomposition.This project was supported by National Natural Science Foundation of China.     

On the distribution of square-full and cube-full numbers

There are many results on the distribution of square-full and cube-full numbers. In this article the distribution of these numbers are studied in more detail. Suchk-full numbers (k=2,3) are considered which are at the same time 1-free (1k+2). At first an asymptotic result is given for the numberN _k,1(x) ofk-full and 1-free numbers not exceedingx. Then the distribution of these numbers in short intervals is investigated. We obtain different estimations of the differenceN _k,1(x+h)–N_k,1(x) in the casesk=2, 1=4,5,6,7,18 andk=3, 1=5,6,7, 18.     

Quick gossiping without duplicate transmissions

There aren people, each knowing a gossip. They communicate by phone calls, and whenever two persons talk they tell all information they know at that time. Denote byf(n) the minimal number of necessary calls when everybody hears each gossip exactly once. We prove thatf(n) = 2.25n – 6 ifn = 4k, k 2 and 2.25n – 4.5 f(n) 2.25n – 3.5 ifn = 4k + 2,k 5. (Ifn is odd, orn = 4k + 2, 0 <k < 5 then there are no appropriate sequences of calls at all.)     

Sub-Ramsey numbers for arithmetic progressions

Letm 3 andk 1 be two given integers. Asub-k-coloring of [n] = {1, 2,...,n} is an assignment of colors to the numbers of [n] in which each color is used at mostk times. Call an arainbow set if no two of its elements have the same color. Thesub-k-Ramsey number sr(m, k) is defined as the minimumn such that every sub-k-coloring of [n] contains a rainbow arithmetic progression ofm terms. We prove that((k – 1)m ²/logmk) sr(m, k) O((k – 1)m ² logmk) asm , and apply the same method to improve a previously known upper bound for a problem concerning mappings from [n] to [n] without fixed points.Research supported in part by Allon Fellowship and by a Bat Sheva de-Rothschild grant.Research supported in part by the AKA Research Fund of the Hungarian Academy of Sciences, grant No. 1-3-86-264.     

Asymptotic behavior of the dwell time distribution for a random walk on a positive semi-axis

Let ₁, ₂, ... be a sequence of independent identically distributed random variables with zero means. We consider the functional _n = _k=o ⁿ (S _k ) where S₁=0, S_k= _i=1 ^k _i (k1) and(x)=1 for x0,(x) = 0 for x<0. It is readily seen that _n is the time spent by the random walk S_n, n0, on the positive semi-axis after n steps. For the simplest walk the asymptotics of the distribution P (_n = k) for n and k, as well as for k = O(n) and k/n<1, was studied in [1]. In this paper we obtain the asymptotic expansions in powers of n^–1 of the probabilities P(h_n = nx) and P(nx_{1 n} nx₂) for 0<₁, x = k/n ₂<1, 0<₁x₁2₂<1.Translated from Matematicheskie Zametki, Vol. 15, No. 4, pp. 613–620, April, 1974.The author wishes to thank B. A. Rogozin for valuable discussions in the course of his work.     

Regressions and monotone chains II: The poset of integer intervals

A regressive function (also called a regression or contractive mapping) on a partial order P is a function mapping P to itself such that (x)x. A monotone k-chain for is a k-chain on which is order-preserving; i.e., a chain x ₁<...ksuch that (x ₁)...(x_k). Let P _nbe the poset of integer intervals {i, i+1, ..., m} contained in {1, 2, ..., n}, ordered by inclusion. Let f(k) be the least value of n such that every regression on P _nhas a monotone k+1-chain, let t(x,j) be defined by t(x, 0)=1 and t(x,j)=x ^t(x,j–1). Then f(k) exists for all k (originally proved by D. White), and t(2,k) < f(K) <t( + _k, k) , where _k 0 as k. Alternatively, the largest k such that every regression on P _nis guaranteed to have a monotone k-chain lies between lg^*(n) and lg^*(n)–2, inclusive, where lg^*(n) is the number of appliations of logarithm base 2 required to reduce n to a negative number. Analogous results hold for choice functions, which are regressions in which every element is mapped to a minimal element.     

Sets of tiles with a prescribed number of tilings

Summary For every k2 and r1 there exists a set of k prototiles that admits exactly r distinct tilings. All the tilings obtained are periodic.     

Extremal Eigenvalues of the Laplacian in a Conformal Class of Metrics: The `Conformal Spectrum'

Let M be a compact connected manifold of dimension n endowed witha conformal class C ofRiemannian metrics of volume one. For any integer k 0, we consider the conformal invariant _k ^c (C) defined as the supremum of the k-th eigenvalue _k (g) of the Laplace–Beltrami operator _g , where g runs over C.First, we give a sharp universal lower bound for _k ^c (C) extending to all k a result obtained by Friedlander andNadirashvili for k = 1. Then, we show that the sequence \{ _k ^c (C)\}, that we call `conformal spectrum',is strictly increasing and satisfies, k 0, _k+1 ^c (C) ^n/2– _k ^c (C) ^n/2 n ^n/2 _n , where _n is the volume of the n-dimensionalstandard sphere.When M is an orientable surface of genus , we also considerthe supremum _k ^top()of _k (g) over theset of all the area one Riemannian metrics on M, and study thebehavior of _k ^top() in terms of .     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.