共查询到20条相似文献,搜索用时 31 毫秒
1.
T. C. Enns 《Discrete Mathematics》1980,30(3):227-234
Let {pk}k≥3 be a sequence of nonnegative integers which satisfies 8 + Σk≥3 (k-4) pk = 0 and p4 ≥ p3. Then there is a convex 4-valent polytope P in E3 such that P has exactly pk k-gons as faces. The inequality p4 ≥ p3 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.
Rodolfo De Sapio 《Topology and its Applications》2003,130(3):221-237
Let πi :Ei→M, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections si :M→Ei. Suppose that U is an open neighborhood of s1(M) in E1 and F :U→E2 a smooth embedding so that π2Fs1 :M→M 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 < … < ck ≤ N - 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.
C. A. Barefoot L. H. Clark R. C. Entringer T. D. Porter L. A. Sz kely Zs. Tuza 《Discrete Mathematics》1996,150(1-3):31-48
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.
Peter C. Fishburn 《Discrete Mathematics》1982,40(2-3):181-191
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.
George Haiman 《Stochastic Processes and their Applications》1999,80(2):231-248
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, thenwhere withandFrom 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. 相似文献
P{max(X1,…,Xn)u}=ν·μn+O{p13(88n(1+124np13)+561)}, n>3,
ν=1−p2+2p3−3p4+p12+6p22−6p1p2,μ=(1+p1−p2+p3−p4+2p12+3p22−5p1p2)−1
pk=pk(u)=P{min(X1,…,Xk)>u}, k1
|O(x)||x|.
7.
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.
Gwang-Yeon Lee 《Linear algebra and its applications》2000,320(1-3):51-61
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)++gn−k(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 h1n1h2n2 … hknk (HSD(h1n1h2n2 … hknk)) is equivalent to a frame idempotent Schröder quasigroup (FISQ(h1n1h2n2 … hknk)) 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.
Michael A. Kouritzin 《Stochastic Processes and their Applications》1995,60(2):343-353
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 zk − E{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 j ≥ m and otherwise 0), quadratic forms, Whittle's and Hosoya's estimates, adaptive filtering and stochastic approximation. 相似文献
12.
P. A. Fillmore W. E. Longstaff G. W. MacDonald H. Radjavi Y. Zhong 《Linear algebra and its applications》2002,350(1-3):185-197
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)=n−j+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.
Eckhard Steffen 《Discrete Mathematics》2004,280(1-3):191-214
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.
James F. Korsh 《Discrete Mathematics》2001,240(1-3):97-122
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 V1 … Vi 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 G−I 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.
Benjamin Doerr 《Discrete Mathematics》2002,250(1-3):63-70
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 (n−n/c/k)k/c. For the discrepancy in c colors we showif 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.
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 ri−si-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. 相似文献