On maximal intersecting families of finite sets

Let r be a positive integer. A finite family $\text{H}$ of pairwise intersecting r-sets is a maximal clique of order r, if for any set A ? $\text{H}$, |A| ? r there exists a member E ? $\text{H}$ such that $\text{A ∩ E = ?}$. For instance, a finite projective plane of order r ? 1 is a maximal clique. Let N(r) denote the minimum number of sets in a maximal clique of order r. We prove $\text{N(r) ?}\text{3}\text{4}\text{r}{}^2$ whenever a projective plane of order $\text{r}\text{2}$ exists. This disproves the known conjecture N(r) ? r² ? r + 1.     

On families of intersecting sets

While algorithms exist which produce optimal binary trees, there are no direct formulas for the cost of such trees. In this note, we give a formula for the cost of the optimal binary tree built on m nodes with weights 1, 2, 3,…, m. The simplicity of this proof suggests that one can try to compute the cost of optimal trees for other special classes of weights.     

Properties of intersecting families of ordered sets

The first part of this paper deals with families of ordered k-tuples having a common element in different position. A quite general theorem is given and special cases are considered. The second part deals with t families of sets with some intersection properties, and generalizes results by Bollobás, Frankl, Lovász and Füredi to this case.     

On the kernel of intersecting families

Let be at-wises-intersecting family, i.e.,|F ₁ ... F _t | s holds for everyt members of. Then there exists a setY such that|F ₁ ... F _t Y| s still holds for everyF ₁,...,F _t . Here exponential lower and upper bounds are proven for the possible sizes ofY. This work was done while the authors visited Bell Communication Research, NJ 07960, and AT&T Bell Laboratories, Murray Hill, NJ 07974, USA, respectively.Research supported in part by Allon Fellowship and by Bat Sheva de Rothschild Foundation.     

On sets of sets mutually intersecting in exactly one element

Let be a finite set, and letS be a set of subsets of mutually intersecting in exactly one element, such that all elements ofS have cardinality at mostr, and such that each element of is contained in at least two elements ofS.We give an upper bound for the cardinality of and a characterization of the pairs (,S) attaining the upper bound.The problem is equivalent to determining the maximum number of lines of a linear space having at mostr lines through a point.     

On ramsey families of sets

The main result of this paper is a lemma which can be used to prove the existence of highchromatic subhypergraphs of large girth in various hypergraphs. In the last part of the paper we use amalgamation techniques to prove the existence for everyl, k 3 of a setA of integers such that the hypergraph having as edges all the arithmetic progressions of lengthk inA has both chromatic number and girth greater thanl.     

Enumeration of intersecting families

It is shown that the logarithm to the base 2 of the number of maximal intersecting families on m elements is asymptotically equal to ($\text{m?1}\text{n?1}$) where $\text{n = [}\text{1}\text{2}\text{m]}$.     

Uniformly cross intersecting families

Let A and B denote two families of subsets of an n-element set. The pair (A,B) is said to be ℓ-cross-intersecting iff |A∩B|=ℓ for all A∈ A and B∈B. Denote by P _e (n) the maximum value of |A||B| over all such pairs. The best known upper bound on P _e (n) is Θ(2 ⁿ ), by Frankl and R?dl. For a lower bound, Ahlswede, Cai and Zhang showed, for all n ≥ 2ℓ, a simple construction of an ℓ-cross-intersecting pair (A,B) with |A||B| = $ \left( {{*{20}c} {2\ell } \\ \ell \\ } \right) $ \left( {\begin{array}{*{20}c} {2\ell } \\ \ell \\ \end{array} } \right) 2 ^n−2ℓ = Θ(2 ⁿ /$ \sqrt \ell $ \sqrt \ell ), and conjectured that this is best possible. Consequently, Sgall asked whether or not P _e (n) decreases with ℓ.     

Game saturation of intersecting families

We consider the following combinatorial game: two players, Fast and Slow, claim k-element subsets of [n] = {1, 2, …, n} alternately, one at each turn, so that both players are allowed to pick sets that intersect all previously claimed subsets. The game ends when there does not exist any unclaimed k-subset that meets all already claimed sets. The score of the game is the number of sets claimed by the two players, the aim of Fast is to keep the score as low as possible, while the aim of Slow is to postpone the game’s end as long as possible. The game saturation numbers, gsat_F(II _n,k ) and gsat_S(II _n,k ), are the score of the game when both players play according to an optimal strategy in the cases when the game starts with Fast’s or Slow’s move, respectively. We prove that $\Omega _k (n^{k/3 - 5} ) \leqslant gsat_F (\mathbb{I}_{n,k} ),gsat_S (\mathbb{I}_{n,k} ) \leqslant O_k (n^{k - \sqrt {k/2} } )$ .     

On interpolation families of wavelet sets

The question of which groups are isomorphic to groups of interpolation maps for interpolation families of wavelet sets was raised by Dai and Larson. In this article it is shown that any finite group is isomorphic to a group of interpolation maps for some interpolation family of wavelet sets.

     

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.