Intersection properties of finite sets

Let X₁, X₂, …, X_m be finite sets. The present paper is concerned with the m² ? m intersection numbers |X_i ∩ X_j| (i ≠ j). We prove several theorems on families of sets with the same prescribed intersection numbers. We state here one of our conclusions that requires no further terminology. Let T₁, T₂, …, T_m be finite sets and let m ? 3. We assume that each of the elements in the set union T₁ ∪ T₂ ∪ … ∪ T_m occurs in at least two of the subsets T₁, T₂, …, T_m. We further assume that every pair of sets T_i and T_j (i ≠ j) intersect in at most one element and that for every such pair of sets there exists exactly one set T_k (k ≠ i, k ≠ j) such that T_k intersects both T_i and T_j. Then it follows that the integer m = 2m′ + 1 is odd and apart from the labeling of sets and elements there exist exactly m′ + 1 such families of sets. The unique family with the minimal number of elements is {1}, {2}, …, {m′}, {1}, {2}, …, {m′}, {1, 2, …, m′}.     

Intersection properties of boxes in R d

A family of sets is calledn-pierceable if there exists a set ofn points such that each member of the family contains at least one of the points. Helly’s theorem on intersections of convex sets concerns 1-pierceable families. Here the following Helly-type problem is investigated: Ifd andn are positive integers, what is the leasth =h(d, n) such that a family of boxes (with parallel edges) ind-space isn-pierceable if each of itsh-membered subfamilies isn-pierceable? The somewhat unexpected solution is: (i)h(d, 2) equals3d for oddd and 3d?1 for evend; (ii)h(2, 3)=16; and (iii)h(d, n) is infinite for all (d, n) withd≧2 andn≧3 except for (d, n)=(2, 3).     

Intersection properties of maximal directed cuts in digraphs

If $D$ is a finite digraph, a directed cut is a subset of arcs in $D$ having tail in some subset $X?V\left(D\right)$ and head in $V\left(D\right)?X$. In this paper we prove two general results concerning intersections between maximal paths, cycles and maximal directed cuts in $D$. As a direct consequence of these results, we deduce that there is a path, or a cycle, in $D$ that crosses each maximal directed cut.     

Intersection properties of boxes part II: Extremal families

In a previous paper (this Journal, Vol. 62, pp. 283–301) we proved an Upper-Bound Theorem for finite families of boxes inR ^d with edges parallel to the coordinate axes. This theorem concerns the maximum possible numbers of intersecting subfamilies of a family having a given number of members and a given clique number. Here we give an intrinsic characterization ofextremal families of boxes, i.e., families for which all the respective maximum numbers are achieved. We also deal with the problem of enumerating the possible intersection types of extremal families.     

Two properties of volume growth entropy in Hilbert geometry

The aim of this paper is to provide two examples in Hilbert geometry which show that volume growth entropy is not always a limit on the one hand, and that it may vanish for a non-polygonal domain in the plane on the other hand.     

Intersection properties of boxes. Part I: An upper-bound theorem

LetP be a family ofn boxes inR ^d (with edges parallel to the coordinate axes). Fork=0, 1, 2, …, denote byf _k (P) the number of subfamilies ofP of sizek+1 with non-empty intersection. We show that iff _r (P)=0 for somer≦n, then where thef _k (n, d, r) are ceg196rtain definite numbers defined by (3.4) below. The result is best possible for eachk. Fork=1 it was conjectured by G. Kalai (Israel J. Math.48 (1984), 161–174). As an application, we prove a ‘fractional’ Helly theorem for families of boxes inR ^d .     

The geometric and numerical properties of duality in projective algebraic geometry

In this paper we investigate some fundamental geometric and numerical properties ofduality for projective varieties inP _k ^N =P ^N . We take a point of view which in our opinion is somewhat moregeometric and lessalgebraic andnumerical than what has been customary in the literature, and find that this can some times yield simpler and more natural proofs, as well as yield additional insight into the situation. We first recall the standard definitions of thedual variety and theconormal scheme, introducing classical numerical invariants associated with duality. In section 2 we recall the well known duality properties these invariants have, and which was noted first byT. Urabe. In section 3 we investigate the connection between these invariants andChern classes in the singular case. In section 4 we give a treatment of the dual variety of a hyperplane section of X, and the dual procedure of taking the dual of a projection of X. This simplifies the proofs of some very interesting theorems due toR. Piene. Section 5 contains a new and simpler proof of a theorem ofA. Hefez and S. L. Kleiman. Section 6 contains some further results, geometric in nature.     

ON THE ORDER PROPERTIES OF DIGITAL CURVES IN THE PAN-EUCLIDEAN GEOMETRY

How to increase the speed in drawing and recognizing curves has always been a major concern. From the Breshenham Algorithm and DDA Algorithm in the sixties to the double-step and quadruple-step line generation iu the eighties, curves were all dragon point by point. The algorithm in this paper fully utilizes machine commands to accelerate the generation of lines and curves. We introduce and prove for the first time characterization theorems of the segment code order of digital lines and curyes. These theorems give new methods in the recognition and the measure of smoothness of lines and curves.     

Intersection Theorems with a Continuum of Intersection Points

In all existing intersection theorems, conditions are given under which a certain subset of a collection of sets has a nonempty intersection. In this paper, conditions are formulated under which the intersection is a continuum of points satisfying some interesting topological properties. In this sense, the intersection theorems considered in this paper belong to a new class. The intersection theorems are formulated on the unit cube and it is shown that both the vector of zeroes and the vector of ones lie in the same component of the intersection. An interesting application concerns the model of an economy with price rigidities. Using the intersection theorems of this paper, it is easily shown that there exists a continuum of zero points in such a model. The intersection theorems treated give a generalization of the well-known lemmas of Knaster, Kuratowski, and Mazurkiewicz (Ref. 1), Scarf (Ref. 2), Shapley (Ref. 3), and Ichiishi (Ref. 4). Moreover, the results can be used to sharpen the usual formulation of the Scarf lemma on the cube.     

幂交半格上的交同余及其性质

给出了幂交半格上几个具体的交同余,证明了任意多个交同余的并是交同余,并指出幂交半格的交同余类是子交半格,介绍了幂交半格上由θ诱导的交同余具有保并性和保序性。     

Problems of distance geometry and convex properties of quadratic maps

A weighted graph is calledd-realizable if its vertices can be chosen ind-dimensional Euclidean space so that the Euclidean distance between every pair of adjacent vertices is equal to the prescribed weight. We prove that if a weighted graph withk edges isd-realizable for somed, then it isd-realizable for (this bound is sharp in the worst case). We prove that for a graphG withn vertices andk edges and for a dimensiond the image of the so-called rigidity map ℝ ^dn →ℝ ^k is a convex set in ℝ ^k provided . These results are obtained as corollaries of a general convexity theorem for quadratic maps which also extends the Toeplitz-Hausdorff theorem. The main ingredients of the proof are the duality for linear programming in the space of quadratic forms and the “corank formula” for the strata of singular quadratic forms. This research was supported by the United States Army Research Office through the Army Center of Excellence for Symbolic Methods in Algorithmic Mathematics (ACSyAM), Mathematical Sciences Institute of Cornell University, Contract DAAL03-91-C0027.     

The geometry and the analytic properties of isotropic multiresolution analysis

In this paper we investigate Isotropic Multiresolution Analysis (IMRA), isotropic refinable functions, and wavelets. The main results are the characterization of IMRAs in terms of the Lax–Wiener Theorem, and the characterization of isotropic refinable functions in terms of the support of their Fourier transform. As an immediate consequence of these results, there are no compactly supported (in the space domain) isotropic refinable functions in many dimensions. Next we study the approximation properties of IMRAs. Finally, we discuss the application of IMRA wavelets to 2D and 3D-texture segmentation in natural and biomedical images.     

Intersection formulae in flag manifolds

Summary Two sets of generators of the cohomology ring of a complex (incomplete) flag manifold are obtained in terms of Ehresmann classes. Intersection formulae of the bases elements with any Ehresmann class are then given, thus determining the ring structure of the cohomology ring.     

Intersection Alexander polynomials

By considering a (not necessarily locally-flat) PL knot as the singular locus of a PL stratified pseudomanifold, we can use intersection homology theory to define intersection Alexander polynomials, a generalization of the classical Alexander polynomial invariants for smooth or PL locally-flat knots. We show that the intersection Alexander polynomials satisfy certain duality and normalization conditions analogous to those of ordinary Alexander polynomials, and we explore the relationships between the intersection Alexander polynomials and certain generalizations of the classical Alexander polynomials that are defined for non-locally-flat knots. We also investigate the relations between the intersection Alexander polynomials of a knot and the intersection and classical Alexander polynomials of the link knots around the singular strata. To facilitate some of these investigations, we introduce spectral sequences for the computation of the intersection homology of certain stratified bundles.     

Persistent Intersection Homology

The theory of intersection homology was developed to study the singularities of a topologically stratified space. This paper incorporates this theory into the already developed framework of persistent homology. We demonstrate that persistent intersection homology gives useful information about the relationship between an embedded stratified space and its singularities. We give an algorithm for the computation of the persistent intersection homology groups of a filtered simplicial complex equipped with a stratification by subcomplexes, and we prove its correctness. We also derive, from Poincaré Duality, some structural results about persistent intersection homology.