首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Let {pk}k≥3 be a sequence of nonnegative integers which satisfies 8 + Σk≥3 (k-4) pk = 0 and p4p3. Then there is a convex 4-valent polytope P in E3 such that P has exactly pk k-gons as faces. The inequality p4p3 is the best possible in the sense that for c < 1 there exist sequences that are not 4-realizable that satisfy both 8 + Σk ≥3 (k - 4) pk = 0 and p4 > cp3. When Σk ≥ 5 pk ≠ 1, one can make the stronger statement that the sequence {pk} is 4-reliazable if it satisfies 8 + Σk ≥ 3 (k - 4) pk = 0 and p4 ≥ 2Σk ≥ 5 pk + max{k ¦ pk ≠ 0}.  相似文献   

2.
Let πi :EiM, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections si :MEi. Suppose that U is an open neighborhood of s1(M) in E1 and F :UE2 a smooth embedding so that π2Fs1 :MM is homotopic to a diffeomorphism f. We show that if k>[(n+1)/2]+1 then E1 and the induced bundle f*E2 are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [(n+1)/2]+1<kn we give examples of nonisomorphic oriented bundles E1 and E2 of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E1 and f*E2 are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[(n+1)/2]+1 and M is a homotopy n-sphere.  相似文献   

3.
Let $A \subset {{\Bbb Z}_N}$, and ${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$ We define the pseudorandom measure of order k of the subset A as follows, Pk(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$fA(n + c1)fA(n + c2) … fA(n + ck)|, where the maximum is taken over all D = (c1, c2, . . . , ck) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c1 < c2 < … < ckN - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if Pk(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4, and lcm(a1, a2, . . . , al) denotes the least common multiple of a1, a2, . . . , al.  相似文献   

4.
A graph G is called Ck-saturated if G contains no cycles of length k but does contain such a cycle after the addition of any new edge. Bounds are obtained for the minimum number of edges in Ck-saturated graphs for all k ≠ 8 or 10 and n sufficiently large. In general, it is shown that the minimum is between n + c1n/k and n + c2n/k for some positive constants c1 and C2. Our results provide an asymptotic solution to a 15-year-old problem of Bollobás.  相似文献   

5.
Let sk(n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an sk(n)-point semiorder. When k = 1, s1(n) = n since all interval orders with no two-point antichains are chains. Given (c1,...,c5) = (1, 2, 3, 4), it is shown that s2(n) = cn for n 4, s3(n) = cn for n 5, and for all positive n, s2 (n+4) =s2(n)+3, s3(n+5) = s3(n)+3. Hence s2 has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s3 has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...].

Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern.  相似文献   


6.
For a 1-dependent stationary sequence {Xn} we first show that if u satisfies p1=p1(u)=P(X1>u)0.025 and n>3 is such that 88np131, then
P{max(X1,…,Xn)u}=ν·μn+O{p13(88n(1+124np13)+561)}, n>3,
where
ν=1−p2+2p3−3p4+p12+6p22−6p1p2,μ=(1+p1p2+p3p4+2p12+3p22−5p1p2)−1
with
pk=pk(u)=P{min(X1,…,Xk)>u}, k1
and
|O(x)||x|.
From this result we deduce, for a stationary T-dependent process with a.s. continuous path {Ys}, a similar, in terms of P{max0skTYs<u}, k=1,2 formula for P{max0stYsu}, t>3T and apply this formula to the process Ys=W(s+1)−W(s), s0, where {W(s)} is the Wiener process. We then obtain numerical estimations of the above probabilities.  相似文献   

7.
Jianxiang Li   《Discrete Mathematics》2003,260(1-3):217-221
Let G be a graph of order n, and let a and b be integers such that 1a<b. Let δ(G) be the minimum degree of G. Then we prove that if δ(G)(k−1)a, n(a+b)(k(a+b)−2)/b, and |NG(x1)NG(x2)NG(xk)|an/(a+b) for any independent subset {x1,x2,…,xk} of V(G), where k2, then G has an [a,b]-factor. This result is best possible in some sense.  相似文献   

8.
For a positive integer k2, the k-Fibonacci sequence {gn(k)} is defined as: g1(k)==gk−2(k)=0, gk−1(k)=gk(k)=1 and for n>k2, gn(k)=gn−1(k)+gn−2(k)++gnk(k). Moreover, the k-Lucas sequence {ln(k)} is defined as ln(k)=gn−1(k)+gn+k−1(k) for n1. In this paper, we consider the relationship between gn(k) and ln(k) and 1-factors of a bipartite graph.  相似文献   

9.
A holey Schröder design of type h1n1h2n2hknk (HSD(h1n1h2n2hknk)) is equivalent to a frame idempotent Schröder quasigroup (FISQ(h1n1h2n2hknk)) of order n with ni missing subquasigroups (holes) of order hi, (1 i k), which are disjoint and spanning, that is, Σ1 i k nihi = n. In this paper, it is shown that an HSD(hn) exists if and only if h2n(n − 1) 0 (mod 4) with expceptions (h, n) ε {{(1,5),(1,9),(2,4)}} and the possible exception of (h, n) = (6,4).  相似文献   

10.
An increasing sequence of positive integers {n1, n2, …} is called a sum-free sequence if every term is never a sum of distinct smaller terms. We prove that there exist sum-free sequences {nk} with polynomial growth and such that limk→∞ nk+1/nk = 1.  相似文献   

11.
Suppose {k, −∞ < k < ∞} is an independent, not necessarily identically distributed sequence of random variables, and {cj}j=0, {dj}j=0 are sequences of real numbers such that Σjc2j < ∞, Σjd2j < ∞. Then, under appropriate moment conditions on {k, −∞ < k < ∞}, yk Σj=0cjk-j, zk Σj=0djk-j exist almost surely and in 4 and the question of Gaussian approximation to S[t]Σ[t]k=1 (yk zkE{yk zk}) becomes of interest. Prior to this work several related central limit theorems and a weak invariance principle were proven under stationary assumptions. In this note, we demonstrate that an almost sure invariance principle for S[t], with error bound sharp enough to imply a weak invariance principle, a functional law of the iterated logarithm, and even upper and lower class results, also exists. Moreover, we remove virtually all constraints on k for “time” k ≤ 0, weaken the stationarity assumptions on {k, −∞ < k < ∞}, and improve the summability conditions on {cj}j=0, {dj}j=0 as compared to the existing weak invariance principle. Applications relevant to this work include normal approximation and almost sure fluctuation results in sample covariances (let dj = cj-m for jm and otherwise 0), quadratic forms, Whittle's and Hosoya's estimates, adaptive filtering and stochastic approximation.  相似文献   

12.
If are maximal nests on a finite-dimensional Hilbert space H, the dimension of the intersection of the corresponding nest algebras is at least dim H. On the other hand, there are three maximal nests whose nest algebras intersect in the scalar operators. The dimension of the intersection of two nest algebras (corresponding to maximal nests) can be of any integer value from n to n(n+1)/2, where n=dim H. For any two maximal nests there exists a basis {f1,f2,…,fn} of H and a permutation π such that and where Mi=  span{f1,f2,…,fi} and Ni= span{fπ(1),fπ(2),…,fπ(i)}. The intersection of the corresponding nest algebras has minimum dimension, namely dim H, precisely when π(j)=nj+1,1jn. Those algebras which are upper-triangular matrix incidence algebras, relative to some basis, can be characterised as intersections of certain nest algebras.  相似文献   

13.
Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let ck be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r3=|E|−c3 and . We show that on one side r3 and r2 bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r3 and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr3. For k=2,3, let ζk denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other.  相似文献   

14.
An up–down permutation P=(p1,p2,…,pn) is a permutation of the integers 1 to n which satisfies constraints specified by a sequence C=(c1,c2,…,cn−1) of U's and D's of length n−1. If ci is U then pi<pi+1 otherwise pi−1>pi. A loopless algorithm is developed for generating all the up–down permutations satisfying any sequence C. Ranking and unranking algorithms are discussed.  相似文献   

15.
Gould et al. (Combinatorics, Graph Theory and Algorithms, Vol. 1, 1999, pp. 387–400) considered a variation of the classical Turán-type extremal problems as follows: For a given graph H, determine the smallest even integer σ(H,n) such that every n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(H,n) has a realization G containing H as a subgraph. In this paper, for given integers k and ℓ, ℓ7 and 3kℓ, we completely determine the smallest even integer σ(kC,n) such that each n-term graphic sequence π=(d1,d2,…,dn) with term sum σ(π)=d1+d2++dnσ(kC,n) has a realization G containing a cycle of length r for each r, krℓ.  相似文献   

16.
We study the number of solutions N(B,F) of the diophantine equation n_1n_2 = n_3 n_4,where 1 ≤ n_1 ≤ B,1 ≤ n_3 ≤ B,n_2,n_4 ∈ F and F[1,B] is a factor closed set.We study more particularly the case when F={m = p_1~(ε1)···p_k~(εk),ε_j∈{0,1},1 ≤ j ≤ k},p_1,...,p_k being distinct prime numbers.  相似文献   

17.
The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V1, V2,…, Va such that for each i at most d vertices in V1Vi have neighbors in Vi+1 and r(Kk, Vi) p | V(G) |, where Vi denotes the subgraph of G induced by Vi. Then there exists a number c depending only on p, d, and k such that r(Kk, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of GI has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.  相似文献   

18.
In this article, we investigate the interrelation between the discrepancies of a given hypergraph in different numbers of colors. Being an extreme example we determine the multi-color discrepancies of the k-balanced hypergraph on partition classes of (equal) size n. Let . Set k0 k mod c and bnkc (nn/c/k)k/c. For the discrepancy in c colors we show
if k0≠0, and , if c divides k. This shows that, in general, there is little correlation between the discrepancies of in different numbers of colors. If c divides k though, holds for any hypergraph .  相似文献   

19.
Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers   总被引:6,自引:0,他引:6  
The Ramsey number r(H,Kn) is the smallest integer N so that each graph on N vertices that fails to contain H as a subgraph has independence number at least n. It is shown that r(K2,m,Kn)(m−1+o(1))(n/log n)2 and r(C2m,Kn)c(n/log n)m/(m−1) for m fixed and n→∞. Also r(K2,n,Kn)=Θ(n3/log2 n) and .  相似文献   

20.
Length-bounded disjoint paths in planar graphs   总被引:1,自引:0,他引:1  
The following problem is considered: given: an undirected planar graph G=(V,E) embedded in , distinct pairs of vertices {r1,s1},…,{rk,sk} of G adjacent to the unbounded face, positive integers b1,…,bk and a function ; find: pairwise vertex-disjoint paths P1,…,Pk such that for each i=1,…,k, Pi is a risi-path and the sum of the l-length of all edges in Pi is at most bi. It is shown that the problem is NP-hard in the strong sense. A pseudo-polynomial-time algorithm is given for the case of k=2.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号