Intersections ofk-element sets

LetF be a collection ofk-element sets with the property that the intersection of no two should be included in a third. We show that such a collection of maximum size satisfies .2715k+o(k)≦≦log₂ |F|≦.7549k+o(k) settling a question raised by Erdős. The lower bound is probabilistic, the upper bound is deduced via an entropy argument. Some open questions are posed. This research has been supported in part by the Office of Naval Research under Contract N00014-76-C-0366. Supported in part by a NSF postdoctoral Fellowship.     

Set systems without a 3-simplex

A 3-simplex is a collection of four sets A₁,…,A₄ with empty intersection such that any three of them have nonempty intersection. We show that the maximum size of a set system on n elements without a 3-simplex is for all n≥1, with equality only achieved by the family of sets containing a given element or of size at most 2. This extends a result of Keevash and Mubayi, who showed the conclusion for n sufficiently large.     

A short proof of an interesting helly-type theorem

We give a short proof of the theorem that any family of subsets ofR ^d , with the property that the intersection of any nonempty finite subfamily can be represented as the disjoint union of at mostk closed convex sets, has Helly number at mostk(d+1). Some of this work was done at the University of California, Berkeley, where the author was supported by a U.C. Presidents Dissertation Year Fellowship and an AT&T Graduate Research Program for Women Grant.     

Contraction and Expansion of Convex Sets

Let S{\mathcal{S}} be a set system of convex sets in ℝ ^d . Helly’s theorem states that if all sets in S{\mathcal{S}} have empty intersection, then there is a subset S￠ ì S{\mathcal{S}}'\subset{\mathcal{S}} of size d+1 which also has empty intersection. The conclusion fails, of course, if the sets in S{\mathcal{S}} are not convex or if S{\mathcal{S}} does not have empty intersection. Nevertheless, in this work we present Helly-type theorems relevant to these cases with the aid of a new pair of operations, affine-invariant contraction, and expansion of convex sets. These operations generalize the simple scaling of centrally symmetric sets. The operations are continuous, i.e., for small ε>0, the contraction C ^−ε and the expansion C ^ε are close (in the Hausdorff distance) to C. We obtain two results. The first extends Helly’s theorem to the case of set systems with nonempty intersection:     

The VC dimension of k‐uniform random hypergraphs

A set of vertices is shattered in a hypergraph if any of its subsets is obtained as the intersection of an edge with the set. The VC dimension is the size of the largest shattered subset. Under the binomial model of k‐uniform random hypergraphs, the threshold function for the VC dimension to be larger than a given integer is obtained. The same is done for the testing dimension, which is the largest integer d such that all sets of cardinality d are shattered. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

On sperner families in which nok sets have an empty intersection III

LetR be anr-element set and ℱ be a Sperner family of its subsets, that is,X ⊈Y for all differentX, Y ∈ ℱ. The maximum cardinality of ℱ is determined under the conditions 1)c≦|X|≦d for allX ∈ ℱ, (c andd are fixed integers) and 2) nok sets (k≧4, fixed integer) in ℱ have an empty intersection. The result is mainly based on a theorem which is proved by induction, simultaneously with a theorem of Frankl.     

Maximal sets of non-polar points of quadrics and symplectic polarities over GF(2)

A cap on a non-singular quadric over GF(2) is a set of points that are pairwise non-polar; equivalently the join of any two of the points is a chord. A non-secant set of the quadric is a set of points off the quadric that are pairwise non-polar; equivalently the join of any two of the points is skew to the quadric. We determine all the maximal caps and all the maximal non-secant sets of all non-singular quadrics over GF(2); and also all the maximal sets of non-polar points for symplectic polarities over GF(2). The classification is in terms of caps of greatest size on elliptic quadrics Q _– ^8k+3 (2), hyperbolic quadrics Q ₊ ^8k+7 (2) and on quadrics Q _4k+2(2), and of non-secant sets of greatest size of Q _– ^8k+1 (2), Q ₊ ^8k+5 (2) and Q _4k (2), for all quadrics of these types that occur as sections of the parent quadric or belong to the symplectic polarity. The sets of greatest size for these types of quadrics are larger than for other types. The results have implications about the non-existence of ovoids and the exterior sets of Thas. Only one part of the simple geometric inductive argument extends to larger ground fields.     

Voronoi Diagrams of Real Algebraic Sets

A collection of n (possibly singular) semi-algebraic sets in ^d of dimension d–1, each defined by polynomials of maximal degree , has ((n) ^d ) first-order Voronoi cells (for any fixed d). In the nonhypersurface case, where the maximal dimension of the semi-algebraic sets is m d–2, the number of first-order Voronoi cells is bounded above by O(n ^{m+1 d} ) (for nonsingular semi-algebraic sets) or by O((n) ^d ) (in general). The complexity of the entire kth-order Voronoi diagram of a generic collection of n non-singular real algebraic sets in R ^d of maximal dimension m<d and maximal degree is O(n ^{min(d+k,2d)2(m+1)d} ).     

Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

Bounding the piercing number

It is shown that for everyk and everyp≥q≥d+1 there is ac=c(k,p,q,d)<∞ such that the following holds. For every familyℋ whose members are unions of at mostk compact convex sets inR ^d in which any set ofp members of the family contains a subset of cardinalityq with a nonempty intersection there is a set of at mostc points inR ^d that intersects each member ofℋ. It is also shown that for everyp≥q≥d+1 there is aC=C(p,q,d)<∞ such that, for every family of compact, convex sets inR ^d so that among andp of them someq have a common hyperplane transversal, there is a set of at mostC hyperplanes that together meet all the members of . This research was supported in part by a United States-Israel BSF Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

On a class of partially ordered sets and their linear invariants

Let (, <) be a finite partially ordered set with rank function. Then is the disjoint union of the classes _k of elements of rank k and the order relation between elements in _k and _k+1 can be represented by a matrix S _k. We study partially ordered sets which satisfy linear recurrence relations of the type S _k (S _k ^T ) – c _k (S _{k – 1})^T S _{k – 1} = d _k ⁺ – c _k d _k ^– ) Id for all k and certain coefficients d _k ⁺, d _k ^- and c _k.     

A two-grid method with expanded mixed element for nonlinear reaction-diffusion equations

Expanded mixed finite element approximation of nonlinear reaction-diffusion equations is discussed. The equations considered here are used to model the hydrologic and bio-geochemical phenomena. To linearize the mixed-method equations, we use a two-grid method involving a small nonlinear system on a coarse gird of size H and a linear system on a fine grid of size h. Error estimates are derived which demonstrate that the error is O(△t + h k+1 + H 2k+2 d/2 ) (k ≥ 1), where k is the degree of the approximating space for the primary variable and d is the spatial dimension. The above estimates are useful for determining an appropriate H for the coarse grid problems.     

VC Dimensions of Principal Component Analysis

Motivated by statistical learning theoretic treatment of principal component analysis, we are concerned with the set of points in ℝ ^d that are within a certain distance from a k-dimensional affine subspace. We prove that the VC dimension of the class of such sets is within a constant factor of (k+1)(d−k+1), and then discuss the distribution of eigenvalues of a data covariance matrix by using our bounds of the VC dimensions and Vapnik’s statistical learning theory. In the course of the upper bound proof, we provide a simple proof of Warren’s bound of the number of sign sequences of real polynomials.     

A Helly-Type Theorem for Unions of Convex Sets

We prove that for any d, k ≥ 1 there are numbers q = q(d,k) and h = h(d,k) such that the following holds: Let be a family of subsets of the d-dimensional Euclidean space, such that the intersection of any subfamily of consisting of at most q sets can be expressed as a union of at most k convex sets. Then the Helly number of is at most h. We also obtain topological generalizations of some cases of this result. The main result was independently obtained by Alon and Kalai, by a different method. Received April 14, 1995, and in revised form August 1, 1995.     

Minimal 2-Fold Coverings of E d

Let N(k, d) be the smallest positive integer such that given any finite collection of open halfspaces which k-fold coversE ^d , there exists a subcollection of cardinality less than or equal toN(k,d) which k-fold coversE ^d . A well-known corollary to Helly's theorem proves N(1,d) =d+1. This provides an inductive base from which we show N(k; d) exists for all positive integers k.Our main result is .     

Families of k-independent sets

A collection F of sets is k-independent if for any selections A, B of k₁ and k₂ of its members with k₁+k₂=k, there are elements in all the members of A and not in the members of B. Bounds on the maximal size of k-independent families exponential in the total number of elements are obtained.     

Graceful Signed Graphs

A (p, q)-sigraph S is an ordered pair (G, s) where G = (V, E) is a (p, q)-graph and s is a function which assigns to each edge of G a positive or a negative sign. Let the sets E ⁺ and E ^– consist of m positive and n negative edges of G, respectively, where m + n = q. Given positive integers k and d, S is said to be (k, d)-graceful if the vertices of G can be labeled with distinct integers from the set {0, 1, ..., k + (q – 1)d such that when each edge uv of G is assigned the product of its sign and the absolute difference of the integers assigned to u and v the edges in E ⁺ and E ^– are labeled k, k + d, k + 2d, ..., k + (m – 1)d and –k, – (k + d), – (k + 2d), ..., – (k + (n – 1)d), respectively.In this paper, we report results of our preliminary investigation on the above new notion, which indeed generalises the well-known concept of (k, d)-graceful graphs due to B. D. Acharya and S. M. Hegde.     

The gonality of smooth curves with plane models

LetC be the normalization of an integral plane curve of degreed with δ ordinary nodes or cusps as its singularities. If δ=0, then Namba proved that there is no linear seriesg _d ^−2/1 and that everyg _d ^−1/1 is cut out by a pencil of lines passing through a point onC. The main purpose of this paper is to generalize his result to the case δ>0. A typical one is as follows: Ifd≥2(k+1), and δ<kd−(k+1)²+3 for somek>0, thenC has no linear seriesg _d ^−3/1 . We also show that ifd≥2k+3 and δ<kd−(k+1)²+2, then each linear seriesg _d ^−2/1 onC is cut out by a pencil of lines. We have similar results forg _d ^−1/1 andg _2d ^−9/1 . Furthermore, we also show that all of our theorems are sharp.     

On Sperner families in which no k sets have an empty intersection, II

Let n_c,d(r, k) denote the maximal cardinality of Sperner families (i.e., XY for all X, Y ε ) on an r-element set satisfying c X d for all X ε and in which no k sets have an empty intersection. n_c,d(r, k) was determined by Frankl (J. Combin. Theory Ser. A 20 (1976), 1–11) if c r/k, and, if c = 0 and d = r, by Frankl and the author (J. Combin. Theory Ser. A 28 (1980), 54–63; Acta Cybernet. 4 (1978), 213–220 for all r and k with exception of 60 values of r if k = 3. In this paper we solve the problem of determination of n_c,d(r, 3) in nearly all unknown cases. In particular, we obtain n_0,r(r, 3) for 33 of the exceptional cases.