Intersecting families with covering number three

被引:1
作者
Frankl, Peter [1 ]
Wang, Jian [2 ]
机构
[1] Renyi Inst, Budapest, Hungary
[2] Taiyuan Univ Technol, Dept Math, Taiyuan 030024, Peoples R China
关键词
Intersecting families; Covering number; Shifting; Erdos-Ko-Rado Theorem; THEOREMS; SYSTEMS;
D O I
10.1016/j.jctb.2024.12.001
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We consider k-graphs on n vertices, that is, F subset of(([n])(k)). A k-graph F is called intersecting if F boolean AND F 'not equal & empty; for all F,F 'is an element of F. In the present paper we prove that for k >= 7, n >= 2k, any intersecting k-graph F with covering number at least three, satisfies |F|<=((n-1)(k-1))-((n-k)(k-1))-((n-k-1)(k-1))+((n-2k)(k-1))+((n-k-2)(k-3))+3, the best possible upper bound which was proved in [4] subject to exponential constraints n>n(0)(k).
引用
收藏
页码:96 / 139
页数:44
相关论文
共 50 条
  • [31] Non-trivially intersecting multi-part families
    Kwan, Matthew
    Sudakov, Benny
    Vieira, Pedro
    JOURNAL OF COMBINATORIAL THEORY SERIES A, 2018, 156 : 44 - 60
  • [32] Two extremal problems on intersecting families
    Huang, Hao
    EUROPEAN JOURNAL OF COMBINATORICS, 2019, 76 : 1 - 9
  • [33] Intersecting families of sets are typically trivial
    Balogh, Jozsef
    Garcia, Ramon I.
    Li, Lina
    Wagner, Adam Zsolt
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 164 : 44 - 67
  • [34] On t-intersecting families of permutations
    Keller, Nathan
    Lifshitz, Noam
    Minzer, Dor
    Sheinfeld, Ohad
    ADVANCES IN MATHEMATICS, 2024, 445
  • [35] Most Probably Intersecting Families of Subsets
    Katona, Gyula O. H.
    Katona, Gyula Y.
    Katona, Zsolt
    COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) : 219 - 227
  • [36] THE PROFILE POLYTOPE OF NONTRIVIAL INTERSECTING FAMILIES
    Gerbner, Daniel
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2023, 37 (04) : 2265 - 2275
  • [37] On disjoint cross intersecting families of permutations
    Songsuwan, Nuttanon
    Sengsamak, Supida
    Jeerawattana, Nutchapol
    Jiarasuksakun, Thiradet
    Kaemawichanurat, Pawaton
    DISCRETE MATHEMATICS LETTERS, 2023, 11 : 27 - 30
  • [38] INTERSECTING FAMILIES OF PERMUTATIONS
    Ellis, David
    Friedgut, Ehud
    Pilpel, Haran
    JOURNAL OF THE AMERICAN MATHEMATICAL SOCIETY, 2011, 24 (03) : 649 - 682
  • [39] Intersecting families of transformations
    Sonmez, Demet Parlak
    Sonmez, Orhan
    JOURNAL OF ALGEBRA AND ITS APPLICATIONS, 2024,
  • [40] On cross-intersecting uniform sub-families of hereditary families
    Borg, Peter
    ELECTRONIC JOURNAL OF COMBINATORICS, 2010, 17 (01)