Maximal <Emphasis Type="Italic">k</Emphasis>-Intersecting Families of Subsets and Boolean Functions

A family of subsets of an n-element set is k-intersecting if the intersection of every k subsets in the family is nonempty. A family is maximalk-intersecting if no subset can be added to the family without violating the k-intersection property. There is a one-to-one correspondence between the families of subsets and Boolean functions defined as follows: To each family of subsets, assign the Boolean function whose unit tuples are the characteristic vectors of the subsets.We show that a family of subsets is maximal 2-intersecting if and only if the corresponding Boolean function is monotone and selfdual. Asymptotics for the number of such families is obtained. Some properties of Boolean functions corresponding to k-intersecting families are established fork > 2.     

Some intersection theorems

LetL(A) be the set of submatrices of anm×n matrixA. ThenL(A) is a ranked poset with respect to the inclusion, and the poset rank of a submatrix is the sum of the number of rows and columns minus 1, the rank of the empty matrix is zero. We attack the question: What is the maximum number of submatrices such that any two of them have intersection of rank at leastt? We have a solution fort=1,2 using the followoing theorem of independent interest. Letm(n,i,j,k) = max(|F|;|G|), where maximum is taken for all possible pairs of families of subsets of ann-element set such thatF isi-intersecting,G isj-intersecting andF ansd,G are cross-k-intersecting. Then fori≤j≤k, m(n,i,j,k) is attained ifF is a maximali-intersecting family containing subsets of size at leastn/2, andG is a maximal2k?i-intersecting family. Furthermore, we discuss and Erd?s-Ko-Rado-type question forL(A), as well.     

Intersection Theorems for t-Valued Functions

This paper investigates the maximum possible size of families ℱ of t-valued functions on an n-element set S = {1, 2, . . . , n}, assuming any two functions of ℱ agree in sufficiently many places. More precisely, given a family ℬ of k-element subsets of S, it is assumed for each pair h, g ∈ ℱ that there exists a B in ℬ such that h = g on B. If ℬ is ‘not too large’ it is shown that the maximal families have t^n−k members.     

Erdős–Ko–Rado and Hilton–Milner Type Theorems for Intersecting Chains in Posets

t -intersecting k-chains in posets using the kernel method. These results are common generalizations of the original EKR and HM theorems, and our earlier results for intersecting k-chains in the Boolean algebra. For intersecting k-chains in the c-truncated Boolean algebra we also prove an exact EKR type theorem (for all n) using the shift method. An application of the general theorem gives a similar result for t-intersecting chains if n is large enough. Received November 20, 1997     

Extremal t-intersecting families for direct products

In this paper, by shifting technique we study t-intersecting families for direct products where the ground set is divided into several parts. Assuming the size of each part is sufficiently large, we determine all extremal t-intersecting families for direct products. We also prove that every largest t-intersecting subfamily of a more general family introduced by Katona is trivial under certain conditions.     

A generalization of the katona theorem for crosst-intersecting families

LetX be ann-element set and letA and? be families of subsets ofX. We say thatA and? are crosst-intersecting if |A ∩ B| ≥ t holds for all A ∈A and for allB ∈ ?. Suppose thatA and ? are crosst-intersecting. This paper first proves a crosst-intersecting version of Harper's Theorem:

1. There are two crosst-intersecting Hamming spheresA ₀,? ₀ with centerX such that |A| ≤ |A ₀| and|?| ≤ |? ₀| hold.
2. Suppose thatt ≥ 2 and that the pair of integers (|A) is maximal with respect to direct product ordering among pairs of crosst-intersecting families. Then,A and? are Hamming spheres with centerX.

Using these claims, the following conjecture of Frankl is proven:

1. Ifn + t = 2k ? 1 then |A| |?| ≤ max \(\left\{ {\left( {K_k^n + \left( {_{k - 1}^{n - 1} } \right)} \right)^2 ,K_k^n K_{k - 1}^n } \right\}\) holds, whereK _l ⁿ is defined as \(\left( {_n^n } \right)\left( {_{n - 1}^n } \right) + \cdots + \left( {_l^n } \right).\)
2. Ifn + t = 2k then |A| |? ≤ (K _k ⁿ )² holds.

The extremal configurations are also determined.     

A Common Generalization to Theorems on Set Systems with <Emphasis Type="Italic">L</Emphasis>-intersections

In this paper, we provide a common generalization to the well-known Erdös–Ko–Rado Theorem, Frankl–Wilson Theorem, Alon–Babai–Suzuki Theorem, and Snevily Theorem on set systems with L-intersections. As a consequence, we derive a result which strengthens substantially the well-known theorem on set systems with k-wise L-intersections by Füredi and Sudakov [J. Combin. Theory, Ser. A, 105, 143–159 (2004)]. We will also derive similar results on L-intersecting families of subspaces of an n-dimensional vector space over a finite field F _q , where q is a prime power.     

A discrete isodiametric result: The Erdős–Ko–Rado theorem for multisets

There are many generalizations of the Erdős–Ko–Rado theorem. Here the new results (and problems) concern families of $t$-intersecting $k$-element multisets of an $n$-set. We point out connections to coding theory and geometry. We verify the conjecture that for $n\ge t(k-t)+2$ such a family can have at most $\left(\genfrac{}{}{00}{}{n+k-t-1}{k-t}\right)$ members.     

Profile polytopes of some classes of families

The profile vector of a family F of subsets of an n-element set is (f ₀,f ₁,…,f _n ) where f _i denotes the number of the i-element members of F. The extreme points of the set of profile vectors for some class of families has long been studied. In this paper we introduce the notion of k-antichainpair families and determine the extreme points of the set of profile vectors of these families, extending results of Engel and P.L. Erd?s regarding extreme points of the set of profile vectors of intersecting, co-intersecting Sperner families. Using this result we determine the extreme points of the set of profile vectors for some other classes of families, including complement-free k-Sperner families and self-complementary k-Sperner families. We determine the maximum cardinality of intersecting k-Sperner families, generalizing a classical result of Milner from k = 1.     

3-Wise Exactly 1-Intersecting Families of Sets

Let f(l, t, n) be the maximal size of a family such that any l2 sets of have an exactly t1-element intersection. If l3, it trivially comes from [8] that the optimal families are trivially intersecting (there is a t-element core contained by all the members of the family). Hence it is easy to determine Let g(l,t,n) be the maximal size of an l-wise exaclty t-intersecting family that is not trivially t-intersecting. We give upper and lower bounds which only meet in the following case: g(3, 1, n) = n^2/3(1 + o(1)).     

The existence of regular self-complementary 3-uniform hypergraphs

A k-uniform hypergraph with vertex set V and edge set E is called t-subset-regular if every t-element subset of V lies in the same number of elements of E. In this paper we show that a 1-subset-regular self-complementary 3-uniform hypergraph with n vertices exists if and only if n≥5 and n is congruent to 1 or 2 modulo 4.     

Perfect matchings in large uniform hypergraphs with large minimum collective degree

We define a perfect matching in a k-uniform hypergraph H on n vertices as a set of ⌊n/k⌋ disjoint edges. Let δk−1(H) be the largest integer d such that every (k−1)-element set of vertices of H belongs to at least d edges of H.In this paper we study the relation between δk−1(H) and the presence of a perfect matching in H for k?3. Let t(k,n) be the smallest integer t such that every k-uniform hypergraph on n vertices and with δk−1(H)?t contains a perfect matching.For large n divisible by k, we completely determine the values of t(k,n), which turn out to be very close to n/2−k. For example, if k is odd and n is large and even, then t(k,n)=n/2−k+2. In contrast, for n not divisible by k, we show that t(k,n)∼n/k.In the proofs we employ a newly developed “absorbing” technique, which has a potential to be applicable in a more general context of establishing existence of spanning subgraphs of graphs and hypergraphs.     

On the measure of intersecting families,uniqueness and stability

Let t≥1 be an integer and let A be a family of subsets of {1,2,…,n} every two of which intersect in at least t elements. Identifying the sets with their characteristic vectors in {0,1} ⁿ we study the maximal measure of such a family under a non uniform product measure. We prove, for a certain range of parameters, that the t-intersecting families of maximal measure are the families of all sets containing t fixed elements, and that the extremal examples are not only unique, but also stable: any t-intersecting family that is close to attaining the maximal measure must in fact be close in structure to a genuine maximum family. This is stated precisely in Theorem 1.6. We deduce some similar results for the more classical case of Erdős-Ko-Rado type theorems where all the sets in the family are restricted to be of a fixed size. See Corollary 1.7. The main technique that we apply is spectral analysis of intersection matrices that encode the relevant combinatorial information concerning intersecting families. An interesting twist is that part of the linear algebra involved is done over certain polynomial rings and not in the traditional setting over the reals. A crucial tool that we use is a recent result of Kindler and Safra [22] concerning Boolean functions whose Fourier transforms are concentrated on small sets. Research supported in part by the Israel Science Foundation, grant no. 0329745.     

New Bounds for Perfect Hashing via Information Theory

A set of sequences of length t from a b-element alphabet is called k-separated if for every k-tuple of the sequences there exists a coordinate in which they all differ. The problem of finding, for fixed t, b, and k, the largest size N(t, b, k) of a k-separated set of sequences is equivalent to finding the minimum size of a (b, k)-family of perfect hash functions for a set of a given size. We shall improve the bounds for N(t, b, k) obtained by Fredman and Komlós [1].Körner [2] has shown that the proof in [1] can be reduced to an application of the sub-additivity of graph entropy [3]. He also pointed out that this sub-additivity yields a method to prove non-existence bounds for graph covering problems. Our new non-existence bound is based on an extension of graph entropy to hypergraphs.     

Gray codes in graphs of subsets

Let G(n,k) be a graph whose vertices are the k-element subsets of an n-set represented as n-tuples of “O's” and “1's” with k “1's”. Two such subsets are adjacent if one can be obtained from the other by switching a “O” and a “1” which are in adjacent positions, where the first and nth positions are also considered adjacent. The problem of finding hamiltonian cycles in G(n,k) is discussed. This may be considered a problem of finding “Gray codes” of the k-element subsets of an n-set. It is shown that no such cycle exists if n and k are both even or if k=2 and n?7 and that such a cycle does exist in all other cases where k?5.     

On Jensen’s inequality and Hölder’s inequality for g-expectation

In this paper, we shall prove that for n > 1, the n-dimensional Jensen inequality holds for the g-expectation if and only if g is independent of y and linear with respect to z, in other words, the corresponding g-expectation must be linear. A Similar result also holds for the general nonlinear expectation defined in Coquet et al. (Prob. Theory Relat. Fields 123 (2002), 1–27 or Peng (Stochastic Methods in Finance Lectures, LNM 1856, 143–217, Springer-Verlag, Berlin, 2004). As an application of a special n-dimensional Jensen inequality for g-expectation, we give a sufficient condition for g under which the Hölder’s inequality and Minkowski’s inequality for the corresponding g-expectation hold true.     

Domino tilings of rectangles with fixed width

Let t(k,n) denote the number of ways to tile a 1 × n rectangle with 1 × 2 rectangles (called dominoes). We show that for each fixed k the sequence t_k=(t(k,0), t(k,1),…) satisfies a difference equation (linear, homogeneous, and with constant coefficients). Furthermore, a computational method is given for finding this difference equation together with the initial terms of the sequence. This gives rise to a new way to compute t(k,n) which differs completely with the known Pfaffian method. The generating function of t_k is a rational function F_k, and F_k is given explicitly for k=1,…,8. We end with some conjectures concerning the form of F_k based on our computations.     

A generalization of k-Cohen–Macaulay simplicial complexes

For a positive integer k and a non-negative integer t, a class of simplicial complexes, to be denoted by k-CM _t , is introduced. This class generalizes two notions for simplicial complexes: being k-Cohen–Macaulay and k-Buchsbaum. In analogy with the Cohen–Macaulay and Buchsbaum complexes, we give some characterizations of CM _t (=1?CM _t ) complexes, in terms of vanishing of some homologies of its links, and in terms of vanishing of some relative singular homologies of the geometric realization of the complex and its punctured space. We give a result on the behavior of the CM _t property under the operation of join of two simplicial complexes. We show that a complex is k-CM _t if and only if the links of its non-empty faces are k-CM _t?1. We prove that for an integer s≤d, the (d?s?1)-skeleton of a (d?1)-dimensional k-CM _t complex is (k+s)-CM _t . This result generalizes Hibi’s result for Cohen–Macaulay complexes and Miyazaki’s result for Buchsbaum complexes.     

Lelek maps and n-dimensional maps from compacta to polyhedra

For a natural number m?0, a map from a compactum X to a metric space Y is an m-dimensional Lelek map if the union of all non-trivial continua contained in the fibers of f is of dimension ?m. In [M. Levin, Certain finite-dimensional maps and their application to hyperspaces, Israel J. Math. 105 (1998) 257-262], Levin proved that in the space C(X,I) of all maps of an n-dimensional compactum X to the unit interval I=[0,1], almost all maps are (n−1)-dimensional Lelek maps. Moreover, he showed that in the space C(X,Ik) of all maps of an n-dimensional compactum X to the k-dimensional cube Ik (k?1), almost all maps are (n−k)-dimensional Lelek maps. In this paper, we generalize Levin's result. For any (separable) metric space Y, we define the piecewise embedding dimension ped(Y) of Y and we prove that in the space C(X,Y) of all maps of an n-dimensional compactum X to a complete metric ANR Y, almost all maps are (n−k)-dimensional Lelek maps, where k=ped(Y). As a corollary, we prove that in the space C(X,Y) of all maps of an n-dimensional compactum X to a Peano curve Y, almost all maps are (n−1)-dimensional Lelek maps and in the space C(X,M) of all maps of an n-dimensional compactum X to a k-dimensional Menger manifold M, almost all maps are (n−k)-dimensional Lelek maps. It is known that k-dimensional Lelek maps are k-dimensional maps for k?0.