Maximal 3-Wise Intersecting Families

被引:0
|
作者
Balogh, Jozsef [1 ]
Chen, Ce [1 ]
Hendrey, Kevin [2 ]
Lund, Ben [2 ]
Luo, Haoran [1 ]
Tompkins, Casey [3 ]
Tran, Tuan [4 ]
机构
[1] Univ Illinois, Dept Math, Urbana, IL 61801 USA
[2] Inst Basic Sci IBS, Discrete Math Grp, Daejeon, South Korea
[3] Hungarian Acad Sci, Alfred Reny Inst Math, Budapest, Hungary
[4] Univ Sci & Technol China, Sch Math Sci, Hefei 230026, Anhui, Peoples R China
基金
中国国家自然科学基金;
关键词
Intersecting; Set-system; Maximal; Saturation; GRAPHS; PAIRS;
D O I
10.1007/s00493-023-00046-3
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A family .7' on ground set [n] := {1, 2, ... , n} is maximal k -wise intersecting if every collection of at most k sets in .7' has non-empty intersection, and no other set can be added to .7' while maintaining this property. In 1974, Erdos and Kleitman asked for the minimum size of a maximal k-wise intersecting family. We answer their question for k = 3 and sufficiently large n. We show that the unique minimum family is obtained by partitioning the ground set [n] into two sets A and B with almost equal sizes and taking the family consisting of all the proper supersets of A and of B.
引用
收藏
页码:1045 / 1066
页数:22
相关论文
共 25 条
  • [1] Maximal 3-Wise Intersecting Families
    József Balogh
    Ce Chen
    Kevin Hendrey
    Ben Lund
    Haoran Luo
    Casey Tompkins
    Tuan Tran
    Combinatorica, 2023, 43 : 1045 - 1066
  • [2] Idealness of k-wise intersecting families
    Abdi, Ahmad
    Cornuejols, Gerard
    Huynh, Tony
    Lee, Dabeen
    MATHEMATICAL PROGRAMMING, 2022, 192 (1-2) : 29 - 50
  • [3] On k-Wise L-Intersecting Families for Simplicial Complexes
    Zhang, Huihui
    Li, Hui
    BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2024, 47 (04)
  • [4] Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas
    Borg, Peter
    DISCRETE MATHEMATICS, 2018, 341 (05) : 1331 - 1335
  • [5] ALMOST INTERSECTING FAMILIES OF SETS
    Gerbner, Daniel
    Lemons, Nathan
    Palmer, Cory
    Patkos, Balazs
    Szecsi, Vajk
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2012, 26 (04) : 1657 - 1669
  • [6] Structure and supersaturation for intersecting families
    Balogh, Jozsef
    Das, Shagnik
    Liu, Hong
    Sharifzadeh, Maryam
    Tuan Tran
    ELECTRONIC JOURNAL OF COMBINATORICS, 2019, 26 (02)
  • [7] Almost Intersecting Families for Vector Spaces
    Shan, Yunjing
    Zhou, Junling
    GRAPHS AND COMBINATORICS, 2024, 40 (03)
  • [8] On intersecting families of independent sets in trees
    Hurlbert, Glenn
    Kamat, Vikram
    DISCRETE APPLIED MATHEMATICS, 2022, 321 : 4 - 9
  • [9] Triangle-intersecting families of graphs
    Ellis, David
    Filmus, Yuval
    Friedgut, Ehud
    JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY, 2012, 14 (03) : 841 - 885
  • [10] Restricted intersecting families on simplicial complex
    Wang, Larry X. W.
    ADVANCES IN APPLIED MATHEMATICS, 2021, 124