共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper we investigate the existence of holey self-orthogonal Latin squares with a symmetric orthogonal mate of type 2nu1 (HSOLSSOM(2nu1)). For u2, necessary conditions for existence of such an HSOLSSOM are that u must be even and n3u/2+1. Xu Yunqing and Hu Yuwang have shown that these HSOLSSOMs exist whenever either (1) n9 and n3u/2+1 or (2) n263 and n2(u-2). In this paper we show that in (1) the condition n9 can be extended to n30 and that in (2), the condition n263 can be improved to n4, except possibly for 19 pairs (n,u), the largest of which is (53,28). 相似文献
2.
C. Iliopoulos K. Perdikuri E. Theodoridis A. Tsakalidis K. Tsichlas 《Journal of Discrete Algorithms》2007,5(2):229-242
In this paper we present three algorithms for the Motif Identification Problem in Biological Weighted Sequences. The first algorithm extracts repeated motifs from a biological weighted sequence. The motifs correspond to repetitive words which are approximately equal, under a Hamming distance, with probability of occurrence 1/k, where k is a small constant. The second algorithm extracts common motifs from a set of N2 weighted sequences. In this case, the motifs consists of words that must occur with probability 1/k, in 1qN distinct sequences of the set. The third algorithm extracts maximal pairs from a biological weighted sequence. A pair in a sequence is the occurrence of the same word twice. In addition, the algorithms presented in this paper improve previous work on these problems. 相似文献
3.
Let R be a ring generated by l elements with stable range r. Assume that the group ELd(R) has Kazhdan constant 0>0 for some dr+1. We prove that there exist (0,l)>0 and , s.t. for every nd, ELn(R) has a generating set of order k and a Kazhdan constant larger than . As a consequence, we obtain for where n3, a Kazhdan constant which is independent of n w.r.t. generating set of a fixed size. 相似文献
4.
Let I(F) be the distribution function (d.f.) of the maximum of a random walk whose i.i.d. increments have the common d.f. F and a negative mean. We derive a recursive sequence of embedded random walks whose underlying d.f.'s Fk converge to the d.f. of the first ladder variable and satisfy FF1F2 on [0,∞) and I(F)=I(F1)=I(F2)=. Using these random walks we obtain improved upper bounds for the difference of I(F) and the d.f. of the maximum of the random walk after finitely many steps. 相似文献
5.
In this paper we present some new results about unlike powers in arithmetic progression. We prove among other things that for given k 4 and L 3 there are only finitely many arithmetic progressions of the form with xi , gcd(x0, xl) = 1 and 2 li L for i = 0, 1, …, k − 1. Furthermore, we show that, for L = 3, the progression (1, 1,…, 1) is the only such progression up to sign. Our proofs involve some well-known theorems of Faltings [9], Darmon and Granville [6] as well as Chabauty's method applied to superelliptic curves. 相似文献
6.
For integers m2, we study divergent continued fractions whose numerators and denominators in each of the m arithmetic progressions modulo m converge. Special cases give, among other things, an infinite sequence of divergence theorems, the first of which is the classical Stern–Stolz theorem.We give a theorem on a class of Poincaré-type recurrences which shows that they tend to limits when the limits are taken in residue classes and the roots of their characteristic polynomials are distinct roots of unity.We also generalize a curious q-continued fraction of Ramanujan's with three limits to a continued fraction with k distinct limit points, k2. The k limits are evaluated in terms of ratios of certain q-series.Finally, we show how to use Daniel Bernoulli's continued fraction in an elementary way to create analytic continued fractions with m limit points, for any positive integer m2. 相似文献
7.
Alfredo García Ferran Hurtado Clemens Huemer Javier Tejel Pavel Valtr 《Computational Geometry》2009,42(9):913-922
Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph. 相似文献
8.
The purpose of this paper is to introduce and construct the implicit and explicit viscosity iterative processes by a generalized contraction mapping f and a nonexpansive semigroup {T(t):t0}, and to prove that under suitable conditions these iterative processes converge strongly to a unique common fixed point of {T(t):t0} in reflexive Banach spaces which admits a weakly sequentially continuous duality mapping. 相似文献
9.
Let D be an X-outer S-derivation of a prime ring R, where S is an automorphism of R. The following is proved among other things: The degree of the minimal semi-invariant polynomial of the Ore extension R[X;S,D] is ν if charR=0, and is pkν for some k0 if charR=p2, where ν is the least integer ν1 such that SνDS−ν−D is X-inner. A similar result holds for cv-polynomials. These are done by introducing the new notion of k-basic polynomials for each integer k0, which enable us to analyze semi-invariant polynomials inductively. 相似文献
10.
We show that, for any fixed constant k3, the sum of the distances between all pairs of vertices of an abstract graph with n vertices and treewidth at most k can be computed in O(nlogk−1n) time.We also show that, for any fixed constant k2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(nlogk+1n) expected time. The dilation (or stretch-factor) of a geometric graph is defined as the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance.The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth. 相似文献
11.
On shredders and vertex connectivity augmentation 总被引:1,自引:0,他引:1
We consider the following problem: given a k-(node) connected graph G find a smallest set F of new edges so that the graph G+F is (k+1)-connected. The complexity status of this problem is an open question. The problem admits a 2-approximation algorithm. Another algorithm due to Jordán computes an augmenting edge set with at most (k−1)/2 edges over the optimum. CV(G) is a k-separator (k-shredder) of G if |C|=k and the number b(C) of connected components of G−C is at least two (at least three). We will show that the problem is polynomially solvable for graphs that have a k-separator C with b(C)k+1. This leads to a new splitting-off theorem for node connectivity. We also prove that in a k-connected graph G on n nodes the number of k-shredders with at least p components (p3) is less than 2n/(2p−3), and that this bound is asymptotically tight. 相似文献
12.
Let {X,Xn;n1} be a sequence of i.i.d. real-valued random variables and set , n1. Let h() be a positive nondecreasing function such that . Define Lt=logemax{e,t} for t0. In this note we prove that if and only if E(X)=0 and E(X2)=1, where , t1. When h(t)≡1, this result yields what is called the Davis–Gut law. Specializing our result to h(t)=(Lt)r, 0<r1, we obtain an analog of the Davis–Gut law. 相似文献
13.
D. S. Lubinsky 《Journal of Approximation Theory》2000,104(2):17
For n1, let {xjn}nj=1 be n distinct points in a compact set K
and letLn[·] denote the corresponding Lagrange interpolation operator. Let v be a suitably restricted function on K. What conditions on the array {xjn}1jn, n1 ensure the existence of p>0 such that limn→∞ (f−Ln[f]) vLp(K)=0 for very continuous f: K→
? We show that it is necessary and sufficient that there exists r>0 with supn1 πnvLr(K) ∑nj=1 (1/|π′n| (xjn))<∞. Here for n1, πn is a polynomial of degree n having {xjn}nj=1 as zeros. The necessity of this condition is due to Ying Guang Shi. 相似文献
14.
Hajnal and Corrádi proved that any simple graph on at least 3k vertices with minimal degree at least 2k contains k independent cycles. We prove the analogous result for chorded cycles. Let G be a simple graph with |V(G)|4k and minimal degree δ(G)3k. Then G contains k independent chorded cycles. This result is sharp. 相似文献
15.
Kirsten Eisentrger 《Journal of Algebra》2007,310(2):170
Let k be a subfield of a p-adic field of odd residue characteristic, and let be the function field of a variety of dimension n1 over k. Then Hilbert's Tenth Problem for is undecidable. In particular, Hilbert's Tenth Problem for function fields of varieties over number fields of dimension 1 is undecidable. 相似文献
16.
A new parallel extended GCD algorithm is proposed. It matches the best existing parallel integer GCD algorithms of Sorenson and Chor and Goldreich, since it can be achieved in O(n/logn) time using at most n1+ processors on CRCW PRAM. Sorenson and Chor and Goldreich both use a modular approach which consider the least significant bits. By contrast, our algorithm only deals with the leading bits of the integers u and v, with uv. This approach is more suitable for extended GCD algorithms since the coefficients of the extended version a and b, such that au+bv=gcd(u,v), are deeply linked with the order of magnitude of the rational v/u and its continuants. Consequently, the computation of such coefficients is much easier. 相似文献
17.
Janez
erovnik 《Advances in Applied Mathematics》2008,41(2):197-205
Let
be a direct product of cycles. It is known that for any r1, and any n2, each connected component of G contains a so-called canonical r-perfect code provided that each ℓi is a multiple of rn+(r+1)n. Here we prove that up to a reasonably defined equivalence, these are the only perfect codes that exist. 相似文献
18.
Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ2(G)n+k-1. Let v1,…,vk be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C1,…,Ck with viV(Ci) for all 1ik.Then G has k vertex-disjoint cycles such that
- (i) for all 1ik.
- (ii) , and
- (iii) At least k-1 of the k cycles are triangles.
Keywords: Degree sum condition; Independent vertices; Vertex-disjoint cycles 相似文献
19.
We introduce polar SAT and show that a general SAT can be reduced to it in polynomial time. A set of clauses C is called polar if there exists a partition CpCn=C, called a polar partition, such that each clause in Cp involves only positive (i.e., non-complemented) variables, while each clause in Cn contains only negative (i.e., complemented) variables. A polar set of clauses C=(Cp,Cn) is called (p,n)-polar, where p1 and n1, if each clause in Cp (respectively, in Cn) contains exactly p (respectively, exactly n) literals. We classify all (p,n)-polar SAT Problems according to their complexity. Specifically, a (p,n)-Polar SAT problem is NP-complete if either p>n2 or n>p2. Otherwise it can be solved in polynomial time. We introduce two new hereditary classes of graphs, namely polar satgraphs and polar (3,2)-satgraphs, and we characterize them in terms of forbidden induced subgraphs. Both characterization involve an infinite number of minimal forbidden induced subgraphs. As are result, we obtain two narrow hereditary subclasses of weakly chordal graphs where Independent Domination is an NP-complete problem. 相似文献
20.
The (isotropic) orthogonal graph O(2ν+δ,q) over of odd characteristic, where ν1 and δ=0,1 or 2 is introduced. When ν=1, O(21+δ,q) is a complete graph. When ν2, O(2ν+δ,q) is strongly regular and its parameters are computed, as well as its chromatic number. The automorphism groups of orthogonal graphs are also determined. 相似文献