首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 31 毫秒
1.
Let ={P 1,...,P m } be a family of sets. A partial order P(, <) on is naturally defined by the condition P i <P j iff P i is contained in P j . When the elements of are disks (i.e. circles together with their interiors), P(, <) is called a circle order; if the elements of are n-polygons, P(, <) is called an n-gon order. In this paper we study circle orders and n-gon orders. The crossing number of a partial order introduced in [5] is studied here. We show that for every n, there are partial orders with crossing number n. We prove next that the crossing number of circle orders is at most 2 and that the crossing number of n-gon orders is at most 2n. We then produce for every n4 partial orders of dimension n which are not circle orders. Also for every n>3, we prove that there are partial orders of dimension 2n+2 which are not n-gon orders. Finally, we prove that every partial order of dimension 2n is an n-gon order.This research was supported under Natural Sciences and Engineering Research Council of Canada (NSERC Canada) grant numbers A2507 and A0977.  相似文献   

2.
We consider measurable subsets {ofR}n with 0<m()<, and we assume that has a spectral set . (In the special case when is also assumed open, may be obtained as the joint spectrum of a family of commuting self-adjoint operators {H k: 1kn} in L 2 () such that each H k is an extension of i(/x k) on C c (), k=1, ..., n.)It is known that is a fundamental domain for a lattice if is itself a lattice. In this paper, we consider a class of examples where is not assumed to be a lattice. Instead is assumed to have a certain inhomogeneous form, and we prove a necessary and sufficient condition for to be a fundamental domain for some lattice in {ofR}n. We are thus able to decide the question, fundamental domain or not, by considering only properties of the spectrum . Our criterion is obtained as a corollary to a theorem concerning partitions of sets which have a spectrum of inhomogeneous form.Work supported in part by the NSF.Work supported in part by the NSRC, Denmark.  相似文献   

3.
Summary Consideration of the Associativity Equation,x (y z) = (x y) z, in the case where:I × I I (I a real interval) is continuous and satisfies a cancellation property on both sides, provides a complete characterization of real continuous cancellation semigroups, namely that they are topologically order-isomorphic to addition on some real interval: ( – ,b), ( – ,b], –, +), (a, + ), or [a, + ) — whereb = 0 or –1 anda = 0 or 1. The original proof, however, involves some awkward handling of cases and has defied streamlining for some time. A new proof is given following a simpler approach, devised by Páles and fine-tuned by Craigen.  相似文献   

4.
Let the set of generalized polynomials having bounded coefficients beK={p= jgj. j j j,j=1, 2, ...,n}, whereg 1,g 2, ...,g n are linearly independent continuous functions defined on the interval [a, b], j, j are extended real numbers satisfying j<+, j>-, and j j. Assume thatf is a continuous function defined on a compact setX [a, b]. This paper gives the characterization theorem forp being the best uniform approximation tof fromK, and points out that the characterization theorem can be applied in calculating the approximate solution of best approximation tof fromK.  相似文献   

5.
LetA be anM-matrix in standard lower block triangular form, with diagonal blocksA ii irreducible. LetS be the set of indices such that the diagonal blockA is singular. We define the singular graph ofA to be the setS with partial order defined by > if there exists a chain of non-zero blocksA i, Aij, , Al.Let 1 be the set of maximal elements ofS, and define thep-th level p ,p = 2, 3, , inductively as the set of maximal elements ofS \( 1 p-1). Denote by p the number of elements in p . The Weyr characteristic (associated with 0) ofA is defined to be (A) = ( 1, 2,, h ), where 1 + + p = dim KerA p ,p = 1, 2, , and h > 0, h+1 = 0.Using a special type of basis, called anS-basis, for the generalized eigenspaceE(A) of 0 ofA, we associate a matrixD withA. We show that(A) = ( 1, , h) if and only if certain submatricesD p,p+1 ,p = 1, , h – 1, ofD have full column rank. This condition is also necessary and sufficient forE(A) to have a basis consisting of non-negative vectors, which is a Jordan basis for –A. We also consider a given finite partially ordered setS, and we find a necessary and sufficient condition that allM-matricesA with singular graphS have(A) = ( 1, , h). This condition is satisfied ifS is a rooted forest.The work of the second-named author was partly supported by the National Science Foundation, under grant MPS-08618 A02.  相似文献   

6.
In 1972 M. O'Nan proved thatL n (q),h 3; can be characterized as a doubly-transitive groupG on a finite set , whereG a has an Abelian normal subgroup acting not semi-regularly on -a. In the Main Theorem we show that a similar statement holds if is infinite. Our result implies O'Nan's theorem.This paper is part of the author's Ph.D. thesis written under supervision of Prof. F. G. Timmesfeld.  相似文献   

7.
The unit sphere of Hilbert space, 2, is shown to contain a remarkable sequence of nearly orthogonal sets. Precisely, there exist a sequence of sets of norm one elements of 2, (C i ) i=1 , and reals i 0 so that a) each setC i has nonempty intersection with every infinite dimensional closed subspace of 2 and b) forij,xC, andyC j , |x, y|<min(i, j) E. Odell was partially supported by NSF and TARP. Th. Schlumprecht was partially supported by NSF and LEQSF.  相似文献   

8.
Let f C[a, b]. LetP be a subset ofC[a, b], L b – a be a given real number. We say thatp P is a best approximation tof fromP, with arc length constraintL, ifA[p] b a [1 + (p(x)) 2]dx L andp – f q – f for allq P withA[q] L. represents an arbitrary norm onC[a, b]. The constraintA[p] L might be interpreted physically as a materials constraint.In this paper we consider the questions of existence, uniqueness and characterization of constrained best approximations. In addition a bound, independent of degree, is found for the arc length of a best unconstrained Chebyshev polynomial approximation.The work of L. L. Keener is supported by the National Research Council of Canada Grant A8755.  相似文献   

9.
Let I,I be the minor of a matrix which corresponds to row set I and column set I. We give a characterization of the inequalities of the form I,I K,K J,J L,L which hold for all totally nonnegative matrices. This generalizes a recent result of Fallat, Gekhtman, and Johnson.  相似文献   

10.
Frank Ruskey 《Order》1989,6(3):227-233
A permutation 1 2... n is alternating if 1< 2> 3< 4.... Alternating permutations are counted by the Euler numbers. Here we show that alternating permutations can be listed so that successive permutations differ by a transposition, ifn is odd. Extensions and open problems are mentioned.Research supported by the Natural Sciences and Engineering Research Council of Canada under grant A3379.  相似文献   

11.
The hypermetric coneH n is the cone in the spaceR n(n–1)/2 of all vectorsd=(d ij)1i<jn satisfying the hypermetric inequalities: –1ijn z j z j d ij 0 for all integer vectorsz inZ n with –1in z i =1. We explore connections of the hypermetric cone with quadratic forms and the geometry of numbers (empty spheres andL-polytopes in lattices). As an application, we show that the hypermetric coneH n is polyhedral.  相似文献   

12.
In this paper, the generalized Schrödinger equation (–)u=0 on the punctured unit disk of 2 is investigated. If is rotation free and satisfies the Picard principle at the origin, it is shown that if a setE is minimal thin relatively to an extremal harmonic functionh with zero boundary values at {|x|=1}, there exists a sequence (r n ) converging to zero such that B(O,r n ) C E. Lete be the -unit. It is proved that if a measure satisfies \E e h d<, for a minimal thin, relatively toh , setE then the Picard principle is valid for the measure + .
  相似文献   

13.
A-design is a family B 1,B 2,...,B v of subsets of X={1, 2,..., v} such that B i B j = for all i jand not all B i are of the same size. Ryser's andWoodall's -design conjecture states thateach -design can be obtained from a symmetricblock design by a certain complementation procedure. Our mainresult is that the conjecture is true when is twice a prime number.  相似文献   

14.
Inclusion-exclusion: Exact and approximate   总被引:1,自引:0,他引:1  
It is often required to find the probability of the union of givenn eventsA 1 ,...,A n . The answer is provided, of course, by the inclusion-exclusion formula: Pr(A i )= i i<j Pr(A i A j )±.... Unfortunately, this formula has exponentially many terms, and only rarely does one manage to carry out the exact calculation. From a computational point of view, finding the probability of the union is an intractable, #P-hard problem, even in very restricted cases. This state of affairs makes it reasonable to seek approximate solutions that are computationally feasible. Attempts to find such approximate solutions have a long history starting already with Boole [1]. A recent step in this direction was taken by Linial and Nisan [4] who sought approximations to the probability of the union, given the probabilities of allj-wise intersections of the events forj=1,...k. The developed a method to approximate Pr(A i ), from the above data with an additive error of exp . In the present article we develop an expression that can be computed in polynomial time, that, given the sums |S|=j Pr( iS A i ) forj=1,...k, approximates Pr(A i ) with an additive error of exp . This error is optimal, up to the logarithmic factor implicit in the notation.The problem of enumerating satisfying assignments of a boolean formula in DNF formF=v l m C i is an instance of the general problem that had been extensively studied [7]. HereA i is the set of assignments that satisfyC i , and Pr( iS A i )=a S /2n where iS C i is satisfied bya S assignments. Judging from the general results, it is hard to expect a decent approximation ofF's number of satisfying assignments, without knowledge of the numbersa S for, say, all cardinalities . Quite surprisingly, already the numbersa S over |S|log(n+1)uniquely determine the number of satisfying assignments for F.We point out a connection between our work and the edge-reconstruction conjecture. Finally we discuss other special instances of the problem, e.g., computing permanents of 0,1 matrices, evaluating chromatic polynomials of graphs and for families of events whose VC dimension is bounded.Work supported in part by a grant of the Binational Israel-US Science Foundation.Work supported in part by a grant of the Binational Israel-US Science Foundation and by the Israel Science Foundation.  相似文献   

15.
Tomasz Łuczak 《Order》1991,8(3):291-297
Let =(n,p) be a binary relation on the set [n]={1, 2, ..., n} such that (i,i) for every i and (i,j) with probability p, independently for each pair i,j [n], where i<j. Define as the transitive closure of and denote poset ([n], ) by R(n, p). We show that for any constant p probability of each first order property of R(n, p) converges as n .  相似文献   

16.
Summary LetC be a compact set inR 2. A setS R 2 C is said to have aj-partition relative toC if and only if there existj or fewer pointsc 1,, c j inC such that each point ofS sees somec i via the complement ofC. Letm, j be fixed integers, 3 m, 2 j, and writem (uniquely) asm = qj + r, where 1 r j. Assume thatC is a convexm-gon in R2, withS R 2 C. Forq = 0 orq = 1, the setS has aj-partition relative toC. Forq 2,S has aj-partition relative toC if and only if every (qj + 1)-member subset ofS has aj-partition relative toC, and the Helly numberqj + 1 is best possible.IfC is a disk, no such Helly number exists.  相似文献   

17.
Summary We prove the following two non-existence theorems for symmetric balanced ternary designs. If 1 = 1 and 0 (mod 4) then eitherV = + 1 or 42 – + 1 is a square and (42 – + 1) divides 2 – 1. If 1 = 2 thenV = ((m + 1)/2) 2 + 2,K = (m 2 + 7)/4 and = ((m – 1)/2)2 + 1 wherem 3 (mod 4). An example belonging to the latter series withV = 18 is constructed.  相似文献   

18.
Thek-core of the setS n is the intersection of the convex hull of all setsA S with ¦SA¦<-k. The Caratheodory number of thek-core is the smallest integerf (d,k) with the property thatx core kS, S n implies the existence of a subsetT S such thatx corekT and ¦T¦f (d, k). In this paper various properties off(d, k) are established.Research of this author was partially supported by Hungarian National Science Foundation grant no. 1812.  相似文献   

19.
Let (x, ) and (x,) be two functions,x[a, b] and { j } j=1 and { j } j=1 be two sequences where i j and i j whenij. We define the vector spacesU k =span{(x, j )} j=1 k andV k =span{(x, j )} j=1 k where we assume thatdim(U k )=dim(V k )=k,k1. We then look for the generalized polynomialsp m xU m+1\U m so that a b p m (x)(x, j )d(x)=0,j=1,2,...,m. If such generalized polynomials exist for allm1 we say that {p m } m=1 is a dual-orthogonal polynomial sequence from {(x, j )} j=1 to {(x, j )} j=1 with respect to the distribution (x),x[a, b]. In this article we present existence theorems for dual-orthogonal polynomials, explicit formulae forp m(x), theorems about the zeros ofp m(x), and, in the end, a Gauss-type quadrature formula for dual-orthogonal polynomials.  相似文献   

20.
Summary Consider a random walk of law on a locally compact second countable groupG. Let the starting measure be equivalent to the Haar measure and denote byQ the corresponding Markov measure on the space of pathsG . We study the relation between the spacesL (G , a ,Q) andL (G , i ,Q) where a and i stand for the asymptotic and invariant -algebras, respectively. We obtain a factorizationL (G , a ,Q) L (G , i ,Q)L (C) whereC is a cyclic group whose order (finite or infinite) coincides with the period of the Markov shift and is determined by the asymptotic behaviour of the convolution powers n.  相似文献   

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

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