共查询到20条相似文献,搜索用时 31 毫秒
1.
Laurie B. Hopkins William T. Trotter Douglas B. West 《Discrete Applied Mathematics》1984,8(2):163-187
The interval number of a graph G, denoted i(G), is the least positive integer t for which G is the intersection graph of a family of sets each of which is the union of at most t closed intervals of the real line . Trotter and Harary showed that the interval number of the complete bipartite graph K(m,n) is . Matthews showed that the interval number of the complete multipartite graph K(n1,n2,…,np) was the same as the interval number of K(n1,n2) when n1 = n2 = ? = np. Trotter and Hopkins showed that i(K(n1,n2,…,np)) ≤ 1 + i(K(n1,n2)) whenever p ≥ 2 and n1≥n2≥ ? ≥np. West showed that for each n ≥ 3, there exists a constant cn so that if p ≥ cn,n1 = n2?n ?1, and n2 = n3 = ? np = n, then i(K(n1,n2,…,np) = 1 + i(K(n1, n2)). In view of these results, it is natural to consider the problem of determining those pairs (n1,n2) with n1 ≥ n2 so that i(K(n2,…,np)) = i(K(n1,n2)) whenever p ≥ 2 and n2 ≥ n3 ≥ ? ≥ np. In this paper, we present constructions utilizing Eulerian circuits in directed graphs to show that the only exceptional pairs are (n2 ? n ? 1, n) for n ≥ 3 and (7,5). 相似文献
2.
Minyoung Yun 《Journal of Applied Mathematics and Computing》1997,4(2):453-467
A sort sequenceS n is a sequence of all unordered pairs of indices inI n = 1, 2, ...,n. With a sort sequenceS n, we associate a sorting algorithmA(S n) to sort input setX = x 1, x2, ..., xn as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S n) denote the average number of comparisons required by the algorithmA(S n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S n) over all sort sequencesS n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n). 相似文献
3.
《Journal of Combinatorial Theory, Series B》1987,42(2):156-166
We prove the inequality Σn≥7 (n−6) pn≤v−12 for any 3-dimensional polytope with v vertices and pn n-sided faces, such that Σn≥6 pn≥3. The polytopes satisfying Σn≥7 (n−6) pn=v−12 are described and an interpretation of our results is given in terms of density of n-sided faces in planar graphs. 相似文献
4.
Let Kn denote the set of all n × n nonnegative matrices whose entries have sum n, and let ϕ be a real function on Kn defined by ϕ (X) = Πni=1Σnj=1xij + Πnj=1Σni=1xij − per X for X = [xij] ϵ Kn. A matrix A ϵ Kn is called a ϕ -maximizing matrix on Kn if ϕ (A) ⩾ ϕ (X) for all X ϵ Kn. It is conjectured that Jn = [1/n]n × n is the unique ϕ-maximizing matrix on Kn. In this note, the following are proved: (i) If A is a positive ϕ-maximizing matrix, then A = Jn. (ii) If A is a row stochastic ϕ-maximizing matrix, then A = Jn. (iii) Every row sum and every column sum of a ϕ-maximizing matrix lies between 1 − √2·n!/nn and 1 + (n − 1)√2·n!/nn. (iv) For any p.s.d. symmetric A ϵ Kn, ϕ (A) ⩽ 2 − n!/nn with equality iff A = Jn. (v) ϕ attains a strict local maximum on Kn at Jn. 相似文献
5.
Minimal free resolutions for prime ideals with generic zero (tn3,tn3?n10tn11,tn3?n20tn2, tn31), n1<n2<n3 positive integers, (n1,n2,n3)=1, are determined. 相似文献
6.
G. MacGillivray S. Nasserasr P. van den Driessche 《Linear algebra and its applications》2008,428(7):1740-1752
A primitive digraph D on n vertices has large exponent if its exponent, γ(D), satisfies αn?γ(D)?wn, where αn=⌊wn/2⌋+2 and wn=(n-1)2+1. It is shown that the minimum number of arcs in a primitive digraph D on n?5 vertices with exponent equal to αn is either n+1 or n+2. Explicit constructions are given for fixed n even and odd, for a primitive digraph on n vertices with exponent αn and n+2 arcs. These constructions extend to digraphs with some exponents between αn and wn. A necessary and sufficient condition is presented for the existence of a primitive digraph on n vertices with exponent αn and n+1 arcs. Together with some number theoretic results, this gives an algorithm that determines for fixed n whether the minimum number of arcs is n+1 or n+2. 相似文献
7.
Let Ξ0=[−1,1], and define the segments Ξn recursively in the following manner: for every n=0,1,…, let Ξn+1=Ξn∩[an+1−1,an+1+1], where the point an+1 is chosen randomly on the segment Ξn with uniform distribution. For the radius ρn of Ξn, we prove that n(ρn−1/2) converges in distribution to an exponential law, and we show that the centre of the limiting unit interval has arcsine distribution. 相似文献
8.
Miodrag ?ivkovi? 《Linear algebra and its applications》2006,414(1):310-346
Denote by An the set of square (0, 1) matrices of order n. The set An, n ? 8, is partitioned into row/column permutation equivalence classes enabling derivation of various facts by simple counting. For example, the number of regular (0, 1) matrices of order 8 is 10160459763342013440. Let Dn, Sn denote the set of absolute determinant values and Smith normal forms of matrices from An. Denote by an the smallest integer not in Dn. The sets D9 and S9 are obtained; especially, a9 = 103. The lower bounds for an, 10 ? n ? 19 (exceeding the known lower bound an ? 2fn − 1, where fn is nth Fibonacci number) are obtained. Row/permutation equivalence classes of An correspond to bipartite graphs with n black and n white vertices, and so the other applications of the classification are possible. 相似文献
9.
Suppose {Xnn?-0} are random variables such that for normalizing constants an>0, bn, n?0 we have Yn(·)=(X[n, ·]-bn/an ? Y(·) in D(0.∞) . Then an and bn must in specific ways and the process Y possesses a scaling property. If {Nn} are positive integer valued random variables we discuss when YNn → Y and Y'n=(X[Nn]-bn)/an ? Y'. Results given subsume random index limit theorems for convergence to Brownian motion, stable processes and extremal processes. 相似文献
10.
Rajeeva L. Karandikar Vidyadhar G. Kulkarni 《Stochastic Processes and their Applications》1985,19(2):225-235
Let \s{Xn, n ? 0\s} and \s{Yn, n ? 0\s} be two stochastic processes such that Yn depends on Xn in a stationary manner, i.e. P(Yn ? A\vbXn) does not depend on n. Sufficient conditions are derived for Yn to have a limiting distribution. If Xn is a Markov chain with stationary transition probabilities and Yn = f(Xn,..., Xn+k) then Yn depends on Xn is a stationary way. Two situations are considered: (i) \s{Xn, n ? 0\s} has a limiting distribution (ii) \s{Xn, n ? 0\s} does not have a limiting distribution and exits every finite set with probability 1. Several examples are considered including that of a non-homogeneous Poisson process with periodic rate function where we obtain the limiting distribution of the interevent times. 相似文献
11.
《Journal of Computational and Applied Mathematics》2001,132(2):331-340
In recent years, there has been much interest in the growth and decay rates (Lyapunov constants) of solutions to random recurrences such as the random Fibonacci sequence xn+1=±xn±xn−1. Many of these problems involve nonsmooth dynamics (nondifferentiable invariant measures), making computations hard. Here, however, we consider recurrences with smooth random coefficients and smooth invariant measures. By computing discretised invariant measures and applying Richardson extrapolation, we can compute Lyapunov constants to 10 digits of accuracy. In particular, solutions to the recurrence xn+1=xn+cn+1xn−1, where the {cn} are independent standard normal variables, increase exponentially (almost surely) at the asymptotic rate (1.0574735537…)n. Solutions to the related recurrences xn+1=cn+1xn+xn−1 and xn+1=cn+1xn+dn+1xn−1 (where the {dn} are also independent standard normal variables) increase (decrease) at the rates (1.1149200917…)n and (0.9949018837…)n, respectively. 相似文献
12.
LongYun Ding 《中国科学 数学(英文版)》2012,55(12):2621-2630
Let Xn, n ∈ N be a sequence of non-empty sets, ψn : Xn2 → IR+. We consider the relation E = E((Xn, ψn)n∈N) on ∏n∈N Xn by (x, y) ∈ E((Xn, ψn)n∈N) <=>Σn∈Nψn(x(n), y(n)) < +∞. If E is an equiv- alence relation and all ψn, n ∈ N, are Borel, we show a trichotomy that either IRN/e1≤B E, E1≤B E, or E≤B E0. We also prove that, for a rather general case, E((Xn, ψn)n∈N) is an equivalence relation iff it is an ep-like equivalence relation. 相似文献
13.
Yoshio Mimura 《Journal of Number Theory》1983,16(1):138-146
Apéry introduced a recurrence relation for a proof of the irrationality of ζ(3). Let an (n ≥ 0) satisfy the relation n3an ? (34n3 ? 51n2 + 27n ? 5)an ? 1 + (n ? 1)3an ? 2 = 0. Which values of a0 and a1 cause each an to be an integer? This question is answered and some congruence properties of the an are given. 相似文献
14.
Roger Howe 《Advances in Mathematics》2006,206(1):145-210
We construct bases for the stable branching algebras for the symmetric pairs (GLn,On), (On+m,On×Om) and (Sp2n,GLn). 相似文献
15.
We study the eigenvalues of non-normal square matrices of the form A n ?=?U n T n V n with U n , V n independent Haar distributed on the unitary group and T n real diagonal. We show that when the empirical measure of the eigenvalues of T n converges, and T n satisfies some technical conditions, all these eigenvalues lie in a single ring. 相似文献
16.
《Applied Mathematics Letters》2000,13(1):1-6
In this paper, the linear delay difference equation xn+1 −xn = −anxn−k, where an ≥ 0 (n ≥ 0) any nonnegative coefficient sequence, is considered and its stability properties are investigated. The obtained result is extended to the nonlinear difference equation xn+1 − xn = fn(xn−k). 相似文献
17.
W.Dale Brownawell 《Journal of Number Theory》1974,6(1):11-21
We sharpen a technique of Gelfond to show that, in a sense, the only possible gap-free sequences of “good” Diophantine approximations to a fixed α ∈ C are trivial ones. For example, suppose that a > 1 and that (δn)n=1∞ and (σn)n=1∞ are two positive, strictly increasing unbounded sequences satisfying δn+1 ≤ aδn and σn+1 ≤ aσn. If there is a sequence of nonzero polynomials Pn ∈ Z[x] with deg Pn ≤ δn, deg Pn + log height Pn ≤ σn, and ∣Pn(α)∣ ≤ e?(2a+1)δnσn, then each Pn(α) = 0. 相似文献
18.
《Indagationes Mathematicae (Proceedings)》1979,82(3):307-316
We consider the generalized eigenvalue problem x-Kx = μBx in a complex Banach space E. Here, K and B are bounded linear operators, B is compact, and 1 is not in the spectrum of K. If {En: n = 1, 2,…} is a sequence of closed subspaces of E and Pn: E → En is a linear projection which maps E onto En, then we consider the sequence of approximate eigenvalue problems {xn - PnKxn = μPnBxn in En: n = 1, 2,…}. Assuming that ∥K-PnK∥ → 0 and t|B-PnB∥ → 0 as n → ∞, we prove the convergence of sequences of eigenvalues and eigenelements of the approximate eigenvalue problem to eigenvalues and eigenelements of the original eigenvalue problem, and establish upper bounds for the errors. These error bounds are sharper than those given by Vainikko in Ref. 2 for the more general problem x = μTx in E, T linear and compact, and the sequence of approximate problems {xn = μTnxn in En: n = 1, 2,…}, and do not involve the operator Sn = Tn-PnT ∥;En. 相似文献
19.
V.V. Bavula 《Journal of Pure and Applied Algebra》2010,214(10):1874-263
We study in detail the algebra Sn in the title which is an algebra obtained from a polynomial algebra Pn in n variables by adding commuting, left (but not two-sided) inverses of the canonical generators of Pn. The algebra Sn is non-commutative and neither left nor right Noetherian but the set of its ideals satisfies the a.c.c., and the ideals commute. It is proved that the classical Krull dimension of Sn is 2n; but the weak and the global dimensions of Sn are n. The prime and maximal spectra of Sn are found, and the simple Sn-modules are classified. It is proved that the algebra Sn is central, prime, and catenary. The set In of idempotent ideals of Sn is found explicitly. The set In is a finite distributive lattice and the number of elements in the set In is equal to the Dedekind number dn. 相似文献
20.
Paul Pollack 《Monatshefte für Mathematik》2011,162(3):321-327
Let s(n) denote the sum of the proper divisors of n. Set s 0(n) = n, and for k > 0, put s k (n) := s(s k-1(n)) if s k-1(n) > 0. Thus, perfect numbers are those n with s(n)?=?n and amicable numbers are those n with s(n) ?? n but s 2(n)?=?n. We prove that for each fixed k ?? 1, the set of n which divide s k (n) has density zero, and similarly for the set of n for which s k (n) divides n. These results generalize the theorem of Erd?s that for each fixed k, the set of n for which s k (n)?=?n has density zero. 相似文献