Covering times of random walks on bounded degree trees and other graphs

The motivating problem for this paper is to find the expected covering time of a random walk on a balanced binary tree withn vertices. Previous upper bounds for general graphs ofO(|V| |E|)⁽¹⁾ andO(|V| |E|/d _min)⁽²⁾ imply an upper bound ofO(n ²). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log² n). The previous lower bound was (|V| log |V|) for trees.⁽²⁾ In our main result, we show a lower bound of (|V| (log _{d max} |V|)²) for trees, which yields a lower bound of (n log² n). We also extend our techniques to show an upper bound for general graphs ofO(max{E T_i} log |V|).     

THE SECOND EXPONENT SET OF PRIMITIVE DIGRAPHS

51.IntroductionandNotationsLetD=(V,E)beadigraphandL(D)denotethesetofcyclelengthsofD.ForuEVandintegeri21,letfo(u):={vEVIthereedestsadirectedwalkoflengthifromutov}.WedelveRo(u):={u}.Letu,vEV.IfN (v)=N (v)andN--(v)=N--(v),thenwecanvacopyofu.LotDbeaprimitivedigraphand7(D)denotetheexponentofD.In1950,H.WielandtI61foundthat7(D)5(n--1)' 1andshowedthatthereisapiquedigraphthatattainsthisbound.In1964,A.L.DulmageandN.S.Mendelsohn[2]ObservedthattherearegapsintheexponentsetEd={ry(D)IDEPD.}…     

Test elements for endomorphisms of free groups and algebras

LetE be a bounded Borel subset of ℝⁿ,n≥2, of positive Lebesgue measure andP _E the corresponding ‘Pompeiu transform”. We prove thatP _E is injective onL ^p(ℝⁿ) if 1≤p≤2n/(n-1). We explore the connection between this problem and a Wiener-Tauberian type theorem for theM(n) action onL ^q(ℝⁿ) for various values ofq. We also take up the question of whenP _E is injective in caseE is of finite, positive measure, but is not necessarily a bounded set. Finally, we briefly look at these questions in the contexts of symmetric spaces of compact and non-compact type.     

Partition conditions and vertex-connectivity of graphs

It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev ₁, ...,v _n ≠V(G) and for any sequence of positive integersk ₁, ...,k _n such thatk ₁+...+k _n =|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv ₁, ...,v(n), and the class of the partition containingv _i induces a connected subgraph consisting ofk _i vertices, fori=1, 2, ...,n. Now fix the integersk ₁, ...,k _n . In this paper we study what can we say about the vertex-connectivity ofG if there exists such a partition ofV(G) for any sequence of verticesv ₁, ...,v _n ≠V(G). We find some interesting cases when the existence of such partitions implies then-vertex-connectivity ofG, in the other cases we give sharp lower bounds for the vertex-connectivity ofG.     

Sums of cubes of square-free numbers II

Letr _s (n) denote the number of representations ofn as the sum ofs cubes of square-free numbers. We prove an asymptotic formula forr _s (n) and a strong lower bound forr ₇ (n).     

On the convex hull of uniform random points in a simpled-polytope

Denote the expected number of facets and vertices and the expected volume of the convex hullP _n ofn random points, selected independently and uniformly from the interior of a simpled-polytope byE _n (f), E _n (v), andE _n (V), respectively. In this note we determine the sharp constants of the asymptotic expansion ofE _n (f), E _n (v), andE _n (V), asn tends to infinity. Further, some results concerning the expected shape ofP _n are given. The work of F. Affentranger was supported by the Swiss National Foundation.     

The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

The minimal positive integer represented by a positive definite quadratic form

In this paper we shall give an upper bound on the size of the gap between the constant term and the next nonzero Fourier coefficient of a holomorphic modular form of given weight for the group G₀(2) \Gamma_{0}(2) . We derive an upper bound for the minimal positive integer represented by an even positive definite quadratic form of level two. In our paper we prove two conjectures given in [1]. In particular, we can prove the following result: let Q \mathcal{Q} be an even positive definite quadratic form of level two in v v variables, with v o 4(mod 8) v \equiv 4(\textrm{mod}\, 8) , then Q \mathcal{Q} represents a positive integer 2n ￡ 3+v/4 2n \leq 3+v/4 .     

A lower bound on the independence number of arbitrary hypergraphs

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d(v) = (d₁(v), d₂(v), …) where d_m(v) is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ Σ_v∈V f(d(v)). This lower bound is sharp when H is a match, and it generalizes known bounds of Caro/Wei and Caro/Tuza for ordinary graphs and uniform hypergraphs. Furthermore, an algorithm for computing independent sets of size as guaranteed by the lower bound is given. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 213–221, 1999     

The cotype constant and an almost euclidean decomposition for finite-dimensional normed spaces

Every 2n-dimensional normed spaceE contains twon-dimensional subspacesE ₁ andE ₂ which are orthogonal with respect to the inner product induced by the John ellipsoid ofE and which satisfyd(E _i, l ₂ ⁿ )≦f(K ₂(E)), wheref(K ₂(E)) is some number that depends only on the cotype constant ofE, denotedK ₂(E). Supported in part by NSF grant DMS 8401906.     

Some divisibilities amongst the terms of linear recurrences

Let (u_n)n≥0 be a non-degenerate linear recurrence sequence of integers. We show that the set of positive integersn such that either ω)(n) orΩ(n) dividesu _n is of asymptotic density zero, where ω(n) and Ω(n) are the numbers of prime and prime power divisors ofn, respectively. The same also holds for the set of positive integersn such that τ(n)u _n , where τ(n) is the number of the positive integer divisors of n, provided thatu _n satisfies some mild technical conditions.     

Planar realizations of nonlinear davenport-schinzel sequences by segments

LetG={l ₁,...,l _n } be a collection ofn segments in the plane, none of which is vertical. Viewing them as the graphs of partially defined linear functions ofx, letY _G be their lower envelope (i.e., pointwise minimum).Y _G is a piecewise linear function, whose graph consists of subsegments of the segmentsl _i . Hart and Sharir [7] have shown thatY _G consists of at mostO(n(n)) segments (where(n) is the extremely slowly growing inverse Ackermann's function). We present here a construction of a setG ofn segments for whichY _G consists of(n(n)) subsegments, proving that the Hart-Sharir bound is tight in the worst case.Another interpretation of our result is in terms of Davenport-Schinzel sequences: the sequenceE _G of indices of segments inG in the order in which they appear alongY _G is a Davenport-Schinzel sequence of order 3, i.e., no two adjacent elements ofE _G are equal andE _G contains no subsequence of the forma ...b ...a ...b ...a. Hart and Sharir have shown that the maximal length of such a sequence composed ofn symbols is (n(n)). Our result shows that the lower bound construction of Hart and Sharir can be realized by the lower envelope ofn straight segments, thus settling one of the main open problems in this area.Work on this paper has been partially supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. This paper is part of the first author's M.Sc. thesis prepared at Tel Aviv University under the supervision of the second author. A preliminary version of this paper has appeared inProceedings of the 27th IEEE Symposium on Foundations of Computer Science, Toronto, 97–106, 1986.     

Some unavoidable subdigraphs of tournaments

Let H(n, i) be a simple (n ? 1)-path v₁ → v₂ → …? → v_n with an additional arc v₁v_i (3 ? i ? n). We prove that for each n and i (3 ? i ? n), with few exceptions, every n-tournament T_n contains a copy of H(n, i).     

Symmetric edge-decompositions of hypercubes

We call a set of edgesE of the n-cubeQ _n a fundamental set for Q _n if for some subgroupG of the automorphism group ofQ _n , theG-translates ofE partition the edge set ofQ _n .Q _n possesses an abundance of fundamental sets. For example, a corollary of one of our main results is that if |E| =n and the subgraph induced byE is connected, then if no three edges ofE are mutually parallel,E is a fundamental set forQ _n . The subgroupG is constructed explicitly. A connected graph onn edges can be embedded intoQ _n so that the image of its edges forms such a fundamental set if and only if each of its edges belongs to at most one cycle.We also establish a necessary condition forE to be a fundamental set. This involves a number-theoretic condition on the integersa _j (E), where for 1 j n, a _j (E) is the number of edges ofE in thej ^th direction (i.e. parallel to thej ^th coordinate axis).     

Momentopes, the Complexity of Vector Partitioning, and Davenport—Schinzel Sequences

The computational complexity of the partition problem , which concerns the partitioning of a set of n vectors in d -space into p parts so as to maximize an objective function which is convex on the sum of vectors in each part, is determined by the number of vertices of the corresponding p-partition polytope defined to be the convex hull in (d\times p) -space of all solutions. In this article, introducing and using the class of Momentopes , we establish the lower bound v _p,d (n)=Ω(n^ \lfloor (d-1)/2 \rfloor p ) on the maximum number of vertices of any p -partition polytope of a set of n points in d -space, which is quite compatible with the recent upper bound v _p,d (n)=O(n ^d(p-1)-1 ) , implying the same bound on the complexity of the partition problem. We also discuss related problems on the realizability of Davenport—Schinzel sequences and describe some further properties of Momentopes. Received April 4, 2001, and in revised form October 3, 2001. Online publication February 28, 2002.     

Bounds for the crossing number of the N-cube

Let Q_n denote the n-dimensional hypercube. In this paper we derive upper and lower bounds for the crossing number v(Q_n), i.e., the minimum number of edge-crossings in any planar drawing of Q_n. The upper bound is close to a result conjectured by Eggleton and Guy and the lower bound is a significant improvement over what was previously known. Let N = 2ⁿ be the number of vertices of Q_n. We show that v(Q_n) < 1/6N². For the lower bound we prove that v(Q_n) = Ω(N(lg N)^{c lg lg N}), where c > 0 is a constant and lg is the logarithm base 2. The best lower bound using standard arguments is v(Q_n) = Ω(N(lg N)²). The lower bound is obtained by constructing a large family of homeomorphs of a subcube with the property that no given pair of edges can appear in more than a constant number of the homeomorphs.     

The structure of injective covers of special modules

In this paper, we prove that the injective cover of theR-moduleE(R/B)/R/B for a prime ideal B ofR is the direct sum of copies ofE(R/B) for prime ideals D ⊃ B, and if B is maximal, the injective cover is a finite sum of copies ofE(R/B). For a finitely generatedR-moduleM withn generators andG an injectiveR-module, we argue that the natural mapG ⁿ →G ⁿ/Hom _R (M, G) is an injective precover if Ext _R ¹ (M, R) = 0, and that the converse holds ifG is an injective cogenerator ofR. Consequently, for a maximal ideal R ofR, depth_R R ≧ 2 if and only if the natural mapE(R/R) →E(R/R)/R/R is an injective cover and depth_R R > 0.     

Sur un problème de Rényi

Let (n) be the number of all prime divisors ofn and (n) the number of distinct prime divisors ofn. We definev _q (x)=|{nx(n)–(n)=q}|. In this paper, we give an asymptotic development ofv _q (x); this improves on previous results.

     

Illuminating high-dimensional convex sets

A setL of points in thed-spaceE ^d is said toilluminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d if for every setS _i inF and every pointx in the boundary ofS _i there is a pointv inL such thatv illuminatesx, i.e. the line segment joiningv tox intersects the union of the elements ofF in exactly {x}.The problem we treat is the size of a setS needed to illuminate a familyF={S ₁, ...,S _n } ofn disjoint compact sets inE ^d . We also treat the problem of putting these convex sets in mutually disjoint convex polytopes, each one having at most a certain number of facets.     

Tighter Bounds on the Solution of a Divide-and-Conquer Maximin Recurrence

LetM(n) be defined by the recurrencewherefis an arbitrary nondecreasing function andM(1) is given. The recurrenceM(n) is a divide-and-conquer maximin recurrence, which occurs in a variety of problems in the analysis of algorithms. In this paper, a new upper bound onM(n) is first derived. The derived bound is smaller than the one proposed previously by Li and Reingold. It is at most two times the exact solution ofM(n). Using the bound, we further show thatM(n) ≤ 2E(n), whereE(n) is defined by the recurrenceE(n) = E(⌊n/2⌋) + E(⌈n/2⌉) + f(⌊n/2⌋). From this result, we can conclude that a divide-and-conquer algorithm whose time complexity is expressed asM(n) is as efficient as a divide-and-conquer algorithm whose time complexity is expressed asE(n).