On symmetric 3-wise intersecting families
HTML articles powered by AMS MathViewer
- by David Ellis and Bhargav Narayanan
- Proc. Amer. Math. Soc. 145 (2017), 2843-2847
- DOI: https://doi.org/10.1090/proc/13452
- Published electronically: January 23, 2017
- PDF | Request permission
Abstract:
A family of sets is said to be symmetric if its automorphism group is transitive, and $3$-wise intersecting if any three sets in the family have nonempty intersection. Frankl conjectured in 1981 that if $\mathcal {A}$ is a symmetric $3$-wise intersecting family of subsets of $\{1,2,\dots ,n\}$, then $|\mathcal {A}| = o(2^n)$. Here, we give a short proof of Frankl’s conjecture using a ‘sharp threshold’ result of Friedgut and Kalai.References
- Rudolf Ahlswede and Levon H. Khachatrian, The complete intersection theorem for systems of finite sets, European J. Combin. 18 (1997), no. 2, 125–136. MR 1429238, DOI 10.1006/eujc.1995.0092
- Jean Bourgain, Jeff Kahn, Gil Kalai, Yitzhak Katznelson, and Nathan Linial, The influence of variables in product spaces, Israel J. Math. 77 (1992), no. 1-2, 55–64. MR 1194785, DOI 10.1007/BF02808010
- P. J. Cameron, P. Frankl, and W. M. Kantor, Intersecting families of finite sets and fixed-point-free $2$-elements, European J. Combin. 10 (1989), no. 2, 149–160. MR 988508, DOI 10.1016/S0195-6698(89)80042-3
- P. Erdős, Chao Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford Ser. (2) 12 (1961), 313–320. MR 140419, DOI 10.1093/qmath/12.1.313
- Peter Frankl, Regularity conditions and intersecting hypergraphs, Proc. Amer. Math. Soc. 82 (1981), no. 2, 309–311. MR 609674, DOI 10.1090/S0002-9939-1981-0609674-1
- Ehud Friedgut and Gil Kalai, Every monotone graph property has a sharp threshold, Proc. Amer. Math. Soc. 124 (1996), no. 10, 2993–3002. MR 1371123, DOI 10.1090/S0002-9939-96-03732-X
- Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, DOI 10.1007/BF00537230
Bibliographic Information
- David Ellis
- Affiliation: School of Mathematical Sciences, Queen Mary, University of London, London E1 4NS, United Kingdom
- Email: d.ellis@qmul.ac.uk
- Bhargav Narayanan
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, United Kingdom
- MR Author ID: 1058391
- Email: b.p.narayanan@dpmms.cam.ac.uk
- Received by editor(s): August 18, 2016
- Published electronically: January 23, 2017
- Communicated by: Patricia L. Hersh
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 2843-2847
- MSC (2010): Primary 05D05; Secondary 05E18
- DOI: https://doi.org/10.1090/proc/13452
- MathSciNet review: 3637934