首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 328 毫秒
1.
The isovariant version of Borsuk–Ulam type theorems has been studied by Wasserman and the first author. In this paper, first we consider the relation between the existence of Cn-isovariant maps from free Cn-manifolds to representation spheres and Borsuk–Ulam type inequalities for their dimensions. Our main result classifies the Cn-isovariant maps by Cn-isovariant homotopy types when a Borsuk–Ulam type inequality holds. For proving it, we use the multidegree of a Cn-equivariant map developed by the first author.  相似文献   

2.
Discrete subspaces of countably tight compacta   总被引:1,自引:0,他引:1  
Our main result is that the following cardinal arithmetic assumption, which is a slight weakening of GCH, “2κ is a finite successor of κ for every cardinal κ”, implies that in any countably tight compactum X there is a discrete subspace D with . This yields a (consistent) confirmation of Alan Dow’s Conjecture 2 from [A. Dow, Closures of discrete sets in compact spaces, Studia Math. Sci. Hung. 42 (2005) 227–234].  相似文献   

3.
Finding the closest or farthest line segment (line) from a point are fundamental proximity problems. Given a set S of n points in the plane and another point q, we present optimal O(nlogn) time, O(n) space algorithms for finding the closest and farthest line segments (lines) from q among those spanned by the points in S. We further show how to apply our techniques to find the minimum (maximum) area triangle with a vertex at q and the other two vertices in S{q} in optimal O(nlogn) time and O(n) space. Finally, we give an O(nlogn) time, O(n) space algorithm to find the kth closest line from q and show how to find the k closest lines from q in O(nlogn+k) time and O(n+k) space.  相似文献   

4.
Let M1 and M2 be two matroids on the same ground set S. We conjecture that if there do not exist disjoint subsets A1,A2,…,Ak+1 of S, such that ispM1(Ai)≠Ø, and similarly for M2, then S is partitioned into k sets, each independent in both M1 and M2. This is a possible generalization of König's edge-coloring theorem. We prove the conjecture for the case k=2 and for a regular case, in which both matroids have the same rank d, and S consists of k·d elements. Finally, we prove another special case related to a conjecture of Rota.  相似文献   

5.
Given a set S of n points in , and an integer k such that 0k<n, we show that a geometric graph with vertex set S, at most n−1+k edges, maximum degree five, and dilation O(n/(k+1)) can be computed in time O(nlogn). For any k, we also construct planar n-point sets for which any geometric graph with n−1+k edges has dilation Ω(n/(k+1)); a slightly weaker statement holds if the points of S are required to be in convex position.  相似文献   

6.
Let T be a set of n triangles in three-dimensional space, let s be a line segment, and let t be a triangle, both disjoint from T. We consider the subdivision of T based on (in)visibility from s; this is the visibility map of the segment s with respect to T. The visibility map of the triangle t is defined analogously. We look at two different notions of visibility: strong (complete) visibility, and weak (partial) visibility. The trivial Ω(n2) lower bound for the combinatorial complexity of the strong visibility map of both s and t is almost tight: we prove an O(n2(n)) upper bound for both structures, where (n) is the extremely slowly increasing inverse Ackermann function. Furthermore, we prove that the weak visibility map of s has complexity Θ(n5), and the weak visibility map of t has complexity Θ(n7). If T is a polyhedral terrain, the complexity of the weak visibility map is Ω(n4) and O(n5), both for a segment and a triangle. We also present efficient algorithms to compute all discussed structures.  相似文献   

7.
One of the most important objects in genetic mapping and forensic studies are minisatellites. They consist of a heterogeneous tandem array of short repeat units called variants. The evolution of minisatellites is realized by tandem duplication and tandem deletion of variants. Jeffrey et al. proposed a method to obtain the sequence of variants, called maps. Bérard and Rivals designed the first algorithm of comparison of two minisatellite maps under an evolutionary model including deletion, insertion, mutation, amplification and contraction. The complexity of this first algorithm was O(n4) in time and O(n3) in space where n is the size of the maps. In this paper we propose a more efficient algorithm using the same generic evolutionary model which is O(n3) in time and O(n2) in space. Our algorithm with this better efficiency can even solve generalized and more refined models.  相似文献   

8.
Z 《Discrete Mathematics》2008,308(14):2984-3002
We give a mass formula for self-dual codes over Zp2, where p is an odd prime. Using the mass formula, we classify such codes of lengths up to n=8 over the ring Z9, n=7 over Z25 and n=6 over Z49.  相似文献   

9.
Let (Σ,j) be a Riemann surface. The almost complex manifolds (M,J) for which the J-holomorphic curves :ΣM are of variational type, are characterized. This problem is related to the existence of a vertically non-degenerate closed complex 3-form on Σ×M (see Theorem 4.3 below), which determines a family of J-symplectic structures on (M,J) parametrized by Σ.  相似文献   

10.
Let n be a positive integer and · any norm in . Denote by B the unit ball of · and the class of convex lattice polygons with n vertices and least ·-perimeter. We prove that after suitable normalization, all members of tend to a fixed convex body, as n→∞.  相似文献   

11.
Covering point sets with two disjoint disks or squares   总被引:1,自引:0,他引:1  
We study the following problem: Given a set of red points and a set of blue points on the plane, find two unit disks CR and CB with disjoint interiors such that the number of red points covered by CR plus the number of blue points covered by CB is maximized. We give an algorithm to solve this problem in O(n8/3log2n) time, where n denotes the total number of points. We also show that the analogous problem of finding two axis-aligned unit squares SR and SB instead of unit disks can be solved in O(nlogn) time, which is optimal. If we do not restrict ourselves to axis-aligned squares, but require that both squares have a common orientation, we give a solution using O(n3logn) time.  相似文献   

12.
Recently, it was proved by Leedham-Green and others that with a finite number of exceptions, every p-group of coclass r is a quotient of one of only a finite number of p-adic uniserial space groups. In this paper we use that structure to demonstrate that there are only finitely many isomorphism classes of cohomology rings of 2-groups of coclass r with coefficients in any fixed field k of characteristic 2. In addition, there is experimental evidence indicating that in many cases successive quotients of the uniserial space groups have isomorphic cohomology rings.  相似文献   

13.
In this paper we first give a lower bound on multiplicities for Buchsbaum homogeneous k-algebras A in terms of the dimension d, the codimension c, the initial degree q, and the length of the local cohomology modules of A. Next, we introduce the notion of Buchsbaum k-algebras with minimal multiplicity of degree q, and give several characterizations for those rings. In particular, we will show that those algebras have linear free resolutions. Further, we will give many examples of those algebras.  相似文献   

14.
We study the existence of solutions for the nonlinear elliptic system
where Ω is a bounded domain, f1 is superlinear and f2 is sublinear at zero and infinity, h1 and h2 are perturbation terms. We will show that the system has at least two semi-trivial solutions (u,0), (0,v) and a nontrivial solution (u*,v*).  相似文献   

15.
The performance of a linear t-error correcting code over a q-ary symmetric memoryless channel with symbol error probability ε is characterized by the probability that a transmission error will remain undetected. This probability is a function of ε involving the code weight distribution and the weight distribution of the cosets of minimum weight at most t. When the undetectable error probability is an increasing function of ε, the code is called t-proper.

The paper presents sufficient conditions for t-properness and a list of codes known to be proper, many of which have been studied by these sufficient conditions. Special attention is paid to error detecting codes of interest in modern communication.  相似文献   


16.
By constructing a class of solutions to the integral inequality for t  t0 large enough, where 0<A1a(τ)A2<+ and λ>1, that tend to zero as t→+ we address an open problem in the theory of nonlinear oscillations.  相似文献   

17.
We introduce the concept of N-differential graded algebras (N-dga), and study the moduli space of deformations of the differential of an N-dga. We prove that it is controlled by what we call the (M,N)-Maurer–Cartan equation.  相似文献   

18.
We prove a Bruckner–Garg type theorem for the fiber structure of a generic map from a continuum X into the unit interval I. We also study the specific case of X=S2. We show that each nondegenerate component of each fiber of a generic map in C(S2,I) is figure-eight-like. This together with a result by Krasinkiewicz and Levin gives that each nondegenerate component of each fiber of a generic map in C(S2,I) is hereditarily indecomposable and figure-eight-like. We also show that pseudoarcs, pseudocircles and Lakes of Wada appear in abundance in fibers of a generic map in C(S2,I). We also exhibit a general method for proving when a P-like hereditarily indecomposable continuum is Q-like when Q is a certain graph containing P.  相似文献   

19.
The Padmakar–Ivan index of a graph G is the sum over all edges uv of G of number of edges which are not equidistant from u and v. In this work, an exact expression for the PI index of the Cartesian product of bipartite graphs is computed. Using this formula, the PI indices of C4 nanotubes and nanotori are computed.  相似文献   

20.
Let Γ be the boundary of a family tree Γ associated with a supercritical branching process in varying environments. In this paper, the Hausdorff dimension, the upper box dimension and the packing dimension of Γ are computed explicitly. In contrast to the (fixed environment) Galton–Watson case, the Hausdorff and upper box dimension may take different values.  相似文献   

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

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