×

Beyond the Erdős matching conjecture. (English) Zbl 1466.05206

Summary: A family \(\mathcal{F}\subset\binom{[ n ]}{k}\) is \(U(s,q)\) of for any \(F_1,\dots,F_s\in\mathcal{F}\) we have \(|F_1\cup\cdots\cup F_s |\leq q\). This notion generalizes the property of a family to be \(t\)-intersecting and to have matching number smaller than \(s\).
In this paper, we find the maximum \(|\mathcal{F}|\) for \(\mathcal{F}\) that are \(U(s,q)\), provided \(n>C(s,q)k\) with moderate \(C(s,q)\). In particular, we generalize the result of the first author on the Erdős Matching Conjecture [J. Comb. Theory, Ser. A 120, No. 5, 1068–1072 (2013; Zbl 1277.05123)] and prove a generalization of the Erdős-Ko-Rado theorem, which states that for \(n>s^2k\) the largest family \(\mathcal{F}\subset\binom{[n]}{k}\) with property \(U(s,s(k-1)+1)\) is the star and is in particular intersecting. (Conversely, it is easy to see that any intersecting family in \(\binom{[n]}{k}\) is \(U(s,s(k-1)+1)\).)
We investigate the case \(k=3\) more thoroughly, showing that, unlike in the case of the Erdős Matching Conjecture, in general there may be 3 extremal families.

MSC:

05D05 Extremal set theory

Citations:

Zbl 1277.05123
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahlswede, R.; Khachatrian, L., The complete intersection theorem for systems of finite sets, European J. Combin., 18, N2, 125-136 (1997) · Zbl 0869.05066
[2] Akiyama, J.; Frankl, P., On the size of graphs with complete-factors, J. Graph Theory, 9, N1, 197-201 (1985) · Zbl 0593.05042
[3] Bollobás, B.; Daykin, D. E.; Erdős, P., Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser., 27, N2, 25-32 (1976) · Zbl 0337.05135
[4] Erdős, P., A problem on independent r-tuples, Ann. Univ. Sci. Budapest., 8, 93-95 (1965) · Zbl 0136.21302
[5] Erdős, P.; Gallai, T., On the minimal number of vertices representing the edges of a graph, Puhl. Math. Inst. Hungar. Acnd. Sci., 6, 181-203 (1961) · Zbl 0101.41001
[6] Erdős, P.; Ko, C.; Rado, R., Intersection theorems for systems of finite sets, Q. J. Math., 12, N1, 313-320 (1961) · Zbl 0100.01902
[7] Frankl, P., Families of finite sets satisfying union restrictions, Studia Sci. Math. Hungar., 11, N1-2, 1-6 (1976) · Zbl 0438.05001
[8] Frankl, P., The Erdős-Ko-Rado theorem is true for n=ckt, (Combinatorics (Proc. Fifth Hungarian Colloq. Keszthely, 1976), I. Combinatorics (Proc. Fifth Hungarian Colloq. Keszthely, 1976), I, Colloq. Math. Soc. János Bolyai, vol. 18 (1976), North-Holland), 365-375 · Zbl 0401.05001
[9] Frankl, P., Families of finite sets satisfying a union condition, Discrete Math., 26, N2, 111-118 (1979) · Zbl 0397.05004
[10] Frankl, P., The shifting technique in extremal set theory, (Surveys in Combinatorics. Surveys in Combinatorics, Lond. Math. Soc. Lecture Note Ser., vol. 123 (1987), Cambridge University Press: Cambridge University Press Cambridge), 81-110 · Zbl 0633.05038
[11] Frankl, P., Improved bounds for Erdős’ matching conjecture, J. Combin. Theory Ser. A, 120, 1068-1072 (2013) · Zbl 1277.05123
[12] Frankl, P., On the maximum number of edges in a hypergraph with given matching number, Discrete Appl. Math., 216, 562-581 (2017) · Zbl 1358.05202
[13] Frankl, P.; Füredi, Z., Beyond the Erdős-Ko-Rado theorem, J. Combin. Theory Ser. A, 56, N2, 182-194 (1991) · Zbl 0742.05080
[14] P. Frankl, A. Kupavskii, The Erdős matching conjecture and concentration inequalities, arXiv:1806.08855. · Zbl 1415.05175
[15] Frankl, P.; Kupavskii, A., Two problems on matchings in set families – in the footsteps of Erdős and Kleitman, J. Combin. Theory Ser. B. (2021), arXiv:1607.06126 (in press)
[16] Huang, H.; Loh, P.-S.; Sudakov, B., The size of a hypergraph and its matching number, Combin. Probab. Comput., 21, N3, 442-450 (2012) · Zbl 1242.05268
[17] Katona, G. O.H., Intersection theorems for systems of finite sets, Acta Math. Hungar., 15, N3-4, 329-337 (1964) · Zbl 0134.25101
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.