首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Given some arbitrary integers d ≥ 2, ? ? 1 and an integer vector $ \bar \tau Given some arbitrary integers d ≥ 2, ϰ ⩾ 1 and an integer vector = (τ 0, τ 1, …, τ d ) with τ 0τ 1 ⩾ … ⩾ τ d = 1 and τ d − 1d 2ϰ + 3, the existence is proved of a graph of diameter d and connectivity ϰ whose ball diversity vector is . Moreover, the nonexistence is proved of a graph of diameter d with connectivity ϰ and ball diversity vector (τ 0, τ 1, …, τ d ), where τ 0 < (d − 1)ϰ + 2. Original Russian Text ? K.L. Rychkov, 2007, published in Diskretnyi Analiz i Issledovanie Operatsii, Ser. 1, 2007, Vol. 14, No. 4, pp. 43–56.  相似文献   

2.
 Suppose G is a graph and T is a set of non-negative integers that contains 0. A T-coloring of G is an assignment of a non-negative integer f(x) to each vertex x of G such that |f(x)−f(y)|∉T whenever xyE(G). The edge span of a T-coloring−f is the maximum value of |f(x) f(y)| over all edges xy, and the T-edge span of a graph G is the minimum value of the edge span of a T-coloring of G. This paper studies the T-edge span of the dth power C d n of the n-cycle C n for T={0, 1, 2, …, k−1}. In particular, we find the exact value of the T-edge span of C n d for n≡0 or (mod d+1), and lower and upper bounds for other cases. Received: May 13, 1996 Revised: December 8, 1997  相似文献   

3.
For integers d≥0, s≥0, a (d, d+s)‐graph is a graph in which the degrees of all the vertices lie in the set {d, d+1, …, d+s}. For an integer r≥0, an (r, r+1)‐factor of a graph G is a spanning (r, r+1)‐subgraph of G. An (r, r+1)‐factorization of a graph G is the expression of G as the edge‐disjoint union of (r, r+1)‐factors. For integers r, s≥0, t≥1, let f(r, s, t) be the smallest integer such that, for each integer df(r, s, t), each simple (d, d+s) ‐graph has an (r, r+1) ‐factorization with x (r, r+1) ‐factors for at least t different values of x. In this note we evaluate f(r, s, t). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 257‐268, 2009  相似文献   

4.
Isomorphic embeddings ofl l m intol n are studied, and ford(n, k)=inf{‖T ‖ ‖T −1 ‖;T varies over all isomorphic embeddings ofl 1 [klog2n] intol n we have that lim n→∞ d(n, k)=γ(k)−1,k>1, whereγ(k) is the solution of (1+γ)ln(1+γ)+(1 −γ)ln(1 −γ)=k −1ln4. Here [x] denotes the integer part of the real numberx.  相似文献   

5.
We prove that, for any real numbers ξ ≠ 0 and ν, the sequence of integer parts [ξ2 n  + ν], n = 0, 1, 2, . . . , contains infinitely many composite numbers. Moreover, if the number ξ is irrational, then the above sequence contains infinitely many elements divisible by 2 or 3. The same holds for the sequence [ξ( − 2) n  + ν n ], n = 0, 1, 2, . . . , where ν 0, ν 1, ν 2, . . . all lie in a half open real interval of length 1/3. For this, we show that if a sequence of integers x 1, x 2, x 3, . . . satisfies the recurrence relation x n+d  = cx n  + F(x n+1, . . . , x n+d-1) for each n  ≥  1, where c ≠ 0 is an integer, F(z1,...,zd-1) ? \mathbb Z[z1,...,zd-1],{F(z_1,\dots,z_{d-1}) \in \mathbb {Z}[z_1,\dots,z_{d-1}],} and lim n→ ∞|x n | = ∞, then the number |x n | is composite for infinitely many positive integers n. The proofs involve techniques from number theory, linear algebra, combinatorics on words and some kind of symbolic computation modulo 3.  相似文献   

6.
Let g and m be two positive integers, and let F be a polynomial with integer coefficients. We show that the recurrent sequence x0 = g, xn = x n−1 n + F(n), n = 1, 2, 3,…, is periodic modulo m. Then a special case, with F(z) = 1 and with m = p > 2 being a prime number, is considered. We show, for instance, that the sequence x0 = 2, xn = x n−1 n + 1, n = 1, 2, 3, …, has infinitely many elements divisible by every prime number p which is less than or equal to 211 except for three prime numbers p = 23, 47, 167 that do not divide xn. These recurrent sequences are related to the construction of transcendental numbers ζ for which the sequences [ζn!], n = 1, 2, 3, …, have some nice divisibility properties. Bibliography: 18 titles. Published in Zapiski Nauchnykh Seminarov POMI, Vol. 322, 2005, pp. 76–82.  相似文献   

7.
We present a new condition on the degree sums of a graph that implies the existence of a long cycle. Let c(G) denote the length of a longest cycle in the graph G and let m be any positive integer. Suppose G is a 2-connected graph with vertices x1,…,xn and edge set E that satisfies the property that, for any two integers j and k with j < k, xjxk ? E, d(xi) ? j and d(xk) ? K - 1, we have (1) d(xi) + d(xk ? m if j + k ? n and (2) if j + k < n, either m ? n or d(xj) + d(xk) ? min(K + 1,m). Then c(G) ? min(m, n). This result unifies previous results of J.C. Bermond and M. Las Vergnas, respectively.  相似文献   

8.
Let d(n), σ 1(n), and φ(n) stand for the number of positive divisors of n, the sum of the positive divisors of n, and Euler’s function, respectively. For each ν ∈, Z, we obtain asymptotic formulas for the number of integers nx for which e n = 2 v r for some odd integer m as well as for the number of integers nx for which e n = 2 v r for some odd rational number r. Our method also applies when φ(n) is replaced by σ 1(n), thus, improving upon an earlier result of Bateman, Erdős, Pomerance, and Straus, according to which the set of integers n such that is an integer is of density 1/2. Research supported in part by a grant from NSERC. Research supported by the Applied Number Theory Research Group of the Hungarian Academy of Science and by a grant from OTKA. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 3, pp. 315–331, July–September, 2006.  相似文献   

9.
Let n be a nonzero integer. A set of m distinct positive integers is called a D(n)-m-tuple if the product of any two of them increased by n is a perfect square. Let k be a positive integer. In this paper, we show that if {k 2, k 2 + 1, 4k 2 + 1, d} is a D(−k 2)-quadruple, then d = 1, and that if {k 2 − 1, k 2, 4k 2 − 1, d} is a D(k 2)-quadruple, then d = 8k 2(2k 2 − 1).  相似文献   

10.
We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(Kr,r,n) such that every n-term graphic sequence π = (d1,d2,...,dn) with term sum σ(π) = d1 + d2 + ... + dn ≥ σ(Kr,r,n) is potentially Kr,r-graphic, where Kr,r is an r × r complete bipartite graph, i.e. π has a realization G containing Kr,r as its subgraph. In this paper, the values σ(Kr,r,n) for even r and n ≥ 4r2 - r - 6 and for odd r and n ≥ 4r2 + 3r - 8 are determined.  相似文献   

11.
Aiming at a simultaneous extension of Khintchine(X,X,m,T)(X,\mathcal{X},\mu,T) and a set A ? XA\in\mathcal{X} of positive measure, the set of integers n such that A T^2nA T^knA)(A)^k+1-\mu(A{\cap} T^{n}A{\cap} T^{2n}A{\cap} \ldots{\cap} T^{kn}A)>\mu(A)^{k+1}-\epsilon is syndetic. The size of this set, surprisingly enough, depends on the length (k+1) of the arithmetic progression under consideration. In an ergodic system, for k=2 and k=3, this set is syndetic, while for kòf(x)f(Tnx)f(T2nx)? f(Tknx)  dm(x)\int{f(x)f(T^{n}x)f(T^{2n}x){\ldots} f(T^{kn}x) \,d\mu(x)} , where k and n are positive integers and f is a bounded measurable function. We also derive combinatorial consequences of these results, for example showing that for a set of integers E with upper Banach density d*(E)>0 and for all {n ? \mathbbZ\colon d*(E?(E+n)?(E+2n)?(E+3n)) > d*(E)4-e}\big\{n\in\mathbb{Z}{\colon} d^*\big(E\cap(E+n)\cap(E+2n)\cap(E+3n)\big) > d^*(E)^4-\epsilon\big\}  相似文献   

12.
Let R be a prime ring of char R ≠ = 2 with center Z(R) and with extended centroid C, d a nonzero derivation of R and f(x 1, ..., x n ) a nonzero multilinear polynomial over C. Suppose that x s d(x)x t Z(R) for all x ∈ {d(f(x 1, ..., x n ))|x 1, ..., x n ρ}, where ρ is a nonzero right ideal of R and s ≥ 0, t ≥ 0 are fixed integers. If d(ρ)ρ ≠ = 0, then ρ C = eRC for some idempotent e in the socle of RC and f(x 1, ..., x n ) N is central-valued in eRCe, where N = s + t + 1.   相似文献   

13.
In [2], it was shown that if a and b are multiplicatively independent integers and ɛ > 0, then the inequality gcd (an − 1,bn − 1) < exp(ɛn) holds for all but finitely many positive integers n. Here, we generalize the above result. In particular, we show that if f(x),f1(x),g(x),g1(x) are non-zero polynomials with integer coefficients, then for every ɛ > 0, the inequality holds for all but finitely many positive integers n.  相似文献   

14.
For a classical theory T, ℋ(T) denotes the intuitionistic theory of T-normal (i.e. locally T) Kripke structures. S. Buss has asked for a characterization of the theories in the range of ℋ and raised the particular question of whether HA is an ℋ-theory. We show that T i ∈ range(ℋ) iff T i = ℋ(T). As a corollary, no fragment of HA extending 1 belongs to the range of ℋ. A. Visser has already proved that HA is not in the range of H by different methods. We provide more examples of theories not in the range of ℋ. We show PA-normality of once-branching Kripke models of HA + MP, where it is not known whether the same holds if MP is dropped. Received: 15 August 1999 / Published online: 3 October 2001  相似文献   

15.
 Let Γ be a distance-regular graph of diameter d. The height of Γ is defined by h = max{jp d d,j ≠ 0}. Let e, f be positive integers such that e < f and e + fd, and let d = 2e + s for some positive integer s. We show that if k e = k f , h≤ 2s and the height h is even, then Γ is an antipodal 2-cover. Received: October 23, 1997 Final version received: July 31, 2000  相似文献   

16.
Let a(Kr,+1 - K3,n) be the smallest even integer such that each n-term graphic sequence п= (d1,d2,…dn) with term sum σ(п) = d1 + d2 +…+ dn 〉 σ(Kr+1 -K3,n) has a realization containing Kr+1 - K3 as a subgraph, where Kr+1 -K3 is a graph obtained from a complete graph Kr+1 by deleting three edges which form a triangle. In this paper, we determine the value σ(Kr+1 - K3,n) for r ≥ 3 and n ≥ 3r+ 5.  相似文献   

17.
In this paper, we prove that if a, b and c are pairwise coprime positive integers such that a^2+b^2=c^r,a〉b,a≡3 (mod4),b≡2 (mod4) and c-1 is not a square, thena a^x+b^y=c^z has only the positive integer solution (x, y, z) = (2, 2, r).
Let m and r be positive integers with 2|m and 2 r, define the integers Ur, Vr by (m +√-1)^r=Vr+Ur√-1. If a = |Ur|,b=|Vr|,c = m^2+1 with m ≡ 2 (mod 4),a ≡ 3 (mod 4), and if r 〈 m/√1.5log3(m^2+1)-1, then a^x + b^y = c^z has only the positive integer solution (x,y, z) = (2, 2, r). The argument here is elementary.  相似文献   

18.
We prove that the “quadratic irrational rotation” exhibits a central limit theorem. More precisely, let α be an arbitrary real root of a quadratic equation with integer coefficients; say, α = $ \sqrt 2 $ \sqrt 2 . Given any rational number 0 < x < 1 (say, x = 1/2) and any positive integer n, we count the number of elements of the sequence α, 2α, 3α, …, modulo 1 that fall into the subinterval [0, x]. We prove that this counting number satisfies a central limit theorem in the following sense. First, we subtract the “expected number” nx from the counting number, and study the typical fluctuation of this difference as n runs in a long interval 1 ≤ nN. Depending on α and x, we may need an extra additive correction of constant times logarithm of N; furthermore, what we always need is a multiplicative correction: division by (another) constant times square root of logarithm of N. If N is large, the distribution of this renormalized counting number, as n runs in 1 ≤ nN, is very close to the standard normal distribution (bell shaped curve), and the corresponding error term tends to zero as N tends to infinity. This is the main result of the paper (see Theorem 1.1). The proof is rather complicated and long; it has many interesting detours and byproducts. For example, the exact determination of the key constant factors (in the additive and multiplicative norming), which depend on α and x, requires surprisingly deep algebraic tools such as Dedeking sums, the class number of quadratic fields, and generalized class number formulas. The crucial property of a quadratic irrational is the periodicity of its continued fraction. Periodicity means self-similarity, which leads us to Markov chains: our basic probabilistic tool to prove the central limit theorem. We also use a lot of Fourier analysis. Finally, I just mention one byproduct of this research: we solve an old problem of Hardy and Littlewood on diophantine sums.  相似文献   

19.
Consider a general random walk on ℤd together with an i.i.d. random coloring of ℤd. TheT, T -1-process is the one where time is indexed by ℤ, and at each unit of time we see the step taken by the walk together with the color of the newly arrived at location. S. Kalikow proved that ifd = 1 and the random walk is simple, then this process is not Bernoulli. We generalize his result by proving that it is not Bernoulli ind = 2, Bernoulli but not Weak Bernoulli ind = 3 and 4, and Weak Bernoulli ind ≥ 5. These properties are related to the intersection behavior of the past and the future of simple random walk. We obtain similar results for general random walks on ℤd, leading to an almost complete classification. For example, ind = 1, if a step of sizex has probability proportional to l/|x|α (x ⊋ 0), then theT, T -1-process is not Bernoulli when α ≥2, Bernoulli but not Weak Bernoulli when 3/2 ≤α < 2, and Weak Bernoulli when 1 < α < 3/2. Research partially carried out while a guest of the Department of Mathematics, Chalmers University of Technology, Sweden in January 1996. Research supported by grants from the Swedish Natural Science Research Council and from the Royal Swedish Academy of Sciences.  相似文献   

20.
Let c ≥ 3 be a positive integer such that c, 4c + 1, c − 1 are square-free integers relatively prime in pairs. In this paper we find the minimal index and determine all elements with minimal index in the bicyclic biquadratic field K = ℚ(√(4c + 1)c, √(c − 1)c). The author was supported by the Ministry of Science, Education and Sports, Republic of Croatia, grant 037-0372781-2821.  相似文献   

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

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