The maximum measure of non-trivial 3-wise intersecting families | Mathematical Programming Skip to main content
Springer Nature Link
Log in

The maximum measure of non-trivial 3-wise intersecting families

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

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.

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.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Ahlswede, K., Katona, G.O.H.: Contributions to the geometry of Hamming spaces. Discrete Math. 17, 1–22 (1977)

    Article  MathSciNet  Google Scholar 

  2. Ahlswede, R., Khachatrian, L.H.: The diametric theorem in Hamming spaces-optimal anticodes. Adv. Appl. Math. 20, 429–449 (1998)

    Article  MathSciNet  Google Scholar 

  3. 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)

    Article  MathSciNet  Google Scholar 

  4. Balogh, J., Linz, W.: Short Proofs of Three Results About Intersecting Systems. arXiv:2104.00778

  5. Brace, A., Daykin, D.E.: A finite set covering theorem. Bull. Aust. Math. Soc. 5, 197–202 (1971)

    Article  MathSciNet  Google Scholar 

  6. Ellis, D., Keller, N., Lifshitz, N.: Stability for the Complete Intersection Theorem, and the Forbidden Intersection Problem of Erdős and Sós. arXiv:1604.06135

  7. Filmus, Y.: More complete intersection theorems. Discrete Math. 342, 128–142 (2019)

    Article  MathSciNet  Google Scholar 

  8. Filmus, Y., Golubev, K., Lifshitz, N.: High dimensional Hoffman bound and applications in extremal combinatorics. Algebr. Comb. 4(6), 1005–1026 (2021)

    MathSciNet  Google Scholar 

  9. 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)

  10. Frankl, P., Tokushige, N.: Weighted multiply intersecting families. Studia Sci. Math. Hung. 40, 287–291 (2003)

    MathSciNet  Google Scholar 

  11. Frankl, P., Tokushige, N.: Weighted non-trivial multiply intersecting families. Combinatorica 26, 37–46 (2006)

    Article  MathSciNet  Google Scholar 

  12. Gärtner, B., Matoušek, J.: Approximation Algorithms and Semidefinite Programming. xii+251 pp. Springer, Heidelberg (2012)

  13. 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)

    Article  Google Scholar 

  14. 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)

    Article  MathSciNet  Google Scholar 

  15. Kato, M., Kosuda, M., Tokushige, N.: Extending Muirhead’s inequality. Graphs Comb. 37, 1923–1941 (2011)

    Article  MathSciNet  Google Scholar 

  16. 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)

    Article  MathSciNet  Google Scholar 

  17. O’Neill, J., Versträete, J.: Non-trivial \(d\)-wise intersecting families. J. Comb. Theory Ser. A 178, 105369 (2021)

    Article  MathSciNet  Google Scholar 

  18. Suda, S., Tanaka, H.: A cross-intersection theorem for vector spaces based on semidefinite programming. Bull. Lond. Math. Soc. 46, 342–348 (2014)

    Article  MathSciNet  Google Scholar 

  19. 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)

    Article  MathSciNet  Google Scholar 

  20. Tokushige, N.: Brace–Daykin type inequalities for intersecting families. Eur. J. Comb. 29, 273–285 (2008)

    Article  MathSciNet  Google Scholar 

  21. Tokushige, N.: On cross \(t\)-intersecting families of sets. J. Comb. Theory A 117, 1167–1177 (2010)

    Article  MathSciNet  Google Scholar 

  22. Tokushige, N.: Application of hypergraph Hoffman’s bound to intersecting families. Algebr. Comb. 5(3), 537–557 (2022)

    MathSciNet  Google Scholar 

  23. Tokushige, N.: Non-trivial 3-wise intersecting uniform families. Discrete Math. 346(5), Paper No. 113368 (2023)

  24. Wagner, A.Z.: Refuting conjectures in extremal combinatorics via linear programming. J. Comb. Theory A 169, 105130 (2020)

    Article  MathSciNet  Google Scholar 

Download references

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

  1. University of the Ryukyus, 1 Senbaru, Okinawa, 903-0213, Japan

    Norihide Tokushige

Authors
  1. Norihide Tokushige
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Norihide Tokushige.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-023-01969-x

Keywords

Mathematics Subject Classification

Search

Navigation