A Ramsey-Sperner theorem

Letn≥k≥1 be integers and letf(n, k) be the smallest integer for which the following holds: If ℱ is a family of subsets of ann-setX with |ℱ|<f(n,k) then for everyk-coloring ofX there existA B ∈ ℱ,A∈B, A⊂B such thatB-A is monochromatic. Here it is proven that for a fixedk there exist constantsc _k andd _k such that and ask→∞. The proofs of both the lower and the upper bounds use probabilistic methods.     

The expected number of parts in a partition ofn

Forn a positive integer letp(n) denote the number of partitions ofn into positive integers and letp(n,k) denote the number of partitions ofn into exactlyk parts. Let , thenP(n) represents the total number of parts in all the partitions ofn. In this paper we obtain the following asymptotic formula for .     

The Threshold for the Erdos, Jacobson and Lehel Conjecture to Be True

Let σ（k, n） be the smallest even integer such that each n-term positive graphic sequence with term sum at least σ（k, n） can be realized by a graph containing a clique of k ＋ 1 vertices. Erdos et al. （Graph Theory, 1991, 439-449） conjectured that σ（k, n） = （k - 1）（2n- k） ＋ 2. Li et al. （Science in China, 1998, 510-520） proved that the conjecture is true for k 〉 5 and n ≥ （k2） ＋ 3, and raised the problem of determining the smallest integer N（k） such that the conjecture holds for n ≥ N（k）. They also determined the values of N（k） for 2 ≤ k ≤ 7, and proved that [5k-1/2] ≤ N（k） ≤ （k2） ＋ 3 for k ≥ 8. In this paper, we determine the exact values of σ（k, n） for n ≥ 2k＋3 and k ≥ 6. Therefore, the problem of determining σ（k, n） is completely solved. In addition, we prove as a corollary that N（k） -= [5k-1/2] for k ≥6.     

Tight Lower Bounds on the Size of a Maximum Matching in a Regular Graph

In this paper we study tight lower bounds on the size of a maximum matching in a regular graph. For k ≥3, let G be a connected k-regular graph of order n and let α′(G) be the size of a maximum matching in G. We show that if k is even, then , while if k is odd, then . We show that both bounds are tight. Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Integration and Lipschitz functions

The aim of the paper is to prove that every f ∈ L ¹([0,1]) is of the form f = , where j _n,k is the characteristic function of the interval [k- 1 / 2 ⁿ , k / 2 ⁿ ) and Σ _n=0^∞Σ _k=1²ⁿ |a _n,k | is arbitrarily close to ||f|| (Theorem 2). It is also shown that if μ is any probabilistic Borel measure on [0,1], then for any ɛ > 0 there exists a sequence (b _n,k ) _n≧0 ^k=1,...,2n of real numbers such that and for each Lipschitz function g: [0,1] → ℝ (Theorem 3).      

Sufficient and necessary conditions for limit laws on lag sums of I. I. D. R. V. S

Let {X, X _n ;n>-1} be a sequence of i.i.d.r.v.s withEX=0 andEX ²=σ²(0 < σ < ∞). we obtain some sufficient and necessary conditions for

Precise Rates in the Law of Iterated Logarithm for the Moment of I.I.D. Random Variables

Let{X,Xn;n≥1} be a sequence of i,i.d, random variables, E X = 0, E X^2 = σ^2 〈 ∞.Set Sn=X1＋X2＋…＋Xn,Mn=max k≤n│Sk│,n≥1.Let an=O（1/loglogn）.In this paper,we prove that,for b〉-1,lim ε→0 →^2（b＋1）∑n=1^∞ （loglogn）^b/nlogn n^1/2 E{Mn-σ（ε＋an）√2nloglogn}＋σ2^-b/（b＋1）（2b＋3）E│N│^2b＋3∑k=0^∞ （-1）k/（2k＋1）^2b＋3 holds if and only if EX=0 and EX^2=σ^2〈∞.     

Minimal rates of entropy convergence for completely ergodic systems

If (X,T) is a completely ergodic system, then there exists a positive monotone increasing sequence {a _n } _n ^1/∞ with lim _n →∞a _n =∞ and a positive concave functiong defined on [1, ∞) for whichg(x)/x ² isnot integrable such that for all nontrivial partitions α ofX into two sets.     

Fully-Dynamic Min-Cut*

We show that we can maintain up to polylogarithmic edge connectivity for a fully-dynamic graph in worst-case time per edge insertion or deletion. Within logarithmic factors, this matches the best time bound for 1-edge connectivity. Previously, no o(n) bound was known for edge connectivity above 3, and even for 3-edge connectivity, the best update time was O(n^2/3), dating back to FOCS'92. Our algorithm maintains a concrete min-cut in terms of a pointer to a tree spanning one side of the cut plus ability to list the cut edges in O(log n) time per edge. By dealing with polylogarithmic edge connectivity, we immediately get a sampling based expected factor (1+o(1)) approximation to general edge connectivity in time per edge insertion or deletion. This algorithm also maintains a pointer to one side of a near-minimal cut, but if we want to list the cut edges in O(log n) time per edge, the update time increases to . * A preliminary version of this work was presented at the The 33rd ACM Symposium on Theory of Computing( STOC) [22], Crete, Greece, July 2001.     

A fixed-parameter-tractable algorithm for set packing

1. IntroductionIt is a useful and challenging task to find efficient algorithms for many computationalhard problems. Recently, the research on Fixed-Parameter nactable Theory arouses muchinterest. FOr example, different fixed- p ax amet er- t rac t ab le- algori t hms for many well- knowndecisio11 pruble11ls illc1udi11g 3-dimellsio11al IIlatchiIlg: a11d vertex--cover Problen1 have beenPrese11ted in [1 8]. Jia11er Chen, DoIlald K. FYiesen al1d Weijia Jia proPosed a coll1pletelynew appro…     

Some inequalities about mixed volumes

We prove inequalities about the quermassintegralsV _k (K) of a convex bodyK in ℝ ⁿ (here,V _k (K) is the mixed volumeV((K, k), (B _n ,n − k)) whereB _n is the Euclidean unit ball). (i) The inequality

Directeds-t numberings,Rubber bands,and testing digraphk-vertex connectivity

LetG=(V, E) be a directed graph andn denote |V|. We show thatG isk-vertex connected iff for every subsetX ofV with |X| =k, there is an embedding ofG in the (k–1)-dimensional spaceR ^k–1,fVR ^k–1, such that no hyperplane containsk points of {f(v)|vV}, and for eachvV–X, f(v) is in the convex hull of {f(w)| (v, w)E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in Rubber bands, convex embeddings and graph connectivity,Combinatorica 8 (1988), 91–102.Using this characterization, a directed graph can be tested fork-vertex connectivity by a Monte Carlo algorithm in timeO((M(n)+nM(k)) · (logn)) with error probability<1/n, and by a Las Vegas algorithm in expected timeO((M(n)+nM(k)) ·k), whereM(n) denotes the number of arithmetic steps for multiplying twon×n matrices (M(n)=O(n ^2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities fork>n ^0.19; e.g., for , the factor of improvement is >n ^0.62. Both algorithms have processor efficient parallel versions that run inO((logn)²) time on the EREW PRAM model of computation, using a number of processors equal to logn times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at leastn ²/(logn)³ while having the same running time.Generalizing the notion ofs-t numberings, we give a combinatorial construction of a directeds-t numbering for any 2-vertex connected directed graph.     

Precise asymptotics in self-normalized sums of iterated logarithm for multidimensionally indexed random variables

In the case of Zd (d ≥ 2)-the positive d-dimensional lattice points with partial ordering ≤, {Xk,k ∈ Zd } i.i.d. random variables with mean 0, Sn = ∑k≤nXk and Vn2 = ∑j≤nX2j, the precise asymptotics for ∑n1/|n|(log|n|)dP(|Sn/vn|≥ ε√loglog|n|) and ∑n(logn|)δ/|n|(log|n|)d-1 P(|Sn/Vn| ≥ ε√log n), as ε ↘ 0, is established.     

On the integersn for which Ω(n)=k (II)

Let (n) be the number of prime divisors ofn, counted with multiplicity. We denote byS(x, k) the set of thenx for which (n)=k, and byV _p(n) the exponent of the primep in the factorization ofn. In a previous paper we proved a result which implies that, ify=x/2 ^k tends to infinity withk>2loglogx where >1, then the distribution of the numbers on the setS(x, k) converges to the normal distribution of Gauss. Here, besides a slight improvement of that result, we give, for the moment of orderq of the above mentioned distribution, a formula which holds uniformly for 2loglogxklog (x/3)/log2 where 1<<3/2.     

A note on symbolic and ordinary powers of homogeneous ideals

In this note we are interested in the graded modulesM _k=I^(k)/I^k and , whereI is a saturated ideal in the homogeneous coordinate ringS=K[x₀,…,x_n] of ℙⁿ,I ^(k) is the symbolic power and is the saturation of the ordinary power. Very little is known about these modules, and we provide a bound on their diameters, we compute the Hilbert functions and we study some characteristic submodules in the special case ofn+1 general points in ℙⁿ.

---

Sunto In questa nota siamo interessati ai moduli graduatiM _k=I(k)/I^k e , doveI è un ideale saturato nell'anello delle coordinate omogeneeS:=K[x₀,…,x_n] di ℙⁿ,I ^(k) è la potenza simbolica e è la saturazione della potenza ordinaria. Poco è noto su questi moduli e qui viene fornito un limite superiore ai loro diametri. Ne calcoliamo inoltre le funzioni di Hilbert e studiamo alcuni sottomoduli caratteristici nel caso speciale din+1 punti in posizione generale, in ℙⁿ.

     

A construction of inflation rules based onn-fold symmetry

Summary In analogy to the well-known tilings of the euclidean plane by Penrose rhombs (or, to be more precise, to the equivalent tilings by Robinson triangles) we give a construction of an inflation rule based on then-fold symmetryD _nfor everyn greater than 3 and not divisible by 3. For givenn the inflation factor η can be any quotient as well as any product where . The construction is based on the system ofn tangents of the well-known deltoidD, which form angles with the ζ-axis of typevπ/n. None of these tilings permits two linearly independent translations. We conjecture that they have no period at all. For some of them the Fourier transform contains a ℤ-module of Dirac deltas. Editors' note: This paper was accepted for the special issue ofDiscrete & Computational Geometry (Volume 13, Numbers 3–4) devoted to the László Fejes Tóth, Festschrift, but was not received in final form in time to appear in that issue. Research supported by the DFG and the Fritz Thyssen Stiftung.     

Asymptotics for the standard and the Capelli identities

Let {c _n (St _k )} and {c _n (C _k )} be the sequences of codimensions of the T-ideals generated by the standard polynomial of degreek and by thek-th Capelli polynomial, respectively. We study the asymptotic behaviour of these two sequences over a fieldF of characteristic zero. For the standard polynomial, among other results, we show that the following asymptotic equalities hold:

The complexity and depth of Boolean circuits for multiplication and inversion in some fields <Emphasis Type="Italic">GF</Emphasis>(2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>)

Let n = (p − 1) · p ^k , where p is a prime number such that 2 is a primitive root modulo p, and 2 ^p−1 − 1 is not a multiple of p ². For a standard basis of the field GF(2 ⁿ ), a multiplier of complexity O(log log p)n log n log log _p n and an inverter of complexity O(log p log log p)n log n log log _p n are constructed. In particular, in the case p = 3 the upper bound

Volume Distortion for Subsets of Euclidean Spaces

In Rao (Proceedings of the 15th Annual Symposium on Computational Geometry, pp. 300–306, 1999), it is shown that every n-point Euclidean metric with polynomial aspect ratio admits a Euclidean embedding with k-dimensional distortion bounded by , a result which is tight for constant values of k. We show that this holds without any assumption on the aspect ratio and give an improved bound of . Our main result is an upper bound of independent of the value of k, nearly resolving the main open questions of Dunagan and Vempala (Randomization, Approximation, and Combinatorial Optimization, pp. 229–240, 2001) and Krauthgamer et al. (Discrete Comput. Geom. 31(3):339–356, 2004). The best previous bound was O(log n), and our bound is nearly tight, as even the two-dimensional volume distortion of an n-vertex path is . This research was done while the author was a postdoctoral fellow at the Institute for Advanced Study, Princeton, NJ.     

The number oft-wise balanced designs

We prove that the number oft-wise balanced designs of ordern is asymptotically , provided that blocks of sizet are permitted. In the process, we prove that the number oft-profiles (multisets of block sizes) is bounded below by and above by for constants c₂>c₁>0.