共查询到20条相似文献,搜索用时 234 毫秒
1.
We show the power of posets in computational geometry by solving several problems posed on a set S of n points in the plane: (1) find the n − k − 1 rectilinear farthest neighbors (or, equivalently, k nearest neighbors) to every point of S (extendable to higher dimensions), (2) enumerate the k largest (smallest) rectilinear distances in decreasing (increasing) order among the points of S, (3) given a distance δ > 0, report all the pairs of points that belong to S and are of rectilinear distance δ or more (less), covering k ≥ n/2 points of S by rectilinear (4) and circular (5) concentric rings, and (6) given a number k ≥ n/2 decide whether a query rectangle contains k points or less. 相似文献
2.
Some Ore-type Results for Matching and Perfect Matching in <Emphasis Type="Italic">k</Emphasis>-uniform Hypergraphs 下载免费PDF全文
Let S1 and S2 be two (k-1)-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E(H) such that S1 ∩ e ≠∅ and S2 ∩ e ≠∅ or e ⊆ S1 ∪ S2 or e ⊇ S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2k2-k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent (k-1)-sets equal to 2n-4(k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+(k-2)k. If the degree sum of any two middle independent (k-1)-subsets is larger than 2(d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent (k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n. 相似文献
3.
Tams Lengyel 《Discrete Mathematics》1996,150(1-3):281-292
We partially characterize the rational numbers x and integers n 0 for which the sum ∑k=0∞ knxk assumes integers. We prove that if ∑k=0∞ knxk is an integer for x = 1 − a/b with a, b> 0 integers and gcd(a,b) = 1, then a = 1 or 2. Partial results and conjectures are given which indicate for which b and n it is an integer if a = 2. The proof is based on lower bounds on the multiplicities of factors of the Stirling number of the second kind, S(n,k). More specifically, we obtain
for all integers k, 2 k n, and a 3, provided a is odd or divisible by 4, where va(m) denotes the exponent of the highest power of a which divides m, for m and a> 1 integers.
New identities are also derived for the Stirling numbers, e.g., we show that ∑k=02nk! S(2n, k) , for all integers n 1. 相似文献
4.
Jean-Philippe Furter 《Journal of Pure and Applied Algebra》1998,130(3):123-292
We study the degree of the inverse of an automorphism f of the affine n-space over a
-algebra k, in terms of the degree d of f and of other data. For n = 1, we obtain a sharp upper bound for deg (f− 1) in terms of d and of the nilpotency index of the ideal generated by the coefficients of f′'. For n = 2 and arbitrary d≥ 3, we construct a (triangular) automorphism f of Jacobian one such that deg(f− 1) > d. This answers a question of A. van den Essen (see [3]) and enables us to deduce that some schemes introduced by authors to study the Jacobian conjecture are not reduced. Still for n = 2, we give an upper bound for deg (f− 1) when f is triangular. Finally, in the case d = 2 and any n, we complete a result of G. Meisters and C. Olech and use it to give the sharp bound for the degree of the inverse of a quadratic automorphism, with Jacobian one, of the affine 3-space. 相似文献
5.
J. -F. Sacl 《Discrete Mathematics》1996,150(1-3):359-369
In this paper, we give a lower bound for the size B(n) of a minimum broadcast graph of order n = 2k − 4, 2k − 6, 2k − 5 or 2k − 3 which is shown to be accurate in the cases when k = 5 and k = 6. This result provides, together with an upper bound obtained by a construction given in Bermond et al. (1992), an estimation of the value B(n) for n = 2k − 4. 相似文献
6.
A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed. 相似文献
7.
Michel Sebille 《Discrete Mathematics》2001,240(1-3):197-204
In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an Sλ(t,k,v) such thatthen there exists an Sλ(v−t+1)(t,k,v+1) having v+1 pairwise disjoint subdesigns Sλ(t,k,v). Moreover, if Bi and Bj are any two blocks belonging to two distinct such subdesigns, then d|Bi∩Bj|<k−h. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an Sλ(t,k,v) such thatwhere m=min{s,v−k} and n=min{i,t}, then there exists anhaving
pairwise disjoint subdesigns Sλ(t,k,v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs. 相似文献
8.
Kathy Hoke 《Discrete Applied Mathematics》1995,60(1-3):211-217
Let P be a simplicial d-polytope with n facets ((d − 1)-dimensional faces) in Rd. A shelling of P is an ordering of the facets of P such that the intersection of each facet F with the union of all facets that precede it the ordering is a nonempty union of (d − 2)-faces of F. The following open question was raised by Tverberg and is recorded in [4]. Suppose for some k < n, there is an ordering of k of the facets of P so that the intersection of each of these facets with the union of all of the facets that precede it in the ordering is a nonempty union of (d − 2)-faces. Can this initial “segment” be extended to a shelling of all the facets? This question is open even in the case that P is the dual of the d-dimensional hypercube. The question in this case has resurfaced several times since G. Danaraj and V. Klee (1978) in a variety of forms. It is related to the hierarchies of completely unimodal pseudo-Boolean functions studied in P.L. Hammer et al. (1988), the author (1988) and D. Wiedemann (1986). (A pseudo-Boolean function is a function mapping the vertices of the d-dimensional hypercube into the reals). In this paper, the hierarchies are compared and combined. This hierarchy is then extended to general simple polytopes, and the relationship to the above open question is explained. 相似文献
9.
A k-connected graph G is said to be critically k-connected if G−v is not k-connected for any vV(G). We show that if n,k are integers with k4 and nk+2, and G is a critically k-connected graph of order n, then |E(G)|n(n−1)/2−p(n−k)+p2/2, where p=(n/k)+1 if n/k is an odd integer and p=n/k otherwise. We also characterize extremal graphs. 相似文献
10.
Yoshimi Egawa Mariko Hagita Ken-ichi Kawarabayashi Hong Wang 《Discrete Mathematics》2003,270(1-3):115-125
Let d, k and n be three integers with k3, d4k−1 and n3k. We show that if d(x)+d(y)d for each pair of nonadjacent vertices x and y of a graph G of order n, then G contains k vertex-disjoint cycles converting at least min{d,n} vertices of G. 相似文献
11.
In this note, we prove that if C is a duadic binary abelian code with splitting μ=μ−1 and the minimum odd weight of C satisfies d2−d+1≠n, then d(d−1)n+11. We show by an example that this bound is sharp. A series of open problems on this subject are proposed. 相似文献
12.
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. 相似文献
13.
A graph G is said to be n-factor-critical if G−S has a 1-factor for any SV(G) with |S|=n. In this paper, we prove that if G is a 2-connected n-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. To extend this theorem, we define a (k,n)-factor-critical graph to be a graph G such that G−S has a k-factor for any SV(G) with |S|=n. We conjecture that if G is a 2-connected (k,n)-factor-critical graph of order p with
, then G is hamiltonian with some exceptions. In this paper, we characterize all such graphs that satisfy the assumption, but are not 1-tough. Using this, we verify the conjecture for k2. 相似文献
14.
Lszl Liptk 《Discrete Mathematics》1997,170(1-3):203-209
We prove using a direct construction that one can choose n − 2 subsets of an n-element set with different cardinality such that none of them contains any other. As a generalization, we prove that if for any j we can have at most k subsets containing exactly j elements (k> 1), then for n 5 we can choose at most k(n − 3) subsets from an n-element set such that they form a Sperner system. Moreover, we prove that this can be achieved if n is large enough, and give a construction for n 8k − 4. 相似文献
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.
Pierre-Alain Cherix 《Linear and Multilinear Algebra》1995,39(1):153-160
A telephone network can be modeled by a kind of graph called a uniform connector. In this model the notion of (n,k,d)-expander is defined to quantify the ability of a graph to transmit information; d is called the expanding constant. Let Г be a finite group and S be a generating system of Г the Kazhdan constant K(Г,S), gives a lower bound for the expanding constant of a double cover of the Cayley graph of Г associated with S. In this paper, we compute Kazhdan constants for some semidirect products, In particular we get these constants for dihedral groups. 相似文献
17.
Amihood Amir Alberto Apostolico Gad M. Landau Giorgio Satta 《Journal of Discrete Algorithms》2003,1(5-6):409-421
We consider the problem of fingerprinting text by sets of symbols. Specifically, if S is a string, of length n, over a finite, ordered alphabet Σ, and S′ is a substring of S, then the fingerprint of S′ is the subset φ of Σ of precisely the symbols appearing in S′. In this paper we show efficient methods of answering various queries on fingerprint statistics. Our preprocessing is done in time O(n|Σ|lognlog|Σ|) and enables answering the following queries:
- (1)Given an integer k, compute the number of distinct fingerprints of size k in time O(1).
- (2)Given a set φΣ, compute the total number of distinct occurrences in S of substrings with fingerprint φ in time O(|Σ|logn).
18.
We consider scalar-valued matrix functions for n×n matrices A=(aij) defined by Where G is a subgroup of Sn the group of permutations on n letters, and χ is a linear character of G. Two such functions are the permanent and the determinant. A function (1) is multiplicative on a semigroup S of n×n matrices if d(AB)=d(A)d(B) AB∈S.
With mild restrictions on the underlying scalar ring we show that every element of a semigroup containing the diagonal matrices on which (1) is multiplicative can have at most one nonzero diagonal(i.e., diagonal with all nonzero entries)and conversely, provided that χ is the principal character(χ≡1). 相似文献
With mild restrictions on the underlying scalar ring we show that every element of a semigroup containing the diagonal matrices on which (1) is multiplicative can have at most one nonzero diagonal(i.e., diagonal with all nonzero entries)and conversely, provided that χ is the principal character(χ≡1). 相似文献
19.
《Discrete Mathematics》1999,200(1-3):137-147
We form squares from the product of integers in a short interval [n, n + tn], where we include n in the product. If p is prime, p|n, and (2p) > n, we prove that p is the minimum tn. If no such prime exists, we prove tn √5n when n> 32. If n = p(2p − 1) and both p and 2p − 1 are primes, then tn = 3p> 3 √n/2. For n(n + u) a square > n2, we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g2(n) be minimal such that a square can be formed as the product of distinct integers from [n, g2(n)] so that no pair of consecutive integers is omitted. We prove that g2(n) 3n − 3, and list or conjecture the values of g2(n) for all n. We describe the generalization to kth powers and conjecture the values for large n. 相似文献
20.
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. 相似文献