On regular 3-wise intersecting families

Frankston, Keith; Kahn, Jeff; Narayanan, Bhargav

doi:10.1090/proc/14153

On regular 3-wise intersecting families
HTML articles powered by AMS MathViewer

by Keith Frankston, Jeff Kahn and Bhargav Narayanan PDF

Proc. Amer. Math. Soc. 146 (2018), 4091-4097 Request permission

Abstract:

Ellis and the third author showed, verifying a conjecture of Frankl, that any $3$-wise intersecting family of subsets of $\{1,2,\dots ,n\}$ admitting a transitive automorphism group has cardinality $o(2^n)$, while a construction of Frankl demonstrates that the same conclusion need not hold under the weaker constraint of being regular. Answering a question of Cameron, Frankl, and Kantor from 1989, we show that the restriction of admitting a transitive automorphism group may be relaxed significantly: we prove that any $3$-wise intersecting family of subsets of $\{1,2,\dots ,n\}$ that is regular and increasing has cardinality $o(2^n)$.

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
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
M. Deza and P. Frankl, Erdős-Ko-Rado theorem—$22$ years later, SIAM J. Algebraic Discrete Methods 4 (1983), no. 4, 419–431. MR 721612, DOI 10.1137/0604042
D. Ellis, G. Kalai, and B. Narayanan, On symmetric intersecting families, preprint, arXiv:1702.02607.
David Ellis and Bhargav Narayanan, On symmetric 3-wise intersecting families, Proc. Amer. Math. Soc. 145 (2017), no. 7, 2843–2847. MR 3637934, DOI 10.1090/proc/13452
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, Boolean functions with low average sensitivity depend on few coordinates, Combinatorica 18 (1998), no. 1, 27–35. MR 1645642, DOI 10.1007/PL00009809
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
F. Ihringer and A. Kupavskii, Regular intersecting families, preprint, arXiv:1709.10462.
G. A. Margulis, Probabilistic characteristics of graphs with large connectivity, Problemy Peredači Informacii 10 (1974), no. 2, 101–108 (Russian). MR 0472604
Robert J. McEliece, The theory of information and coding, Encyclopedia of Mathematics and its Applications, Vol. 3, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1977. A mathematical framework for communication; With a foreword by Mark Kac. MR 0469516
Dhruv Mubayi and Jacques Verstraëte, A survey of Turán problems for expansions, Recent trends in combinatorics, IMA Vol. Math. Appl., vol. 159, Springer, [Cham], 2016, pp. 117–143. MR 3526406, DOI 10.1007/978-3-319-24298-9_{5}
Lucio Russo, An approximate zero-one law, Z. Wahrsch. Verw. Gebiete 61 (1982), no. 1, 129–139. MR 671248, DOI 10.1007/BF00537230
Michel Talagrand, On Russo’s approximate zero-one law, Ann. Probab. 22 (1994), no. 3, 1576–1587. MR 1303654