Abstract
Let \(\mathcal G\) be a family of subsets of an n-element set. The family \(\mathcal G\) is called non-trivial 3-wise intersecting if the intersection of any three subsets in \(\mathcal G\) is non-empty, but the intersection of all subsets is empty. For a real number \(p\in (0,1)\) we define the measure of the family by the sum of \(p^{|G|}(1-p)^{n-|G|}\) over all \(G\in \mathcal G\). We determine the maximum measure of non-trivial 3-wise intersecting families. We also discuss the uniqueness and stability of the corresponding optimal structure. These results are obtained by solving linear programming problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ahlswede, K., Katona, G.O.H.: Contributions to the geometry of Hamming spaces. Discrete Math. 17, 1–22 (1977)
Ahlswede, R., Khachatrian, L.H.: The diametric theorem in Hamming spaces-optimal anticodes. Adv. Appl. Math. 20, 429–449 (1998)
Ahlswede, R., Khachatrian, L.H.: The complete nontrivial-intersection theorem for systems of finite sets. J. Comb. Theory Ser. A 76(1), 121–138 (1996)
Balogh, J., Linz, W.: Short Proofs of Three Results About Intersecting Systems. ar**v:2104.00778
Brace, A., Daykin, D.E.: A finite set covering theorem. Bull. Aust. Math. Soc. 5, 197–202 (1971)
Ellis, D., Keller, N., Lifshitz, N.: Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdős and Sós. ar**v:1604.06135
Filmus, Y.: More complete intersection theorems. Discrete Math. 342, 128–142 (2019)
Filmus, Y., Golubev, K., Lifshitz, N.: High dimensional Hoffman bound and applications in extremal combinatorics. Algebr. Comb. 4(6), 1005–1026 (2021)
Frankl, P.: The Shifting Technique in Extremal Set Theory. Surveys in Combinatorics (New Cross), London Mathematical Society Lecture Note Series 123, pp. 81–110 (1987)
Frankl, P., Tokushige, N.: Weighted multiply intersecting families. Studia Sci. Math. Hung. 40, 287–291 (2003)
Frankl, P., Tokushige, N.: Weighted non-trivial multiply intersecting families. Combinatorica 26, 37–46 (2006)
Gärtner, B., Matoušek, J.: Approximation Algorithms and Semidefinite Programming. xii+251 pp. Springer, Heidelberg (2012)
Gupta, P., Mogge, Y., Piga, S., Schülke, B.: \(r\)-cross \(t\)-intersecting families via necessary intersection points. Procedia Comput. Sci. 195, 453–458 (2021)
Hilton, A.J.W., Milner, E.C.: Some intersection theorems for systems of finite sets. Q. J. Math. Oxf. Ser. (2) 18, 369–384 (1967)
Kato, M., Kosuda, M., Tokushige, N.: Extending Muirhead’s inequality. Graphs Comb. 37, 1923–1941 (2011)
Lee, S.J., Siggers, M., Tokushige, N.: Toward extending the Ahlswede–Khachatrian theorem to cross \(t\)-intersecting families. Discrete Appl. Math. 216, 627–645 (2017)
O’Neill, J., Versträete, J.: Non-trivial \(d\)-wise intersecting families. J. Comb. Theory Ser. A 178, 105369 (2021)
Suda, S., Tanaka, H.: A cross-intersection theorem for vector spaces based on semidefinite programming. Bull. Lond. Math. Soc. 46, 342–348 (2014)
Suda, S., Tanaka, H., Tokushige, N.: A semidefinite programming approach to a cross-intersection problem with measures. Math. Program. Ser. A 166, 113–130 (2017)
Tokushige, N.: Brace–Daykin type inequalities for intersecting families. Eur. J. Comb. 29, 273–285 (2008)
Tokushige, N.: On cross \(t\)-intersecting families of sets. J. Comb. Theory A 117, 1167–1177 (2010)
Tokushige, N.: Application of hypergraph Hoffman’s bound to intersecting families. Algebr. Comb. 5(3), 537–557 (2022)
Tokushige, N.: Non-trivial 3-wise intersecting uniform families. Discrete Math. 346(5), Paper No. 113368 (2023)
Wagner, A.Z.: Refuting conjectures in extremal combinatorics via linear programming. J. Comb. Theory A 169, 105130 (2020)
Acknowledgements
I thank both referees for their careful reading and many helpful suggestions. This research was supported by JSPS KAKENHI 18K03399 and 23K032101.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The author was supported by JSPS KAKENHI 18K03399 and 23K032101.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Tokushige, N. The maximum measure of non-trivial 3-wise intersecting families. Math. Program. 204, 643–676 (2024). https://doi.org/10.1007/s10107-023-01969-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-023-01969-x