Turan problems for vertex-disjoint cliques in multi-partite hypergraphs

被引:1
作者
Liu, Erica L. L. [1 ]
Wang, Jian [2 ]
机构
[1] Tianjin Univ, Ctr Appl Math, Tianjin 300072, Peoples R China
[2] Taiyuan Univ Technol, Dept Math, Taiyuan 030024, Peoples R China
基金
中国国家自然科学基金;
关键词
Turan number; Multi-partite hypergraphs; Probabilistic argument; MAXIMUM NUMBER; EDGES;
D O I
10.1016/j.disc.2020.112005
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
For two s-uniform hypergraphs H and F, the Turan number ex(s)(H, F) is the maximum number of edges in an F-free subgraph of H. Let s, r, k, n(1), ..., n(r) be integers satisfying 2 <= s <= r and n(1) <= n(2) <= .... <= n(r). De Silva, Heysse and Young determined ex(2)(K-n1, ..., n(r), kK(2)) and De Silva, Heysse, Kapilow, Schenfisch and Young determined ex(2)(K-n1, ..., n(r), kK(r)). In this paper, as a generalization of these results, we consider three Turan-type problems for k disjoint cliques in r-partite s-uniform hypergraphs. First, we consider a multi-partite version of the Erd6s matching conjecture and determine ex(s)(K-n1((s)), ..., n(r), kK(s)((s))) for n(1) >= s(3)k(2) + sr. Then, using a probabilistic argument, we determine ex(s)(K-n1((s)), ..., n(r), kK(r)((s)) ) for all n(1) >= k. Recently, Alon and Shikhelman determined asymptotically, for all F, the generalized Turan number ex(2)(K-n, K-s, F), which is the maximum number of copies of K-s in an F-free graph on n vertices. Here we determine ex(2)(K-n1, ..., n(r), K-s, kK(r)) with n(1) >= k and n(3) = ... = n(r). Utilizing a result on rainbow matchings due to Glebov, Sudakov and Szabo, we determine ex(2)(K-n1, ..., K-s, kK(r)) for all n(1), ..., n(r) with n(4) >= r(r) (k - 1)k(2r-2). (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页数:16
相关论文
共 18 条
[1]   A Rainbow r-Partite Version of the Erdos-Ko-Rado Theorem [J].
Aharoni, Ron ;
Howard, David .
COMBINATORICS PROBABILITY & COMPUTING, 2017, 26 (03) :321-337
[2]   Many T copies in H-free graphs [J].
Alon, Noga ;
Shikhelman, Clara .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2016, 121 :146-172
[3]   Weighted Turan problems with applications [J].
Bennett, Patrick ;
English, Sean ;
Talanda-Fisher, Maria .
DISCRETE MATHEMATICS, 2019, 342 (08) :2165-2172
[4]   SETS OF INDEPENDENT EDGES OF A HYPERGRAPH [J].
BOLLOBAS, B ;
DAYKIN, DE ;
ERDOS, P .
QUARTERLY JOURNAL OF MATHEMATICS, 1976, 27 (105) :25-32
[5]   Turan numbers of vertex-disjoint cliques in r-partite graphs [J].
De Silva, Jessica ;
Heysse, Kristin ;
Kapilow, Adam ;
Schenfisch, Anna ;
Young, Michael .
DISCRETE MATHEMATICS, 2018, 341 (02) :492-496
[6]  
Erdo P., 1965, Ann. Univ. Sci. Budapest, V8, P93
[7]  
Frankl P., 1987, LONDON MATH SOC LECT, V123, P81
[8]   On the maximum number of edges in a hypergraph with given matching number [J].
Frankl, Peter .
DISCRETE APPLIED MATHEMATICS, 2017, 216 :562-581
[9]   Improved bounds for Erdos' Matching Conjecture [J].
Frankl, Peter .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (05) :1068-1072
[10]   On the Maximum Number of Edges in a Triple System Not Containing a Disjoint Family of a Given Size [J].
Frankl, Peter ;
Roedl, Vojtech ;
Rucinski, Andrzej .
COMBINATORICS PROBABILITY & COMPUTING, 2012, 21 (1-2) :141-148