Symmetric block bases in finite-dimensional normed spaces

It is shown that for 1 ≦p < ∞, any basisC-equivalent to the unit vector basis ofl _p ⁿ has a (1 + ε)-symmetric block basis of cardinality proportional ton/logn. When 1 <p < ∞, an upper bound proportional ton log logn/logn is also obtained. These results extend results of Amir and Milman in [2].     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

Ann-dimensional search problem with restricted questions

The problem is the following: How many questions are necessary in the worst case to determine whether a pointX in then-dimensional Euclidean spaceR ⁿ belongs to then-dimensional unit cubeQ ⁿ, where we are allowed to ask which halfspaces of (n−1)-dimensional hyperplanes contain the pointX? It is known that ⌌3n/2⌍ questions are sufficient. We prove here thatcn questions are necessary, wherec≈1.2938 is the solution of the equationx log₂ x−(x−1) log₂ (x−1)=1.     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

A generalization of a result of R. Lyons about measures on [0, 1)

Letμ be a probability measure on [0, 1), invariant underS:x ↦px mod 1, and for which almost every ergodic component has positive entropy. Ifq is a real number greater than 1 for which logq/ logp is irrational, andT _n sendsx toq ⁿx mod 1, then for any ε>0 the measureμT _n ⁻¹ will — for a set ofn of positive lower density — be within ε of Lebesgue measure.     

Minkowski spaces with extremal distance from the Euclidean space

It is proved that if the Banach-Mazur distance between ann-dimensional Minkowski spaceB andl ₂ ⁿ satisfiesd (B ₁ l ₂ ⁿ ) ≧c √n (for some constantc>0 and for bign) thenB contains anA(c)-isomorphic copy ofl ₁ ^k (fork ∼ log log logn). In the special cased (B ₁ l ₂ ⁿ ) = √n,B contains an isometric copy ofl ₁ ^k fork ∼ logn.     

Euclidean minimum spanning trees and bichromatic closest pairs

We present an algorithm to compute a Euclidean minimum spanning tree of a given setS ofN points inE ^d in timeO(F _d (N,N) log ^d N), whereF _d (n,m) is the time required to compute a bichromatic closest pair amongn red andm green points inE ^d . IfF _d (N,N)=Ω(N ^1+ε), for some fixed ɛ>0, then the running time improves toO(F _d (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected timeO((nm logn logm)^2/3+m log² n+n log² m) inE ₃, which yields anO(N ^4/3 log^4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree ofN points inE ³. Ind≥4 dimensions we obtain expected timeO((nm)^{1−1/([d/2]+1)+ε}+m logn+n logm) for the bichromatic closest pair problem andO(N ^{2−2/([d/2]+1)ε}) for the Euclidean minimum spanning tree problem, for any positive ɛ. The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm “Datenstrukturen und effiziente Algorithmen”. The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).     

Symmetric block bases of sequences with large average growth

We show that if 0<ε≦1, 1≦p<2 andx ₁, …,x _n is a sequence of unit vectors in a normed spaceX such thatE ‖∑ _l ⁿ ε_i x _l‖≧n ^1/p, then one can find a block basisy ₁, …,y _m ofx ₁, …,x _n which is (1+ε)-symmetric and has cardinality at leastγn ^2/p-1(logn)⁻¹, where γ depends on ε only. Two examples are given which show that this bound is close to being best possible. The first is a sequencex ₁, …,x _n satisfying the above conditions with no 2-symmetric block basis of cardinality exceeding 2n ^2/p-1. This sequence is not linearly independent. The second example is a sequence which satisfies a lowerp-estimate but which has no 2-symmetric block basis of cardinality exceedingCn ^2/p-1(logn)^4/3, whereC is an absolute constant. This applies when 1≦p≦3/2. Finally, we obtain improvements of the lower bound when the spaceX containing the sequence satisfies certain type-condition. These results extend results of Amir and Milman in [1] and [2]. We include an appendix giving a simple counterexample to a question about norm-attaining operators.     

On large deviations and density functions

Suppose thatX ₁,X ₂, ... is a sequence of absolutely continuous or integer valued random variables with corresponding probability density functionsf _n (x). Let {φ _n } _n=1 ^∞ be a sequence of real numbers, then necessary and sufficient conditions are given forn ⁻¹ logf _n (φ _n )-n ⁻¹ log P (X _n >φ _n )=0(1) asn→∞.     

On the strong law of large numbers for sequences of random variables without the independence condition

New sufficient conditions for the applicability of the strong law of large numbers to a sequence of dependent random variables X ₁, X ₂, …, with finite variances are established. No particular type of dependence between the random variables in the sequence is assumed. The statement of the theorem involves the classical condition Σ _n ^∞ (log₂ n)²/n ² < ∞, which appears in various theorems on the strong law of large numbers for sequences of random variables without the independence condition.     

Isomorphic embedding of ℓ p n , 1<p<2, into ℓ 1 (1+ε)n

In this paper we partially answer a question posed by V. Milman and G. Schechtman by proving that ℓ _p ⁿ , (C logn)^1/q(1+1/ε)-embeds into ℓ ₁ ^(1+ε)n , where 1<p<2 and 1/p+1/q=1. Supported by ISF.     

Unconditional and symmetric sets inn-dimensional normed spaces

Isoperimetric inequalities are used to obtain measure estimates on almost constancy sets of functions on product spaces. These are applied to produce almost unconditional or symmetric block sequences from given sequences. Their length, which is (logn)^1/2 in the general case, improves ton ^a where a cotype condition is imposed or when the given sequences arep-type attaining for somep<2. In thep-type attaining case, block sequences (1+ε)-equivalent to the unit vector basis ofl _p ^m can be obtained when log logm ∼ log logn. Research supported in part by NSF Grant MCS 7902489.     

Planar Graphs, via Well-Orderly Maps and Trees

The family of well-orderly maps is a family of planar maps with the property that every connected planar graph has at least one plane embedding which is a well-orderly map. We show that the number of well-orderly maps with n nodes is at most 2^αn+O(logn), where α≈4.91. A direct consequence of this is a new upper bound on the number p(n) of unlabeled planar graphs with n nodes, log₂p(n)≤4.91n. The result is then used to show that asymptotically almost all (labeled or unlabeled), (connected or not) planar graphs with n nodes have between 1.85n and 2.44n edges. Finally we obtain as an outcome of our combinatorial analysis an explicit linear-time encoding algorithm for unlabeled planar graphs using, in the worst-case, a rate of 4.91 bits per node and of 2.82 bits per edge.     

Sudakov-type minoration for gaussian chaos processes

Consider a setA of symmetricn×n matricesa=(a _i,j) _i,j≤n . Consider an independent sequence (g _i) _i≤n of standard normal random variables, and letM=Esup_a∈A|Σ_i,j⪯na_i,jg_ig_j|. Denote byN ₂(A, α) (resp.N _t(A, α)) the smallest number of balls of radiusα for thel ₂ norm ofR ^{n 2} (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN ₂(A, α))^1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN _t≤K(δ)M. Work partially supported by an N.S.F. grant.     

Can visibility graphs Be represented compactly?

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graphG, a familyG={G ₁,G ₂,...,G _k } is called aclique cover ofG if (i) eachG _i is a clique or a bipartite clique, and (ii) the union ofG _i isG. The size of the clique coverG is defined as ∑ _i=1 ^k n _i , wheren _i is the number of vertices inG _i . Our main result is that there are visibility graphs ofn nonintersecting line segments in the plane whose smallest clique cover has size Ω(n ²/log² n). An upper bound ofO(n ²/logn) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of sizeO(nlog³ n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n logn). The work by the first author was supported by National Science Foundation Grant CCR-91-06514. The work by the second author was supported by a USA-Israeli BSF grant. The work by the third author was supported by National Science Foundation Grant CCR-92-11541.     

Central limit theorems for the ergodic adding machine

In this paper we find a second class of sequences of random numbers (x _n ) _n=1 ^∞ (the orbit of the ergodic adding machine) such that the corresponding sequences of zeros and ones 1_[0,y](x _n) (n=1,2,...,N) satisfy Central Limit Theorems with extremely small standard deviationσ _N=O(√logN), instead ofO(√N), asN → ∞. Dedicated to Professor Benjamin Weiss on the occasion of his 60^th birthday.     

Precise rates in the law of the iterated logarithm under dependence assumptions

Let {X, X1, X2,...} be a strictly stationaryφ-mixing sequence which satisfies EX = 0,EX^2（log2{X}）^2〈∞and φ（n）=O（1/log n）^Tfor some T〉2.Let Sn=∑k=1^nXk and an=O（√n/（log2n）^γ for some γ〉1/2.We prove that limε→√2√ε^2-2∑n=3^∞1/nP（｜Sn｜≥ε√ESn^2log2n＋an）=√2.The results of Gut and Spataru （2000） are special cases of ours.     

On some 2-adic properties of a recurrence involving stirling numbers

We analyze some 2-adic properties of the sequence defined by the recurrence Z(1) = 1; Z(n) = Σ _k=1 ⁿ⁻¹ S(n, k)Z(k), n ≥ 2, which counts the number of ultradissimilarity relations, i.e., ultrametrics on an n-set. We prove the 2-adic growth property ν ₂(Z(n)) ≥ ⌈log₂ n⌉ −1 and present conjectures on the exact values.     

On-line coloringk-colorable graphs

We show that for anyk, there exists an on-line algorithm that will color anyk-colorable graph onn vertices withO(n ^1−1/k! ) colors. This improves the previous best upper bound ofO(nlog^(2k−3) n/log^(2k−4) n) due to Lovász, Saks, and Trotter. In the special casesk=3 andk=4 we obtain on-line algorithms that useO(n ^2/3log^1/3 n) andO(n ^5/6log^1/6 n) colors, respectively.     

Covering of graphs by complete bipartite subgraphs; Complexity of 0–1 matrices

We prove that the edge set of an arbitrary simple graphG onn vertices can be covered by at mostn−[log₂ n]+1 complete bipartite subgraphs ofG. If the weight of a subgraph is the number of its vertices, then there always exists a cover with total weightc(n ²/logn) and this bound is sharp apart from a constant factor. Our result answers a problem of T. G. Tarján. Dedicated to Paul Erdős on his seventieth birthday