On the measure of intersecting families, uniqueness and stability.(English)Zbl 1199.05319
Summary: Let \(t\geq 1\) be an integer and let \(\mathcal A\) be a family of subsets of \(\{1,2,\dots, 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.
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.
MSC:
| 05D05 | Extremal set theory |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Keywords:
intersecting familiesCite
Full Text:DOI
References:
| [1] | R. Ahlswede and L. Khachatrian: The complete intersection theorem for systems of finite sets, European J. Combin. 18(2) (1997), 125–136. ·Zbl 0869.05066 ·doi:10.1006/eujc.1995.0092 |
| [2] | N. Alon, I. Dinur, E. Friedgut and B. Sudakov: Graph Products, Fourier Analysis and Spectral Techniques; G.A.F.A. 14(5) (2004), 913–940. ·Zbl 1056.05104 |
| [3] | N. Alon and J. Spencer: The probabilistic method, Second edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley and Sons], New York, 2000. |
| [4] | J. Bourgain: On the distribution of the Fourier spectrum of boolean functions, Israel J. Math. 131 (2002), 269–276. ·Zbl 1021.43004 ·doi:10.1007/BF02785861 |
| [5] | P. Delsarte: The association schemes of coding theory, in: Combinatorics (Proc. NATO Advanced Study Inst., Breukelen, 1974), Part 1: Theory of designs, finite geometry and coding theory, pp. 139–157. Math. Centre Tracts, No. 55, Math.Centrum, Amsterdam, 1974. |
| [6] | I. Dinur and E. Friedgut: Intersecting families are approximately contained in juntas, in preparation. ·Zbl 1243.05235 |
| [7] | I. Dinur and E. Friedgut: A proof of an intersection theorem via graph homomorphisms, Electron. J. Comb. 13(1) (2006), #N6. ·Zbl 1087.05060 |
| [8] | I. Dinur, E. Friegut and O. Regev: Independent sets in graph powers are almost contained in juntas, to appear in G.A.F.A. http://dx.doi.org/10.1007/s00039-008-0651-1 ·Zbl 1147.05058 |
| [9] | I. Dinur and S. Safra: On the importance of being biased (1.36 hardness of approximating Vertex-Cover), Annals of Mathematics, to appear. Proc. of 34th STOC, 2002. ·Zbl 1192.68318 |
| [10] | P. Erdos, C. Ko and R. Rado: Intersection theorems for systems of finite sets, Quart. J. Math. Oxford, Ser. 2 12 (1961), 313–318. ·Zbl 0100.01902 ·doi:10.1093/qmath/12.1.313 |
| [11] | P. C. Fishburn, P. Frankl, D. Freed, J. C. Lagarias and A. M. Odlyzko: Probabilities for intersecting systems and random subsets of finite sets, SIAM J. Algebraic Discrete Methods 7(1) (1986), 73–79. ·Zbl 0582.60014 ·doi:10.1137/0607009 |
| [12] | P. Frankl: The Erdos-Ko-Rado theorem is true for n = ckt, in: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, pp. 365–375, Colloq. Math. Soc. János Bolyai, 18, North-Holland, Amsterdam-New York, 1978. |
| [13] | P. Frankl: On intersecting families of finite sets, J. Combin. Theory Ser. A 24(2) (1978), 146–161. ·Zbl 0384.05002 ·doi:10.1016/0097-3165(78)90003-1 |
| [14] | P. Frankl and Z. Füredi: Beyond the Erdos-Ko-Rado theorem, J. Combin. Theory Ser. A 56(2) (1991), 182–194. ·Zbl 0742.05080 ·doi:10.1016/0097-3165(91)90031-B |
| [15] | P. Frankl and Z. Füredi: Finite projective spaces and intersecting hypergraphs, Combinatorica 6(4) (1986), 335–354. ·Zbl 0643.05018 ·doi:10.1007/BF02579260 |
| [16] | P. Frankl and N. Tokushige: Weighted multiply intersecting families, Studia Sci. Math. Hungar. 40(3) (2003), 287–291. ·Zbl 1045.05084 |
| [17] | E. Friedgut: A Katona-type proof of an Erd?os-Ko-Rado-type theorem, J. Combin. Theory Ser. A 111(2) (2005), 239–244. ·Zbl 1073.05067 ·doi:10.1016/j.jcta.2004.12.004 |
| [18] | E. Friedgut, A. Naor and G. Kalai: Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels, Adv. in Appl. Math. 29 (2002), 427–437. ·Zbl 1039.91014 ·doi:10.1016/S0196-8858(02)00024-6 |
| [19] | Z. Füredi: Erdos-Ko-Rado type theorems with upper bounds on the maximum degree, in: Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 177–207, Colloq. Math. Soc. János Bolyai, 25, North-Holland, Amsterdam-New York, 1981. |
| [20] | A. J. W. Hilton and E. C. Milner: Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford, Ser. 2 18 (1967), 369–384. ·Zbl 0168.26205 ·doi:10.1093/qmath/18.1.369 |
| [21] | A. J. Hoffman: On eigenvalues and colorings of graphs, in: 1970 Graph Theory and its Applications (Proc. Advanced Sem., Math. Research Center, Univ. of Wisconsin, Madison, Wis., 1969), pp. 79–91, Academic Press, New York (Reviewer: R. C. Read). |
| [22] | G. Kindler and S. Safra: Noise-resistant boolean functions are juntas, submitted. |
| [23] | N. Linial, Y. Mansour and N. Nisan: Constant depth circuits, Fourier transform, and learnability; J. Assoc. Comput. Mach. 40(3) (1993), 607–620. ·Zbl 0781.94006 |
| [24] | L. Lovász: On the Shannon capacity of a graph, IEEE Transactions on Information Theory 25 (1979), 1–7. ·Zbl 0395.94021 ·doi:10.1109/TIT.1979.1055985 |
| [25] | A. Schrijver: Association schemes and the Shannon capacity: Eberlein polynomials and the Erdos-Ko-Rado theorem; in: Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 671–688, Colloq. Math. Soc. János Bolyai, 25, North-Holland, Amsterdam-New York, 1981. |
| [26] | R. M. Wilson: The exact bound in the Erdos-Ko-Rado theorem, Combinatorica 4(2–3) (1984), 247–257. ·Zbl 0556.05039 ·doi:10.1007/BF02579226 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
