Name
Abstract | ||
|---|---|---|
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} n 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. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/s00493-008-2318-9 | Combinatorica |
Keywords | Field | DocType |
boolean function,intersecting families,certain polynomial ring,certain range,genuine maximum family,maximal measure,fixed element,erd˝,non uniform product measure,intersecting family,t-intersecting family,fixed size,fourier transform,polynomial ring,linear algebra | Integer,Boolean function,Discrete mathematics,Uniqueness,Linear algebra,Family of sets,Combinatorics,Product measure,Polynomial ring,Matrix (mathematics),Mathematics | Journal |
Volume | Issue | ISSN |
28 | 5 | 0209-9683 |
Citations | PageRank | References |
26 | 1.81 | 10 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ehud Friedgut | 1 | 440 | 38.93 |