×

Maximum size intersecting families of bounded minimum positive co-degree. (English) Zbl 1468.05297

Summary: Let \(\mathcal{H}\) be an \(r\)-uniform hypergraph. The minimum positive co-degree of \(\mathcal{H} \), denoted by \(\delta_{r-1}^+(\mathcal{H})\), is the minimum \(k\) such that if \(S\) is an \((r-1)\)-set contained in a hyperedge of \(\mathcal{H}\), then \(S\) is contained in at least \(k\) hyperedges of \(\mathcal{H}\). For \(r\geq k\) fixed and \(n\) sufficiently large, we determine the maximum possible size of an intersecting \(r\)-uniform \(n\)-vertex hypergraph with minimum positive co-degree \(\delta_{r-1}^+(\mathcal{H})\geq k\) and characterize the unique hypergraph attaining this maximum. This generalizes the Erdős-Ko-Rado theorem which corresponds to the case \(k=1\). Our proof is based on the delta-system method.

MSC:

05D05 Extremal set theory
05C65 Hypergraphs

References:

[1] R. Alweiss, S. Lovett, K. Wu, and J. Zhang Improved bounds for the sunflower lemma, in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), 2020, pp. 624-630. · Zbl 07298275
[2] J. Balogh, N. Lemons, and C. Palmer, Maximum Size Intersecting Families of Bounded Minimum Positive Co-Degree, arXiv:2005.04282, 2020.
[3] P. Erd\Hos, Problems and results in combinatorial analysis (Italian summary), in Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo II, Atti dei Convegni Lincei 17, Accademia Nazionale dei Lincei, Rome, 1976, pp. 3-17. · Zbl 0361.05037
[4] P. Erd\Hos, C. Ko, and R. Rado, Intersection theorems for systems of finite sets, Quart. J. Math. Oxford, 2 (1961), pp. 313-320. · Zbl 0100.01902
[5] P. Erd\Hos and R. Rado, Intersection theorems for systems of sets, J. Lond. Math. Soc., 35 (1960), pp. 85-90. · Zbl 0103.27901
[6] P. Frankl, On intersecting families of finite sets, J. Combin. Theory Ser. A, 24 (1978), pp. 146-161. · Zbl 0384.05002
[7] P. Frankl, On intersecting families of finite sets, Bull. Austral. Math. Soc., 21 (1980), pp. 363-372. · Zbl 0425.05002
[8] P. Frankl, Erd\Hos-Ko-Rado theorem with conditions on the maximal degree, J. Combin. Theory Ser. A, 46 (1987), pp. 252-263. · Zbl 0661.05002
[9] P. Frankl, Maximum degree and diversity in intersecting hypergraphs, J. Combin. Theory Ser. B, 144 (2020), pp. 81-94. · Zbl 1443.05178
[10] P. Frankl and Z. Füredi, A new generalization of the Erd\Hos-Ko-Rado theorem, Combinatorica, 3 (1983), pp. 341-349. · Zbl 0529.05001
[11] P. Frankl and N. Tokushige, A note on Huang-Zhao theorem on intersecting families with large minimum degree, Discrete Math., 340 (2017), pp. 1098-1103. · Zbl 1357.05064
[12] P. Frankl and N. Tokushige, Invitation to intersection problems for finite sets (English summary), J. Combin. Theory Ser. A, 144 (2016), pp. 157-211. · Zbl 1343.05153
[13] P. Frankl, K. Ota, and N. Tokushige, Uniform intersecting families with covering number four, J. Combin. Theory Ser. A, 71 (1995), pp. 127-145. · Zbl 0827.05058
[14] Z. Füredi, Erd\Hos-Ko-Rado Type Theorems with Upper Bounds on the Maximum Degree, in Algebraic Methods in Graph Theory, Vol. I, II (Szeged, 1978), Colloq. Math. Soc. János Bolyai, 25, North-Holland, Amsterdam, 1981, pp. 177-207. · Zbl 0474.05002
[15] Z. Füredi, An intersection problem with 6 extremes, Acta Math. Hungar., 42 (1983), pp. 177-187. · Zbl 0538.05002
[16] Z. Füredi, On finite set-systems whose every intersection is a Kernel of a star, Discrete Math., 47 (1983), pp. 129-132. · Zbl 0531.05002
[17] H. Huang and Y. Zhao, Degree versions of the Erd\Hos-Ko-Rado theorem and Erd\Hos hypergraph matching conjecture, J. Combin. Theory Ser. A, 150 (2017), pp. 233-247. · Zbl 1362.05091
[18] P. Keevash and D. Mubayi, Stability theorems for cancellative hypergraphs, J. Combin. Theory Ser. B, 92 (2004), pp. 163-175. · Zbl 1052.05051
[19] A. Kostochka, D. Mubayi, and J. Verstraëte, Turán Problems and Shadows I: Paths and Cycles, J. Combin. Theory Ser. A, 129 (2015), pp. 57-79. · Zbl 1302.05129
[20] A. Kupavskii, Degree versions of theorems on intersecting families via stability, J. Combin. Theory Ser. A, 168 (2019), pp. 272-287. · Zbl 1421.05090
[21] A. Kupavskii, Diversity of uniform intersecting families, European J. Combin., 74 (2018), pp. 39-47. · Zbl 1394.05137
[22] N. Lemons and C. Palmer, The unbalance of set systems, Graphs Combin., 24 (2008), pp. 361-365. · Zbl 1185.05014
[23] D. Mubayi and Y. Zhao, Co-degree density of hypergraphs, J. Combin. Theory Ser. A, 114 (2007), pp. 1118-1132. · Zbl 1125.05070
[24] D. Mubayi and Y. Zhao, Forbidding complete hypergraphs as traces, Graphs Combin., 23 (2007), pp. 667-679. · Zbl 1140.05047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.