Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

On the measure of intersecting families, uniqueness and stability

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

Lett≥1 be an integer and letA be a family of subsets of {1,2,…,n} every two of which intersect in at leastt 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 thet-intersecting families of maximal measure are the families of all sets containingt fixed elements, and that the extremal examples are not only unique, but also stable: anyt-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.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. R. Ahlswede andL. Khachatrian: The complete intersection theorem for systems of finite sets,European J. Combin.18(2) (1997), 125–136.

    Article MathSciNet  Google Scholar 

  2. N. Alon,I. Dinur,E. Friedgut andB. Sudakov: Graph Products, Fourier Analysis and Spectral Techniques;G.A.F.A.14(5) (2004), 913–940.

    MATH MathSciNet  Google Scholar 

  3. N. Alon andJ. Spencer:The probabilistic method, Second edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience [John Wiley and Sons], New York, 2000.

    Google Scholar 

  4. J. Bourgain: On the distribution of the Fourier spectrum of boolean functions,Israel J. Math.131 (2002), 269–276.

    Article MATH MathSciNet  Google Scholar 

  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.

    Google Scholar 

  6. I. Dinur andE. Friedgut: Intersecting families are approximately contained in juntas, in preparation.

  7. I. Dinur andE. Friedgut: A proof of an intersection theorem via graph homomorphisms,Electron. J. Comb.13(1) (2006), #N6.

    Google Scholar 

  8. I. Dinur, E. Friegut andO. Regev: Independent sets in graph powers are almost contained in juntas, to appear inG.A.F.A.http://dx.doi.org/10.1007/s00039-008-0651-1

  9. I. Dinur andS. Safra: On the importance of being biased (1.36 hardness of approximating Vertex-Cover),Annals of Mathematics, to appear.Proc. of 34th STOC, 2002.

  10. P. Erdős,C. Ko andR. Rado: Intersection theorems for systems of finite sets,Quart. J. Math. Oxford, Ser. 212 (1961), 313–318.

    Article MathSciNet  Google Scholar 

  11. P. C. Fishburn,P. Frankl,D. Freed,J. C. Lagarias andA. M. Odlyzko: Probabilities for intersecting systems and random subsets of finite sets,SIAM J. Algebraic Discrete Methods7(1) (1986), 73–79.

    Article MATH MathSciNet  Google Scholar 

  12. P. Frankl: The Erdős-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.

    Google Scholar 

  13. P. Frankl: On intersecting families of finite sets,J. Combin. Theory Ser. A24(2) (1978), 146–161.

    Article MATH MathSciNet  Google Scholar 

  14. P. Frankl andZ. Füredi: Beyond the Erdős-Ko-Rado theorem,J. Combin. Theory Ser. A56(2) (1991), 182–194.

    Article MATH MathSciNet  Google Scholar 

  15. P. Frankl andZ. Füredi: Finite projective spaces and intersecting hypergraphs,Combinatorica6(4) (1986), 335–354.

    Article MATH MathSciNet  Google Scholar 

  16. P. Frankl andN. Tokushige: Weighted multiply intersecting families,Studia Sci. Math. Hungar.40(3) (2003), 287–291.

    MATH MathSciNet  Google Scholar 

  17. E. Friedgut: A Katona-type proof of an Erd?os-Ko-Rado-type theorem,J. Combin. Theory Ser. A111(2) (2005), 239–244.

    Article MATH MathSciNet  Google Scholar 

  18. E. Friedgut,A. Naor andG. Kalai: Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels,Adv. in Appl. Math.29 (2002), 427–437.

    Article MATH MathSciNet  Google Scholar 

  19. Z. Füredi: Erdős-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.

    Google Scholar 

  20. A. J. W. Hilton andE. C. Milner: Some intersection theorems for systems of finite sets,Quart. J. Math. Oxford,Ser. 218 (1967), 369–384.

    Article MATH MathSciNet  Google Scholar 

  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 andS. Safra: Noise-resistant boolean functions are juntas, submitted.

  23. N. Linial,Y. Mansour andN. Nisan: Constant depth circuits, Fourier transform, and learnability;J. Assoc. Comput. Mach.40(3) (1993), 607–620.

    MATH MathSciNet  Google Scholar 

  24. L. Lovász: On the Shannon capacity of a graph,IEEE Transactions on Information Theory25 (1979), 1–7.

    Article MATH  Google Scholar 

  25. A. Schrijver: Association schemes and the Shannon capacity: Eberlein polynomials and the Erdős-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.

    Google Scholar 

  26. R. M. Wilson: The exact bound in the Erdős-Ko-Rado theorem,Combinatorica4(2–3) (1984), 247–257.

    Article MATH MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Mathematics, Hebrew University, Jerusalem, Israel

    Ehud Friedgut

Authors
  1. Ehud Friedgut

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toEhud Friedgut.

Additional information

Research supported in part by the Israel Science Foundation, grant no. 0329745.

Rights and permissions

About this article

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp