共查询到20条相似文献,搜索用时 556 毫秒
1.
David Zuckerman 《Journal of Theoretical Probability》1989,2(1):147-157
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|)(1) andO(|V| |E|/d
min)(2) imply an upper bound ofO(n
2). We show an upper bound on general graphs ofO( |E| log |V|), which implies an upper bound ofO(n log2
n). The previous lower bound was (|V| log |V|) for trees.(2) In our main result, we show a lower bound of (|V| (log
d
max |V|)2) for trees, which yields a lower bound of (n log2
n). We also extend our techniques to show an upper bound for general graphs ofO(max{E
Ti} log |V|). 相似文献
2.
THE SECOND EXPONENT SET OF PRIMITIVE DIGRAPHS 总被引:2,自引:0,他引:2
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.}… 相似文献
3.
Vladimir Shpilrain 《Israel Journal of Mathematics》1995,91(1-3):307-316
LetE be a bounded Borel subset of ℝn,n≥2, of positive Lebesgue measure andP
E the corresponding ‘Pompeiu transform”. We prove thatP
E is injective onL
p(ℝn) 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(ℝn) 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. 相似文献
4.
Ervin Győri 《Combinatorica》1981,1(3):263-273
It was proved ([5], [6]) that ifG is ann-vertex-connected graph then for any vertex sequencev
1, ...,v
n
≠V(G) and for any sequence of positive integersk
1, ...,k
n
such thatk
1+...+k
n
=|V(G)|, there exists ann-partition ofV(G) such that this partition separates the verticesv
1, ...,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
1, ...,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
1, ...,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. 相似文献
5.
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
7
(n). 相似文献
6.
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. 相似文献
7.
X. Wang 《Archiv der Mathematik》2003,80(3):245-254
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 G0(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 . 相似文献
8.
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. 相似文献
9.
Torsten Thiele 《Journal of Graph Theory》1999,30(3):213-221
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) = (d1(v), d2(v), …) where dm(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 相似文献
10.
F. Luca I. E. Shparlinski 《Abhandlungen aus dem Mathematischen Seminar der Universit?t Hamburg》2006,76(1):143-156
Let (un)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. 相似文献
11.
Every 2n-dimensional normed spaceE contains twon-dimensional subspacesE
1 andE
2 which are orthogonal with respect to the inner product induced by the John ellipsoid ofE and which satisfyd(E
i, l
2
n
)≦f(K
2(E)), wheref(K
2(E)) is some number that depends only on the cotype constant ofE, denotedK
2(E).
Supported in part by NSF grant DMS 8401906. 相似文献
12.
LetG={l
1,...,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. 相似文献
13.
Vojislav Petrovi 《Journal of Graph Theory》1988,12(3):317-325
Let H(n, i) be a simple (n ? 1)-path v1 → v2 → …? → vn with an additional arc v1vi (3 ? i ? n). We prove that for each n and i (3 ? i ? n), with few exceptions, every n-tournament Tn contains a copy of H(n, i). 相似文献
14.
Mark Ramras 《Graphs and Combinatorics》1991,7(1):65-87
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). 相似文献
15.
Tom Madej 《Journal of Graph Theory》1991,15(1):81-97
Let Qn denote the n-dimensional hypercube. In this paper we derive upper and lower bounds for the crossing number v(Qn), i.e., the minimum number of edge-crossings in any planar drawing of Qn. 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 = 2n be the number of vertices of Qn. We show that v(Qn) < 1/6N2. For the lower bound we prove that v(Qn) = Ω(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(Qn) = Ω(N(lg N)2). 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. 相似文献
16.
Thomas J. Cheatham Edgar E. Enochs Overtoun M. G. Jenda 《Israel Journal of Mathematics》1988,63(2):237-242
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
n →G
n/Hom
R
(M, G) is an injective precover if Ext
R
1
(M, R) = 0, and that the converse holds ifG is an injective cogenerator ofR. Consequently, for a maximal ideal R ofR, depthR
R ≧ 2 if and only if the natural mapE(R/R) →E(R/R)/R/R is an injective cover and depthR
R > 0. 相似文献
17.
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. 相似文献
18.
J. Wu 《Monatshefte für Mathematik》1994,117(3-4):303-322
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. 相似文献
19.
Biing-Feng Wang 《Journal of Algorithms in Cognition, Informatics and Logic》1997,23(2):329-344
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). 相似文献
20.
Jurek Czyzowicz Bruno Gaujal Eduardo Rivera-Campo Jorge Urrutia Joseph Zaks 《Geometriae Dedicata》1995,56(2):115-120
A setL of points in thed-spaceE
d
is said toilluminate a familyF={S
1, ...,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
1, ...,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. 相似文献