The number of partial orders of fixed width

We investigate the approximate number of n-element partial orders of width k, for each fixed k. We show that the number of width 2 partial orders with vertex set {1, 2, ..., n} is

The dimension of interior levels of the Boolean lattice

LetP(k,r;n) denote the containment order generated by thek-element andr-element subsets of ann-element set, and letd(k,r;n) be its dimension. Previous research in this area has focused on the casek=1.P(1,n–1;n) is the standard example of ann-dimensional poset, and Dushnik determined the value ofd(1,r;n) exactly, whenr2 . Spencer used the Erdös-Szekeres theorem to show thatd(1, 2;n) lg lgn, and he used the concept of scrambling families of sets to show thatd(1,r;n)=(lg lgn) for fixedr. Füredi, Hajnal, Rödl and Trotter proved thatd(1, 2;n)=lg lgn+(1/2+o(1))lg lg lgn. In this paper, we concentrate on the casek2. We show thatP(2,n–2;n) is (n–1)-irreducible, and we investigated(2,r;n) whenr2 , obtaining the exact value for almost allr.The research was supported in part by NSF grant DMS 9201467.The research was supported in part by the Universities in Russia program.     

On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>)

The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K²(2k+1, k))4k when k is odd and (K²(2k+1, k))4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K²(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003     

A Sharp Bound for the Number of Sets that Pairwise Intersect at <Emphasis Type="Italic">k</Emphasis> Positive Values

In this paper we prove that if is a set of k positive integers and {A ₁, ..., A _m } is a family of subsets of an n-element set satisfying , for all 1 i < j m, then . The case k = 1 was proven 50 years ago by Majumdar.     

Hypersurfaces of restricted type in Minkowski space

A submanifold M _n ^r of Minkowski space is said to be of restricted type if its shape operator with respect to the mean curvature vector is the restriction of a fixed linear transformation of to the tangent space of M _n ^r at every point of M _n ^r . In this paper we completely classify hypersurfaces of restricted type in . More precisely, we prove that a hypersurface of is of restricted type if and only if it is either a minimal hypersurface, or an open part of one of the following hypersurfaces: S ^k × , S _k ¹ × , H ^k × , S _n ¹ , H ⁿ , with 1kn–1, or an open part of a cylinder on a plane curve of restricted type.This work was done when the first and fourth authors were visiting Michigan State University.Aangesteld Navorser N.F.W.O., Belgium.     

Divisibility of Certain Partition Functions by Powers of Primes

Let be the prime factorization of a positive integer k and let b _k (n) denote the number of partitions of a non-negative integer n into parts none of which are multiples of k. If M is a positive integer, let S _k (N; M) be the number of positive integers N for which b _k(n ) 0(mod M). If we prove that, for every positive integer j In other words for every positive integer j, b _k(n) is a multiple of for almost every non-negative integer n. In the special case when k=p is prime, then in representation-theoretic terms this means that the number ofp -modular irreducible representations of almost every symmetric groupS _n is a multiple of p ^j. We also examine the behavior of b _k(n) (mod ) where the non-negative integers n belong to an arithmetic progression. Although almost every non-negative integer n (mod t) satisfies b _k(n) 0 (mod ), we show that there are infinitely many non-negative integers n r (mod t) for which b _k(n) 0 (mod ) provided that there is at least one such n. Moreover the smallest such n (if there are any) is less than 2 .     

A New Family of Ternary Sequences with Ideal Two-level Autocorrelation Function

Let be a primitive element of . Letd=3^2k -3 ^k +1 wheren=3k. We show that the ternary sequence s(t) given by has a two-level idealautocorrelation function.     

The order dimension of two levels of the Boolean lattice

LetB _n(s, t) denote the partially ordered set consisting of alls-subsets andt-subsets of ann-element underlying set where these sets are ordered by inclusion. Answering a question of Trotter we prove that dim(B _n(k, n–k))=n–2 for 3k<(1/7)n ^1/3. The proof uses extremal hypergraph theory.     

Manifolds with involution

In this paper, we determine the groups (k _i are odd), (k _i are odd and (k _i are even andn>k _l ), (k _i are even andn>k _l ), (k _i are even andn>k _l ,k _l 12),J _n ^1,2,J _n ^2,3,J _n ^1,4. And we obtain the relation Im _n ^k =J _n ^l,k .     

Asymptotic solution of a turán-type problem

LetA, B, C be disjointk-element sets. It is shown that if a 2k-graph onn vertices contains no three edges of the formA B, A C, B C then it has at most edges. Moreover, this is essentially best possible.     

New constructions for De Bruijn tori

A De Bruijn torus is a periodicd-dimensionalk-ary array such that eachn ₁ × ... ×n _d k-ary array appears exactly once with the same period. We describe two new methods of constructing such arrays. The first is a type of product that constructs ak ₁ k ₂ -ary torus from ak ₁ -ary torus and ak ₂ -ary torus. The second uses a decomposition of ad-dimensional torus to produce ad+1 dimensional torus. Both constructions will produce two dimensionalk-ary tori for which the period is not a power ofk. In particular, for and for all natural numbers (n ₁ , n ₂ ), we construct 2-dimensionalk-ary De Bruijn tori with order n ₁ , n ₂ and period where .Dedicated to the memory of Tony BrewsterPartially supported by NSF grant DMS-9201467Partially supported by a grant from the Reidler Foundation     

Verifiable Partial Escrow of Integer Factors

We construct an efficient interactive protocol for realizing verifiable partial escrow of the factors of an integer n with time-delayed and threshold key recovery features. The computational cost of the new scheme amounts to 10k P multiplications of numbers of size of P, where P is a protocol parameter which permits n of size up to ( P) - 4 to be dealt with and k is a security parameter which controls the error probability for correct key escrow under 1/2^k. The new scheme realizes a practical method for fine tuning the time complexity for factoring an integer, where the complexity tuning has no respect to the size of the integer.     

On Small Sumsets in (ℤ/2ℤ)<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

It is proved that any subset of (/2)ⁿ, having k elements, such that (with c<4), is contained in a subgroup of order at most u^–1k where u=u(c)>0 is an explicit function of c which does not depend on k nor on n. This improves by a radically different method the corresponding bounds deduced from a more general result of I. Z. Ruzsa.     

Higher order asymptotic theory for normalizing transformations of maximum likelihood estimators

Suppose thatX _n =(X ₁,...X _n) is a collection ofm-dimensional random vectorsX _i forming a stochastic process with a parameter . Let be the MLE of . We assume that a transformationA( ) of has thek-thorder Edgeworth expansion (k=2,3). IfA extinguishes the terms in the Edgeworth expansion up tok-th-order (k2), then we say thatA is thek-th-order normalizing transformation. In this paper, we elucidate thek-th-order asymptotics of the normalizing transformations. Some conditions forA to be thek-th-order normalizing transformation will be given. Our results are very general, and can be applied to the i.i.d. case, multivariate analysis and time series analysis. Finally, we also study thek-th-order asymptotics of a modified signed log likelihood ratio in terms of the Edgeworth approximation.Research supported by the Office of Naval Research Contract N00014-91-J-1020.     

The Maximum Size Of Graphs With A Unique<Emphasis Type="Italic">k</Emphasis>- Factor

For suitable positive integers n and k let m(n, k) denote the maximum number of edges in a graph of order n which has a unique k-factor. In 1964, Hetyei and in 1984, Hendry proved for even n and , respectively. Recently, Johann confirmed the following conjectures of Hendry: for and kn even and for n = 2kq, where q is a positive integer. In this paper we prove for and kn even, and we determine m(n, 3).     

The Method of Extremal Metric in Extremal Decomposition Problems with Free Parameters

Let a₁,..., a_n be a system of distinct points on the z-sphere , and let be a system of all non-overlapping simply-connected domains D₁,..., D_n on such that a_k ∈ D_k, k = 1,..., n. Let M (D_k, a_k) be the reduced module of the domain D_k with respect to the point a_k ∈ Dk. In the present paper, we solve some problems concerning the maximum of weighted sums of the reduced modules M (D_k, a_k) in certain families of systems of domains {D_k} described above, where the systems of points {a_k} satisfy prescribed symmetry conditions. In each case, the proof is based on an explicit construction of an admissible metric of the module problem, which is equivalent to the extremal problem under consideration, from known extremal metrics of simpler module problems. Bibliography: 7 titles.__________Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 302, 2003, pp. 52–67.     

Upper bounds for prime <Emphasis Type="Italic">k</Emphasis>-tuples of size log <Emphasis Type="Italic">N</Emphasis> and oscillations

We prove the estimate for the number E_k(N) of k-tuples (n + a₁,..., n + a_k) of primes not exceeding N, for k of size c₁ log N and N sufficiently large. A bound of this strength was previously known in the special case < only, (Vaughan, 1973). For general a_i this is an improvement upon the work of Hofmann and Wolke (1996). The number of prime tuples of this size has considerable oscillations, when varying the prime pattern. Received: 20 December 2002     

Large empty convex polygons in k-convex sets

A point set is k-convex if there are at most k points of in any triangle having its vertices in . Károlyi, Pach and Tóth [6] showed that if a 1-convex set has sufficiently many points, then it contains an arbitrarily large emtpy convex polygon. They also constructed exponentially large 1-convex sets that contain no empty convex n-gons. Here we shall give an exponential upper bound to the number of points needed. Valtr [8] proved a similar result for k-convex sets. In this paper we improve his upper bound and give an elementary proof of the statement.